src/mem/cache/prefetch/access_map_pattern_matching.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  * Authors: Javier Bueno
  29  */
  30
  31  /**
  32   * Implementation of the Access Map Pattern Matching Prefetcher
  33   *
  34   * References:
  35   *     Access map pattern matching for high performance data cache prefetch.
  36   *     Ishii, Y., Inaba, M., & Hiraki, K. (2011).
  37   *     Journal of Instruction-Level Parallelism, 13, 1-24.
  38   */
  39
  40 #ifndef __MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__
  41 #define __MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__
  42
  43 #include "mem/cache/prefetch/associative_set.hh"
  44 #include "mem/cache/prefetch/queued.hh"
  45 #include "mem/packet.hh"
  46 #include "sim/clocked_object.hh"
  47
  48 struct AccessMapPatternMatchingParams;
  49
  50 class AccessMapPatternMatching : public ClockedObject
  51 {
  52     /** Cacheline size used by the prefetcher using this object */
  53     const unsigned blkSize;
  54     /** Limit the stride checking to -limitStride/+limitStride */
  55     const unsigned limitStride;
  56     /** Maximum number of prefetch generated */
  57     const unsigned startDegree;
  58     /** Amount of memory covered by a hot zone */
  59     const uint64_t hotZoneSize;
  60     /** A prefetch coverage factor bigger than this is considered high */
  61     const double highCoverageThreshold;
  62     /** A prefetch coverage factor smaller than this is considered low */
  63     const double lowCoverageThreshold;
  64     /** A prefetch accuracy factor bigger than this is considered high */
  65     const double highAccuracyThreshold;
  66     /** A prefetch accuracy factor smaller than this is considered low */
  67     const double lowAccuracyThreshold;
  68     /** A cache hit ratio bigger than this is considered high */
  69     const double highCacheHitThreshold;
  70     /** A cache hit ratio smaller than this is considered low */
  71     const double lowCacheHitThreshold;
  72     /** Cycles in an epoch period */
  73     const Cycles epochCycles;
  74     /** Off chip memory latency to use for the epoch bandwidth calculation */
  75     const Tick offChipMemoryLatency;
  76
  77     /** Data type representing the state of a cacheline in the access map */
  78     enum AccessMapState
  79     {
  80         AM_INIT,
  81         AM_PREFETCH,
  82         AM_ACCESS,
  83         AM_INVALID
  84     };
  85
  86     /** AccessMapEntry data type */
  87     struct AccessMapEntry : public TaggedEntry
  88     {
  89         /** vector containing the state of the cachelines in this zone */
  90         std::vector<AccessMapState> states;
  91
  92         AccessMapEntry(size_t num_entries) : states(num_entries, AM_INIT)
  93         {}
  94
  95         /** Reset the entries to their initial values */
  96         void reset() override
  97         {
  98             for (auto &entry : states) {
  99                 entry = AM_INIT;
 100             }
 101         }
 102     };
 103     /** Access map table */
 104     AssociativeSet<AccessMapEntry> accessMapTable;
 105
 106     /**
 107      * Number of good prefetches
 108      * - State transitions from PREFETCH to ACCESS
 109      */
 110     uint64_t numGoodPrefetches;
 111     /**
 112      * Number of prefetches issued
 113      * - State transitions from INIT to PREFETCH
 114      */
 115     uint64_t numTotalPrefetches;
 116     /**
 117      * Number of raw cache misses
 118      * - State transitions from INIT or PREFETCH to ACCESS
 119      */
 120     uint64_t numRawCacheMisses;
 121     /**
 122      * Number of raw cache hits
 123      * - State transitions from ACCESS to ACCESS
 124      */
 125     uint64_t numRawCacheHits;
 126     /** Current degree */
 127     unsigned degree;
 128     /** Current useful degree */
 129     unsigned usefulDegree;
 130
 131     /**
 132      * Given a target cacheline, this function checks if the cachelines
 133      * that follow the provided stride have been accessed. If so, the line
 134      * is considered a good candidate.
 135      * @param states vector containing the states of three contiguous hot zones
 136      * @param current target block (cacheline)
 137      * @param stride access stride to obtain the reference cachelines
 138      * @return true if current is a prefetch candidate
 139      */
 140     inline bool checkCandidate(std::vector<AccessMapState> const &states,
 141                         Addr current, int stride) const
 142     {
 143         enum AccessMapState tgt   = states[current - stride];
 144         enum AccessMapState s     = states[current + stride];
 145         enum AccessMapState s2    = states[current + 2 * stride];
 146         enum AccessMapState s2_p1 = states[current + 2 * stride + 1];
 147         return (tgt != AM_INVALID &&
 148                 ((s == AM_ACCESS && s2 == AM_ACCESS) ||
 149                 (s == AM_ACCESS && s2_p1 == AM_ACCESS)));
 150     }
 151
 152     /**
 153      * Obtain an AccessMapEntry  from the AccessMapTable, if the entry is not
 154      * found a new one is initialized and inserted.
 155      * @param am_addr address of the hot zone
 156      * @param is_secure whether the address belongs to the secure memory area
 157      * @return the corresponding entry
 158      */
 159     AccessMapEntry *getAccessMapEntry(Addr am_addr, bool is_secure);
 160
 161     /**
 162      * Updates the state of a block within an AccessMapEntry, also updates
 163      * the prefetcher metrics.
 164      * @param entry AccessMapEntry to update
 165      * @param block cacheline within the hot zone
 166      * @param state new state
 167      */
 168     void setEntryState(AccessMapEntry &entry, Addr block,
 169         enum AccessMapState state);
 170
 171     /**
 172      * This event constitues the epoch of the statistics that keep track of
 173      * the prefetcher accuracy, when this event triggers, the prefetcher degree
 174      * is adjusted and the statistics counters are reset.
 175      */
 176     void processEpochEvent();
 177     EventFunctionWrapper epochEvent;
 178
 179   public:
 180     AccessMapPatternMatching(const AccessMapPatternMatchingParams* p);
 181     ~AccessMapPatternMatching()
 182     {}
 183     void startup() override;
 184     void calculatePrefetch(const BasePrefetcher::PrefetchInfo &pfi,
 185         std::vector<QueuedPrefetcher::AddrPriority> &addresses);
 186 };
 187
 188 struct AMPMPrefetcherParams;
 189
 190 class AMPMPrefetcher : public QueuedPrefetcher
 191 {
 192     AccessMapPatternMatching &ampm;
 193   public:
 194     AMPMPrefetcher(const AMPMPrefetcherParams* p);
 195     ~AMPMPrefetcher()
 196     {}
 197     void calculatePrefetch(const PrefetchInfo &pfi,
 198                            std::vector<AddrPriority> &addresses) override;
 199 };
 200 #endif//__MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__