signature_path.hh revision 13624
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 4513553Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/associative_set.hh" 4613553Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/queued.hh" 4713553Sjavier.bueno@metempsy.com#include "mem/packet.hh" 4813553Sjavier.bueno@metempsy.com 4913553Sjavier.bueno@metempsy.comstruct SignaturePathPrefetcherParams; 5013553Sjavier.bueno@metempsy.com 5113553Sjavier.bueno@metempsy.comclass SignaturePathPrefetcher : public QueuedPrefetcher 5213553Sjavier.bueno@metempsy.com{ 5313624Sjavier.bueno@metempsy.com protected: 5413553Sjavier.bueno@metempsy.com /** Signature type */ 5513553Sjavier.bueno@metempsy.com typedef uint16_t signature_t; 5613553Sjavier.bueno@metempsy.com /** Stride type */ 5713553Sjavier.bueno@metempsy.com typedef int16_t stride_t; 5813553Sjavier.bueno@metempsy.com 5913553Sjavier.bueno@metempsy.com /** Number of strides stored in each pattern entry */ 6013553Sjavier.bueno@metempsy.com const unsigned stridesPerPatternEntry; 6113553Sjavier.bueno@metempsy.com /** Number of bits to shift when generating a new signature */ 6213553Sjavier.bueno@metempsy.com const uint8_t signatureShift; 6313553Sjavier.bueno@metempsy.com /** Size of the signature, in bits */ 6413553Sjavier.bueno@metempsy.com const signature_t signatureBits; 6513553Sjavier.bueno@metempsy.com /** Maximum pattern entries counter value */ 6613553Sjavier.bueno@metempsy.com const uint8_t maxCounterValue; 6713553Sjavier.bueno@metempsy.com /** Minimum confidence to issue a prefetch */ 6813553Sjavier.bueno@metempsy.com const double prefetchConfidenceThreshold; 6913553Sjavier.bueno@metempsy.com /** Minimum confidence to keep navigating lookahead entries */ 7013553Sjavier.bueno@metempsy.com const double lookaheadConfidenceThreshold; 7113553Sjavier.bueno@metempsy.com 7213553Sjavier.bueno@metempsy.com /** Signature entry data type */ 7313553Sjavier.bueno@metempsy.com struct SignatureEntry : public TaggedEntry 7413553Sjavier.bueno@metempsy.com { 7513553Sjavier.bueno@metempsy.com /** Path signature */ 7613553Sjavier.bueno@metempsy.com signature_t signature; 7713553Sjavier.bueno@metempsy.com /** Last accessed block within a page */ 7813553Sjavier.bueno@metempsy.com stride_t lastBlock; 7913553Sjavier.bueno@metempsy.com SignatureEntry() : signature(0), lastBlock(0) 8013553Sjavier.bueno@metempsy.com {} 8113553Sjavier.bueno@metempsy.com }; 8213553Sjavier.bueno@metempsy.com /** Signature table */ 8313553Sjavier.bueno@metempsy.com AssociativeSet<SignatureEntry> signatureTable; 8413553Sjavier.bueno@metempsy.com 8513553Sjavier.bueno@metempsy.com /** A stride entry with its counter */ 8613553Sjavier.bueno@metempsy.com struct PatternStrideEntry 8713553Sjavier.bueno@metempsy.com { 8813553Sjavier.bueno@metempsy.com /** stride in a page in blkSize increments */ 8913553Sjavier.bueno@metempsy.com stride_t stride; 9013553Sjavier.bueno@metempsy.com /** counter value (max value defined by maxCounterValue) */ 9113553Sjavier.bueno@metempsy.com uint8_t counter; 9213553Sjavier.bueno@metempsy.com PatternStrideEntry() : stride(0), counter(0) 9313553Sjavier.bueno@metempsy.com {} 9413553Sjavier.bueno@metempsy.com }; 9513553Sjavier.bueno@metempsy.com /** Pattern entry data type, a set of stride and counter entries */ 9613553Sjavier.bueno@metempsy.com struct PatternEntry : public TaggedEntry 9713553Sjavier.bueno@metempsy.com { 9813553Sjavier.bueno@metempsy.com /** group of stides */ 9913553Sjavier.bueno@metempsy.com std::vector<PatternStrideEntry> strideEntries; 10013624Sjavier.bueno@metempsy.com /** use counter, used by SPPv2 */ 10113624Sjavier.bueno@metempsy.com uint8_t counter; 10213624Sjavier.bueno@metempsy.com PatternEntry(size_t num_strides) : strideEntries(num_strides), 10313624Sjavier.bueno@metempsy.com counter(0) 10413553Sjavier.bueno@metempsy.com {} 10513553Sjavier.bueno@metempsy.com 10613553Sjavier.bueno@metempsy.com /** Reset the entries to their initial values */ 10713553Sjavier.bueno@metempsy.com void reset() override 10813553Sjavier.bueno@metempsy.com { 10913553Sjavier.bueno@metempsy.com for (auto &entry : strideEntries) { 11013553Sjavier.bueno@metempsy.com entry.counter = 0; 11113553Sjavier.bueno@metempsy.com entry.stride = 0; 11213553Sjavier.bueno@metempsy.com } 11313624Sjavier.bueno@metempsy.com counter = 0; 11413553Sjavier.bueno@metempsy.com } 11513553Sjavier.bueno@metempsy.com 11613553Sjavier.bueno@metempsy.com /** 11713553Sjavier.bueno@metempsy.com * Returns the entry with the desired stride 11813553Sjavier.bueno@metempsy.com * @param stride the stride to find 11913553Sjavier.bueno@metempsy.com * @result a pointer to the entry, if the stride was found, or nullptr, 12013553Sjavier.bueno@metempsy.com * if the stride was not found 12113553Sjavier.bueno@metempsy.com */ 12213553Sjavier.bueno@metempsy.com PatternStrideEntry *findStride(stride_t stride) 12313553Sjavier.bueno@metempsy.com { 12413553Sjavier.bueno@metempsy.com PatternStrideEntry *found_entry = nullptr; 12513553Sjavier.bueno@metempsy.com for (auto &entry : strideEntries) { 12613553Sjavier.bueno@metempsy.com if (entry.stride == stride) { 12713553Sjavier.bueno@metempsy.com found_entry = &entry; 12813553Sjavier.bueno@metempsy.com break; 12913553Sjavier.bueno@metempsy.com } 13013553Sjavier.bueno@metempsy.com } 13113553Sjavier.bueno@metempsy.com return found_entry; 13213553Sjavier.bueno@metempsy.com } 13313553Sjavier.bueno@metempsy.com 13413553Sjavier.bueno@metempsy.com /** 13513553Sjavier.bueno@metempsy.com * Gets the entry with the provided stride, if there is no entry with 13613553Sjavier.bueno@metempsy.com * the associated stride, it replaces one of them. 13713553Sjavier.bueno@metempsy.com * @param stride the stride to find 13813553Sjavier.bueno@metempsy.com * @param max_counter_value maximum value of the confidence counters, 13913553Sjavier.bueno@metempsy.com * it is used when no strides are found and an entry needs to be 14013553Sjavier.bueno@metempsy.com * replaced 14113553Sjavier.bueno@metempsy.com * @result reference to the selected entry 14213553Sjavier.bueno@metempsy.com */ 14313553Sjavier.bueno@metempsy.com PatternStrideEntry &getStrideEntry(stride_t stride, 14413553Sjavier.bueno@metempsy.com uint8_t max_counter_value); 14513553Sjavier.bueno@metempsy.com }; 14613553Sjavier.bueno@metempsy.com /** Pattern table */ 14713553Sjavier.bueno@metempsy.com AssociativeSet<PatternEntry> patternTable; 14813553Sjavier.bueno@metempsy.com 14913553Sjavier.bueno@metempsy.com /** 15013553Sjavier.bueno@metempsy.com * Generates a new signature from an existing one and a new stride 15113553Sjavier.bueno@metempsy.com * @param sig current signature 15213553Sjavier.bueno@metempsy.com * @param str stride to add to the new signature 15313553Sjavier.bueno@metempsy.com * @result the new signature 15413553Sjavier.bueno@metempsy.com */ 15513553Sjavier.bueno@metempsy.com inline signature_t updateSignature(signature_t sig, stride_t str) const { 15613553Sjavier.bueno@metempsy.com sig <<= signatureShift; 15713553Sjavier.bueno@metempsy.com sig ^= str; 15813553Sjavier.bueno@metempsy.com sig &= mask(signatureBits); 15913553Sjavier.bueno@metempsy.com return sig; 16013553Sjavier.bueno@metempsy.com } 16113553Sjavier.bueno@metempsy.com 16213553Sjavier.bueno@metempsy.com /** 16313553Sjavier.bueno@metempsy.com * Generates an address to be prefetched. 16413553Sjavier.bueno@metempsy.com * @param ppn page number to prefetch from 16513624Sjavier.bueno@metempsy.com * @param last_block last accessed block within the page ppn 16613624Sjavier.bueno@metempsy.com * @param delta difference, in number of blocks, from the last_block 16713624Sjavier.bueno@metempsy.com * accessed to the block to prefetch. The block to prefetch is 16813624Sjavier.bueno@metempsy.com * computed by this formula: 16913624Sjavier.bueno@metempsy.com * ppn * pageBytes + (last_block + delta) * blkSize 17013624Sjavier.bueno@metempsy.com * This value can be negative. 17113624Sjavier.bueno@metempsy.com * @param path_confidence the confidence factor of this prefetch 17213624Sjavier.bueno@metempsy.com * @param signature the current path signature 17313553Sjavier.bueno@metempsy.com * @param is_secure whether this page is inside the secure memory area 17413624Sjavier.bueno@metempsy.com * @param addresses addresses to prefetch will be added to this vector 17513553Sjavier.bueno@metempsy.com */ 17613624Sjavier.bueno@metempsy.com void addPrefetch(Addr ppn, stride_t last_block, stride_t delta, 17713624Sjavier.bueno@metempsy.com double path_confidence, signature_t signature, 17813624Sjavier.bueno@metempsy.com bool is_secure, 17913624Sjavier.bueno@metempsy.com std::vector<AddrPriority> &addresses); 18013553Sjavier.bueno@metempsy.com 18113553Sjavier.bueno@metempsy.com /** 18213553Sjavier.bueno@metempsy.com * Obtains the SignatureEntry of the given page, if the page is not found, 18313553Sjavier.bueno@metempsy.com * it allocates a new one, replacing an existing entry if needed 18413624Sjavier.bueno@metempsy.com * It also provides the stride of the current block and the initial 18513624Sjavier.bueno@metempsy.com * path confidence of the corresponding entry 18613553Sjavier.bueno@metempsy.com * @param ppn physical page number of the page 18713553Sjavier.bueno@metempsy.com * @param is_secure whether this page is inside the secure memory area 18813553Sjavier.bueno@metempsy.com * @param block accessed block within the page 18913624Sjavier.bueno@metempsy.com * @param miss if the entry is not found, this will be set to true 19013624Sjavier.bueno@metempsy.com * @param stride set to the computed stride 19113624Sjavier.bueno@metempsy.com * @param initial_confidence set to the initial confidence value 19213553Sjavier.bueno@metempsy.com * @result a reference to the SignatureEntry 19313553Sjavier.bueno@metempsy.com */ 19413624Sjavier.bueno@metempsy.com SignatureEntry &getSignatureEntry(Addr ppn, bool is_secure, stride_t block, 19513624Sjavier.bueno@metempsy.com bool &miss, stride_t &stride, double &initial_confidence); 19613553Sjavier.bueno@metempsy.com /** 19713553Sjavier.bueno@metempsy.com * Obtains the PatternEntry of the given signature, if the signature is 19813553Sjavier.bueno@metempsy.com * not found, it allocates a new one, replacing an existing entry if needed 19913553Sjavier.bueno@metempsy.com * @param signature the signature of the desired entry 20013553Sjavier.bueno@metempsy.com * @result a reference to the PatternEntry 20113553Sjavier.bueno@metempsy.com */ 20213624Sjavier.bueno@metempsy.com PatternEntry& getPatternEntry(Addr signature); 20313553Sjavier.bueno@metempsy.com 20413553Sjavier.bueno@metempsy.com /** 20513553Sjavier.bueno@metempsy.com * Updates the pattern table with the provided signature and stride 20613553Sjavier.bueno@metempsy.com * @param signature the signature to use to index the pattern table 20713553Sjavier.bueno@metempsy.com * @param stride the stride to use to index the set of strides of the 20813553Sjavier.bueno@metempsy.com * pattern table entry 20913553Sjavier.bueno@metempsy.com */ 21013553Sjavier.bueno@metempsy.com void updatePatternTable(Addr signature, stride_t stride); 21113553Sjavier.bueno@metempsy.com 21213624Sjavier.bueno@metempsy.com /** 21313624Sjavier.bueno@metempsy.com * Computes the lookahead path confidence of the provided pattern entry 21413624Sjavier.bueno@metempsy.com * @param sig the PatternEntry to use 21513624Sjavier.bueno@metempsy.com * @param lookahead PatternStrideEntry within the provided PatternEntry 21613624Sjavier.bueno@metempsy.com * @return the computed confidence factor 21713624Sjavier.bueno@metempsy.com */ 21813624Sjavier.bueno@metempsy.com virtual double calculateLookaheadConfidence(PatternEntry const &sig, 21913624Sjavier.bueno@metempsy.com PatternStrideEntry const &lookahead) const; 22013624Sjavier.bueno@metempsy.com 22113624Sjavier.bueno@metempsy.com /** 22213624Sjavier.bueno@metempsy.com * Computes the prefetch confidence of the provided pattern entry 22313624Sjavier.bueno@metempsy.com * @param sig the PatternEntry to use 22413624Sjavier.bueno@metempsy.com * @param entry PatternStrideEntry within the provided PatternEntry 22513624Sjavier.bueno@metempsy.com * @return the computed confidence factor 22613624Sjavier.bueno@metempsy.com */ 22713624Sjavier.bueno@metempsy.com virtual double calculatePrefetchConfidence(PatternEntry const &sig, 22813624Sjavier.bueno@metempsy.com PatternStrideEntry const &entry) const; 22913624Sjavier.bueno@metempsy.com 23013624Sjavier.bueno@metempsy.com /** 23113624Sjavier.bueno@metempsy.com * Increases the counter of a given PatternEntry/PatternStrideEntry 23213624Sjavier.bueno@metempsy.com * @param pattern_entry the corresponding PatternEntry 23313624Sjavier.bueno@metempsy.com * @param pstride_entry the PatternStrideEntry within the PatternEntry 23413624Sjavier.bueno@metempsy.com */ 23513624Sjavier.bueno@metempsy.com virtual void increasePatternEntryCounter(PatternEntry &pattern_entry, 23613624Sjavier.bueno@metempsy.com PatternStrideEntry &pstride_entry); 23713624Sjavier.bueno@metempsy.com 23813624Sjavier.bueno@metempsy.com /** 23913624Sjavier.bueno@metempsy.com * Whenever a new SignatureEntry is allocated, it computes the new 24013624Sjavier.bueno@metempsy.com * signature to be used with the new entry, the resulting stride and the 24113624Sjavier.bueno@metempsy.com * initial path confidence of the new entry. 24213624Sjavier.bueno@metempsy.com * @param current_block accessed block within the page of the associated 24313624Sjavier.bueno@metempsy.com entry 24413624Sjavier.bueno@metempsy.com * @param new_signature new signature of the allocated entry 24513624Sjavier.bueno@metempsy.com * @param new_conf the initial path confidence of this entry 24613624Sjavier.bueno@metempsy.com * @param new_stride the resulting current stride 24713624Sjavier.bueno@metempsy.com */ 24813624Sjavier.bueno@metempsy.com virtual void handleSignatureTableMiss(stride_t current_block, 24913624Sjavier.bueno@metempsy.com signature_t &new_signature, double &new_conf, 25013624Sjavier.bueno@metempsy.com stride_t &new_stride); 25113624Sjavier.bueno@metempsy.com 25213624Sjavier.bueno@metempsy.com /** 25313624Sjavier.bueno@metempsy.com * Auxiliar prefetch mechanism used at the end of calculatePrefetch. 25413624Sjavier.bueno@metempsy.com * This prefetcher uses this to activate the next line prefetcher if 25513624Sjavier.bueno@metempsy.com * no prefetch candidates have been found. 25613624Sjavier.bueno@metempsy.com * @param ppn physical page number of the current accessed page 25713624Sjavier.bueno@metempsy.com * @param current_block last accessed block within the page ppn 25813624Sjavier.bueno@metempsy.com * @param is_secure whether this page is inside the secure memory area 25913624Sjavier.bueno@metempsy.com * @param addresses the addresses to be prefetched are added to this vector 26013624Sjavier.bueno@metempsy.com * @param updated_filter_entries set of addresses containing these that 26113624Sjavier.bueno@metempsy.com * their filter has been updated, if this call updates a new entry 26213624Sjavier.bueno@metempsy.com */ 26313624Sjavier.bueno@metempsy.com virtual void auxiliaryPrefetcher(Addr ppn, stride_t current_block, 26413624Sjavier.bueno@metempsy.com bool is_secure, std::vector<AddrPriority> &addresses); 26513624Sjavier.bueno@metempsy.com 26613624Sjavier.bueno@metempsy.com /** 26713624Sjavier.bueno@metempsy.com * Handles the situation when the lookahead process has crossed the 26813624Sjavier.bueno@metempsy.com * boundaries of the current page. This is not fully described in the 26913624Sjavier.bueno@metempsy.com * paper that was used to implement this code, however, the article 27013624Sjavier.bueno@metempsy.com * describing the upgraded version of this prefetcher provides some 27113624Sjavier.bueno@metempsy.com * details. For this prefetcher, there are no specific actions to be 27213624Sjavier.bueno@metempsy.com * done. 27313624Sjavier.bueno@metempsy.com * @param signature the lookahead signature that crossed the page 27413624Sjavier.bueno@metempsy.com * @param delta the current stride that caused it 27513624Sjavier.bueno@metempsy.com * @param last_offset the last accessed block within the page 27613624Sjavier.bueno@metempsy.com * @param path_confidence the path confidence at the moment of crossing 27713624Sjavier.bueno@metempsy.com */ 27813624Sjavier.bueno@metempsy.com virtual void handlePageCrossingLookahead(signature_t signature, 27913624Sjavier.bueno@metempsy.com stride_t last_offset, stride_t delta, double path_confidence) { 28013624Sjavier.bueno@metempsy.com } 28113624Sjavier.bueno@metempsy.com 28213553Sjavier.bueno@metempsy.com public: 28313553Sjavier.bueno@metempsy.com SignaturePathPrefetcher(const SignaturePathPrefetcherParams* p); 28413553Sjavier.bueno@metempsy.com ~SignaturePathPrefetcher() {} 28513553Sjavier.bueno@metempsy.com void calculatePrefetch(const PrefetchInfo &pfi, 28613553Sjavier.bueno@metempsy.com std::vector<AddrPriority> &addresses) override; 28713553Sjavier.bueno@metempsy.com}; 28813553Sjavier.bueno@metempsy.com 28913553Sjavier.bueno@metempsy.com#endif//__MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__ 290