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