signature_path.cc (13624:3d8220c2d41d) signature_path.cc (13963:94555f0223ba)
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>
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>
34
35#include "debug/HWPrefetch.hh"
36#include "mem/cache/prefetch/associative_set_impl.hh"
37#include "params/SignaturePathPrefetcher.hh"
38
39SignaturePathPrefetcher::SignaturePathPrefetcher(
40 const SignaturePathPrefetcherParams *p)
41 : QueuedPrefetcher(p),
42 stridesPerPatternEntry(p->strides_per_pattern_entry),
43 signatureShift(p->signature_shift),
44 signatureBits(p->signature_bits),
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),
45 maxCounterValue(p->max_counter_value),
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,
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))
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 &
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 uint8_t max_counter_value)
67SignaturePathPrefetcher::PatternEntry::getStrideEntry(stride_t stride)
69{
70 PatternStrideEntry *pstride_entry = findStride(stride);
71 if (pstride_entry == nullptr) {
72 // Specific replacement algorithm for this table,
73 // pick the entry with the lowest counter value,
74 // then decrease the counter of all entries
75
76 // If all counters have the max value, this will be the pick
77 PatternStrideEntry *victim_pstride_entry = &(strideEntries[0]);
78
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
79 uint8_t current_counter = max_counter_value;
78 unsigned long current_counter = ULONG_MAX;
80 for (auto &entry : strideEntries) {
81 if (entry.counter < current_counter) {
82 victim_pstride_entry = &entry;
83 current_counter = entry.counter;
84 }
79 for (auto &entry : strideEntries) {
80 if (entry.counter < current_counter) {
81 victim_pstride_entry = &entry;
82 current_counter = entry.counter;
83 }
85 if (entry.counter > 0) {
86 entry.counter -= 1;
87 }
84 entry.counter--;
88 }
89 pstride_entry = victim_pstride_entry;
85 }
86 pstride_entry = victim_pstride_entry;
90 pstride_entry->counter = 0;
87 pstride_entry->counter.reset();
91 pstride_entry->stride = stride;
92 }
93 return *pstride_entry;
94}
95
96void
97SignaturePathPrefetcher::addPrefetch(Addr ppn, stride_t last_block,
98 stride_t delta, double path_confidence, signature_t signature,

--- 43 unchanged lines hidden (view full) ---

142 new_conf = 1.0;
143 new_stride = current_block;
144}
145
146void
147SignaturePathPrefetcher::increasePatternEntryCounter(
148 PatternEntry &pattern_entry, PatternStrideEntry &pstride_entry)
149{
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{
150 if (pstride_entry.counter < maxCounterValue) {
151 pstride_entry.counter += 1;
152 }
147 pstride_entry.counter++;
153}
154
155void
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);
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);
161 PatternStrideEntry &ps_entry = p_entry.getStrideEntry(stride,
162 maxCounterValue);
156 PatternStrideEntry &ps_entry = p_entry.getStrideEntry(stride);
163 increasePatternEntryCounter(p_entry, ps_entry);
164}
165
166SignaturePathPrefetcher::SignatureEntry &
167SignaturePathPrefetcher::getSignatureEntry(Addr ppn, bool is_secure,
168 stride_t block, bool &miss, stride_t &stride,
169 double &initial_confidence)
170{

--- 33 unchanged lines hidden (view full) ---

204 }
205 return *pattern_entry;
206}
207
208double
209SignaturePathPrefetcher::calculatePrefetchConfidence(PatternEntry const &sig,
210 PatternStrideEntry const &entry) const
211{
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{
212 return ((double) entry.counter) / maxCounterValue;
206 return entry.counter.calcSaturation();
213}
214
215double
216SignaturePathPrefetcher::calculateLookaheadConfidence(PatternEntry const &sig,
217 PatternStrideEntry const &lookahead) const
218{
207}
208
209double
210SignaturePathPrefetcher::calculateLookaheadConfidence(PatternEntry const &sig,
211 PatternStrideEntry const &lookahead) const
212{
219 double lookahead_confidence;
220 if (lookahead.counter == maxCounterValue) {
213 double lookahead_confidence = lookahead.counter.calcSaturation();
214 if (lookahead_confidence > 0.95) {
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;
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;
227 } else {
228 lookahead_confidence = ((double) lookahead.counter / maxCounterValue);
229 }
230 return lookahead_confidence;
231}
232
233void
234SignaturePathPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
235 std::vector<AddrPriority> &addresses)
236{

--- 38 unchanged lines hidden (view full) ---

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) {
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) {
283 uint8_t max_counter = 0;
275 unsigned long 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 =
291 calculatePrefetchConfidence(*current_pattern_entry, entry);

--- 41 unchanged lines hidden --- 		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 ---