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