gem5  v20.1.0.0
spatio_temporal_memory_streaming.cc
Go to the documentation of this file.
1 
30 
31 #include "debug/HWPrefetch.hh"
33 #include "params/STeMSPrefetcher.hh"
34 
35 namespace Prefetcher {
36 
37 STeMS::STeMS(const STeMSPrefetcherParams *p)
38  : Queued(p), spatialRegionSize(p->spatial_region_size),
39  spatialRegionSizeBits(floorLog2(p->spatial_region_size)),
40  reconstructionEntries(p->reconstruction_entries),
41  activeGenerationTable(p->active_generation_table_assoc,
42  p->active_generation_table_entries,
43  p->active_generation_table_indexing_policy,
44  p->active_generation_table_replacement_policy,
46  spatialRegionSize / blkSize)),
47  patternSequenceTable(p->pattern_sequence_table_assoc,
48  p->pattern_sequence_table_entries,
49  p->pattern_sequence_table_indexing_policy,
50  p->pattern_sequence_table_replacement_policy,
52  spatialRegionSize / blkSize)),
53  rmob(p->region_miss_order_buffer_entries)
54 {
56  "The spatial region size must be a power of 2.");
57 }
58 
59 void
61 {
62  // This prefetcher operates attached to the L1 and it observes all
63  // accesses, this guarantees that no evictions are missed
64 
65  // Iterate over all entries, if any recorded cacheline has been evicted,
66  // the generation finishes, move the entry to the PST
67  for (auto &agt_entry : activeGenerationTable) {
68  if (agt_entry.isValid()) {
69  bool generation_ended = false;
70  bool sr_is_secure = agt_entry.isSecure();
71  for (auto &seq_entry : agt_entry.sequence) {
72  if (seq_entry.counter > 0) {
73  Addr cache_addr =
74  agt_entry.paddress + seq_entry.offset * blkSize;
75  if (!inCache(cache_addr, sr_is_secure) &&
76  !inMissQueue(cache_addr, sr_is_secure)) {
77  generation_ended = true;
78  break;
79  }
80  }
81  }
82  if (generation_ended) {
83  // PST is indexed using the PC (secure bit is unused)
84  ActiveGenerationTableEntry *pst_entry =
85  patternSequenceTable.findEntry(agt_entry.pc,
86  false /*unused*/);
87  if (pst_entry == nullptr) {
88  // Tipically an entry will not exist
89  pst_entry = patternSequenceTable.findVictim(agt_entry.pc);
90  assert(pst_entry != nullptr);
91  patternSequenceTable.insertEntry(agt_entry.pc,
92  false /*unused*/, pst_entry);
93  } else {
94  patternSequenceTable.accessEntry(pst_entry);
95  }
96  // If the entry existed, this will update the values, if not,
97  // this also sets the values of the entry
98  pst_entry->update(agt_entry);
99  // Free the AGT entry
100  activeGenerationTable.invalidate(&agt_entry);
101  }
102  }
103  }
104 }
105 
106 void
107 STeMS::addToRMOB(Addr sr_addr, Addr pst_addr, unsigned int delta)
108 {
109  RegionMissOrderBufferEntry rmob_entry;
110  rmob_entry.srAddress = sr_addr;
111  rmob_entry.pstAddress = pst_addr;
112  rmob_entry.delta = delta;
113 
114  rmob.push_back(rmob_entry);
115 }
116 
117 void
119  std::vector<AddrPriority> &addresses)
120 {
121  if (!pfi.hasPC()) {
122  DPRINTF(HWPrefetch, "Ignoring request with no PC.\n");
123  return;
124  }
125 
126  Addr pc = pfi.getPC();
127  bool is_secure = pfi.isSecure();
128  // Spatial region address
129  Addr sr_addr = pfi.getAddr() / spatialRegionSize;
130  Addr paddr = pfi.getPaddr();
131 
132  // Offset in cachelines within the spatial region
133  Addr sr_offset = (pfi.getAddr() % spatialRegionSize) / blkSize;
134 
135  // Check if any active generation has ended
137 
138  ActiveGenerationTableEntry *agt_entry =
139  activeGenerationTable.findEntry(sr_addr, is_secure);
140  if (agt_entry != nullptr) {
141  // found an entry in the AGT, entry is currently being recorded,
142  // add the offset
143  activeGenerationTable.accessEntry(agt_entry);
144  agt_entry->addOffset(sr_offset);
145  lastTriggerCounter += 1;
146  } else {
147  // Not found, this is the first access (Trigger access)
148 
149  // Add entry to RMOB
150  Addr pst_addr = (pc << spatialRegionSizeBits) + sr_offset;
151  addToRMOB(sr_addr, pst_addr, lastTriggerCounter);
152  // Reset last trigger counter
153  lastTriggerCounter = 0;
154 
155  // allocate a new AGT entry
156  agt_entry = activeGenerationTable.findVictim(sr_addr);
157  assert(agt_entry != nullptr);
158  activeGenerationTable.insertEntry(sr_addr, is_secure, agt_entry);
159  agt_entry->pc = pc;
160  agt_entry->paddress = paddr;
161  agt_entry->addOffset(sr_offset);
162  }
163  // increase the seq Counter for other entries
164  for (auto &agt_e : activeGenerationTable) {
165  if (agt_e.isValid() && agt_entry != &agt_e) {
166  agt_e.seqCounter += 1;
167  }
168  }
169 
170  // Prefetch generation: if this is a miss, search for the most recent
171  // entry in the RMOB, and reconstruct the registered access sequence
172  if (pfi.isCacheMiss()) {
173  auto it = rmob.end();
174  while (it != rmob.begin()) {
175  --it;
176  if (it->srAddress == sr_addr) {
177  // reconstruct the access sequence
178  reconstructSequence(it, addresses);
179  break;
180  }
181  }
182  }
183 }
184 
185 void
188  std::vector<AddrPriority> &addresses)
189 {
191  unsigned int idx = 0;
192 
193  // Process rmob entries from rmob_it (most recent with address = sr_addr)
194  // to the latest one
195  for (auto it = rmob_it; it != rmob.end() && (idx < reconstructionEntries);
196  it++) {
197  reconstruction[idx] = it->srAddress * spatialRegionSize;
198  idx += (it+1)->delta + 1;
199  }
200 
201  // Now query the PST with the PC of each RMOB entry
202  idx = 0;
203  for (auto it = rmob_it; it != rmob.end() && (idx < reconstructionEntries);
204  it++) {
205  ActiveGenerationTableEntry *pst_entry =
206  patternSequenceTable.findEntry(it->pstAddress, false /* unused */);
207  if (pst_entry != nullptr) {
208  patternSequenceTable.accessEntry(pst_entry);
209  for (auto &seq_entry : pst_entry->sequence) {
210  if (seq_entry.counter > 1) {
211  // 2-bit counter: high enough confidence with a
212  // value greater than 1
213  Addr rec_addr = it->srAddress * spatialRegionSize +
214  seq_entry.offset;
215  unsigned ridx = idx + seq_entry.delta;
216  // Try to use the corresponding position, if it has been
217  // already used, look the surrounding positions
218  if (ridx < reconstructionEntries &&
219  reconstruction[ridx] == MaxAddr) {
220  reconstruction[ridx] = rec_addr;
221  } else if ((ridx + 1) < reconstructionEntries &&
222  reconstruction[ridx + 1] == MaxAddr) {
223  reconstruction[ridx + 1] = rec_addr;
224  } else if ((ridx + 2) < reconstructionEntries &&
225  reconstruction[ridx + 2] == MaxAddr) {
226  reconstruction[ridx + 2] = rec_addr;
227  } else if ((ridx > 0) &&
228  ((ridx - 1) < reconstructionEntries) &&
229  reconstruction[ridx - 1] == MaxAddr) {
230  reconstruction[ridx - 1] = rec_addr;
231  } else if ((ridx > 1) &&
232  ((ridx - 2) < reconstructionEntries) &&
233  reconstruction[ridx - 2] == MaxAddr) {
234  reconstruction[ridx - 2] = rec_addr;
235  }
236  }
237  }
238  }
239  idx += (it+1)->delta + 1;
240  }
241 
242  for (Addr pf_addr : reconstruction) {
243  if (pf_addr != MaxAddr) {
244  addresses.push_back(AddrPriority(pf_addr, 0));
245  }
246  }
247 }
248 
249 } // namespace Prefetcher
250 
252 STeMSPrefetcherParams::create()
253 {
254  return new Prefetcher::STeMS(this);
255 }
associative_set_impl.hh
Prefetcher::Queued::AddrPriority
std::pair< Addr, int32_t > AddrPriority
Definition: queued.hh:182
Prefetcher::STeMS::spatialRegionSize
const size_t spatialRegionSize
Size of each spatial region.
Definition: spatio_temporal_memory_streaming.hh:58
Prefetcher::Base::blkSize
unsigned blkSize
The block size of the parent cache.
Definition: base.hh:262
Prefetcher::Base::PrefetchInfo::getPC
Addr getPC() const
Returns the program counter that generated this request.
Definition: base.hh:135
Prefetcher::STeMS::RegionMissOrderBufferEntry
Data type of the Region Miss Order Buffer entry.
Definition: spatio_temporal_memory_streaming.hh:155
Prefetcher::STeMS::RegionMissOrderBufferEntry::pstAddress
Addr pstAddress
Address used to index the PST table, generated using the PC and the offset within the spatial region.
Definition: spatio_temporal_memory_streaming.hh:162
Prefetcher::STeMS::reconstructionEntries
const unsigned int reconstructionEntries
Number of reconstruction entries.
Definition: spatio_temporal_memory_streaming.hh:62
Prefetcher::STeMS::ActiveGenerationTableEntry::paddress
Addr paddress
Physical address of the spatial region.
Definition: spatio_temporal_memory_streaming.hh:70
Prefetcher::STeMS::ActiveGenerationTableEntry::addOffset
void addOffset(unsigned int offset)
Add a new access to the sequence.
Definition: spatio_temporal_memory_streaming.hh:128
Prefetcher::Base::inCache
bool inCache(Addr addr, bool is_secure) const
Determine if address is in cache.
Definition: base.cc:145
std::vector
STL vector class.
Definition: stl.hh:37
Prefetcher::STeMS::RegionMissOrderBufferEntry::delta
unsigned int delta
Delta within the global miss order sequence.
Definition: spatio_temporal_memory_streaming.hh:164
floorLog2
std::enable_if< std::is_integral< T >::value, int >::type floorLog2(T x)
Definition: intmath.hh:63
Prefetcher::STeMS::rmob
CircularQueue< RegionMissOrderBufferEntry > rmob
Region Miss Order Buffer (RMOB)
Definition: spatio_temporal_memory_streaming.hh:168
MaxAddr
const Addr MaxAddr
Definition: types.hh:166
CircularQueue::iterator
Iterator to the circular queue.
Definition: circular_queue.hh:155
Prefetcher::STeMS::lastTriggerCounter
unsigned int lastTriggerCounter
Counter to keep the count of accesses between trigger accesses.
Definition: spatio_temporal_memory_streaming.hh:171
Prefetcher::STeMS::STeMS
STeMS(const STeMSPrefetcherParams *p)
Definition: spatio_temporal_memory_streaming.cc:37
Prefetcher::STeMS::spatialRegionSizeBits
const size_t spatialRegionSizeBits
log_2 of the spatial region size
Definition: spatio_temporal_memory_streaming.hh:60
Prefetcher::STeMS::checkForActiveGenerationsEnd
void checkForActiveGenerationsEnd()
Checks if the active generations have ended.
Definition: spatio_temporal_memory_streaming.cc:60
Prefetcher::Base::PrefetchInfo::getPaddr
Addr getPaddr() const
Gets the physical address of the request.
Definition: base.hh:182
DPRINTF
#define DPRINTF(x,...)
Definition: trace.hh:234
MipsISA::pc
Bitfield< 4 > pc
Definition: pra_constants.hh:240
Prefetcher::STeMS::addToRMOB
void addToRMOB(Addr sr_addr, Addr pst_addr, unsigned int delta)
Adds an entry to the RMOB.
Definition: spatio_temporal_memory_streaming.cc:107
Prefetcher::Base::PrefetchInfo::isCacheMiss
bool isCacheMiss() const
Check if this event comes from a cache miss.
Definition: base.hh:191
Prefetcher
Copyright (c) 2018 Metempsy Technology Consulting All rights reserved.
Definition: base.hh:78
Prefetcher::STeMS::activeGenerationTable
AssociativeSet< ActiveGenerationTableEntry > activeGenerationTable
Active Generation Table (AGT)
Definition: spatio_temporal_memory_streaming.hh:150
Prefetcher::STeMS::ActiveGenerationTableEntry::sequence
std::vector< SequenceEntry > sequence
Sequence of accesses.
Definition: spatio_temporal_memory_streaming.hh:88
Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:142
Prefetcher::Queued
Definition: queued.hh:54
Prefetcher::STeMS::ActiveGenerationTableEntry::pc
Addr pc
PC that started this generation.
Definition: spatio_temporal_memory_streaming.hh:72
Prefetcher::Base::PrefetchInfo::isSecure
bool isSecure() const
Returns true if the address targets the secure memory space.
Definition: base.hh:126
Prefetcher::STeMS::ActiveGenerationTableEntry::update
void update(ActiveGenerationTableEntry const &e)
Update the entry data with an entry from a generation that just ended.
Definition: spatio_temporal_memory_streaming.hh:116
Prefetcher::STeMS::calculatePrefetch
void calculatePrefetch(const PrefetchInfo &pfi, std::vector< AddrPriority > &addresses) override
Definition: spatio_temporal_memory_streaming.cc:118
Prefetcher::Base::PrefetchInfo
Class containing the information needed by the prefetch to train and generate new prefetch requests.
Definition: base.hh:90
Prefetcher::STeMS::patternSequenceTable
AssociativeSet< ActiveGenerationTableEntry > patternSequenceTable
Pattern Sequence Table (PST)
Definition: spatio_temporal_memory_streaming.hh:152
MipsISA::p
Bitfield< 0 > p
Definition: pra_constants.hh:323
Prefetcher::Base::inMissQueue
bool inMissQueue(Addr addr, bool is_secure) const
Determine if address is in cache miss queue.
Definition: base.cc:151
Prefetcher::STeMS
Definition: spatio_temporal_memory_streaming.hh:55
fatal_if
#define fatal_if(cond,...)
Conditional fatal macro that checks the supplied condition and only causes a fatal error if the condi...
Definition: logging.hh:219
spatio_temporal_memory_streaming.hh
Prefetcher::Base::PrefetchInfo::getAddr
Addr getAddr() const
Obtains the address value of this Prefetcher address.
Definition: base.hh:117
isPowerOf2
bool isPowerOf2(const T &n)
Definition: intmath.hh:102
Prefetcher::STeMS::reconstructSequence
void reconstructSequence(CircularQueue< RegionMissOrderBufferEntry >::iterator rmob_it, std::vector< AddrPriority > &addresses)
Reconstructs a sequence of accesses and generates the prefetch addresses, adding them to the addresse...
Definition: spatio_temporal_memory_streaming.cc:186
Prefetcher::Base::PrefetchInfo::hasPC
bool hasPC() const
Returns true if the associated program counter is valid.
Definition: base.hh:145
Prefetcher::STeMS::RegionMissOrderBufferEntry::srAddress
Addr srAddress
Address of the spatial region.
Definition: spatio_temporal_memory_streaming.hh:157
Prefetcher::STeMS::ActiveGenerationTableEntry
Entry data type for the Active Generation Table (AGT) and the Pattern Sequence Table (PST)
Definition: spatio_temporal_memory_streaming.hh:68

Generated on Wed Sep 30 2020 14:02:12 for gem5 by doxygen 1.8.17