gem5  v21.1.0.2
signature_path.cc
Go to the documentation of this file.
1 
30 
31 #include <cassert>
32 #include <climits>
33 
34 #include "debug/HWPrefetch.hh"
36 #include "params/SignaturePathPrefetcher.hh"
37 
38 namespace gem5
39 {
40 
42 namespace prefetch
43 {
44 
45 SignaturePath::SignaturePath(const SignaturePathPrefetcherParams &p)
46  : Queued(p),
47  stridesPerPatternEntry(p.strides_per_pattern_entry),
48  signatureShift(p.signature_shift),
49  signatureBits(p.signature_bits),
50  prefetchConfidenceThreshold(p.prefetch_confidence_threshold),
51  lookaheadConfidenceThreshold(p.lookahead_confidence_threshold),
52  signatureTable(p.signature_table_assoc, p.signature_table_entries,
53  p.signature_table_indexing_policy,
54  p.signature_table_replacement_policy),
55  patternTable(p.pattern_table_assoc, p.pattern_table_entries,
56  p.pattern_table_indexing_policy,
57  p.pattern_table_replacement_policy,
58  PatternEntry(stridesPerPatternEntry, p.num_counter_bits))
59 {
61  "The prefetch confidence threshold must be greater than 0\n");
63  "The prefetch confidence threshold must be less than 1\n");
65  "The lookahead confidence threshold must be greater than 0\n");
67  "The lookahead confidence threshold must be less than 1\n");
68 }
69 
72 {
73  PatternStrideEntry *pstride_entry = findStride(stride);
74  if (pstride_entry == nullptr) {
75  // Specific replacement algorithm for this table,
76  // pick the entry with the lowest counter value,
77  // then decrease the counter of all entries
78 
79  // If all counters have the max value, this will be the pick
80  PatternStrideEntry *victim_pstride_entry = &(strideEntries[0]);
81 
82  unsigned long current_counter = ULONG_MAX;
83  for (auto &entry : strideEntries) {
84  if (entry.counter < current_counter) {
85  victim_pstride_entry = &entry;
86  current_counter = entry.counter;
87  }
88  entry.counter--;
89  }
90  pstride_entry = victim_pstride_entry;
91  pstride_entry->counter.reset();
92  pstride_entry->stride = stride;
93  }
94  return *pstride_entry;
95 }
96 
97 void
99  stride_t delta, double path_confidence, signature_t signature,
100  bool is_secure, std::vector<AddrPriority> &addresses)
101 {
102  stride_t block = last_block + delta;
103 
104  Addr pf_ppn;
105  stride_t pf_block;
106  if (block < 0) {
107  stride_t num_cross_pages = 1 + (-block) / (pageBytes/blkSize);
108  if (num_cross_pages > ppn) {
109  // target address smaller than page 0, ignore this request;
110  return;
111  }
112  pf_ppn = ppn - num_cross_pages;
113  pf_block = block + (pageBytes/blkSize) * num_cross_pages;
114  handlePageCrossingLookahead(signature, last_block, delta,
115  path_confidence);
116  } else if (block >= (pageBytes/blkSize)) {
117  stride_t num_cross_pages = block / (pageBytes/blkSize);
118  if (MaxAddr/pageBytes < (ppn + num_cross_pages)) {
119  // target address goes beyond MaxAddr, ignore this request;
120  return;
121  }
122  pf_ppn = ppn + num_cross_pages;
123  pf_block = block - (pageBytes/blkSize) * num_cross_pages;
124  handlePageCrossingLookahead(signature, last_block, delta,
125  path_confidence);
126  } else {
127  pf_ppn = ppn;
128  pf_block = block;
129  }
130 
131  Addr new_addr = pf_ppn * pageBytes;
132  new_addr += pf_block * (Addr)blkSize;
133 
134  DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr);
135  addresses.push_back(AddrPriority(new_addr, 0));
136 }
137 
138 void
140  signature_t &new_signature, double &new_conf, stride_t &new_stride)
141 {
142  new_signature = current_block;
143  new_conf = 1.0;
144  new_stride = current_block;
145 }
146 
147 void
149  PatternEntry &pattern_entry, PatternStrideEntry &pstride_entry)
150 {
151  pstride_entry.counter++;
152 }
153 
154 void
156 {
157  assert(stride != 0);
158  // The pattern table is indexed by signatures
159  PatternEntry &p_entry = getPatternEntry(signature);
160  PatternStrideEntry &ps_entry = p_entry.getStrideEntry(stride);
161  increasePatternEntryCounter(p_entry, ps_entry);
162 }
163 
166  stride_t block, bool &miss, stride_t &stride,
167  double &initial_confidence)
168 {
169  SignatureEntry* signature_entry = signatureTable.findEntry(ppn, is_secure);
170  if (signature_entry != nullptr) {
171  signatureTable.accessEntry(signature_entry);
172  miss = false;
173  stride = block - signature_entry->lastBlock;
174  } else {
175  signature_entry = signatureTable.findVictim(ppn);
176  assert(signature_entry != nullptr);
177 
178  // Sets signature_entry->signature, initial_confidence, and stride
179  handleSignatureTableMiss(block, signature_entry->signature,
180  initial_confidence, stride);
181 
182  signatureTable.insertEntry(ppn, is_secure, signature_entry);
183  miss = true;
184  }
185  signature_entry->lastBlock = block;
186  return *signature_entry;
187 }
188 
191 {
192  PatternEntry* pattern_entry = patternTable.findEntry(signature, false);
193  if (pattern_entry != nullptr) {
194  // Signature found
195  patternTable.accessEntry(pattern_entry);
196  } else {
197  // Signature not found
198  pattern_entry = patternTable.findVictim(signature);
199  assert(pattern_entry != nullptr);
200 
201  patternTable.insertEntry(signature, false, pattern_entry);
202  }
203  return *pattern_entry;
204 }
205 
206 double
208  PatternStrideEntry const &entry) const
209 {
210  return entry.counter.calcSaturation();
211 }
212 
213 double
215  PatternStrideEntry const &lookahead) const
216 {
217  double lookahead_confidence = lookahead.counter.calcSaturation();
218  if (lookahead_confidence > 0.95) {
224  lookahead_confidence = 0.95;
225  }
226  return lookahead_confidence;
227 }
228 
229 void
231  std::vector<AddrPriority> &addresses)
232 {
233  Addr request_addr = pfi.getAddr();
234  Addr ppn = request_addr / pageBytes;
235  stride_t current_block = (request_addr % pageBytes) / blkSize;
237  bool is_secure = pfi.isSecure();
238  double initial_confidence = 1.0;
239 
240  // Get the SignatureEntry of this page to:
241  // - compute the current stride
242  // - obtain the current signature of accesses
243  bool miss;
244  SignatureEntry &signature_entry = getSignatureEntry(ppn, is_secure,
245  current_block, miss, stride, initial_confidence);
246 
247  if (miss) {
248  // No history for this page, can't continue
249  return;
250  }
251 
252  if (stride == 0) {
253  // Can't continue with a stride 0
254  return;
255  }
256 
257  // Update the confidence of the current signature
258  updatePatternTable(signature_entry.signature, stride);
259 
260  // Update the current SignatureEntry signature
261  signature_entry.signature =
262  updateSignature(signature_entry.signature, stride);
263 
264  signature_t current_signature = signature_entry.signature;
265  double current_confidence = initial_confidence;
266  stride_t current_stride = signature_entry.lastBlock;
267 
268  // Look for prefetch candidates while the current path confidence is
269  // high enough
270  while (current_confidence > lookaheadConfidenceThreshold) {
271  // With the updated signature, attempt to generate prefetches
272  // - search the PatternTable and select all entries with enough
273  // confidence, these are prefetch candidates
274  // - select the entry with the highest counter as the "lookahead"
275  PatternEntry *current_pattern_entry =
276  patternTable.findEntry(current_signature, false);
277  PatternStrideEntry const *lookahead = nullptr;
278  if (current_pattern_entry != nullptr) {
279  unsigned long max_counter = 0;
280  for (auto const &entry : current_pattern_entry->strideEntries) {
281  //select the entry with the maximum counter value as lookahead
282  if (max_counter < entry.counter) {
283  max_counter = entry.counter;
284  lookahead = &entry;
285  }
286  double prefetch_confidence =
287  calculatePrefetchConfidence(*current_pattern_entry, entry);
288 
289  if (prefetch_confidence >= prefetchConfidenceThreshold) {
290  assert(entry.stride != 0);
291  //prefetch candidate
292  addPrefetch(ppn, current_stride, entry.stride,
293  current_confidence, current_signature,
294  is_secure, addresses);
295  }
296  }
297  }
298 
299  if (lookahead != nullptr) {
300  current_confidence *= calculateLookaheadConfidence(
301  *current_pattern_entry, *lookahead);
302  current_signature =
303  updateSignature(current_signature, lookahead->stride);
304  current_stride += lookahead->stride;
305  } else {
306  current_confidence = 0.0;
307  }
308  }
309 
310  auxiliaryPrefetcher(ppn, current_block, is_secure, addresses);
311 }
312 
313 void
315  bool is_secure, std::vector<AddrPriority> &addresses)
316 {
317  if (addresses.empty()) {
318  // Enable the next line prefetcher if no prefetch candidates are found
319  addPrefetch(ppn, current_block, 1, 0.0 /* unused*/, 0 /* unused */,
320  is_secure, addresses);
321  }
322 }
323 
324 } // namespace prefetch
325 } // 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::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::SignaturePath::PatternStrideEntry::stride
stride_t stride
stride in a page in blkSize increments
Definition: signature_path.hh:93
gem5::prefetch::Queued::AddrPriority
std::pair< Addr, int32_t > AddrPriority
Definition: queued.hh:190
gem5::RiscvISA::ppn
Bitfield< 43, 0 > ppn
Definition: pagetable.hh:48
gem5::prefetch::Base::PrefetchInfo::isSecure
bool isSecure() const
Returns true if the address targets the secure memory space.
Definition: base.hh:134
gem5::prefetch::SignaturePath::handlePageCrossingLookahead
virtual void handlePageCrossingLookahead(signature_t signature, stride_t last_offset, stride_t delta, double path_confidence)
Handles the situation when the lookahead process has crossed the boundaries of the current page.
Definition: signature_path.hh:282
gem5::prefetch::SignaturePath::lookaheadConfidenceThreshold
const double lookaheadConfidenceThreshold
Minimum confidence to keep navigating lookahead entries.
Definition: signature_path.hh:74
gem5::prefetch::SignaturePath::SignatureEntry
Signature entry data type.
Definition: signature_path.hh:77
std::vector
STL vector class.
Definition: stl.hh:37
gem5::prefetch::SignaturePath::calculateLookaheadConfidence
virtual double calculateLookaheadConfidence(PatternEntry const &sig, PatternStrideEntry const &lookahead) const
Computes the lookahead path confidence of the provided pattern entry.
Definition: signature_path.cc:214
gem5::GenericSatCounter::counter
T counter
Definition: sat_counter.hh:331
gem5::prefetch::SignaturePath::prefetchConfidenceThreshold
const double prefetchConfidenceThreshold
Minimum confidence to issue a prefetch.
Definition: signature_path.hh:72
gem5::prefetch::SignaturePath::SignatureEntry::signature
signature_t signature
Path signature.
Definition: signature_path.hh:80
gem5::prefetch::SignaturePath::signature_t
uint16_t signature_t
Signature type.
Definition: signature_path.hh:61
gem5::prefetch::SignaturePath::auxiliaryPrefetcher
virtual void auxiliaryPrefetcher(Addr ppn, stride_t current_block, bool is_secure, std::vector< AddrPriority > &addresses)
Auxiliar prefetch mechanism used at the end of calculatePrefetch.
Definition: signature_path.cc:314
gem5::prefetch::Base::pageBytes
const Addr pageBytes
Definition: base.hh:293
gem5::prefetch::SignaturePath::PatternEntry::findStride
PatternStrideEntry * findStride(stride_t stride)
Returns the entry with the desired stride.
Definition: signature_path.hh:130
gem5::prefetch::SignaturePath::increasePatternEntryCounter
virtual void increasePatternEntryCounter(PatternEntry &pattern_entry, PatternStrideEntry &pstride_entry)
Increases the counter of a given PatternEntry/PatternStrideEntry.
Definition: signature_path.cc:148
gem5::prefetch::SignaturePath::updatePatternTable
void updatePatternTable(Addr signature, stride_t stride)
Updates the pattern table with the provided signature and stride.
Definition: signature_path.cc:155
gem5::MaxAddr
const Addr MaxAddr
Definition: types.hh:171
DPRINTF
#define DPRINTF(x,...)
Definition: trace.hh:186
gem5::MipsISA::p
Bitfield< 0 > p
Definition: pra_constants.hh:326
gem5::prefetch::SignaturePath::stride_t
int16_t stride_t
Stride type.
Definition: signature_path.hh:63
gem5::prefetch::SignaturePath::SignatureEntry::lastBlock
stride_t lastBlock
Last accessed block within a page.
Definition: signature_path.hh:82
gem5::GenericSatCounter::reset
void reset()
Reset the counter to its initial value.
Definition: sat_counter.hh:292
gem5::prefetch::SignaturePath::PatternStrideEntry
A stride entry with its counter.
Definition: signature_path.hh:90
gem5::prefetch::SignaturePath::getPatternEntry
PatternEntry & getPatternEntry(Addr signature)
Obtains the PatternEntry of the given signature, if the signature is not found, it allocates a new on...
Definition: signature_path.cc:190
gem5::prefetch::SignaturePath::calculatePrefetch
void calculatePrefetch(const PrefetchInfo &pfi, std::vector< AddrPriority > &addresses) override
Definition: signature_path.cc:230
gem5::prefetch::SignaturePath::PatternEntry::getStrideEntry
PatternStrideEntry & getStrideEntry(stride_t stride)
Gets the entry with the provided stride, if there is no entry with the associated stride,...
Definition: signature_path.cc:71
gem5::prefetch::SignaturePath::SignaturePath
SignaturePath(const SignaturePathPrefetcherParams &p)
Definition: signature_path.cc:45
gem5::prefetch::SignaturePath::handleSignatureTableMiss
virtual void handleSignatureTableMiss(stride_t current_block, signature_t &new_signature, double &new_conf, stride_t &new_stride)
Whenever a new SignatureEntry is allocated, it computes the new signature to be used with the new ent...
Definition: signature_path.cc:139
gem5::Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:147
gem5::GEM5_DEPRECATED_NAMESPACE
GEM5_DEPRECATED_NAMESPACE(GuestABI, guest_abi)
gem5::prefetch::Queued
Definition: queued.hh:60
gem5::prefetch::SignaturePath::addPrefetch
void addPrefetch(Addr ppn, stride_t last_block, stride_t delta, double path_confidence, signature_t signature, bool is_secure, std::vector< AddrPriority > &addresses)
Generates an address to be prefetched.
Definition: signature_path.cc:98
gem5::prefetch::SignaturePath::signatureTable
AssociativeSet< SignatureEntry > signatureTable
Signature table.
Definition: signature_path.hh:87
gem5::prefetch::SignaturePath::patternTable
AssociativeSet< PatternEntry > patternTable
Pattern table.
Definition: signature_path.hh:151
gem5::prefetch::SignaturePath::PatternEntry
Pattern entry data type, a set of stride and counter entries.
Definition: signature_path.hh:100
gem5::prefetch::Base::blkSize
unsigned blkSize
The block size of the parent cache.
Definition: base.hh:270
gem5::prefetch::SignaturePath::PatternEntry::strideEntries
std::vector< PatternStrideEntry > strideEntries
group of stides
Definition: signature_path.hh:103
gem5::prefetch::SignaturePath::getSignatureEntry
SignatureEntry & getSignatureEntry(Addr ppn, bool is_secure, stride_t block, bool &miss, stride_t &stride, double &initial_confidence)
Obtains the SignatureEntry of the given page, if the page is not found, it allocates a new one,...
Definition: signature_path.cc:165
gem5::context_switch_task_id::Prefetcher
@ Prefetcher
Definition: request.hh:83
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:225
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::prefetch::SignaturePath::calculatePrefetchConfidence
virtual double calculatePrefetchConfidence(PatternEntry const &sig, PatternStrideEntry const &entry) const
Computes the prefetch confidence of the provided pattern entry.
Definition: signature_path.cc:207
gem5::ArmISA::stride
Bitfield< 21, 20 > stride
Definition: misc_types.hh:446
signature_path.hh
gem5::prefetch::SignaturePath::updateSignature
signature_t updateSignature(signature_t sig, stride_t str) const
Generates a new signature from an existing one and a new stride.
Definition: signature_path.hh:159
gem5::prefetch::Base::PrefetchInfo
Class containing the information needed by the prefetch to train and generate new prefetch requests.
Definition: base.hh:97
gem5::prefetch::SignaturePath::PatternStrideEntry::counter
SatCounter8 counter
Saturating counter.
Definition: signature_path.hh:95

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