| /** |
| * 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__ |