gem5  v21.1.0.2
indirect_memory.cc
Go to the documentation of this file.
1 
30 
31  #include "mem/cache/base.hh"
33  #include "params/IndirectMemoryPrefetcher.hh"
34 
35 namespace gem5
36 {
37 
39 namespace prefetch
40 {
41 
42 IndirectMemory::IndirectMemory(const IndirectMemoryPrefetcherParams &p)
43  : Queued(p),
44  maxPrefetchDistance(p.max_prefetch_distance),
45  shiftValues(p.shift_values), prefetchThreshold(p.prefetch_threshold),
46  streamCounterThreshold(p.stream_counter_threshold),
47  streamingDistance(p.streaming_distance),
48  prefetchTable(p.pt_table_assoc, p.pt_table_entries,
49  p.pt_table_indexing_policy, p.pt_table_replacement_policy,
50  PrefetchTableEntry(p.num_indirect_counter_bits)),
51  ipd(p.ipd_table_assoc, p.ipd_table_entries, p.ipd_table_indexing_policy,
52  p.ipd_table_replacement_policy,
53  IndirectPatternDetectorEntry(p.addr_array_len, shiftValues.size())),
54  ipdEntryTrackingMisses(nullptr), byteOrder(p.sys->getGuestByteOrder())
55 {
56 }
57 
58 void
60  std::vector<AddrPriority> &addresses)
61 {
62  // This prefetcher requires a PC
63  if (!pfi.hasPC()) {
64  return;
65  }
66 
67  bool is_secure = pfi.isSecure();
68  Addr pc = pfi.getPC();
69  Addr addr = pfi.getAddr();
70  bool miss = pfi.isCacheMiss();
71 
73 
74  // First check if this is a miss, if the prefetcher is tracking misses
75  if (ipdEntryTrackingMisses != nullptr && miss) {
76  // Check if the entry tracking misses has already set its second index
79  } else {
81  }
82  } else {
83  // if misses are not being tracked, attempt to detect stream accesses
84  PrefetchTableEntry *pt_entry =
85  prefetchTable.findEntry(pc, false /* unused */);
86  if (pt_entry != nullptr) {
87  prefetchTable.accessEntry(pt_entry);
88 
89  if (pt_entry->address != addr) {
90  // Streaming access found
91  pt_entry->streamCounter += 1;
92  if (pt_entry->streamCounter >= streamCounterThreshold) {
93  int64_t delta = addr - pt_entry->address;
94  for (unsigned int i = 1; i <= streamingDistance; i += 1) {
95  addresses.push_back(AddrPriority(addr + delta * i, 0));
96  }
97  }
98  pt_entry->address = addr;
99  pt_entry->secure = is_secure;
100 
101 
102  // if this is a read, read the data from the cache and assume
103  // it is an index (this is only possible if the data is already
104  // in the cache), also, only indexes up to 8 bytes are
105  // considered
106 
107  if (!miss && !pfi.isWrite() && pfi.getSize() <= 8) {
108  int64_t index = 0;
109  bool read_index = true;
110  switch(pfi.getSize()) {
111  case sizeof(uint8_t):
112  index = pfi.get<uint8_t>(byteOrder);
113  break;
114  case sizeof(uint16_t):
115  index = pfi.get<uint16_t>(byteOrder);
116  break;
117  case sizeof(uint32_t):
118  index = pfi.get<uint32_t>(byteOrder);
119  break;
120  case sizeof(uint64_t):
121  index = pfi.get<uint64_t>(byteOrder);
122  break;
123  default:
124  // Ignore non-power-of-two sizes
125  read_index = false;
126  }
127  if (read_index && !pt_entry->enabled) {
128  // Not enabled (no pattern detected in this stream),
129  // add or update an entry in the pattern detector and
130  // start tracking misses
131  allocateOrUpdateIPDEntry(pt_entry, index);
132  } else if (read_index) {
133  // Enabled entry, update the index
134  pt_entry->index = index;
135  if (!pt_entry->increasedIndirectCounter) {
136  pt_entry->indirectCounter--;
137  } else {
138  // Set this to false, to see if the new index
139  // has any match
140  pt_entry->increasedIndirectCounter = false;
141  }
142 
143  // If the counter is high enough, start prefetching
144  if (pt_entry->indirectCounter > prefetchThreshold) {
145  unsigned distance = maxPrefetchDistance *
146  pt_entry->indirectCounter.calcSaturation();
147  for (int delta = 1; delta < distance; delta += 1) {
148  Addr pf_addr = pt_entry->baseAddr +
149  (pt_entry->index << pt_entry->shift);
150  addresses.push_back(AddrPriority(pf_addr, 0));
151  }
152  }
153  }
154  }
155  }
156  } else {
157  pt_entry = prefetchTable.findVictim(pc);
158  assert(pt_entry != nullptr);
159  prefetchTable.insertEntry(pc, false /* unused */, pt_entry);
160  pt_entry->address = addr;
161  pt_entry->secure = is_secure;
162  }
163  }
164 }
165 
166 void
168  const PrefetchTableEntry *pt_entry, int64_t index)
169 {
170  // The address of the pt_entry is used to index the IPD
171  Addr ipd_entry_addr = (Addr) pt_entry;
172  IndirectPatternDetectorEntry *ipd_entry = ipd.findEntry(ipd_entry_addr,
173  false/* unused */);
174  if (ipd_entry != nullptr) {
175  ipd.accessEntry(ipd_entry);
176  if (!ipd_entry->secondIndexSet) {
177  // Second time we see an index, fill idx2
178  ipd_entry->idx2 = index;
179  ipd_entry->secondIndexSet = true;
180  ipdEntryTrackingMisses = ipd_entry;
181  } else {
182  // Third access! no pattern has been found so far,
183  // release the IPD entry
184  ipd.invalidate(ipd_entry);
185  ipdEntryTrackingMisses = nullptr;
186  }
187  } else {
188  ipd_entry = ipd.findVictim(ipd_entry_addr);
189  assert(ipd_entry != nullptr);
190  ipd.insertEntry(ipd_entry_addr, false /* unused */, ipd_entry);
191  ipd_entry->idx1 = index;
192  ipdEntryTrackingMisses = ipd_entry;
193  }
194 }
195 
196 void
198 {
200  // If the second index is not set, we are just filling the baseAddr
201  // vector
202  assert(entry->numMisses < entry->baseAddr.size());
203  std::vector<Addr> &ba_array = entry->baseAddr[entry->numMisses];
204  int idx = 0;
205  for (int shift : shiftValues) {
206  ba_array[idx] = miss_addr - (entry->idx1 << shift);
207  idx += 1;
208  }
209  entry->numMisses += 1;
210  if (entry->numMisses == entry->baseAddr.size()) {
211  // stop tracking misses once we have tracked enough
212  ipdEntryTrackingMisses = nullptr;
213  }
214 }
215 void
217 {
219  // Second index is filled, compare the addresses generated during
220  // the previous misses (using idx1) against newly generated values
221  // using idx2, if a match is found, fill the additional fields
222  // of the PT entry
223  for (int midx = 0; midx < entry->numMisses; midx += 1)
224  {
225  std::vector<Addr> &ba_array = entry->baseAddr[midx];
226  int idx = 0;
227  for (int shift : shiftValues) {
228  if (ba_array[idx] == (miss_addr - (entry->idx2 << shift))) {
229  // Match found!
230  // Fill the corresponding pt_entry
231  PrefetchTableEntry *pt_entry =
232  (PrefetchTableEntry *) entry->getTag();
233  pt_entry->baseAddr = ba_array[idx];
234  pt_entry->shift = shift;
235  pt_entry->enabled = true;
236  pt_entry->indirectCounter.reset();
237  // Release the current IPD Entry
238  ipd.invalidate(entry);
239  // Do not track more misses
240  ipdEntryTrackingMisses = nullptr;
241  return;
242  }
243  idx += 1;
244  }
245  }
246 }
247 
248 void
250 {
251  for (auto &pt_entry : prefetchTable) {
252  if (pt_entry.enabled) {
253  if (addr == pt_entry.baseAddr +
254  (pt_entry.index << pt_entry.shift)) {
255  pt_entry.indirectCounter++;
256  pt_entry.increasedIndirectCounter = true;
257  }
258  }
259  }
260 }
261 
262 } // namespace prefetch
263 } // namespace gem5
gem5::prefetch::Base::PrefetchInfo::getAddr
Addr getAddr() const
Obtains the address value of this Prefetcher address.
Definition: base.hh:125
associative_set_impl.hh
gem5::prefetch::IndirectMemory::shiftValues
const std::vector< int > shiftValues
Shift values considered.
Definition: indirect_memory.hh:62
gem5::GenericSatCounter::calcSaturation
double calcSaturation() const
Calculate saturation percentile of the current counter's value with regard to its maximum possible va...
Definition: sat_counter.hh:303
gem5::prefetch::IndirectMemory::PrefetchTableEntry::baseAddr
Addr baseAddr
BaseAddr detected.
Definition: indirect_memory.hh:89
base.hh
gem5::prefetch::Queued::AddrPriority
std::pair< Addr, int32_t > AddrPriority
Definition: queued.hh:190
gem5::prefetch::IndirectMemory::IndirectMemory
IndirectMemory(const IndirectMemoryPrefetcherParams &p)
Definition: indirect_memory.cc:42
gem5::MipsISA::index
Bitfield< 30, 0 > index
Definition: pra_constants.hh:47
gem5::prefetch::IndirectMemory::PrefetchTableEntry::shift
int shift
Shift detected.
Definition: indirect_memory.hh:91
gem5::prefetch::Base::PrefetchInfo::isSecure
bool isSecure() const
Returns true if the address targets the secure memory space.
Definition: base.hh:134
gem5::prefetch::IndirectMemory::streamingDistance
const int streamingDistance
Number of prefetches generated when using the streaming prefetcher.
Definition: indirect_memory.hh:68
gem5::prefetch::IndirectMemory::IndirectPatternDetectorEntry::idx2
int64_t idx2
Second index.
Definition: indirect_memory.hh:133
gem5::prefetch::IndirectMemory::prefetchThreshold
const unsigned int prefetchThreshold
Counter threshold to start prefetching.
Definition: indirect_memory.hh:64
gem5::prefetch::IndirectMemory::prefetchTable
AssociativeSet< PrefetchTableEntry > prefetchTable
Prefetch table.
Definition: indirect_memory.hh:125
gem5::prefetch::Base::PrefetchInfo::isCacheMiss
bool isCacheMiss() const
Check if this event comes from a cache miss.
Definition: base.hh:199
gem5::ArmISA::byteOrder
ByteOrder byteOrder(const ThreadContext *tc)
Definition: utility.hh:412
std::vector
STL vector class.
Definition: stl.hh:37
gem5::TaggedEntry::getTag
virtual Addr getTag() const
Get tag associated to this block.
Definition: tagged_entry.hh:71
gem5::prefetch::IndirectMemory::ipdEntryTrackingMisses
IndirectPatternDetectorEntry * ipdEntryTrackingMisses
Entry currently tracking misses.
Definition: indirect_memory.hh:167
gem5::prefetch::Base::PrefetchInfo::get
T get(ByteOrder endian) const
Gets the associated data of the request triggering the event.
Definition: base.hh:211
gem5::ArmISA::i
Bitfield< 7 > i
Definition: misc_types.hh:66
gem5::prefetch::IndirectMemory::PrefetchTableEntry::streamCounter
unsigned int streamCounter
Confidence counter of the stream.
Definition: indirect_memory.hh:80
gem5::prefetch::IndirectMemory::IndirectPatternDetectorEntry::secondIndexSet
bool secondIndexSet
Valid bit for the second index.
Definition: indirect_memory.hh:135
indirect_memory.hh
gem5::prefetch::IndirectMemory::streamCounterThreshold
const int streamCounterThreshold
streamCounter value to trigger the streaming prefetcher
Definition: indirect_memory.hh:66
gem5::prefetch::IndirectMemory::trackMissIndex2
void trackMissIndex2(Addr miss_addr)
Update an IPD entry with a detected miss address, when the second index is being tracked.
Definition: indirect_memory.cc:216
gem5::ArmISA::shift
Bitfield< 6, 5 > shift
Definition: types.hh:117
gem5::prefetch::Base::PrefetchInfo::getPC
Addr getPC() const
Returns the program counter that generated this request.
Definition: base.hh:143
gem5::prefetch::IndirectMemory::ipd
AssociativeSet< IndirectPatternDetectorEntry > ipd
Indirect Pattern Detector (IPD) table.
Definition: indirect_memory.hh:164
gem5::prefetch::IndirectMemory::PrefetchTableEntry::address
Addr address
Accessed address.
Definition: indirect_memory.hh:76
gem5::prefetch::IndirectMemory::PrefetchTableEntry::enabled
bool enabled
Enable bit of the indirect fields.
Definition: indirect_memory.hh:85
gem5::MipsISA::p
Bitfield< 0 > p
Definition: pra_constants.hh:326
gem5::prefetch::IndirectMemory::IndirectPatternDetectorEntry
Indirect Pattern Detector entrt.
Definition: indirect_memory.hh:128
gem5::GenericSatCounter::reset
void reset()
Reset the counter to its initial value.
Definition: sat_counter.hh:292
gem5::prefetch::IndirectMemory::IndirectPatternDetectorEntry::idx1
int64_t idx1
First index.
Definition: indirect_memory.hh:131
gem5::prefetch::IndirectMemory::PrefetchTableEntry
Prefetch Table Entry.
Definition: indirect_memory.hh:71
gem5::Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:147
gem5::prefetch::IndirectMemory::maxPrefetchDistance
const unsigned int maxPrefetchDistance
Maximum number of prefetches generated per event.
Definition: indirect_memory.hh:60
gem5::prefetch::IndirectMemory::allocateOrUpdateIPDEntry
void allocateOrUpdateIPDEntry(const PrefetchTableEntry *pt_entry, int64_t index)
Allocate or update an entry in the IPD.
Definition: indirect_memory.cc:167
gem5::GEM5_DEPRECATED_NAMESPACE
GEM5_DEPRECATED_NAMESPACE(GuestABI, guest_abi)
gem5::prefetch::Base::PrefetchInfo::isWrite
bool isWrite() const
Checks if the request that caused this prefetch event was a write request.
Definition: base.hh:181
gem5::prefetch::IndirectMemory::PrefetchTableEntry::indirectCounter
SatCounter8 indirectCounter
Confidence counter of the indirect fields.
Definition: indirect_memory.hh:93
gem5::prefetch::Base::PrefetchInfo::getSize
unsigned int getSize() const
Gets the size of the request triggering this event.
Definition: base.hh:171
gem5::prefetch::Queued
Definition: queued.hh:60
gem5::prefetch::IndirectMemory::PrefetchTableEntry::increasedIndirectCounter
bool increasedIndirectCounter
This variable is set to indicate that there has been at least one match with the current index value.
Definition: indirect_memory.hh:100
gem5::prefetch::IndirectMemory::PrefetchTableEntry::secure
bool secure
Whether this address is in the secure region.
Definition: indirect_memory.hh:78
gem5::prefetch::IndirectMemory::PrefetchTableEntry::index
int64_t index
Current index value.
Definition: indirect_memory.hh:87
gem5::MipsISA::pc
Bitfield< 4 > pc
Definition: pra_constants.hh:243
gem5::prefetch::IndirectMemory::IndirectPatternDetectorEntry::numMisses
int numMisses
Number of misses currently recorded.
Definition: indirect_memory.hh:137
gem5::context_switch_task_id::Prefetcher
@ Prefetcher
Definition: request.hh:83
gem5::prefetch::IndirectMemory::checkAccessMatchOnActiveEntries
void checkAccessMatchOnActiveEntries(Addr addr)
Checks if an access to the cache matches any active PT entry, if so, the indirect confidence counter ...
Definition: indirect_memory.cc:249
gem5::prefetch::IndirectMemory::trackMissIndex1
void trackMissIndex1(Addr miss_addr)
Update an IPD entry with a detected miss address, when the first index is being tracked.
Definition: indirect_memory.cc:197
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::prefetch::IndirectMemory::IndirectPatternDetectorEntry::baseAddr
std::vector< std::vector< Addr > > baseAddr
Potential BaseAddr candidates for each recorded miss.
Definition: indirect_memory.hh:143
gem5::prefetch::IndirectMemory::byteOrder
const ByteOrder byteOrder
Byte order used to access the cache.
Definition: indirect_memory.hh:170
gem5::prefetch::IndirectMemory::calculatePrefetch
void calculatePrefetch(const PrefetchInfo &pfi, std::vector< AddrPriority > &addresses) override
Definition: indirect_memory.cc:59
gem5::prefetch::Base::PrefetchInfo
Class containing the information needed by the prefetch to train and generate new prefetch requests.
Definition: base.hh:97
gem5::X86ISA::addr
Bitfield< 3 > addr
Definition: types.hh:84
gem5::prefetch::Base::PrefetchInfo::hasPC
bool hasPC() const
Returns true if the associated program counter is valid.
Definition: base.hh:153

Generated on Tue Sep 21 2021 12:25:29 for gem5 by doxygen 1.8.17