signature_path.cc (13553:047def1fa787) | signature_path.cc (13624:3d8220c2d41d) |
---|---|
1/** 2 * Copyright (c) 2018 Metempsy Technology Consulting 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; --- 39 unchanged lines hidden (view full) --- 48 signatureTable(p->signature_table_assoc, p->signature_table_entries, 49 p->signature_table_indexing_policy, 50 p->signature_table_replacement_policy), 51 patternTable(p->pattern_table_assoc, p->pattern_table_entries, 52 p->pattern_table_indexing_policy, 53 p->pattern_table_replacement_policy, 54 PatternEntry(stridesPerPatternEntry)) 55{ | 1/** 2 * Copyright (c) 2018 Metempsy Technology Consulting 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; --- 39 unchanged lines hidden (view full) --- 48 signatureTable(p->signature_table_assoc, p->signature_table_entries, 49 p->signature_table_indexing_policy, 50 p->signature_table_replacement_policy), 51 patternTable(p->pattern_table_assoc, p->pattern_table_entries, 52 p->pattern_table_indexing_policy, 53 p->pattern_table_replacement_policy, 54 PatternEntry(stridesPerPatternEntry)) 55{ |
56 fatal_if(prefetchConfidenceThreshold < 0, 57 "The prefetch confidence threshold must be greater than 0\n"); 58 fatal_if(prefetchConfidenceThreshold > 1, 59 "The prefetch confidence threshold must be less than 1\n"); 60 fatal_if(lookaheadConfidenceThreshold < 0, 61 "The lookahead confidence threshold must be greater than 0\n"); 62 fatal_if(lookaheadConfidenceThreshold > 1, 63 "The lookahead confidence threshold must be less than 1\n"); |
|
56} 57 58SignaturePathPrefetcher::PatternStrideEntry & 59SignaturePathPrefetcher::PatternEntry::getStrideEntry(stride_t stride, 60 uint8_t max_counter_value) 61{ 62 PatternStrideEntry *pstride_entry = findStride(stride); 63 if (pstride_entry == nullptr) { --- 17 unchanged lines hidden (view full) --- 81 pstride_entry = victim_pstride_entry; 82 pstride_entry->counter = 0; 83 pstride_entry->stride = stride; 84 } 85 return *pstride_entry; 86} 87 88void | 64} 65 66SignaturePathPrefetcher::PatternStrideEntry & 67SignaturePathPrefetcher::PatternEntry::getStrideEntry(stride_t stride, 68 uint8_t max_counter_value) 69{ 70 PatternStrideEntry *pstride_entry = findStride(stride); 71 if (pstride_entry == nullptr) { --- 17 unchanged lines hidden (view full) --- 89 pstride_entry = victim_pstride_entry; 90 pstride_entry->counter = 0; 91 pstride_entry->stride = stride; 92 } 93 return *pstride_entry; 94} 95 96void |
89SignaturePathPrefetcher::addPrefetch(Addr ppn, stride_t block, | 97SignaturePathPrefetcher::addPrefetch(Addr ppn, stride_t last_block, 98 stride_t delta, double path_confidence, signature_t signature, |
90 bool is_secure, std::vector<AddrPriority> &addresses) 91{ | 99 bool is_secure, std::vector<AddrPriority> &addresses) 100{ |
92 /** 93 * block is relative to the provided ppn. Assuming a page size of 4kB and 94 * a block size of 64B, the range of the stride of this prefetcher is 95 * -63,63 (pageBytes/blkSize) as the last accessed block also ranges from 96 * 0,63, the block value is expected to be between -63 and 126 97 * Negative block means that we are accessing the lower contiguous page, 98 * 64 or greater point to the next contiguous. 99 */ 100 assert(block > -((stride_t)(pageBytes/blkSize))); 101 assert(block < 2*((stride_t)(pageBytes/blkSize))); | 101 stride_t block = last_block + delta; |
102 103 Addr pf_ppn; 104 stride_t pf_block; 105 if (block < 0) { | 102 103 Addr pf_ppn; 104 stride_t pf_block; 105 if (block < 0) { |
106 pf_ppn = ppn - 1; 107 pf_block = block + (pageBytes/blkSize); | 106 stride_t num_cross_pages = 1 + (-block) / (pageBytes/blkSize); 107 if (num_cross_pages > ppn) { 108 // target address smaller than page 0, ignore this request; 109 return; 110 } 111 pf_ppn = ppn - num_cross_pages; 112 pf_block = block + (pageBytes/blkSize) * num_cross_pages; 113 handlePageCrossingLookahead(signature, last_block, delta, 114 path_confidence); |
108 } else if (block >= (pageBytes/blkSize)) { | 115 } else if (block >= (pageBytes/blkSize)) { |
109 pf_ppn = ppn + 1; 110 pf_block = block - (pageBytes/blkSize); | 116 stride_t num_cross_pages = block / (pageBytes/blkSize); 117 if (MaxAddr/pageBytes < (ppn + num_cross_pages)) { 118 // target address goes beyond MaxAddr, ignore this request; 119 return; 120 } 121 pf_ppn = ppn + num_cross_pages; 122 pf_block = block - (pageBytes/blkSize) * num_cross_pages; 123 handlePageCrossingLookahead(signature, last_block, delta, 124 path_confidence); |
111 } else { 112 pf_ppn = ppn; 113 pf_block = block; 114 } 115 116 Addr new_addr = pf_ppn * pageBytes; 117 new_addr += pf_block * (Addr)blkSize; 118 119 DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr); 120 addresses.push_back(AddrPriority(new_addr, 0)); 121} 122 123void | 125 } else { 126 pf_ppn = ppn; 127 pf_block = block; 128 } 129 130 Addr new_addr = pf_ppn * pageBytes; 131 new_addr += pf_block * (Addr)blkSize; 132 133 DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr); 134 addresses.push_back(AddrPriority(new_addr, 0)); 135} 136 137void |
138SignaturePathPrefetcher::handleSignatureTableMiss(stride_t current_block, 139 signature_t &new_signature, double &new_conf, stride_t &new_stride) 140{ 141 new_signature = current_block; 142 new_conf = 1.0; 143 new_stride = current_block; 144} 145 146void 147SignaturePathPrefetcher::increasePatternEntryCounter( 148 PatternEntry &pattern_entry, PatternStrideEntry &pstride_entry) 149{ 150 if (pstride_entry.counter < maxCounterValue) { 151 pstride_entry.counter += 1; 152 } 153} 154 155void |
|
124SignaturePathPrefetcher::updatePatternTable(Addr signature, stride_t stride) 125{ 126 assert(stride != 0); 127 // The pattern table is indexed by signatures 128 PatternEntry &p_entry = getPatternEntry(signature); 129 PatternStrideEntry &ps_entry = p_entry.getStrideEntry(stride, 130 maxCounterValue); | 156SignaturePathPrefetcher::updatePatternTable(Addr signature, stride_t stride) 157{ 158 assert(stride != 0); 159 // The pattern table is indexed by signatures 160 PatternEntry &p_entry = getPatternEntry(signature); 161 PatternStrideEntry &ps_entry = p_entry.getStrideEntry(stride, 162 maxCounterValue); |
131 if (ps_entry.counter < maxCounterValue) { 132 ps_entry.counter += 1; 133 } | 163 increasePatternEntryCounter(p_entry, ps_entry); |
134} 135 136SignaturePathPrefetcher::SignatureEntry & 137SignaturePathPrefetcher::getSignatureEntry(Addr ppn, bool is_secure, | 164} 165 166SignaturePathPrefetcher::SignatureEntry & 167SignaturePathPrefetcher::getSignatureEntry(Addr ppn, bool is_secure, |
138 stride_t block, bool &miss) | 168 stride_t block, bool &miss, stride_t &stride, 169 double &initial_confidence) |
139{ 140 SignatureEntry* signature_entry = signatureTable.findEntry(ppn, is_secure); 141 if (signature_entry != nullptr) { 142 signatureTable.accessEntry(signature_entry); 143 miss = false; | 170{ 171 SignatureEntry* signature_entry = signatureTable.findEntry(ppn, is_secure); 172 if (signature_entry != nullptr) { 173 signatureTable.accessEntry(signature_entry); 174 miss = false; |
175 stride = block - signature_entry->lastBlock; |
|
144 } else { 145 signature_entry = signatureTable.findVictim(ppn); 146 assert(signature_entry != nullptr); 147 | 176 } else { 177 signature_entry = signatureTable.findVictim(ppn); 178 assert(signature_entry != nullptr); 179 |
180 // Sets signature_entry->signature, initial_confidence, and stride 181 handleSignatureTableMiss(block, signature_entry->signature, 182 initial_confidence, stride); 183 |
|
148 signatureTable.insertEntry(ppn, is_secure, signature_entry); | 184 signatureTable.insertEntry(ppn, is_secure, signature_entry); |
149 signature_entry->signature = block; 150 signature_entry->lastBlock = block; | |
151 miss = true; 152 } | 185 miss = true; 186 } |
187 signature_entry->lastBlock = block; |
|
153 return *signature_entry; 154} 155 156SignaturePathPrefetcher::PatternEntry & 157SignaturePathPrefetcher::getPatternEntry(Addr signature) 158{ 159 PatternEntry* pattern_entry = patternTable.findEntry(signature, false); 160 if (pattern_entry != nullptr) { --- 4 unchanged lines hidden (view full) --- 165 pattern_entry = patternTable.findVictim(signature); 166 assert(pattern_entry != nullptr); 167 168 patternTable.insertEntry(signature, false, pattern_entry); 169 } 170 return *pattern_entry; 171} 172 | 188 return *signature_entry; 189} 190 191SignaturePathPrefetcher::PatternEntry & 192SignaturePathPrefetcher::getPatternEntry(Addr signature) 193{ 194 PatternEntry* pattern_entry = patternTable.findEntry(signature, false); 195 if (pattern_entry != nullptr) { --- 4 unchanged lines hidden (view full) --- 200 pattern_entry = patternTable.findVictim(signature); 201 assert(pattern_entry != nullptr); 202 203 patternTable.insertEntry(signature, false, pattern_entry); 204 } 205 return *pattern_entry; 206} 207 |
208double 209SignaturePathPrefetcher::calculatePrefetchConfidence(PatternEntry const &sig, 210 PatternStrideEntry const &entry) const 211{ 212 return ((double) entry.counter) / maxCounterValue; 213} 214 215double 216SignaturePathPrefetcher::calculateLookaheadConfidence(PatternEntry const &sig, 217 PatternStrideEntry const &lookahead) const 218{ 219 double lookahead_confidence; 220 if (lookahead.counter == maxCounterValue) { 221 /** 222 * maximum confidence is 0.95, guaranteeing that 223 * current confidence will eventually fall beyond 224 * the threshold 225 */ 226 lookahead_confidence = 0.95; 227 } else { 228 lookahead_confidence = ((double) lookahead.counter / maxCounterValue); 229 } 230 return lookahead_confidence; 231} 232 |
|
173void 174SignaturePathPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 175 std::vector<AddrPriority> &addresses) 176{ 177 Addr request_addr = pfi.getAddr(); 178 Addr ppn = request_addr / pageBytes; 179 stride_t current_block = (request_addr % pageBytes) / blkSize; 180 stride_t stride; 181 bool is_secure = pfi.isSecure(); | 233void 234SignaturePathPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 235 std::vector<AddrPriority> &addresses) 236{ 237 Addr request_addr = pfi.getAddr(); 238 Addr ppn = request_addr / pageBytes; 239 stride_t current_block = (request_addr % pageBytes) / blkSize; 240 stride_t stride; 241 bool is_secure = pfi.isSecure(); |
242 double initial_confidence = 1.0; |
|
182 183 // Get the SignatureEntry of this page to: 184 // - compute the current stride 185 // - obtain the current signature of accesses 186 bool miss; 187 SignatureEntry &signature_entry = getSignatureEntry(ppn, is_secure, | 243 244 // Get the SignatureEntry of this page to: 245 // - compute the current stride 246 // - obtain the current signature of accesses 247 bool miss; 248 SignatureEntry &signature_entry = getSignatureEntry(ppn, is_secure, |
188 current_block, miss); | 249 current_block, miss, stride, initial_confidence); 250 |
189 if (miss) { 190 // No history for this page, can't continue 191 return; 192 } 193 | 251 if (miss) { 252 // No history for this page, can't continue 253 return; 254 } 255 |
194 stride = current_block - signature_entry.lastBlock; | |
195 if (stride == 0) { 196 // Can't continue with a stride 0 197 return; 198 } 199 200 // Update the confidence of the current signature 201 updatePatternTable(signature_entry.signature, stride); 202 | 256 if (stride == 0) { 257 // Can't continue with a stride 0 258 return; 259 } 260 261 // Update the confidence of the current signature 262 updatePatternTable(signature_entry.signature, stride); 263 |
203 // Update the current SignatureEntry signature and lastBlock | 264 // Update the current SignatureEntry signature |
204 signature_entry.signature = 205 updateSignature(signature_entry.signature, stride); | 265 signature_entry.signature = 266 updateSignature(signature_entry.signature, stride); |
206 signature_entry.lastBlock = current_block; | |
207 208 signature_t current_signature = signature_entry.signature; | 267 268 signature_t current_signature = signature_entry.signature; |
209 double current_confidence = 1.0; | 269 double current_confidence = initial_confidence; |
210 stride_t current_stride = signature_entry.lastBlock; 211 | 270 stride_t current_stride = signature_entry.lastBlock; 271 |
212 do { | 272 // Look for prefetch candidates while the current path confidence is 273 // high enough 274 while (current_confidence > lookaheadConfidenceThreshold) { |
213 // With the updated signature, attempt to generate prefetches 214 // - search the PatternTable and select all entries with enough 215 // confidence, these are prefetch candidates 216 // - select the entry with the highest counter as the "lookahead" 217 PatternEntry *current_pattern_entry = 218 patternTable.findEntry(current_signature, false); 219 PatternStrideEntry const *lookahead = nullptr; 220 if (current_pattern_entry != nullptr) { 221 uint8_t max_counter = 0; 222 for (auto const &entry : current_pattern_entry->strideEntries) { 223 //select the entry with the maximum counter value as lookahead 224 if (max_counter < entry.counter) { 225 max_counter = entry.counter; 226 lookahead = &entry; 227 } 228 double prefetch_confidence = | 275 // With the updated signature, attempt to generate prefetches 276 // - search the PatternTable and select all entries with enough 277 // confidence, these are prefetch candidates 278 // - select the entry with the highest counter as the "lookahead" 279 PatternEntry *current_pattern_entry = 280 patternTable.findEntry(current_signature, false); 281 PatternStrideEntry const *lookahead = nullptr; 282 if (current_pattern_entry != nullptr) { 283 uint8_t max_counter = 0; 284 for (auto const &entry : current_pattern_entry->strideEntries) { 285 //select the entry with the maximum counter value as lookahead 286 if (max_counter < entry.counter) { 287 max_counter = entry.counter; 288 lookahead = &entry; 289 } 290 double prefetch_confidence = |
229 (double) entry.counter / maxCounterValue; | 291 calculatePrefetchConfidence(*current_pattern_entry, entry); |
230 231 if (prefetch_confidence >= prefetchConfidenceThreshold) { 232 assert(entry.stride != 0); 233 //prefetch candidate | 292 293 if (prefetch_confidence >= prefetchConfidenceThreshold) { 294 assert(entry.stride != 0); 295 //prefetch candidate |
234 addPrefetch(ppn, current_stride + entry.stride, 235 is_secure, addresses); | 296 addPrefetch(ppn, current_stride, entry.stride, 297 current_confidence, current_signature, 298 is_secure, addresses); |
236 } 237 } 238 } | 299 } 300 } 301 } |
302 |
|
239 if (lookahead != nullptr) { | 303 if (lookahead != nullptr) { |
240 // If a lookahead was selected, compute its confidence using 241 // the counter of its entry and the accumulated confidence 242 // if the confidence is high enough, generate a new signature 243 double lookahead_confidence; 244 if (lookahead->counter == maxCounterValue) { 245 // maximum confidence is 0.95, guaranteeing that 246 // current confidence will eventually fall beyond 247 // the threshold 248 lookahead_confidence = 0.95; 249 } else { 250 lookahead_confidence = 251 ((double) lookahead->counter / maxCounterValue); 252 } 253 current_confidence *= lookahead_confidence; | 304 current_confidence *= calculateLookaheadConfidence( 305 *current_pattern_entry, *lookahead); |
254 current_signature = 255 updateSignature(current_signature, lookahead->stride); 256 current_stride += lookahead->stride; 257 } else { 258 current_confidence = 0.0; 259 } | 306 current_signature = 307 updateSignature(current_signature, lookahead->stride); 308 current_stride += lookahead->stride; 309 } else { 310 current_confidence = 0.0; 311 } |
260 // If the accumulated confidence is high enough, keep repeating 261 // this process with the updated signature | |
262 } | 312 } |
263 while (current_confidence > lookaheadConfidenceThreshold); | |
264 | 313 |
314 auxiliaryPrefetcher(ppn, current_block, is_secure, addresses); 315} 316 317void 318SignaturePathPrefetcher::auxiliaryPrefetcher(Addr ppn, stride_t current_block, 319 bool is_secure, std::vector<AddrPriority> &addresses) 320{ |
|
265 if (addresses.empty()) { 266 // Enable the next line prefetcher if no prefetch candidates are found | 321 if (addresses.empty()) { 322 // Enable the next line prefetcher if no prefetch candidates are found |
267 addPrefetch(ppn, current_block + 1, is_secure, addresses); | 323 addPrefetch(ppn, current_block, 1, 0.0 /* unused*/, 0 /* unused */, 324 is_secure, addresses); |
268 } 269} 270 271SignaturePathPrefetcher* 272SignaturePathPrefetcherParams::create() 273{ 274 return new SignaturePathPrefetcher(this); 275} | 325 } 326} 327 328SignaturePathPrefetcher* 329SignaturePathPrefetcherParams::create() 330{ 331 return new SignaturePathPrefetcher(this); 332} |