cache/prefetch/signature_path.hh

/**
 * Copyright (c) 2018 Metempsy Technology Consulting
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Javier Bueno
 */

 /**
  * Implementation of the Signature Path Prefetcher
  *
  * References:
  *     Lookahead prefetching with signature path
  *     J Kim, PV Gratz, ALN Reddy
  *     The 2nd Data Prefetching Championship (DPC2)
  * The filter feature described in the paper is not implemented, as it
  * redundant prefetches are dropped by the cache.
  */

#ifndef __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__
#define __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__

#include "mem/cache/prefetch/associative_set.hh"
#include "mem/cache/prefetch/queued.hh"
#include "mem/packet.hh"

struct SignaturePathPrefetcherParams;

class SignaturePathPrefetcher : public QueuedPrefetcher
{
  protected:
    /** Signature type */
    typedef uint16_t signature_t;
    /** Stride type */
    typedef int16_t stride_t;

    /** Number of strides stored in each pattern entry */
    const unsigned stridesPerPatternEntry;
    /** Number of bits to shift when generating a new signature */
    const uint8_t signatureShift;
    /** Size of the signature, in bits */
    const signature_t signatureBits;
    /** Maximum pattern entries counter value */
    const uint8_t maxCounterValue;
    /** Minimum confidence to issue a prefetch */
    const double prefetchConfidenceThreshold;
    /** Minimum confidence to keep navigating lookahead entries */
    const double lookaheadConfidenceThreshold;

    /** Signature entry data type */
    struct SignatureEntry : public TaggedEntry
    {
        /** Path signature */
        signature_t signature;
        /** Last accessed block within a page */
        stride_t lastBlock;
        SignatureEntry() : signature(0), lastBlock(0)
        {}
    };
    /** Signature table */
    AssociativeSet<SignatureEntry> signatureTable;

    /** A stride entry with its counter */
    struct PatternStrideEntry
    {
        /** stride in a page in blkSize increments */
        stride_t stride;
        /** counter value (max value defined by maxCounterValue) */
        uint8_t counter;
        PatternStrideEntry() : stride(0), counter(0)
        {}
    };
    /** Pattern entry data type, a set of stride and counter entries */
    struct PatternEntry : public TaggedEntry
    {
        /** group of stides */
        std::vector<PatternStrideEntry> strideEntries;
        /** use counter, used by SPPv2 */
        uint8_t counter;
        PatternEntry(size_t num_strides) : strideEntries(num_strides),
                                           counter(0)
        {}

        /** Reset the entries to their initial values */
        void reset() override
        {
            for (auto &entry : strideEntries) {
                entry.counter = 0;
                entry.stride = 0;
            }
            counter = 0;
        }

        /**
         * Returns the entry with the desired stride
         * @param stride the stride to find
         * @result a pointer to the entry, if the stride was found, or nullptr,
         *         if the stride was not found
         */
        PatternStrideEntry *findStride(stride_t stride)
        {
            PatternStrideEntry *found_entry = nullptr;
            for (auto &entry : strideEntries) {
                if (entry.stride == stride) {
                    found_entry = &entry;
                    break;
                }
            }
            return found_entry;
        }

        /**
         * Gets the entry with the provided stride, if there is no entry with
         * the associated stride, it replaces one of them.
         * @param stride the stride to find
         * @param max_counter_value maximum value of the confidence counters,
         *        it is used when no strides are found and an entry needs to be
         *        replaced
         * @result reference to the selected entry
         */
        PatternStrideEntry &getStrideEntry(stride_t stride,
                                           uint8_t max_counter_value);
    };
    /** Pattern table */
    AssociativeSet<PatternEntry> patternTable;

    /**
     * Generates a new signature from an existing one and a new stride
     * @param sig current signature
     * @param str stride to add to the new signature
     * @result the new signature
     */
    inline signature_t updateSignature(signature_t sig, stride_t str) const {
        sig <<= signatureShift;
        sig ^= str;
        sig &= mask(signatureBits);
        return sig;
    }

    /**
     * Generates an address to be prefetched.
     * @param ppn page number to prefetch from
     * @param last_block last accessed block within the page ppn
     * @param delta difference, in number of blocks, from the last_block
     *        accessed to the block to prefetch. The block to prefetch is
     *        computed by this formula:
     *          ppn * pageBytes + (last_block + delta) * blkSize
     *        This value can be negative.
     * @param path_confidence the confidence factor of this prefetch
     * @param signature the current path signature
     * @param is_secure whether this page is inside the secure memory area
     * @param addresses addresses to prefetch will be added to this vector
     */
    void addPrefetch(Addr ppn, stride_t last_block, stride_t delta,
                          double path_confidence, signature_t signature,
                          bool is_secure,
                          std::vector<AddrPriority> &addresses);

