signature_path.hh revision 13553:047def1fa787
1/** 2 * Copyright (c) 2018 Metempsy Technology Consulting 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * Authors: Javier Bueno 29 */ 30 31 /** 32 * Implementation of the Signature Path Prefetcher 33 * 34 * References: 35 * Lookahead prefetching with signature path 36 * J Kim, PV Gratz, ALN Reddy 37 * The 2nd Data Prefetching Championship (DPC2) 38 * The filter feature described in the paper is not implemented, as it 39 * redundant prefetches are dropped by the cache. 40 */ 41 42#ifndef __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__ 43#define __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__ 44 45#include "mem/cache/prefetch/associative_set.hh" 46#include "mem/cache/prefetch/queued.hh" 47#include "mem/packet.hh" 48 49struct SignaturePathPrefetcherParams; 50 51class SignaturePathPrefetcher : public QueuedPrefetcher 52{ 53 /** Signature type */ 54 typedef uint16_t signature_t; 55 /** Stride type */ 56 typedef int16_t stride_t; 57 58 /** Number of strides stored in each pattern entry */ 59 const unsigned stridesPerPatternEntry; 60 /** Number of bits to shift when generating a new signature */ 61 const uint8_t signatureShift; 62 /** Size of the signature, in bits */ 63 const signature_t signatureBits; 64 /** Maximum pattern entries counter value */ 65 const uint8_t maxCounterValue; 66 /** Minimum confidence to issue a prefetch */ 67 const double prefetchConfidenceThreshold; 68 /** Minimum confidence to keep navigating lookahead entries */ 69 const double lookaheadConfidenceThreshold; 70 71 /** Signature entry data type */ 72 struct SignatureEntry : public TaggedEntry 73 { 74 /** Path signature */ 75 signature_t signature; 76 /** Last accessed block within a page */ 77 stride_t lastBlock; 78 SignatureEntry() : signature(0), lastBlock(0) 79 {} 80 }; 81 /** Signature table */ 82 AssociativeSet<SignatureEntry> signatureTable; 83 84 /** A stride entry with its counter */ 85 struct PatternStrideEntry 86 { 87 /** stride in a page in blkSize increments */ 88 stride_t stride; 89 /** counter value (max value defined by maxCounterValue) */ 90 uint8_t counter; 91 PatternStrideEntry() : stride(0), counter(0) 92 {} 93 }; 94 /** Pattern entry data type, a set of stride and counter entries */ 95 struct PatternEntry : public TaggedEntry 96 { 97 /** group of stides */ 98 std::vector<PatternStrideEntry> strideEntries; 99 PatternEntry(size_t num_strides) : strideEntries(num_strides) 100 {} 101 102 /** Reset the entries to their initial values */ 103 void reset() override 104 { 105 for (auto &entry : strideEntries) { 106 entry.counter = 0; 107 entry.stride = 0; 108 } 109 } 110 111 /** 112 * Returns the entry with the desired stride 113 * @param stride the stride to find 114 * @result a pointer to the entry, if the stride was found, or nullptr, 115 * if the stride was not found 116 */ 117 PatternStrideEntry *findStride(stride_t stride) 118 { 119 PatternStrideEntry *found_entry = nullptr; 120 for (auto &entry : strideEntries) { 121 if (entry.stride == stride) { 122 found_entry = &entry; 123 break; 124 } 125 } 126 return found_entry; 127 } 128 129 /** 130 * Gets the entry with the provided stride, if there is no entry with 131 * the associated stride, it replaces one of them. 132 * @param stride the stride to find 133 * @param max_counter_value maximum value of the confidence counters, 134 * it is used when no strides are found and an entry needs to be 135 * replaced 136 * @result reference to the selected entry 137 */ 138 PatternStrideEntry &getStrideEntry(stride_t stride, 139 uint8_t max_counter_value); 140 }; 141 /** Pattern table */ 142 AssociativeSet<PatternEntry> patternTable; 143 144 /** 145 * Generates a new signature from an existing one and a new stride 146 * @param sig current signature 147 * @param str stride to add to the new signature 148 * @result the new signature 149 */ 150 inline signature_t updateSignature(signature_t sig, stride_t str) const { 151 sig <<= signatureShift; 152 sig ^= str; 153 sig &= mask(signatureBits); 154 return sig; 155 } 156 157 /** 158 * Generates an address to be prefetched. 159 * @param ppn page number to prefetch from 160 * @param block block number within the page, this value can be negative, 161 * which means that the block refered is actualy in the previous 162 * page (ppn-1), if the value is greater than (pageBytes/blkSize-1) 163 * then the block refers to a block within the next page (ppn+1) 164 * @param is_secure whether this page is inside the secure memory area 165 * @param addresses if allowed, the address will be added to this vector 166 */ 167 void addPrefetch(Addr ppn, stride_t block, bool is_secure, 168 std::vector<AddrPriority> &addresses); 169 170 /** 171 * Obtains the SignatureEntry of the given page, if the page is not found, 172 * it allocates a new one, replacing an existing entry if needed 173 * @param ppn physical page number of the page 174 * @param is_secure whether this page is inside the secure memory area 175 * @param block accessed block within the page 176 * @param miss output, if the entry is not found, this will be set to true 177 * @result a reference to the SignatureEntry 178 */ 179 SignatureEntry & getSignatureEntry(Addr ppn, bool is_secure, 180 stride_t block, bool &miss); 181 /** 182 * Obtains the PatternEntry of the given signature, if the signature is 183 * not found, it allocates a new one, replacing an existing entry if needed 184 * @param signature the signature of the desired entry 185 * @result a reference to the PatternEntry 186 */ 187 PatternEntry & getPatternEntry(Addr signature); 188 189 /** 190 * Updates the pattern table with the provided signature and stride 191 * @param signature the signature to use to index the pattern table 192 * @param stride the stride to use to index the set of strides of the 193 * pattern table entry 194 */ 195 void updatePatternTable(Addr signature, stride_t stride); 196 197 public: 198 SignaturePathPrefetcher(const SignaturePathPrefetcherParams* p); 199 ~SignaturePathPrefetcher() {} 200 void calculatePrefetch(const PrefetchInfo &pfi, 201 std::vector<AddrPriority> &addresses) override; 202}; 203 204#endif//__MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__ 205