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;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 * Authors: Javier Bueno
29 */
30
31 /**
32 * Implementation of the Signature Path Prefetcher
33 *
34 * References:
35 * Lookahead prefetching with signature path
36 * J Kim, PV Gratz, ALN Reddy
37 * The 2nd Data Prefetching Championship (DPC2)
38 * The filter feature described in the paper is not implemented, as it
39 * redundant prefetches are dropped by the cache.
40 */
41
42#ifndef __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__
43#define __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__
44
| 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;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 * Authors: Javier Bueno
29 */
30
31 /**
32 * Implementation of the Signature Path Prefetcher
33 *
34 * References:
35 * Lookahead prefetching with signature path
36 * J Kim, PV Gratz, ALN Reddy
37 * The 2nd Data Prefetching Championship (DPC2)
38 * The filter feature described in the paper is not implemented, as it
39 * redundant prefetches are dropped by the cache.
40 */
41
42#ifndef __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__
43#define __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__
44
|
| 45#include "base/sat_counter.hh"
|
45#include "mem/cache/prefetch/associative_set.hh"
46#include "mem/cache/prefetch/queued.hh"
47#include "mem/packet.hh"
48
49struct SignaturePathPrefetcherParams;
50
51class SignaturePathPrefetcher : public QueuedPrefetcher
52{
53 protected:
54 /** Signature type */
55 typedef uint16_t signature_t;
56 /** Stride type */
57 typedef int16_t stride_t;
58
59 /** Number of strides stored in each pattern entry */
60 const unsigned stridesPerPatternEntry;
61 /** Number of bits to shift when generating a new signature */
62 const uint8_t signatureShift;
63 /** Size of the signature, in bits */
64 const signature_t signatureBits;
| 46#include "mem/cache/prefetch/associative_set.hh"
47#include "mem/cache/prefetch/queued.hh"
48#include "mem/packet.hh"
49
50struct SignaturePathPrefetcherParams;
51
52class SignaturePathPrefetcher : public QueuedPrefetcher
53{
54 protected:
55 /** Signature type */
56 typedef uint16_t signature_t;
57 /** Stride type */
58 typedef int16_t stride_t;
59
60 /** Number of strides stored in each pattern entry */
61 const unsigned stridesPerPatternEntry;
62 /** Number of bits to shift when generating a new signature */
63 const uint8_t signatureShift;
64 /** Size of the signature, in bits */
65 const signature_t signatureBits;
|
65 /** Maximum pattern entries counter value */
66 const uint8_t maxCounterValue;
| |
67 /** Minimum confidence to issue a prefetch */
68 const double prefetchConfidenceThreshold;
69 /** Minimum confidence to keep navigating lookahead entries */
70 const double lookaheadConfidenceThreshold;
71
72 /** Signature entry data type */
73 struct SignatureEntry : public TaggedEntry
74 {
75 /** Path signature */
76 signature_t signature;
77 /** Last accessed block within a page */
78 stride_t lastBlock;
79 SignatureEntry() : signature(0), lastBlock(0)
80 {}
81 };
82 /** Signature table */
83 AssociativeSet<SignatureEntry> signatureTable;
84
85 /** A stride entry with its counter */
86 struct PatternStrideEntry
87 {
88 /** stride in a page in blkSize increments */
89 stride_t stride;
| 66 /** Minimum confidence to issue a prefetch */
67 const double prefetchConfidenceThreshold;
68 /** Minimum confidence to keep navigating lookahead entries */
69 const double lookaheadConfidenceThreshold;
70
71 /** Signature entry data type */
72 struct SignatureEntry : public TaggedEntry
73 {
74 /** Path signature */
75 signature_t signature;
76 /** Last accessed block within a page */
77 stride_t lastBlock;
78 SignatureEntry() : signature(0), lastBlock(0)
79 {}
80 };
81 /** Signature table */
82 AssociativeSet<SignatureEntry> signatureTable;
83
84 /** A stride entry with its counter */
85 struct PatternStrideEntry
86 {
87 /** stride in a page in blkSize increments */
88 stride_t stride;
|
90 /** counter value (max value defined by maxCounterValue) */
91 uint8_t counter;
92 PatternStrideEntry() : stride(0), counter(0)
| 89 /** Saturating counter */
90 SatCounter counter;
91 PatternStrideEntry(unsigned bits) : stride(0), counter(bits)
|
93 {}
94 };
95 /** Pattern entry data type, a set of stride and counter entries */
96 struct PatternEntry : public TaggedEntry
97 {
98 /** group of stides */
99 std::vector<PatternStrideEntry> strideEntries;
100 /** use counter, used by SPPv2 */
| 92 {}
93 };
94 /** Pattern entry data type, a set of stride and counter entries */
95 struct PatternEntry : public TaggedEntry
96 {
97 /** group of stides */
98 std::vector<PatternStrideEntry> strideEntries;
99 /** use counter, used by SPPv2 */
|
101 uint8_t counter;
102 PatternEntry(size_t num_strides) : strideEntries(num_strides),
103 counter(0)
| 100 SatCounter counter;
101 PatternEntry(size_t num_strides, unsigned counter_bits)
102 : strideEntries(num_strides, counter_bits), counter(counter_bits)
|
104 {}
105
106 /** Reset the entries to their initial values */
107 void reset() override
108 {
109 for (auto &entry : strideEntries) {
| 103 {}
104
105 /** Reset the entries to their initial values */
106 void reset() override
107 {
108 for (auto &entry : strideEntries) {
|
110 entry.counter = 0;
| 109 entry.counter.reset();
|
111 entry.stride = 0;
112 }
| 110 entry.stride = 0;
111 }
|
113 counter = 0;
| 112 counter.reset();
|
114 }
115
116 /**
117 * Returns the entry with the desired stride
118 * @param stride the stride to find
119 * @result a pointer to the entry, if the stride was found, or nullptr,
120 * if the stride was not found
121 */
122 PatternStrideEntry *findStride(stride_t stride)
123 {
124 PatternStrideEntry *found_entry = nullptr;
125 for (auto &entry : strideEntries) {
126 if (entry.stride == stride) {
127 found_entry = &entry;
128 break;
129 }
130 }
131 return found_entry;
132 }
133
134 /**
135 * Gets the entry with the provided stride, if there is no entry with
136 * the associated stride, it replaces one of them.
137 * @param stride the stride to find
| 113 }
114
115 /**
116 * Returns the entry with the desired stride
117 * @param stride the stride to find
118 * @result a pointer to the entry, if the stride was found, or nullptr,
119 * if the stride was not found
120 */
121 PatternStrideEntry *findStride(stride_t stride)
122 {
123 PatternStrideEntry *found_entry = nullptr;
124 for (auto &entry : strideEntries) {
125 if (entry.stride == stride) {
126 found_entry = &entry;
127 break;
128 }
129 }
130 return found_entry;
131 }
132
133 /**
134 * Gets the entry with the provided stride, if there is no entry with
135 * the associated stride, it replaces one of them.
136 * @param stride the stride to find
|
138 * @param max_counter_value maximum value of the confidence counters,
139 * it is used when no strides are found and an entry needs to be
140 * replaced
| |
141 * @result reference to the selected entry
142 */
| 137 * @result reference to the selected entry
138 */
|
143 PatternStrideEntry &getStrideEntry(stride_t stride,
144 uint8_t max_counter_value);
| 139 PatternStrideEntry &getStrideEntry(stride_t stride);
|
145 };
146 /** Pattern table */
147 AssociativeSet<PatternEntry> patternTable;
148
149 /**
150 * Generates a new signature from an existing one and a new stride
151 * @param sig current signature
152 * @param str stride to add to the new signature
153 * @result the new signature
154 */
155 inline signature_t updateSignature(signature_t sig, stride_t str) const {
156 sig <<= signatureShift;
157 sig ^= str;
158 sig &= mask(signatureBits);
159 return sig;
160 }
161
162 /**
163 * Generates an address to be prefetched.
164 * @param ppn page number to prefetch from
165 * @param last_block last accessed block within the page ppn
166 * @param delta difference, in number of blocks, from the last_block
167 * accessed to the block to prefetch. The block to prefetch is
168 * computed by this formula:
169 * ppn * pageBytes + (last_block + delta) * blkSize
170 * This value can be negative.
171 * @param path_confidence the confidence factor of this prefetch
172 * @param signature the current path signature
173 * @param is_secure whether this page is inside the secure memory area
174 * @param addresses addresses to prefetch will be added to this vector
175 */
176 void addPrefetch(Addr ppn, stride_t last_block, stride_t delta,
177 double path_confidence, signature_t signature,
178 bool is_secure,
179 std::vector<AddrPriority> &addresses);
180
181 /**
182 * Obtains the SignatureEntry of the given page, if the page is not found,
183 * it allocates a new one, replacing an existing entry if needed
184 * It also provides the stride of the current block and the initial
185 * path confidence of the corresponding entry
186 * @param ppn physical page number of the page
187 * @param is_secure whether this page is inside the secure memory area
188 * @param block accessed block within the page
189 * @param miss if the entry is not found, this will be set to true
190 * @param stride set to the computed stride
191 * @param initial_confidence set to the initial confidence value
192 * @result a reference to the SignatureEntry
193 */
194 SignatureEntry &getSignatureEntry(Addr ppn, bool is_secure, stride_t block,
195 bool &miss, stride_t &stride, double &initial_confidence);
196 /**
197 * Obtains the PatternEntry of the given signature, if the signature is
198 * not found, it allocates a new one, replacing an existing entry if needed
199 * @param signature the signature of the desired entry
200 * @result a reference to the PatternEntry
201 */
202 PatternEntry& getPatternEntry(Addr signature);
203
204 /**
205 * Updates the pattern table with the provided signature and stride
206 * @param signature the signature to use to index the pattern table
207 * @param stride the stride to use to index the set of strides of the
208 * pattern table entry
209 */
210 void updatePatternTable(Addr signature, stride_t stride);
211
212 /**
213 * Computes the lookahead path confidence of the provided pattern entry
214 * @param sig the PatternEntry to use
215 * @param lookahead PatternStrideEntry within the provided PatternEntry
216 * @return the computed confidence factor
217 */
218 virtual double calculateLookaheadConfidence(PatternEntry const &sig,
219 PatternStrideEntry const &lookahead) const;
220
221 /**
222 * Computes the prefetch confidence of the provided pattern entry
223 * @param sig the PatternEntry to use
224 * @param entry PatternStrideEntry within the provided PatternEntry
225 * @return the computed confidence factor
226 */
227 virtual double calculatePrefetchConfidence(PatternEntry const &sig,
228 PatternStrideEntry const &entry) const;
229
230 /**
231 * Increases the counter of a given PatternEntry/PatternStrideEntry
232 * @param pattern_entry the corresponding PatternEntry
233 * @param pstride_entry the PatternStrideEntry within the PatternEntry
234 */
235 virtual void increasePatternEntryCounter(PatternEntry &pattern_entry,
236 PatternStrideEntry &pstride_entry);
237
238 /**
239 * Whenever a new SignatureEntry is allocated, it computes the new
240 * signature to be used with the new entry, the resulting stride and the
241 * initial path confidence of the new entry.
242 * @param current_block accessed block within the page of the associated
243 entry
244 * @param new_signature new signature of the allocated entry
245 * @param new_conf the initial path confidence of this entry
246 * @param new_stride the resulting current stride
247 */
248 virtual void handleSignatureTableMiss(stride_t current_block,
249 signature_t &new_signature, double &new_conf,
250 stride_t &new_stride);
251
252 /**
253 * Auxiliar prefetch mechanism used at the end of calculatePrefetch.
254 * This prefetcher uses this to activate the next line prefetcher if
255 * no prefetch candidates have been found.
256 * @param ppn physical page number of the current accessed page
257 * @param current_block last accessed block within the page ppn
258 * @param is_secure whether this page is inside the secure memory area
259 * @param addresses the addresses to be prefetched are added to this vector
260 * @param updated_filter_entries set of addresses containing these that
261 * their filter has been updated, if this call updates a new entry
262 */
263 virtual void auxiliaryPrefetcher(Addr ppn, stride_t current_block,
264 bool is_secure, std::vector<AddrPriority> &addresses);
265
266 /**
267 * Handles the situation when the lookahead process has crossed the
268 * boundaries of the current page. This is not fully described in the
269 * paper that was used to implement this code, however, the article
270 * describing the upgraded version of this prefetcher provides some
271 * details. For this prefetcher, there are no specific actions to be
272 * done.
273 * @param signature the lookahead signature that crossed the page
274 * @param delta the current stride that caused it
275 * @param last_offset the last accessed block within the page
276 * @param path_confidence the path confidence at the moment of crossing
277 */
278 virtual void handlePageCrossingLookahead(signature_t signature,
279 stride_t last_offset, stride_t delta, double path_confidence) {
280 }
281
282 public:
283 SignaturePathPrefetcher(const SignaturePathPrefetcherParams* p);
284 ~SignaturePathPrefetcher() {}
285 void calculatePrefetch(const PrefetchInfo &pfi,
286 std::vector<AddrPriority> &addresses) override;
287};
288
289#endif//__MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__
| 140 };
141 /** Pattern table */
142 AssociativeSet<PatternEntry> patternTable;
143
144 /**
145 * Generates a new signature from an existing one and a new stride
146 * @param sig current signature
147 * @param str stride to add to the new signature
148 * @result the new signature
149 */
150 inline signature_t updateSignature(signature_t sig, stride_t str) const {
151 sig <<= signatureShift;
152 sig ^= str;
153 sig &= mask(signatureBits);
154 return sig;
155 }
156
157 /**
158 * Generates an address to be prefetched.
159 * @param ppn page number to prefetch from
160 * @param last_block last accessed block within the page ppn
161 * @param delta difference, in number of blocks, from the last_block
162 * accessed to the block to prefetch. The block to prefetch is
163 * computed by this formula:
164 * ppn * pageBytes + (last_block + delta) * blkSize
165 * This value can be negative.
166 * @param path_confidence the confidence factor of this prefetch
167 * @param signature the current path signature
168 * @param is_secure whether this page is inside the secure memory area
169 * @param addresses addresses to prefetch will be added to this vector
170 */
171 void addPrefetch(Addr ppn, stride_t last_block, stride_t delta,
172 double path_confidence, signature_t signature,
173 bool is_secure,
174 std::vector<AddrPriority> &addresses);
175
176 /**
177 * Obtains the SignatureEntry of the given page, if the page is not found,
178 * it allocates a new one, replacing an existing entry if needed
179 * It also provides the stride of the current block and the initial
180 * path confidence of the corresponding entry
181 * @param ppn physical page number of the page
182 * @param is_secure whether this page is inside the secure memory area
183 * @param block accessed block within the page
184 * @param miss if the entry is not found, this will be set to true
185 * @param stride set to the computed stride
186 * @param initial_confidence set to the initial confidence value
187 * @result a reference to the SignatureEntry
188 */
189 SignatureEntry &getSignatureEntry(Addr ppn, bool is_secure, stride_t block,
190 bool &miss, stride_t &stride, double &initial_confidence);
191 /**
192 * Obtains the PatternEntry of the given signature, if the signature is
193 * not found, it allocates a new one, replacing an existing entry if needed
194 * @param signature the signature of the desired entry
195 * @result a reference to the PatternEntry
196 */
197 PatternEntry& getPatternEntry(Addr signature);
198
199 /**
200 * Updates the pattern table with the provided signature and stride
201 * @param signature the signature to use to index the pattern table
202 * @param stride the stride to use to index the set of strides of the
203 * pattern table entry
204 */
205 void updatePatternTable(Addr signature, stride_t stride);
206
207 /**
208 * Computes the lookahead path confidence of the provided pattern entry
209 * @param sig the PatternEntry to use
210 * @param lookahead PatternStrideEntry within the provided PatternEntry
211 * @return the computed confidence factor
212 */
213 virtual double calculateLookaheadConfidence(PatternEntry const &sig,
214 PatternStrideEntry const &lookahead) const;
215
216 /**
217 * Computes the prefetch confidence of the provided pattern entry
218 * @param sig the PatternEntry to use
219 * @param entry PatternStrideEntry within the provided PatternEntry
220 * @return the computed confidence factor
221 */
222 virtual double calculatePrefetchConfidence(PatternEntry const &sig,
223 PatternStrideEntry const &entry) const;
224
225 /**
226 * Increases the counter of a given PatternEntry/PatternStrideEntry
227 * @param pattern_entry the corresponding PatternEntry
228 * @param pstride_entry the PatternStrideEntry within the PatternEntry
229 */
230 virtual void increasePatternEntryCounter(PatternEntry &pattern_entry,
231 PatternStrideEntry &pstride_entry);
232
233 /**
234 * Whenever a new SignatureEntry is allocated, it computes the new
235 * signature to be used with the new entry, the resulting stride and the
236 * initial path confidence of the new entry.
237 * @param current_block accessed block within the page of the associated
238 entry
239 * @param new_signature new signature of the allocated entry
240 * @param new_conf the initial path confidence of this entry
241 * @param new_stride the resulting current stride
242 */
243 virtual void handleSignatureTableMiss(stride_t current_block,
244 signature_t &new_signature, double &new_conf,
245 stride_t &new_stride);
246
247 /**
248 * Auxiliar prefetch mechanism used at the end of calculatePrefetch.
249 * This prefetcher uses this to activate the next line prefetcher if
250 * no prefetch candidates have been found.
251 * @param ppn physical page number of the current accessed page
252 * @param current_block last accessed block within the page ppn
253 * @param is_secure whether this page is inside the secure memory area
254 * @param addresses the addresses to be prefetched are added to this vector
255 * @param updated_filter_entries set of addresses containing these that
256 * their filter has been updated, if this call updates a new entry
257 */
258 virtual void auxiliaryPrefetcher(Addr ppn, stride_t current_block,
259 bool is_secure, std::vector<AddrPriority> &addresses);
260
261 /**
262 * Handles the situation when the lookahead process has crossed the
263 * boundaries of the current page. This is not fully described in the
264 * paper that was used to implement this code, however, the article
265 * describing the upgraded version of this prefetcher provides some
266 * details. For this prefetcher, there are no specific actions to be
267 * done.
268 * @param signature the lookahead signature that crossed the page
269 * @param delta the current stride that caused it
270 * @param last_offset the last accessed block within the page
271 * @param path_confidence the path confidence at the moment of crossing
272 */
273 virtual void handlePageCrossingLookahead(signature_t signature,
274 stride_t last_offset, stride_t delta, double path_confidence) {
275 }
276
277 public:
278 SignaturePathPrefetcher(const SignaturePathPrefetcherParams* p);
279 ~SignaturePathPrefetcher() {}
280 void calculatePrefetch(const PrefetchInfo &pfi,
281 std::vector<AddrPriority> &addresses) override;
282};
283
284#endif//__MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__
|