    /**
     * Obtains the SignatureEntry of the given page, if the page is not found,
     * it allocates a new one, replacing an existing entry if needed
     * It also provides the stride of the current block and the initial
     * path confidence of the corresponding entry
     * @param ppn physical page number of the page
     * @param is_secure whether this page is inside the secure memory area
     * @param block accessed block within the page
     * @param miss if the entry is not found, this will be set to true
     * @param stride set to the computed stride
     * @param initial_confidence set to the initial confidence value
     * @result a reference to the SignatureEntry
     */
    SignatureEntry &getSignatureEntry(Addr ppn, bool is_secure, stride_t block,
            bool &miss, stride_t &stride, double &initial_confidence);
    /**
     * Obtains the PatternEntry of the given signature, if the signature is
     * not found, it allocates a new one, replacing an existing entry if needed
     * @param signature the signature of the desired entry
     * @result a reference to the PatternEntry
     */
    PatternEntry& getPatternEntry(Addr signature);

    /**
     * Updates the pattern table with the provided signature and stride
     * @param signature the signature to use to index the pattern table
     * @param stride the stride to use to index the set of strides of the
     *        pattern table entry
     */
    void updatePatternTable(Addr signature, stride_t stride);

    /**
     * Computes the lookahead path confidence of the provided pattern entry
     * @param sig the PatternEntry to use
     * @param lookahead PatternStrideEntry within the provided PatternEntry
     * @return the computed confidence factor
     */
    virtual double calculateLookaheadConfidence(PatternEntry const &sig,
            PatternStrideEntry const &lookahead) const;

    /**
     * Computes the prefetch confidence of the provided pattern entry
     * @param sig the PatternEntry to use
     * @param entry PatternStrideEntry within the provided PatternEntry
     * @return the computed confidence factor
     */
    virtual double calculatePrefetchConfidence(PatternEntry const &sig,
            PatternStrideEntry const &entry) const;

    /**
     * Increases the counter of a given PatternEntry/PatternStrideEntry
     * @param pattern_entry the corresponding PatternEntry
     * @param pstride_entry the PatternStrideEntry within the PatternEntry
     */
    virtual void increasePatternEntryCounter(PatternEntry &pattern_entry,
            PatternStrideEntry &pstride_entry);

    /**
     * Whenever a new SignatureEntry is allocated, it computes the new
     * signature to be used with the new entry, the resulting stride and the
     * initial path confidence of the new entry.
     * @param current_block accessed block within the page of the associated
              entry
     * @param new_signature new signature of the allocated entry
     * @param new_conf the initial path confidence of this entry
     * @param new_stride the resulting current stride
     */
    virtual void handleSignatureTableMiss(stride_t current_block,
            signature_t &new_signature, double &new_conf,
            stride_t &new_stride);

    /**
     * Auxiliar prefetch mechanism used at the end of calculatePrefetch.
     * This prefetcher uses this to activate the next line prefetcher if
     * no prefetch candidates have been found.
     * @param ppn physical page number of the current accessed page
     * @param current_block last accessed block within the page ppn
     * @param is_secure whether this page is inside the secure memory area
     * @param addresses the addresses to be prefetched are added to this vector
     * @param updated_filter_entries set of addresses containing these that
     *        their filter has been updated, if this call updates a new entry
     */
    virtual void auxiliaryPrefetcher(Addr ppn, stride_t current_block,
            bool is_secure, std::vector<AddrPriority> &addresses);

    /**
     * Handles the situation when the lookahead process has crossed the
     * boundaries of the current page. This is not fully described in the
     * paper that was used to implement this code, however, the article
     * describing the upgraded version of this prefetcher provides some
     * details. For this prefetcher, there are no specific actions to be
     * done.
     * @param signature the lookahead signature that crossed the page
     * @param delta the current stride that caused it
     * @param last_offset the last accessed block within the page
     * @param path_confidence the path confidence at the moment of crossing
     */
    virtual void handlePageCrossingLookahead(signature_t signature,
            stride_t last_offset, stride_t delta, double path_confidence) {
    }

  public:
    SignaturePathPrefetcher(const SignaturePathPrefetcherParams* p);
    ~SignaturePathPrefetcher() {}
    void calculatePrefetch(const PrefetchInfo &pfi,
                           std::vector<AddrPriority> &addresses) override;
};

#endif//__MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__