signature_path.hh revision 13553
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{ 5313553Sjavier.bueno@metempsy.com /** Signature type */ 5413553Sjavier.bueno@metempsy.com typedef uint16_t signature_t; 5513553Sjavier.bueno@metempsy.com /** Stride type */ 5613553Sjavier.bueno@metempsy.com typedef int16_t stride_t; 5713553Sjavier.bueno@metempsy.com 5813553Sjavier.bueno@metempsy.com /** Number of strides stored in each pattern entry */ 5913553Sjavier.bueno@metempsy.com const unsigned stridesPerPatternEntry; 6013553Sjavier.bueno@metempsy.com /** Number of bits to shift when generating a new signature */ 6113553Sjavier.bueno@metempsy.com const uint8_t signatureShift; 6213553Sjavier.bueno@metempsy.com /** Size of the signature, in bits */ 6313553Sjavier.bueno@metempsy.com const signature_t signatureBits; 6413553Sjavier.bueno@metempsy.com /** Maximum pattern entries counter value */ 6513553Sjavier.bueno@metempsy.com const uint8_t maxCounterValue; 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; 8913553Sjavier.bueno@metempsy.com /** counter value (max value defined by maxCounterValue) */ 9013553Sjavier.bueno@metempsy.com uint8_t counter; 9113553Sjavier.bueno@metempsy.com PatternStrideEntry() : stride(0), counter(0) 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; 9913553Sjavier.bueno@metempsy.com PatternEntry(size_t num_strides) : strideEntries(num_strides) 10013553Sjavier.bueno@metempsy.com {} 10113553Sjavier.bueno@metempsy.com 10213553Sjavier.bueno@metempsy.com /** Reset the entries to their initial values */ 10313553Sjavier.bueno@metempsy.com void reset() override 10413553Sjavier.bueno@metempsy.com { 10513553Sjavier.bueno@metempsy.com for (auto &entry : strideEntries) { 10613553Sjavier.bueno@metempsy.com entry.counter = 0; 10713553Sjavier.bueno@metempsy.com entry.stride = 0; 10813553Sjavier.bueno@metempsy.com } 10913553Sjavier.bueno@metempsy.com } 11013553Sjavier.bueno@metempsy.com 11113553Sjavier.bueno@metempsy.com /** 11213553Sjavier.bueno@metempsy.com * Returns the entry with the desired stride 11313553Sjavier.bueno@metempsy.com * @param stride the stride to find 11413553Sjavier.bueno@metempsy.com * @result a pointer to the entry, if the stride was found, or nullptr, 11513553Sjavier.bueno@metempsy.com * if the stride was not found 11613553Sjavier.bueno@metempsy.com */ 11713553Sjavier.bueno@metempsy.com PatternStrideEntry *findStride(stride_t stride) 11813553Sjavier.bueno@metempsy.com { 11913553Sjavier.bueno@metempsy.com PatternStrideEntry *found_entry = nullptr; 12013553Sjavier.bueno@metempsy.com for (auto &entry : strideEntries) { 12113553Sjavier.bueno@metempsy.com if (entry.stride == stride) { 12213553Sjavier.bueno@metempsy.com found_entry = &entry; 12313553Sjavier.bueno@metempsy.com break; 12413553Sjavier.bueno@metempsy.com } 12513553Sjavier.bueno@metempsy.com } 12613553Sjavier.bueno@metempsy.com return found_entry; 12713553Sjavier.bueno@metempsy.com } 12813553Sjavier.bueno@metempsy.com 12913553Sjavier.bueno@metempsy.com /** 13013553Sjavier.bueno@metempsy.com * Gets the entry with the provided stride, if there is no entry with 13113553Sjavier.bueno@metempsy.com * the associated stride, it replaces one of them. 13213553Sjavier.bueno@metempsy.com * @param stride the stride to find 13313553Sjavier.bueno@metempsy.com * @param max_counter_value maximum value of the confidence counters, 13413553Sjavier.bueno@metempsy.com * it is used when no strides are found and an entry needs to be 13513553Sjavier.bueno@metempsy.com * replaced 13613553Sjavier.bueno@metempsy.com * @result reference to the selected entry 13713553Sjavier.bueno@metempsy.com */ 13813553Sjavier.bueno@metempsy.com PatternStrideEntry &getStrideEntry(stride_t stride, 13913553Sjavier.bueno@metempsy.com uint8_t max_counter_value); 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 16013553Sjavier.bueno@metempsy.com * @param block block number within the page, this value can be negative, 16113553Sjavier.bueno@metempsy.com * which means that the block refered is actualy in the previous 16213553Sjavier.bueno@metempsy.com * page (ppn-1), if the value is greater than (pageBytes/blkSize-1) 16313553Sjavier.bueno@metempsy.com * then the block refers to a block within the next page (ppn+1) 16413553Sjavier.bueno@metempsy.com * @param is_secure whether this page is inside the secure memory area 16513553Sjavier.bueno@metempsy.com * @param addresses if allowed, the address will be added to this vector 16613553Sjavier.bueno@metempsy.com */ 16713553Sjavier.bueno@metempsy.com void addPrefetch(Addr ppn, stride_t block, bool is_secure, 16813553Sjavier.bueno@metempsy.com std::vector<AddrPriority> &addresses); 16913553Sjavier.bueno@metempsy.com 17013553Sjavier.bueno@metempsy.com /** 17113553Sjavier.bueno@metempsy.com * Obtains the SignatureEntry of the given page, if the page is not found, 17213553Sjavier.bueno@metempsy.com * it allocates a new one, replacing an existing entry if needed 17313553Sjavier.bueno@metempsy.com * @param ppn physical page number of the page 17413553Sjavier.bueno@metempsy.com * @param is_secure whether this page is inside the secure memory area 17513553Sjavier.bueno@metempsy.com * @param block accessed block within the page 17613553Sjavier.bueno@metempsy.com * @param miss output, if the entry is not found, this will be set to true 17713553Sjavier.bueno@metempsy.com * @result a reference to the SignatureEntry 17813553Sjavier.bueno@metempsy.com */ 17913553Sjavier.bueno@metempsy.com SignatureEntry & getSignatureEntry(Addr ppn, bool is_secure, 18013553Sjavier.bueno@metempsy.com stride_t block, bool &miss); 18113553Sjavier.bueno@metempsy.com /** 18213553Sjavier.bueno@metempsy.com * Obtains the PatternEntry of the given signature, if the signature is 18313553Sjavier.bueno@metempsy.com * not found, it allocates a new one, replacing an existing entry if needed 18413553Sjavier.bueno@metempsy.com * @param signature the signature of the desired entry 18513553Sjavier.bueno@metempsy.com * @result a reference to the PatternEntry 18613553Sjavier.bueno@metempsy.com */ 18713553Sjavier.bueno@metempsy.com PatternEntry & getPatternEntry(Addr signature); 18813553Sjavier.bueno@metempsy.com 18913553Sjavier.bueno@metempsy.com /** 19013553Sjavier.bueno@metempsy.com * Updates the pattern table with the provided signature and stride 19113553Sjavier.bueno@metempsy.com * @param signature the signature to use to index the pattern table 19213553Sjavier.bueno@metempsy.com * @param stride the stride to use to index the set of strides of the 19313553Sjavier.bueno@metempsy.com * pattern table entry 19413553Sjavier.bueno@metempsy.com */ 19513553Sjavier.bueno@metempsy.com void updatePatternTable(Addr signature, stride_t stride); 19613553Sjavier.bueno@metempsy.com 19713553Sjavier.bueno@metempsy.com public: 19813553Sjavier.bueno@metempsy.com SignaturePathPrefetcher(const SignaturePathPrefetcherParams* p); 19913553Sjavier.bueno@metempsy.com ~SignaturePathPrefetcher() {} 20013553Sjavier.bueno@metempsy.com void calculatePrefetch(const PrefetchInfo &pfi, 20113553Sjavier.bueno@metempsy.com std::vector<AddrPriority> &addresses) override; 20213553Sjavier.bueno@metempsy.com}; 20313553Sjavier.bueno@metempsy.com 20413553Sjavier.bueno@metempsy.com#endif//__MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__ 205