2 * Copyright (c) 2018 Metempsy Technology Consulting
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.
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.
30 * Implementation of the Signature Path Prefetcher
33 * Lookahead prefetching with signature path
34 * J Kim, PV Gratz, ALN Reddy
35 * The 2nd Data Prefetching Championship (DPC2)
36 * The filter feature described in the paper is not implemented, as it
37 * redundant prefetches are dropped by the cache.
40 #ifndef __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__
41 #define __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__
43 #include "base/sat_counter.hh"
44 #include "mem/cache/prefetch/associative_set.hh"
45 #include "mem/cache/prefetch/queued.hh"
46 #include "mem/packet.hh"
48 struct SignaturePathPrefetcherParams;
50 namespace Prefetcher {
52 class SignaturePath : public Queued
56 typedef uint16_t signature_t;
58 typedef int16_t stride_t;
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;
66 /** Minimum confidence to issue a prefetch */
67 const double prefetchConfidenceThreshold;
68 /** Minimum confidence to keep navigating lookahead entries */
69 const double lookaheadConfidenceThreshold;
71 /** Signature entry data type */
72 struct SignatureEntry : public TaggedEntry
75 signature_t signature;
76 /** Last accessed block within a page */
78 SignatureEntry() : signature(0), lastBlock(0)
81 /** Signature table */
82 AssociativeSet<SignatureEntry> signatureTable;
84 /** A stride entry with its counter */
85 struct PatternStrideEntry
87 /** stride in a page in blkSize increments */
89 /** Saturating counter */
91 PatternStrideEntry(unsigned bits) : stride(0), counter(bits)
94 /** Pattern entry data type, a set of stride and counter entries */
95 struct PatternEntry : public TaggedEntry
97 /** group of stides */
98 std::vector<PatternStrideEntry> strideEntries;
99 /** use counter, used by SPPv2 */
101 PatternEntry(size_t num_strides, unsigned counter_bits)
102 : TaggedEntry(), strideEntries(num_strides, counter_bits),
103 counter(counter_bits)
107 /** Reset the entries to their initial values */
109 invalidate() override
111 TaggedEntry::invalidate();
112 for (auto &entry : strideEntries) {
113 entry.counter.reset();
120 * Returns the entry with the desired stride
121 * @param stride the stride to find
122 * @result a pointer to the entry, if the stride was found, or nullptr,
123 * if the stride was not found
125 PatternStrideEntry *findStride(stride_t stride)
127 PatternStrideEntry *found_entry = nullptr;
128 for (auto &entry : strideEntries) {
129 if (entry.stride == stride) {
130 found_entry = &entry;
138 * Gets the entry with the provided stride, if there is no entry with
139 * the associated stride, it replaces one of them.
140 * @param stride the stride to find
141 * @result reference to the selected entry
143 PatternStrideEntry &getStrideEntry(stride_t stride);
146 AssociativeSet<PatternEntry> patternTable;
149 * Generates a new signature from an existing one and a new stride
150 * @param sig current signature
151 * @param str stride to add to the new signature
152 * @result the new signature
154 inline signature_t updateSignature(signature_t sig, stride_t str) const {
155 sig <<= signatureShift;
157 sig &= mask(signatureBits);
162 * Generates an address to be prefetched.
163 * @param ppn page number to prefetch from
164 * @param last_block last accessed block within the page ppn
165 * @param delta difference, in number of blocks, from the last_block
166 * accessed to the block to prefetch. The block to prefetch is
167 * computed by this formula:
168 * ppn * pageBytes + (last_block + delta) * blkSize
169 * This value can be negative.
170 * @param path_confidence the confidence factor of this prefetch
171 * @param signature the current path signature
172 * @param is_secure whether this page is inside the secure memory area
173 * @param addresses addresses to prefetch will be added to this vector
175 void addPrefetch(Addr ppn, stride_t last_block, stride_t delta,
176 double path_confidence, signature_t signature,
178 std::vector<AddrPriority> &addresses);
181 * Obtains the SignatureEntry of the given page, if the page is not found,
182 * it allocates a new one, replacing an existing entry if needed
183 * It also provides the stride of the current block and the initial
184 * path confidence of the corresponding entry
185 * @param ppn physical page number of the page
186 * @param is_secure whether this page is inside the secure memory area
187 * @param block accessed block within the page
188 * @param miss if the entry is not found, this will be set to true
189 * @param stride set to the computed stride
190 * @param initial_confidence set to the initial confidence value
191 * @result a reference to the SignatureEntry
193 SignatureEntry &getSignatureEntry(Addr ppn, bool is_secure, stride_t block,
194 bool &miss, stride_t &stride, double &initial_confidence);
196 * Obtains the PatternEntry of the given signature, if the signature is
197 * not found, it allocates a new one, replacing an existing entry if needed
198 * @param signature the signature of the desired entry
199 * @result a reference to the PatternEntry
201 PatternEntry& getPatternEntry(Addr signature);
204 * Updates the pattern table with the provided signature and stride
205 * @param signature the signature to use to index the pattern table
206 * @param stride the stride to use to index the set of strides of the
207 * pattern table entry
209 void updatePatternTable(Addr signature, stride_t stride);
212 * Computes the lookahead path confidence of the provided pattern entry
213 * @param sig the PatternEntry to use
214 * @param lookahead PatternStrideEntry within the provided PatternEntry
215 * @return the computed confidence factor
217 virtual double calculateLookaheadConfidence(PatternEntry const &sig,
218 PatternStrideEntry const &lookahead) const;
221 * Computes the prefetch confidence of the provided pattern entry
222 * @param sig the PatternEntry to use
223 * @param entry PatternStrideEntry within the provided PatternEntry
224 * @return the computed confidence factor
226 virtual double calculatePrefetchConfidence(PatternEntry const &sig,
227 PatternStrideEntry const &entry) const;
230 * Increases the counter of a given PatternEntry/PatternStrideEntry
231 * @param pattern_entry the corresponding PatternEntry
232 * @param pstride_entry the PatternStrideEntry within the PatternEntry
234 virtual void increasePatternEntryCounter(PatternEntry &pattern_entry,
235 PatternStrideEntry &pstride_entry);
238 * Whenever a new SignatureEntry is allocated, it computes the new
239 * signature to be used with the new entry, the resulting stride and the
240 * initial path confidence of the new entry.
241 * @param current_block accessed block within the page of the associated
243 * @param new_signature new signature of the allocated entry
244 * @param new_conf the initial path confidence of this entry
245 * @param new_stride the resulting current stride
247 virtual void handleSignatureTableMiss(stride_t current_block,
248 signature_t &new_signature, double &new_conf,
249 stride_t &new_stride);
252 * Auxiliar prefetch mechanism used at the end of calculatePrefetch.
253 * This prefetcher uses this to activate the next line prefetcher if
254 * no prefetch candidates have been found.
255 * @param ppn physical page number of the current accessed page
256 * @param current_block last accessed block within the page ppn
257 * @param is_secure whether this page is inside the secure memory area
258 * @param addresses the addresses to be prefetched are added to this vector
259 * @param updated_filter_entries set of addresses containing these that
260 * their filter has been updated, if this call updates a new entry
262 virtual void auxiliaryPrefetcher(Addr ppn, stride_t current_block,
263 bool is_secure, std::vector<AddrPriority> &addresses);
266 * Handles the situation when the lookahead process has crossed the
267 * boundaries of the current page. This is not fully described in the
268 * paper that was used to implement this code, however, the article
269 * describing the upgraded version of this prefetcher provides some
270 * details. For this prefetcher, there are no specific actions to be
272 * @param signature the lookahead signature that crossed the page
273 * @param delta the current stride that caused it
274 * @param last_offset the last accessed block within the page
275 * @param path_confidence the path confidence at the moment of crossing
277 virtual void handlePageCrossingLookahead(signature_t signature,
278 stride_t last_offset, stride_t delta, double path_confidence) {
282 SignaturePath(const SignaturePathPrefetcherParams &p);
283 ~SignaturePath() = default;
285 void calculatePrefetch(const PrefetchInfo &pfi,
286 std::vector<AddrPriority> &addresses) override;
289 } // namespace Prefetcher
291 #endif//__MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__