113553Sjavier.bueno@metempsy.com/**
213553Sjavier.bueno@metempsy.com * Copyright (c) 2018 Metempsy Technology Consulting
313553Sjavier.bueno@metempsy.com * All rights reserved.
413553Sjavier.bueno@metempsy.com *
513553Sjavier.bueno@metempsy.com * Redistribution and use in source and binary forms, with or without
613553Sjavier.bueno@metempsy.com * modification, are permitted provided that the following conditions are
713553Sjavier.bueno@metempsy.com * met: redistributions of source code must retain the above copyright
813553Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer;
913553Sjavier.bueno@metempsy.com * redistributions in binary form must reproduce the above copyright
1013553Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer in the
1113553Sjavier.bueno@metempsy.com * documentation and/or other materials provided with the distribution;
1213553Sjavier.bueno@metempsy.com * neither the name of the copyright holders nor the names of its
1313553Sjavier.bueno@metempsy.com * contributors may be used to endorse or promote products derived from
1413553Sjavier.bueno@metempsy.com * this software without specific prior written permission.
1513553Sjavier.bueno@metempsy.com *
1613553Sjavier.bueno@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1713553Sjavier.bueno@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1813553Sjavier.bueno@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1913553Sjavier.bueno@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2013553Sjavier.bueno@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2113553Sjavier.bueno@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2213553Sjavier.bueno@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2313553Sjavier.bueno@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2413553Sjavier.bueno@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2513553Sjavier.bueno@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2613553Sjavier.bueno@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2713553Sjavier.bueno@metempsy.com *
2813553Sjavier.bueno@metempsy.com * Authors: Javier Bueno
2913553Sjavier.bueno@metempsy.com */
3013553Sjavier.bueno@metempsy.com
3113553Sjavier.bueno@metempsy.com /**
3213553Sjavier.bueno@metempsy.com  * Implementation of the Signature Path Prefetcher
3313553Sjavier.bueno@metempsy.com  *
3413553Sjavier.bueno@metempsy.com  * References:
3513553Sjavier.bueno@metempsy.com  *     Lookahead prefetching with signature path
3613553Sjavier.bueno@metempsy.com  *     J Kim, PV Gratz, ALN Reddy
3713553Sjavier.bueno@metempsy.com  *     The 2nd Data Prefetching Championship (DPC2)
3813553Sjavier.bueno@metempsy.com  * The filter feature described in the paper is not implemented, as it
3913553Sjavier.bueno@metempsy.com  * redundant prefetches are dropped by the cache.
4013553Sjavier.bueno@metempsy.com  */
4113553Sjavier.bueno@metempsy.com
4213553Sjavier.bueno@metempsy.com#ifndef __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__
4313553Sjavier.bueno@metempsy.com#define __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__
4413553Sjavier.bueno@metempsy.com
4513963Sodanrc@yahoo.com.br#include "base/sat_counter.hh"
4613553Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/associative_set.hh"
4713553Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/queued.hh"
4813553Sjavier.bueno@metempsy.com#include "mem/packet.hh"
4913553Sjavier.bueno@metempsy.com
5013553Sjavier.bueno@metempsy.comstruct SignaturePathPrefetcherParams;
5113553Sjavier.bueno@metempsy.com
5213553Sjavier.bueno@metempsy.comclass SignaturePathPrefetcher : public QueuedPrefetcher
5313553Sjavier.bueno@metempsy.com{
5413624Sjavier.bueno@metempsy.com  protected:
5513553Sjavier.bueno@metempsy.com    /** Signature type */
5613553Sjavier.bueno@metempsy.com    typedef uint16_t signature_t;
5713553Sjavier.bueno@metempsy.com    /** Stride type */
5813553Sjavier.bueno@metempsy.com    typedef int16_t stride_t;
5913553Sjavier.bueno@metempsy.com
6013553Sjavier.bueno@metempsy.com    /** Number of strides stored in each pattern entry */
6113553Sjavier.bueno@metempsy.com    const unsigned stridesPerPatternEntry;
6213553Sjavier.bueno@metempsy.com    /** Number of bits to shift when generating a new signature */
6313553Sjavier.bueno@metempsy.com    const uint8_t signatureShift;
6413553Sjavier.bueno@metempsy.com    /** Size of the signature, in bits */
6513553Sjavier.bueno@metempsy.com    const signature_t signatureBits;
6613553Sjavier.bueno@metempsy.com    /** Minimum confidence to issue a prefetch */
6713553Sjavier.bueno@metempsy.com    const double prefetchConfidenceThreshold;
6813553Sjavier.bueno@metempsy.com    /** Minimum confidence to keep navigating lookahead entries */
6913553Sjavier.bueno@metempsy.com    const double lookaheadConfidenceThreshold;
7013553Sjavier.bueno@metempsy.com
7113553Sjavier.bueno@metempsy.com    /** Signature entry data type */
7213553Sjavier.bueno@metempsy.com    struct SignatureEntry : public TaggedEntry
7313553Sjavier.bueno@metempsy.com    {
7413553Sjavier.bueno@metempsy.com        /** Path signature */
7513553Sjavier.bueno@metempsy.com        signature_t signature;
7613553Sjavier.bueno@metempsy.com        /** Last accessed block within a page */
7713553Sjavier.bueno@metempsy.com        stride_t lastBlock;
7813553Sjavier.bueno@metempsy.com        SignatureEntry() : signature(0), lastBlock(0)
7913553Sjavier.bueno@metempsy.com        {}
8013553Sjavier.bueno@metempsy.com    };
8113553Sjavier.bueno@metempsy.com    /** Signature table */
8213553Sjavier.bueno@metempsy.com    AssociativeSet<SignatureEntry> signatureTable;
8313553Sjavier.bueno@metempsy.com
8413553Sjavier.bueno@metempsy.com    /** A stride entry with its counter */
8513553Sjavier.bueno@metempsy.com    struct PatternStrideEntry
8613553Sjavier.bueno@metempsy.com    {
8713553Sjavier.bueno@metempsy.com        /** stride in a page in blkSize increments */
8813553Sjavier.bueno@metempsy.com        stride_t stride;
8913963Sodanrc@yahoo.com.br        /** Saturating counter */
9013963Sodanrc@yahoo.com.br        SatCounter counter;
9113963Sodanrc@yahoo.com.br        PatternStrideEntry(unsigned bits) : stride(0), counter(bits)
9213553Sjavier.bueno@metempsy.com        {}
9313553Sjavier.bueno@metempsy.com    };
9413553Sjavier.bueno@metempsy.com    /** Pattern entry data type, a set of stride and counter entries */
9513553Sjavier.bueno@metempsy.com    struct PatternEntry : public TaggedEntry
9613553Sjavier.bueno@metempsy.com    {
9713553Sjavier.bueno@metempsy.com        /** group of stides */
9813553Sjavier.bueno@metempsy.com        std::vector<PatternStrideEntry> strideEntries;
9913624Sjavier.bueno@metempsy.com        /** use counter, used by SPPv2 */
10013963Sodanrc@yahoo.com.br        SatCounter counter;
10113963Sodanrc@yahoo.com.br        PatternEntry(size_t num_strides, unsigned counter_bits)
10213963Sodanrc@yahoo.com.br            : strideEntries(num_strides, counter_bits), counter(counter_bits)
10313553Sjavier.bueno@metempsy.com        {}
10413553Sjavier.bueno@metempsy.com
10513553Sjavier.bueno@metempsy.com        /** Reset the entries to their initial values */
10613553Sjavier.bueno@metempsy.com        void reset() override
10713553Sjavier.bueno@metempsy.com        {
10813553Sjavier.bueno@metempsy.com            for (auto &entry : strideEntries) {
10913963Sodanrc@yahoo.com.br                entry.counter.reset();
11013553Sjavier.bueno@metempsy.com                entry.stride = 0;
11113553Sjavier.bueno@metempsy.com            }
11213963Sodanrc@yahoo.com.br            counter.reset();
11313553Sjavier.bueno@metempsy.com        }
11413553Sjavier.bueno@metempsy.com
11513553Sjavier.bueno@metempsy.com        /**
11613553Sjavier.bueno@metempsy.com         * Returns the entry with the desired stride
11713553Sjavier.bueno@metempsy.com         * @param stride the stride to find
11813553Sjavier.bueno@metempsy.com         * @result a pointer to the entry, if the stride was found, or nullptr,
11913553Sjavier.bueno@metempsy.com         *         if the stride was not found
12013553Sjavier.bueno@metempsy.com         */
12113553Sjavier.bueno@metempsy.com        PatternStrideEntry *findStride(stride_t stride)
12213553Sjavier.bueno@metempsy.com        {
12313553Sjavier.bueno@metempsy.com            PatternStrideEntry *found_entry = nullptr;
12413553Sjavier.bueno@metempsy.com            for (auto &entry : strideEntries) {
12513553Sjavier.bueno@metempsy.com                if (entry.stride == stride) {
12613553Sjavier.bueno@metempsy.com                    found_entry = &entry;
12713553Sjavier.bueno@metempsy.com                    break;
12813553Sjavier.bueno@metempsy.com                }
12913553Sjavier.bueno@metempsy.com            }
13013553Sjavier.bueno@metempsy.com            return found_entry;
13113553Sjavier.bueno@metempsy.com        }
13213553Sjavier.bueno@metempsy.com
13313553Sjavier.bueno@metempsy.com        /**
13413553Sjavier.bueno@metempsy.com         * Gets the entry with the provided stride, if there is no entry with
13513553Sjavier.bueno@metempsy.com         * the associated stride, it replaces one of them.
13613553Sjavier.bueno@metempsy.com         * @param stride the stride to find
13713553Sjavier.bueno@metempsy.com         * @result reference to the selected entry
13813553Sjavier.bueno@metempsy.com         */
13913963Sodanrc@yahoo.com.br        PatternStrideEntry &getStrideEntry(stride_t stride);
14013553Sjavier.bueno@metempsy.com    };
14113553Sjavier.bueno@metempsy.com    /** Pattern table */
14213553Sjavier.bueno@metempsy.com    AssociativeSet<PatternEntry> patternTable;
14313553Sjavier.bueno@metempsy.com
14413553Sjavier.bueno@metempsy.com    /**
14513553Sjavier.bueno@metempsy.com     * Generates a new signature from an existing one and a new stride
14613553Sjavier.bueno@metempsy.com     * @param sig current signature
14713553Sjavier.bueno@metempsy.com     * @param str stride to add to the new signature
14813553Sjavier.bueno@metempsy.com     * @result the new signature
14913553Sjavier.bueno@metempsy.com     */
15013553Sjavier.bueno@metempsy.com    inline signature_t updateSignature(signature_t sig, stride_t str) const {
15113553Sjavier.bueno@metempsy.com        sig <<= signatureShift;
15213553Sjavier.bueno@metempsy.com        sig ^= str;
15313553Sjavier.bueno@metempsy.com        sig &= mask(signatureBits);
15413553Sjavier.bueno@metempsy.com        return sig;
15513553Sjavier.bueno@metempsy.com    }
15613553Sjavier.bueno@metempsy.com
15713553Sjavier.bueno@metempsy.com    /**
15813553Sjavier.bueno@metempsy.com     * Generates an address to be prefetched.
15913553Sjavier.bueno@metempsy.com     * @param ppn page number to prefetch from
16013624Sjavier.bueno@metempsy.com     * @param last_block last accessed block within the page ppn
16113624Sjavier.bueno@metempsy.com     * @param delta difference, in number of blocks, from the last_block
16213624Sjavier.bueno@metempsy.com     *        accessed to the block to prefetch. The block to prefetch is
16313624Sjavier.bueno@metempsy.com     *        computed by this formula:
16413624Sjavier.bueno@metempsy.com     *          ppn * pageBytes + (last_block + delta) * blkSize
16513624Sjavier.bueno@metempsy.com     *        This value can be negative.
16613624Sjavier.bueno@metempsy.com     * @param path_confidence the confidence factor of this prefetch
16713624Sjavier.bueno@metempsy.com     * @param signature the current path signature
16813553Sjavier.bueno@metempsy.com     * @param is_secure whether this page is inside the secure memory area
16913624Sjavier.bueno@metempsy.com     * @param addresses addresses to prefetch will be added to this vector
17013553Sjavier.bueno@metempsy.com     */
17113624Sjavier.bueno@metempsy.com    void addPrefetch(Addr ppn, stride_t last_block, stride_t delta,
17213624Sjavier.bueno@metempsy.com                          double path_confidence, signature_t signature,
17313624Sjavier.bueno@metempsy.com                          bool is_secure,
17413624Sjavier.bueno@metempsy.com                          std::vector<AddrPriority> &addresses);
17513553Sjavier.bueno@metempsy.com
17613553Sjavier.bueno@metempsy.com    /**
17713553Sjavier.bueno@metempsy.com     * Obtains the SignatureEntry of the given page, if the page is not found,
17813553Sjavier.bueno@metempsy.com     * it allocates a new one, replacing an existing entry if needed
17913624Sjavier.bueno@metempsy.com     * It also provides the stride of the current block and the initial
18013624Sjavier.bueno@metempsy.com     * path confidence of the corresponding entry
18113553Sjavier.bueno@metempsy.com     * @param ppn physical page number of the page
18213553Sjavier.bueno@metempsy.com     * @param is_secure whether this page is inside the secure memory area
18313553Sjavier.bueno@metempsy.com     * @param block accessed block within the page
18413624Sjavier.bueno@metempsy.com     * @param miss if the entry is not found, this will be set to true
18513624Sjavier.bueno@metempsy.com     * @param stride set to the computed stride
18613624Sjavier.bueno@metempsy.com     * @param initial_confidence set to the initial confidence value
18713553Sjavier.bueno@metempsy.com     * @result a reference to the SignatureEntry
18813553Sjavier.bueno@metempsy.com     */
18913624Sjavier.bueno@metempsy.com    SignatureEntry &getSignatureEntry(Addr ppn, bool is_secure, stride_t block,
19013624Sjavier.bueno@metempsy.com            bool &miss, stride_t &stride, double &initial_confidence);
19113553Sjavier.bueno@metempsy.com    /**
19213553Sjavier.bueno@metempsy.com     * Obtains the PatternEntry of the given signature, if the signature is
19313553Sjavier.bueno@metempsy.com     * not found, it allocates a new one, replacing an existing entry if needed
19413553Sjavier.bueno@metempsy.com     * @param signature the signature of the desired entry
19513553Sjavier.bueno@metempsy.com     * @result a reference to the PatternEntry
19613553Sjavier.bueno@metempsy.com     */
19713624Sjavier.bueno@metempsy.com    PatternEntry& getPatternEntry(Addr signature);
19813553Sjavier.bueno@metempsy.com
19913553Sjavier.bueno@metempsy.com    /**
20013553Sjavier.bueno@metempsy.com     * Updates the pattern table with the provided signature and stride
20113553Sjavier.bueno@metempsy.com     * @param signature the signature to use to index the pattern table
20213553Sjavier.bueno@metempsy.com     * @param stride the stride to use to index the set of strides of the
20313553Sjavier.bueno@metempsy.com     *        pattern table entry
20413553Sjavier.bueno@metempsy.com     */
20513553Sjavier.bueno@metempsy.com    void updatePatternTable(Addr signature, stride_t stride);
20613553Sjavier.bueno@metempsy.com
20713624Sjavier.bueno@metempsy.com    /**
20813624Sjavier.bueno@metempsy.com     * Computes the lookahead path confidence of the provided pattern entry
20913624Sjavier.bueno@metempsy.com     * @param sig the PatternEntry to use
21013624Sjavier.bueno@metempsy.com     * @param lookahead PatternStrideEntry within the provided PatternEntry
21113624Sjavier.bueno@metempsy.com     * @return the computed confidence factor
21213624Sjavier.bueno@metempsy.com     */
21313624Sjavier.bueno@metempsy.com    virtual double calculateLookaheadConfidence(PatternEntry const &sig,
21413624Sjavier.bueno@metempsy.com            PatternStrideEntry const &lookahead) const;
21513624Sjavier.bueno@metempsy.com
21613624Sjavier.bueno@metempsy.com    /**
21713624Sjavier.bueno@metempsy.com     * Computes the prefetch confidence of the provided pattern entry
21813624Sjavier.bueno@metempsy.com     * @param sig the PatternEntry to use
21913624Sjavier.bueno@metempsy.com     * @param entry PatternStrideEntry within the provided PatternEntry
22013624Sjavier.bueno@metempsy.com     * @return the computed confidence factor
22113624Sjavier.bueno@metempsy.com     */
22213624Sjavier.bueno@metempsy.com    virtual double calculatePrefetchConfidence(PatternEntry const &sig,
22313624Sjavier.bueno@metempsy.com            PatternStrideEntry const &entry) const;
22413624Sjavier.bueno@metempsy.com
22513624Sjavier.bueno@metempsy.com    /**
22613624Sjavier.bueno@metempsy.com     * Increases the counter of a given PatternEntry/PatternStrideEntry
22713624Sjavier.bueno@metempsy.com     * @param pattern_entry the corresponding PatternEntry
22813624Sjavier.bueno@metempsy.com     * @param pstride_entry the PatternStrideEntry within the PatternEntry
22913624Sjavier.bueno@metempsy.com     */
23013624Sjavier.bueno@metempsy.com    virtual void increasePatternEntryCounter(PatternEntry &pattern_entry,
23113624Sjavier.bueno@metempsy.com            PatternStrideEntry &pstride_entry);
23213624Sjavier.bueno@metempsy.com
23313624Sjavier.bueno@metempsy.com    /**
23413624Sjavier.bueno@metempsy.com     * Whenever a new SignatureEntry is allocated, it computes the new
23513624Sjavier.bueno@metempsy.com     * signature to be used with the new entry, the resulting stride and the
23613624Sjavier.bueno@metempsy.com     * initial path confidence of the new entry.
23713624Sjavier.bueno@metempsy.com     * @param current_block accessed block within the page of the associated
23813624Sjavier.bueno@metempsy.com              entry
23913624Sjavier.bueno@metempsy.com     * @param new_signature new signature of the allocated entry
24013624Sjavier.bueno@metempsy.com     * @param new_conf the initial path confidence of this entry
24113624Sjavier.bueno@metempsy.com     * @param new_stride the resulting current stride
24213624Sjavier.bueno@metempsy.com     */
24313624Sjavier.bueno@metempsy.com    virtual void handleSignatureTableMiss(stride_t current_block,
24413624Sjavier.bueno@metempsy.com            signature_t &new_signature, double &new_conf,
24513624Sjavier.bueno@metempsy.com            stride_t &new_stride);
24613624Sjavier.bueno@metempsy.com
24713624Sjavier.bueno@metempsy.com    /**
24813624Sjavier.bueno@metempsy.com     * Auxiliar prefetch mechanism used at the end of calculatePrefetch.
24913624Sjavier.bueno@metempsy.com     * This prefetcher uses this to activate the next line prefetcher if
25013624Sjavier.bueno@metempsy.com     * no prefetch candidates have been found.
25113624Sjavier.bueno@metempsy.com     * @param ppn physical page number of the current accessed page
25213624Sjavier.bueno@metempsy.com     * @param current_block last accessed block within the page ppn
25313624Sjavier.bueno@metempsy.com     * @param is_secure whether this page is inside the secure memory area
25413624Sjavier.bueno@metempsy.com     * @param addresses the addresses to be prefetched are added to this vector
25513624Sjavier.bueno@metempsy.com     * @param updated_filter_entries set of addresses containing these that
25613624Sjavier.bueno@metempsy.com     *        their filter has been updated, if this call updates a new entry
25713624Sjavier.bueno@metempsy.com     */
25813624Sjavier.bueno@metempsy.com    virtual void auxiliaryPrefetcher(Addr ppn, stride_t current_block,
25913624Sjavier.bueno@metempsy.com            bool is_secure, std::vector<AddrPriority> &addresses);
26013624Sjavier.bueno@metempsy.com
26113624Sjavier.bueno@metempsy.com    /**
26213624Sjavier.bueno@metempsy.com     * Handles the situation when the lookahead process has crossed the
26313624Sjavier.bueno@metempsy.com     * boundaries of the current page. This is not fully described in the
26413624Sjavier.bueno@metempsy.com     * paper that was used to implement this code, however, the article
26513624Sjavier.bueno@metempsy.com     * describing the upgraded version of this prefetcher provides some
26613624Sjavier.bueno@metempsy.com     * details. For this prefetcher, there are no specific actions to be
26713624Sjavier.bueno@metempsy.com     * done.
26813624Sjavier.bueno@metempsy.com     * @param signature the lookahead signature that crossed the page
26913624Sjavier.bueno@metempsy.com     * @param delta the current stride that caused it
27013624Sjavier.bueno@metempsy.com     * @param last_offset the last accessed block within the page
27113624Sjavier.bueno@metempsy.com     * @param path_confidence the path confidence at the moment of crossing
27213624Sjavier.bueno@metempsy.com     */
27313624Sjavier.bueno@metempsy.com    virtual void handlePageCrossingLookahead(signature_t signature,
27413624Sjavier.bueno@metempsy.com            stride_t last_offset, stride_t delta, double path_confidence) {
27513624Sjavier.bueno@metempsy.com    }
27613624Sjavier.bueno@metempsy.com
27713553Sjavier.bueno@metempsy.com  public:
27813553Sjavier.bueno@metempsy.com    SignaturePathPrefetcher(const SignaturePathPrefetcherParams* p);
27913553Sjavier.bueno@metempsy.com    ~SignaturePathPrefetcher() {}
28013553Sjavier.bueno@metempsy.com    void calculatePrefetch(const PrefetchInfo &pfi,
28113553Sjavier.bueno@metempsy.com                           std::vector<AddrPriority> &addresses) override;
28213553Sjavier.bueno@metempsy.com};
28313553Sjavier.bueno@metempsy.com
28413553Sjavier.bueno@metempsy.com#endif//__MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__
285