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