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"
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;
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;
89        /** Saturating counter */
90        SatCounter counter;
91        PatternStrideEntry(unsigned bits) : stride(0), counter(bits)
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 */
100        SatCounter counter;
101        PatternEntry(size_t num_strides, unsigned counter_bits)
102            : strideEntries(num_strides, counter_bits), counter(counter_bits)
103        {}
104
105        /** Reset the entries to their initial values */
106        void reset() override
107        {
108            for (auto &entry : strideEntries) {
109                entry.counter.reset();
110                entry.stride = 0;
111            }
112            counter.reset();
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
137         * @result reference to the selected entry
138         */
139        PatternStrideEntry &getStrideEntry(stride_t stride);
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__
285