src/mem/cache/prefetch/indirect_memory.hh

   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
  29 /**
  30  * Implementation of the Indirect Memory Prefetcher
  31  *
  32  * References:
  33  * IMP: Indirect memory prefetcher.
  34  * Yu, X., Hughes, C. J., Satish, N., & Devadas, S. (2015, December).
  35  * In Proceedings of the 48th International Symposium on Microarchitecture
  36  * (pp. 178-190). ACM.
  37  */
  38
  39 #ifndef __MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__
  40 #define __MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__
  41
  42 #include <vector>
  43
  44 #include "base/sat_counter.hh"
  45 #include "mem/cache/prefetch/associative_set.hh"
  46 #include "mem/cache/prefetch/queued.hh"
  47
  48 struct IndirectMemoryPrefetcherParams;
  49
  50 namespace Prefetcher {
  51
  52 class IndirectMemory : public Queued
  53 {
  54     /** Maximum number of prefetches generated per event */
  55     const unsigned int maxPrefetchDistance;
  56     /** Shift values considered */
  57     const std::vector<int> shiftValues;
  58     /** Counter threshold to start prefetching */
  59     const unsigned int prefetchThreshold;
  60     /** streamCounter value to trigger the streaming prefetcher */
  61     const int streamCounterThreshold;
  62     /** Number of prefetches generated when using the streaming prefetcher */
  63     const int streamingDistance;
  64
  65     /** Prefetch Table Entry */
  66     struct PrefetchTableEntry : public TaggedEntry
  67     {
  68         /* Stream table fields */
  69
  70         /** Accessed address */
  71         Addr address;
  72         /** Whether this address is in the secure region */
  73         bool secure;
  74         /** Confidence counter of the stream */
  75         unsigned int streamCounter;
  76
  77         /* Indirect table fields */
  78
  79         /** Enable bit of the indirect fields */
  80         bool enabled;
  81         /** Current index value */
  82         int64_t index;
  83         /** BaseAddr detected */
  84         Addr baseAddr;
  85         /** Shift detected */
  86         int shift;
  87         /** Confidence counter of the indirect fields */
  88         SatCounter indirectCounter;
  89         /**
  90          * This variable is set to indicate that there has been at least one
  91          * match with the current index value. This information is later used
  92          * when a new index is updated. If there were no increases in the
  93          * indirectCounter, the counter is decremented.
  94          */
  95         bool increasedIndirectCounter;
  96
  97         PrefetchTableEntry(unsigned indirect_counter_bits)
  98             : TaggedEntry(), address(0), secure(false), streamCounter(0),
  99               enabled(false), index(0), baseAddr(0), shift(0),
 100               indirectCounter(indirect_counter_bits),
 101               increasedIndirectCounter(false)
 102         {}
 103
 104         void
 105         invalidate() override
 106         {
 107             TaggedEntry::invalidate();
 108             address = 0;
 109             secure = false;
 110             streamCounter = 0;
 111             enabled = false;
 112             index = 0;
 113             baseAddr = 0;
 114             shift = 0;
 115             indirectCounter.reset();
 116             increasedIndirectCounter = false;
 117         }
 118     };
 119     /** Prefetch table */
 120     AssociativeSet<PrefetchTableEntry> prefetchTable;
 121
 122     /** Indirect Pattern Detector entrt */
 123     struct IndirectPatternDetectorEntry : public TaggedEntry
 124     {
 125         /** First index */
 126         int64_t idx1;
 127         /** Second index */
 128         int64_t idx2;
 129         /** Valid bit for the second index */
 130         bool secondIndexSet;
 131         /** Number of misses currently recorded */
 132         int numMisses;
 133         /**
 134          * Potential BaseAddr candidates for each recorded miss.
 135          * The number of candidates per miss is determined by the number of
 136          * elements in the shiftValues array.
 137          */
 138         std::vector<std::vector<Addr>> baseAddr;
 139
 140         IndirectPatternDetectorEntry(unsigned int num_addresses,
 141                                      unsigned int num_shifts)
 142           : TaggedEntry(), idx1(0), idx2(0), secondIndexSet(false),
 143             numMisses(0),
 144             baseAddr(num_addresses, std::vector<Addr>(num_shifts))
 145         {
 146         }
 147
 148         void
 149         invalidate() override
 150         {
 151             TaggedEntry::invalidate();
 152             idx1 = 0;
 153             idx2 = 0;
 154             secondIndexSet = false;
 155             numMisses = 0;
 156         }
 157     };
 158     /** Indirect Pattern Detector (IPD) table */
 159     AssociativeSet<IndirectPatternDetectorEntry> ipd;
 160
 161     /** Entry currently tracking misses */
 162     IndirectPatternDetectorEntry *ipdEntryTrackingMisses;
 163
 164     /** Byte order used to access the cache */
 165     const ByteOrder byteOrder;
 166
 167     /**
 168      * Allocate or update an entry in the IPD
 169      * @param pt_entry Pointer to the associated page table entry
 170      * @param index Detected first index value
 171      */
 172     void allocateOrUpdateIPDEntry(const PrefetchTableEntry *pt_entry,
 173                                   int64_t index);
 174     /**
 175      * Update an IPD entry with a detected miss address, when the first index
 176      * is being tracked
 177      * @param miss_addr The address that caused the miss
 178      */
 179     void trackMissIndex1(Addr miss_addr);
 180
 181     /**
 182      * Update an IPD entry with a detected miss address, when the second index
 183      * is being tracked
 184      * @param miss_addr The address that caused the miss
 185      */
 186     void trackMissIndex2(Addr miss_addr);
 187
 188     /**
 189      * Checks if an access to the cache matches any active PT entry, if so,
 190      * the indirect confidence counter is incremented
 191      * @param addr address of the access
 192      */
 193     void checkAccessMatchOnActiveEntries(Addr addr);
 194
 195   public:
 196     IndirectMemory(const IndirectMemoryPrefetcherParams &p);
 197     ~IndirectMemory() = default;
 198
 199     void calculatePrefetch(const PrefetchInfo &pfi,
 200                            std::vector<AddrPriority> &addresses) override;
 201 };
 202
 203 } // namespace Prefetcher
 204
 205 #endif//__MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__