signature_path.hh revision 13963:94555f0223ba
15647Sgblack@eecs.umich.edu/** 25647Sgblack@eecs.umich.edu * Copyright (c) 2018 Metempsy Technology Consulting 35647Sgblack@eecs.umich.edu * All rights reserved. 45647Sgblack@eecs.umich.edu * 55647Sgblack@eecs.umich.edu * Redistribution and use in source and binary forms, with or without 65647Sgblack@eecs.umich.edu * modification, are permitted provided that the following conditions are 75647Sgblack@eecs.umich.edu * met: redistributions of source code must retain the above copyright 85647Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer; 95647Sgblack@eecs.umich.edu * redistributions in binary form must reproduce the above copyright 105647Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer in the 115647Sgblack@eecs.umich.edu * documentation and/or other materials provided with the distribution; 125647Sgblack@eecs.umich.edu * neither the name of the copyright holders nor the names of its 135647Sgblack@eecs.umich.edu * contributors may be used to endorse or promote products derived from 145647Sgblack@eecs.umich.edu * this software without specific prior written permission. 155647Sgblack@eecs.umich.edu * 165647Sgblack@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 175647Sgblack@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 185647Sgblack@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 195647Sgblack@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 205647Sgblack@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 215647Sgblack@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 225647Sgblack@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 235647Sgblack@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 245647Sgblack@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 255647Sgblack@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 265647Sgblack@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 275647Sgblack@eecs.umich.edu * 285647Sgblack@eecs.umich.edu * Authors: Javier Bueno 295647Sgblack@eecs.umich.edu */ 305647Sgblack@eecs.umich.edu 315647Sgblack@eecs.umich.edu /** 325647Sgblack@eecs.umich.edu * Implementation of the Signature Path Prefetcher 335647Sgblack@eecs.umich.edu * 345647Sgblack@eecs.umich.edu * References: 355647Sgblack@eecs.umich.edu * Lookahead prefetching with signature path 365647Sgblack@eecs.umich.edu * J Kim, PV Gratz, ALN Reddy 375647Sgblack@eecs.umich.edu * The 2nd Data Prefetching Championship (DPC2) 385647Sgblack@eecs.umich.edu * The filter feature described in the paper is not implemented, as it 395647Sgblack@eecs.umich.edu * redundant prefetches are dropped by the cache. 405647Sgblack@eecs.umich.edu */ 415647Sgblack@eecs.umich.edu 425647Sgblack@eecs.umich.edu#ifndef __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__ 435647Sgblack@eecs.umich.edu#define __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__ 445647Sgblack@eecs.umich.edu 455647Sgblack@eecs.umich.edu#include "base/sat_counter.hh" 465647Sgblack@eecs.umich.edu#include "mem/cache/prefetch/associative_set.hh" 475647Sgblack@eecs.umich.edu#include "mem/cache/prefetch/queued.hh" 485647Sgblack@eecs.umich.edu#include "mem/packet.hh" 495647Sgblack@eecs.umich.edu 505647Sgblack@eecs.umich.edustruct SignaturePathPrefetcherParams; 515647Sgblack@eecs.umich.edu 525647Sgblack@eecs.umich.educlass SignaturePathPrefetcher : public QueuedPrefetcher 535647Sgblack@eecs.umich.edu{ 545647Sgblack@eecs.umich.edu protected: 555647Sgblack@eecs.umich.edu /** Signature type */ 565647Sgblack@eecs.umich.edu typedef uint16_t signature_t; 575647Sgblack@eecs.umich.edu /** Stride type */ 585648Sgblack@eecs.umich.edu typedef int16_t stride_t; 595647Sgblack@eecs.umich.edu 605654Sgblack@eecs.umich.edu /** Number of strides stored in each pattern entry */ 615647Sgblack@eecs.umich.edu const unsigned stridesPerPatternEntry; 626137Sgblack@eecs.umich.edu /** Number of bits to shift when generating a new signature */ 636137Sgblack@eecs.umich.edu const uint8_t signatureShift; 646137Sgblack@eecs.umich.edu /** Size of the signature, in bits */ 655654Sgblack@eecs.umich.edu const signature_t signatureBits; 666046Sgblack@eecs.umich.edu /** Minimum confidence to issue a prefetch */ 675647Sgblack@eecs.umich.edu const double prefetchConfidenceThreshold; 685648Sgblack@eecs.umich.edu /** Minimum confidence to keep navigating lookahead entries */ 695648Sgblack@eecs.umich.edu const double lookaheadConfidenceThreshold; 705647Sgblack@eecs.umich.edu 715647Sgblack@eecs.umich.edu /** Signature entry data type */ 725647Sgblack@eecs.umich.edu struct SignatureEntry : public TaggedEntry 735647Sgblack@eecs.umich.edu { 745647Sgblack@eecs.umich.edu /** Path signature */ 755647Sgblack@eecs.umich.edu signature_t signature; 765647Sgblack@eecs.umich.edu /** Last accessed block within a page */ 775647Sgblack@eecs.umich.edu stride_t lastBlock; 785647Sgblack@eecs.umich.edu SignatureEntry() : signature(0), lastBlock(0) 795648Sgblack@eecs.umich.edu {} 805647Sgblack@eecs.umich.edu }; 815648Sgblack@eecs.umich.edu /** Signature table */ 825648Sgblack@eecs.umich.edu AssociativeSet<SignatureEntry> signatureTable; 835648Sgblack@eecs.umich.edu 845648Sgblack@eecs.umich.edu /** A stride entry with its counter */ 855648Sgblack@eecs.umich.edu struct PatternStrideEntry 865648Sgblack@eecs.umich.edu { 875648Sgblack@eecs.umich.edu /** stride in a page in blkSize increments */ 885648Sgblack@eecs.umich.edu stride_t stride; 895648Sgblack@eecs.umich.edu /** Saturating counter */ 905648Sgblack@eecs.umich.edu SatCounter counter; 915648Sgblack@eecs.umich.edu PatternStrideEntry(unsigned bits) : stride(0), counter(bits) 925648Sgblack@eecs.umich.edu {} 935648Sgblack@eecs.umich.edu }; 945648Sgblack@eecs.umich.edu /** Pattern entry data type, a set of stride and counter entries */ 955648Sgblack@eecs.umich.edu struct PatternEntry : public TaggedEntry 965648Sgblack@eecs.umich.edu { 975648Sgblack@eecs.umich.edu /** group of stides */ 985648Sgblack@eecs.umich.edu std::vector<PatternStrideEntry> strideEntries; 995648Sgblack@eecs.umich.edu /** use counter, used by SPPv2 */ 1005648Sgblack@eecs.umich.edu SatCounter counter; 1015648Sgblack@eecs.umich.edu PatternEntry(size_t num_strides, unsigned counter_bits) 1025648Sgblack@eecs.umich.edu : strideEntries(num_strides, counter_bits), counter(counter_bits) 1035648Sgblack@eecs.umich.edu {} 1045648Sgblack@eecs.umich.edu 1055648Sgblack@eecs.umich.edu /** Reset the entries to their initial values */ 1065648Sgblack@eecs.umich.edu void reset() override 1075648Sgblack@eecs.umich.edu { 1085648Sgblack@eecs.umich.edu for (auto &entry : strideEntries) { 1095648Sgblack@eecs.umich.edu entry.counter.reset(); 1105648Sgblack@eecs.umich.edu entry.stride = 0; 1115648Sgblack@eecs.umich.edu } 1125648Sgblack@eecs.umich.edu counter.reset(); 1135648Sgblack@eecs.umich.edu } 1145648Sgblack@eecs.umich.edu 1155648Sgblack@eecs.umich.edu /** 1165648Sgblack@eecs.umich.edu * Returns the entry with the desired stride 1175648Sgblack@eecs.umich.edu * @param stride the stride to find 1185648Sgblack@eecs.umich.edu * @result a pointer to the entry, if the stride was found, or nullptr, 1195648Sgblack@eecs.umich.edu * if the stride was not found 1205648Sgblack@eecs.umich.edu */ 1215648Sgblack@eecs.umich.edu PatternStrideEntry *findStride(stride_t stride) 1225648Sgblack@eecs.umich.edu { 1235648Sgblack@eecs.umich.edu PatternStrideEntry *found_entry = nullptr; 1245648Sgblack@eecs.umich.edu for (auto &entry : strideEntries) { 1255648Sgblack@eecs.umich.edu if (entry.stride == stride) { 1265648Sgblack@eecs.umich.edu found_entry = &entry; 1275648Sgblack@eecs.umich.edu break; 1285648Sgblack@eecs.umich.edu } 1295648Sgblack@eecs.umich.edu } 1305648Sgblack@eecs.umich.edu return found_entry; 1315648Sgblack@eecs.umich.edu } 1325648Sgblack@eecs.umich.edu 1335648Sgblack@eecs.umich.edu /** 1345648Sgblack@eecs.umich.edu * Gets the entry with the provided stride, if there is no entry with 1355648Sgblack@eecs.umich.edu * the associated stride, it replaces one of them. 1365648Sgblack@eecs.umich.edu * @param stride the stride to find 1375648Sgblack@eecs.umich.edu * @result reference to the selected entry 1385648Sgblack@eecs.umich.edu */ 1395648Sgblack@eecs.umich.edu PatternStrideEntry &getStrideEntry(stride_t stride); 1405648Sgblack@eecs.umich.edu }; 1415648Sgblack@eecs.umich.edu /** Pattern table */ 1425648Sgblack@eecs.umich.edu AssociativeSet<PatternEntry> patternTable; 1435648Sgblack@eecs.umich.edu 1445648Sgblack@eecs.umich.edu /** 1455648Sgblack@eecs.umich.edu * Generates a new signature from an existing one and a new stride 1465648Sgblack@eecs.umich.edu * @param sig current signature 1475648Sgblack@eecs.umich.edu * @param str stride to add to the new signature 1485648Sgblack@eecs.umich.edu * @result the new signature 1495648Sgblack@eecs.umich.edu */ 1505648Sgblack@eecs.umich.edu inline signature_t updateSignature(signature_t sig, stride_t str) const { 1515648Sgblack@eecs.umich.edu sig <<= signatureShift; 1525648Sgblack@eecs.umich.edu sig ^= str; 1535648Sgblack@eecs.umich.edu sig &= mask(signatureBits); 1545648Sgblack@eecs.umich.edu return sig; 1555648Sgblack@eecs.umich.edu } 1565648Sgblack@eecs.umich.edu 1575648Sgblack@eecs.umich.edu /** 1585648Sgblack@eecs.umich.edu * Generates an address to be prefetched. 1595648Sgblack@eecs.umich.edu * @param ppn page number to prefetch from 1605648Sgblack@eecs.umich.edu * @param last_block last accessed block within the page ppn 1615648Sgblack@eecs.umich.edu * @param delta difference, in number of blocks, from the last_block 1625648Sgblack@eecs.umich.edu * accessed to the block to prefetch. The block to prefetch is 1635648Sgblack@eecs.umich.edu * computed by this formula: 1645648Sgblack@eecs.umich.edu * ppn * pageBytes + (last_block + delta) * blkSize 1655648Sgblack@eecs.umich.edu * This value can be negative. 1665648Sgblack@eecs.umich.edu * @param path_confidence the confidence factor of this prefetch 1675648Sgblack@eecs.umich.edu * @param signature the current path signature 1685648Sgblack@eecs.umich.edu * @param is_secure whether this page is inside the secure memory area 1695648Sgblack@eecs.umich.edu * @param addresses addresses to prefetch will be added to this vector 1705648Sgblack@eecs.umich.edu */ 1715648Sgblack@eecs.umich.edu void addPrefetch(Addr ppn, stride_t last_block, stride_t delta, 1725648Sgblack@eecs.umich.edu double path_confidence, signature_t signature, 1735648Sgblack@eecs.umich.edu bool is_secure, 1745648Sgblack@eecs.umich.edu std::vector<AddrPriority> &addresses); 1755648Sgblack@eecs.umich.edu 1765648Sgblack@eecs.umich.edu /** 1775648Sgblack@eecs.umich.edu * Obtains the SignatureEntry of the given page, if the page is not found, 1785648Sgblack@eecs.umich.edu * it allocates a new one, replacing an existing entry if needed 1795648Sgblack@eecs.umich.edu * It also provides the stride of the current block and the initial 1805648Sgblack@eecs.umich.edu * path confidence of the corresponding entry 1815648Sgblack@eecs.umich.edu * @param ppn physical page number of the page 1825648Sgblack@eecs.umich.edu * @param is_secure whether this page is inside the secure memory area 1835648Sgblack@eecs.umich.edu * @param block accessed block within the page 1845648Sgblack@eecs.umich.edu * @param miss if the entry is not found, this will be set to true 1855648Sgblack@eecs.umich.edu * @param stride set to the computed stride 1865648Sgblack@eecs.umich.edu * @param initial_confidence set to the initial confidence value 1875648Sgblack@eecs.umich.edu * @result a reference to the SignatureEntry 1885648Sgblack@eecs.umich.edu */ 1895648Sgblack@eecs.umich.edu SignatureEntry &getSignatureEntry(Addr ppn, bool is_secure, stride_t block, 1905648Sgblack@eecs.umich.edu bool &miss, stride_t &stride, double &initial_confidence); 1915648Sgblack@eecs.umich.edu /** 1925648Sgblack@eecs.umich.edu * Obtains the PatternEntry of the given signature, if the signature is 1935648Sgblack@eecs.umich.edu * not found, it allocates a new one, replacing an existing entry if needed 1945648Sgblack@eecs.umich.edu * @param signature the signature of the desired entry 1955648Sgblack@eecs.umich.edu * @result a reference to the PatternEntry 1965648Sgblack@eecs.umich.edu */ 1975648Sgblack@eecs.umich.edu PatternEntry& getPatternEntry(Addr signature); 1985648Sgblack@eecs.umich.edu 1995648Sgblack@eecs.umich.edu /** 2005648Sgblack@eecs.umich.edu * Updates the pattern table with the provided signature and stride 2015648Sgblack@eecs.umich.edu * @param signature the signature to use to index the pattern table 2025648Sgblack@eecs.umich.edu * @param stride the stride to use to index the set of strides of the 2035648Sgblack@eecs.umich.edu * pattern table entry 2045648Sgblack@eecs.umich.edu */ 2055648Sgblack@eecs.umich.edu void updatePatternTable(Addr signature, stride_t stride); 2065648Sgblack@eecs.umich.edu 2075648Sgblack@eecs.umich.edu /** 2085648Sgblack@eecs.umich.edu * Computes the lookahead path confidence of the provided pattern entry 2095648Sgblack@eecs.umich.edu * @param sig the PatternEntry to use 2105648Sgblack@eecs.umich.edu * @param lookahead PatternStrideEntry within the provided PatternEntry 2115648Sgblack@eecs.umich.edu * @return the computed confidence factor 2125648Sgblack@eecs.umich.edu */ 2135648Sgblack@eecs.umich.edu virtual double calculateLookaheadConfidence(PatternEntry const &sig, 2145648Sgblack@eecs.umich.edu PatternStrideEntry const &lookahead) const; 2155648Sgblack@eecs.umich.edu 2165648Sgblack@eecs.umich.edu /** 2175648Sgblack@eecs.umich.edu * Computes the prefetch confidence of the provided pattern entry 2185648Sgblack@eecs.umich.edu * @param sig the PatternEntry to use 2195648Sgblack@eecs.umich.edu * @param entry PatternStrideEntry within the provided PatternEntry 2205648Sgblack@eecs.umich.edu * @return the computed confidence factor 2215648Sgblack@eecs.umich.edu */ 2225648Sgblack@eecs.umich.edu virtual double calculatePrefetchConfidence(PatternEntry const &sig, 2235648Sgblack@eecs.umich.edu PatternStrideEntry const &entry) const; 2245649Sgblack@eecs.umich.edu 2255649Sgblack@eecs.umich.edu /** 2265649Sgblack@eecs.umich.edu * Increases the counter of a given PatternEntry/PatternStrideEntry 2275648Sgblack@eecs.umich.edu * @param pattern_entry the corresponding PatternEntry 2285898Sgblack@eecs.umich.edu * @param pstride_entry the PatternStrideEntry within the PatternEntry 2295648Sgblack@eecs.umich.edu */ 2305648Sgblack@eecs.umich.edu virtual void increasePatternEntryCounter(PatternEntry &pattern_entry, 2315648Sgblack@eecs.umich.edu PatternStrideEntry &pstride_entry); 2325648Sgblack@eecs.umich.edu 2335648Sgblack@eecs.umich.edu /** 2345648Sgblack@eecs.umich.edu * Whenever a new SignatureEntry is allocated, it computes the new 2355648Sgblack@eecs.umich.edu * signature to be used with the new entry, the resulting stride and the 2365648Sgblack@eecs.umich.edu * initial path confidence of the new entry. 2375648Sgblack@eecs.umich.edu * @param current_block accessed block within the page of the associated 2385648Sgblack@eecs.umich.edu entry 2395648Sgblack@eecs.umich.edu * @param new_signature new signature of the allocated entry 2405648Sgblack@eecs.umich.edu * @param new_conf the initial path confidence of this entry 2415648Sgblack@eecs.umich.edu * @param new_stride the resulting current stride 2425649Sgblack@eecs.umich.edu */ 2435649Sgblack@eecs.umich.edu virtual void handleSignatureTableMiss(stride_t current_block, 2445649Sgblack@eecs.umich.edu signature_t &new_signature, double &new_conf, 2455648Sgblack@eecs.umich.edu stride_t &new_stride); 2465898Sgblack@eecs.umich.edu 2475648Sgblack@eecs.umich.edu /** 2485647Sgblack@eecs.umich.edu * Auxiliar prefetch mechanism used at the end of calculatePrefetch. 2495691Sgblack@eecs.umich.edu * This prefetcher uses this to activate the next line prefetcher if 2505691Sgblack@eecs.umich.edu * no prefetch candidates have been found. 2515691Sgblack@eecs.umich.edu * @param ppn physical page number of the current accessed page 2525691Sgblack@eecs.umich.edu * @param current_block last accessed block within the page ppn 2535691Sgblack@eecs.umich.edu * @param is_secure whether this page is inside the secure memory area 2545691Sgblack@eecs.umich.edu * @param addresses the addresses to be prefetched are added to this vector 2555691Sgblack@eecs.umich.edu * @param updated_filter_entries set of addresses containing these that 2565691Sgblack@eecs.umich.edu * their filter has been updated, if this call updates a new entry 2575691Sgblack@eecs.umich.edu */ 2585691Sgblack@eecs.umich.edu virtual void auxiliaryPrefetcher(Addr ppn, stride_t current_block, 2595691Sgblack@eecs.umich.edu bool is_secure, std::vector<AddrPriority> &addresses); 2605691Sgblack@eecs.umich.edu 2615691Sgblack@eecs.umich.edu /** 2625691Sgblack@eecs.umich.edu * Handles the situation when the lookahead process has crossed the 2635691Sgblack@eecs.umich.edu * boundaries of the current page. This is not fully described in the 2645691Sgblack@eecs.umich.edu * paper that was used to implement this code, however, the article 2655691Sgblack@eecs.umich.edu * describing the upgraded version of this prefetcher provides some 2665691Sgblack@eecs.umich.edu * details. For this prefetcher, there are no specific actions to be 2675691Sgblack@eecs.umich.edu * done. 2685691Sgblack@eecs.umich.edu * @param signature the lookahead signature that crossed the page 2695691Sgblack@eecs.umich.edu * @param delta the current stride that caused it 2705691Sgblack@eecs.umich.edu * @param last_offset the last accessed block within the page 2715691Sgblack@eecs.umich.edu * @param path_confidence the path confidence at the moment of crossing 2725691Sgblack@eecs.umich.edu */ 2735691Sgblack@eecs.umich.edu virtual void handlePageCrossingLookahead(signature_t signature, 2745691Sgblack@eecs.umich.edu stride_t last_offset, stride_t delta, double path_confidence) { 2755691Sgblack@eecs.umich.edu } 2765691Sgblack@eecs.umich.edu 2775691Sgblack@eecs.umich.edu public: 2785691Sgblack@eecs.umich.edu SignaturePathPrefetcher(const SignaturePathPrefetcherParams* p); 2795691Sgblack@eecs.umich.edu ~SignaturePathPrefetcher() {} 2805691Sgblack@eecs.umich.edu void calculatePrefetch(const PrefetchInfo &pfi, 2815691Sgblack@eecs.umich.edu std::vector<AddrPriority> &addresses) override; 2825691Sgblack@eecs.umich.edu}; 2835691Sgblack@eecs.umich.edu 2845691Sgblack@eecs.umich.edu#endif//__MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__ 2855691Sgblack@eecs.umich.edu