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; --- 17 unchanged lines hidden (view full) --- 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * Authors: Javier Bueno 29 */ 30 31#include "mem/cache/prefetch/signature_path.hh" 32 33#include <cassert> |
34#include <climits> |
35 36#include "debug/HWPrefetch.hh" 37#include "mem/cache/prefetch/associative_set_impl.hh" 38#include "params/SignaturePathPrefetcher.hh" 39 40SignaturePathPrefetcher::SignaturePathPrefetcher( 41 const SignaturePathPrefetcherParams *p) 42 : QueuedPrefetcher(p), 43 stridesPerPatternEntry(p->strides_per_pattern_entry), 44 signatureShift(p->signature_shift), 45 signatureBits(p->signature_bits), |
46 prefetchConfidenceThreshold(p->prefetch_confidence_threshold), 47 lookaheadConfidenceThreshold(p->lookahead_confidence_threshold), 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, p->num_counter_bits)) |
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"); 64} 65 66SignaturePathPrefetcher::PatternStrideEntry & |
67SignaturePathPrefetcher::PatternEntry::getStrideEntry(stride_t stride) |
68{ 69 PatternStrideEntry *pstride_entry = findStride(stride); 70 if (pstride_entry == nullptr) { 71 // Specific replacement algorithm for this table, 72 // pick the entry with the lowest counter value, 73 // then decrease the counter of all entries 74 75 // If all counters have the max value, this will be the pick 76 PatternStrideEntry *victim_pstride_entry = &(strideEntries[0]); 77 |
78 unsigned long current_counter = ULONG_MAX; |
79 for (auto &entry : strideEntries) { 80 if (entry.counter < current_counter) { 81 victim_pstride_entry = &entry; 82 current_counter = entry.counter; 83 } |
84 entry.counter--; |
85 } 86 pstride_entry = victim_pstride_entry; |
87 pstride_entry->counter.reset(); |
88 pstride_entry->stride = stride; 89 } 90 return *pstride_entry; 91} 92 93void 94SignaturePathPrefetcher::addPrefetch(Addr ppn, stride_t last_block, 95 stride_t delta, double path_confidence, signature_t signature, --- 43 unchanged lines hidden (view full) --- 139 new_conf = 1.0; 140 new_stride = current_block; 141} 142 143void 144SignaturePathPrefetcher::increasePatternEntryCounter( 145 PatternEntry &pattern_entry, PatternStrideEntry &pstride_entry) 146{ |
147 pstride_entry.counter++; |
148} 149 150void 151SignaturePathPrefetcher::updatePatternTable(Addr signature, stride_t stride) 152{ 153 assert(stride != 0); 154 // The pattern table is indexed by signatures 155 PatternEntry &p_entry = getPatternEntry(signature); |
156 PatternStrideEntry &ps_entry = p_entry.getStrideEntry(stride); |
157 increasePatternEntryCounter(p_entry, ps_entry); 158} 159 160SignaturePathPrefetcher::SignatureEntry & 161SignaturePathPrefetcher::getSignatureEntry(Addr ppn, bool is_secure, 162 stride_t block, bool &miss, stride_t &stride, 163 double &initial_confidence) 164{ --- 33 unchanged lines hidden (view full) --- 198 } 199 return *pattern_entry; 200} 201 202double 203SignaturePathPrefetcher::calculatePrefetchConfidence(PatternEntry const &sig, 204 PatternStrideEntry const &entry) const 205{ |
206 return entry.counter.calcSaturation(); |
207} 208 209double 210SignaturePathPrefetcher::calculateLookaheadConfidence(PatternEntry const &sig, 211 PatternStrideEntry const &lookahead) const 212{ |
213 double lookahead_confidence = lookahead.counter.calcSaturation(); 214 if (lookahead_confidence > 0.95) { |
215 /** 216 * maximum confidence is 0.95, guaranteeing that 217 * current confidence will eventually fall beyond 218 * the threshold 219 */ 220 lookahead_confidence = 0.95; |
221 } 222 return lookahead_confidence; 223} 224 225void 226SignaturePathPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 227 std::vector<AddrPriority> &addresses) 228{ --- 38 unchanged lines hidden (view full) --- 267 // With the updated signature, attempt to generate prefetches 268 // - search the PatternTable and select all entries with enough 269 // confidence, these are prefetch candidates 270 // - select the entry with the highest counter as the "lookahead" 271 PatternEntry *current_pattern_entry = 272 patternTable.findEntry(current_signature, false); 273 PatternStrideEntry const *lookahead = nullptr; 274 if (current_pattern_entry != nullptr) { |
275 unsigned long max_counter = 0; |
276 for (auto const &entry : current_pattern_entry->strideEntries) { 277 //select the entry with the maximum counter value as lookahead 278 if (max_counter < entry.counter) { 279 max_counter = entry.counter; 280 lookahead = &entry; 281 } 282 double prefetch_confidence = 283 calculatePrefetchConfidence(*current_pattern_entry, entry); --- 41 unchanged lines hidden --- |