113554Sjavier.bueno@metempsy.com/** 213554Sjavier.bueno@metempsy.com * Copyright (c) 2018 Metempsy Technology Consulting 313554Sjavier.bueno@metempsy.com * All rights reserved. 413554Sjavier.bueno@metempsy.com * 513554Sjavier.bueno@metempsy.com * Redistribution and use in source and binary forms, with or without 613554Sjavier.bueno@metempsy.com * modification, are permitted provided that the following conditions are 713554Sjavier.bueno@metempsy.com * met: redistributions of source code must retain the above copyright 813554Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer; 913554Sjavier.bueno@metempsy.com * redistributions in binary form must reproduce the above copyright 1013554Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer in the 1113554Sjavier.bueno@metempsy.com * documentation and/or other materials provided with the distribution; 1213554Sjavier.bueno@metempsy.com * neither the name of the copyright holders nor the names of its 1313554Sjavier.bueno@metempsy.com * contributors may be used to endorse or promote products derived from 1413554Sjavier.bueno@metempsy.com * this software without specific prior written permission. 1513554Sjavier.bueno@metempsy.com * 1613554Sjavier.bueno@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713554Sjavier.bueno@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813554Sjavier.bueno@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913554Sjavier.bueno@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013554Sjavier.bueno@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113554Sjavier.bueno@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213554Sjavier.bueno@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313554Sjavier.bueno@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413554Sjavier.bueno@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513554Sjavier.bueno@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613554Sjavier.bueno@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713554Sjavier.bueno@metempsy.com * 2813554Sjavier.bueno@metempsy.com * Authors: Javier Bueno 2913554Sjavier.bueno@metempsy.com */ 3013554Sjavier.bueno@metempsy.com 3113554Sjavier.bueno@metempsy.com /** 3213554Sjavier.bueno@metempsy.com * Implementation of the Access Map Pattern Matching Prefetcher 3313554Sjavier.bueno@metempsy.com * 3413554Sjavier.bueno@metempsy.com * References: 3513554Sjavier.bueno@metempsy.com * Access map pattern matching for high performance data cache prefetch. 3613554Sjavier.bueno@metempsy.com * Ishii, Y., Inaba, M., & Hiraki, K. (2011). 3713554Sjavier.bueno@metempsy.com * Journal of Instruction-Level Parallelism, 13, 1-24. 3813554Sjavier.bueno@metempsy.com */ 3913554Sjavier.bueno@metempsy.com 4013554Sjavier.bueno@metempsy.com#ifndef __MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__ 4113554Sjavier.bueno@metempsy.com#define __MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__ 4213554Sjavier.bueno@metempsy.com 4313554Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/associative_set.hh" 4413554Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/queued.hh" 4513554Sjavier.bueno@metempsy.com#include "mem/packet.hh" 4613700Sjavier.bueno@metempsy.com#include "sim/clocked_object.hh" 4713554Sjavier.bueno@metempsy.com 4813700Sjavier.bueno@metempsy.comstruct AccessMapPatternMatchingParams; 4913554Sjavier.bueno@metempsy.com 5013700Sjavier.bueno@metempsy.comclass AccessMapPatternMatching : public ClockedObject 5113554Sjavier.bueno@metempsy.com{ 5213700Sjavier.bueno@metempsy.com /** Cacheline size used by the prefetcher using this object */ 5313700Sjavier.bueno@metempsy.com const unsigned blkSize; 5413700Sjavier.bueno@metempsy.com /** Limit the stride checking to -limitStride/+limitStride */ 5513700Sjavier.bueno@metempsy.com const unsigned limitStride; 5613554Sjavier.bueno@metempsy.com /** Maximum number of prefetch generated */ 5713554Sjavier.bueno@metempsy.com const unsigned startDegree; 5813554Sjavier.bueno@metempsy.com /** Amount of memory covered by a hot zone */ 5913554Sjavier.bueno@metempsy.com const uint64_t hotZoneSize; 6013554Sjavier.bueno@metempsy.com /** A prefetch coverage factor bigger than this is considered high */ 6113554Sjavier.bueno@metempsy.com const double highCoverageThreshold; 6213554Sjavier.bueno@metempsy.com /** A prefetch coverage factor smaller than this is considered low */ 6313554Sjavier.bueno@metempsy.com const double lowCoverageThreshold; 6413554Sjavier.bueno@metempsy.com /** A prefetch accuracy factor bigger than this is considered high */ 6513554Sjavier.bueno@metempsy.com const double highAccuracyThreshold; 6613554Sjavier.bueno@metempsy.com /** A prefetch accuracy factor smaller than this is considered low */ 6713554Sjavier.bueno@metempsy.com const double lowAccuracyThreshold; 6813554Sjavier.bueno@metempsy.com /** A cache hit ratio bigger than this is considered high */ 6913554Sjavier.bueno@metempsy.com const double highCacheHitThreshold; 7013554Sjavier.bueno@metempsy.com /** A cache hit ratio smaller than this is considered low */ 7113554Sjavier.bueno@metempsy.com const double lowCacheHitThreshold; 7213554Sjavier.bueno@metempsy.com /** Cycles in an epoch period */ 7313554Sjavier.bueno@metempsy.com const Cycles epochCycles; 7413554Sjavier.bueno@metempsy.com /** Off chip memory latency to use for the epoch bandwidth calculation */ 7513554Sjavier.bueno@metempsy.com const Tick offChipMemoryLatency; 7613554Sjavier.bueno@metempsy.com 7713554Sjavier.bueno@metempsy.com /** Data type representing the state of a cacheline in the access map */ 7813554Sjavier.bueno@metempsy.com enum AccessMapState 7913554Sjavier.bueno@metempsy.com { 8013554Sjavier.bueno@metempsy.com AM_INIT, 8113554Sjavier.bueno@metempsy.com AM_PREFETCH, 8213554Sjavier.bueno@metempsy.com AM_ACCESS, 8313554Sjavier.bueno@metempsy.com AM_INVALID 8413554Sjavier.bueno@metempsy.com }; 8513554Sjavier.bueno@metempsy.com 8613554Sjavier.bueno@metempsy.com /** AccessMapEntry data type */ 8713554Sjavier.bueno@metempsy.com struct AccessMapEntry : public TaggedEntry 8813554Sjavier.bueno@metempsy.com { 8913554Sjavier.bueno@metempsy.com /** vector containing the state of the cachelines in this zone */ 9013554Sjavier.bueno@metempsy.com std::vector<AccessMapState> states; 9113554Sjavier.bueno@metempsy.com 9213554Sjavier.bueno@metempsy.com AccessMapEntry(size_t num_entries) : states(num_entries, AM_INIT) 9313554Sjavier.bueno@metempsy.com {} 9413554Sjavier.bueno@metempsy.com 9513554Sjavier.bueno@metempsy.com /** Reset the entries to their initial values */ 9613554Sjavier.bueno@metempsy.com void reset() override 9713554Sjavier.bueno@metempsy.com { 9813554Sjavier.bueno@metempsy.com for (auto &entry : states) { 9913554Sjavier.bueno@metempsy.com entry = AM_INIT; 10013554Sjavier.bueno@metempsy.com } 10113554Sjavier.bueno@metempsy.com } 10213554Sjavier.bueno@metempsy.com }; 10313554Sjavier.bueno@metempsy.com /** Access map table */ 10413554Sjavier.bueno@metempsy.com AssociativeSet<AccessMapEntry> accessMapTable; 10513554Sjavier.bueno@metempsy.com 10613554Sjavier.bueno@metempsy.com /** 10713554Sjavier.bueno@metempsy.com * Number of good prefetches 10813554Sjavier.bueno@metempsy.com * - State transitions from PREFETCH to ACCESS 10913554Sjavier.bueno@metempsy.com */ 11013554Sjavier.bueno@metempsy.com uint64_t numGoodPrefetches; 11113554Sjavier.bueno@metempsy.com /** 11213554Sjavier.bueno@metempsy.com * Number of prefetches issued 11313554Sjavier.bueno@metempsy.com * - State transitions from INIT to PREFETCH 11413554Sjavier.bueno@metempsy.com */ 11513554Sjavier.bueno@metempsy.com uint64_t numTotalPrefetches; 11613554Sjavier.bueno@metempsy.com /** 11713554Sjavier.bueno@metempsy.com * Number of raw cache misses 11813554Sjavier.bueno@metempsy.com * - State transitions from INIT or PREFETCH to ACCESS 11913554Sjavier.bueno@metempsy.com */ 12013554Sjavier.bueno@metempsy.com uint64_t numRawCacheMisses; 12113554Sjavier.bueno@metempsy.com /** 12213554Sjavier.bueno@metempsy.com * Number of raw cache hits 12313554Sjavier.bueno@metempsy.com * - State transitions from ACCESS to ACCESS 12413554Sjavier.bueno@metempsy.com */ 12513554Sjavier.bueno@metempsy.com uint64_t numRawCacheHits; 12613554Sjavier.bueno@metempsy.com /** Current degree */ 12713554Sjavier.bueno@metempsy.com unsigned degree; 12813554Sjavier.bueno@metempsy.com /** Current useful degree */ 12913554Sjavier.bueno@metempsy.com unsigned usefulDegree; 13013554Sjavier.bueno@metempsy.com 13113554Sjavier.bueno@metempsy.com /** 13213554Sjavier.bueno@metempsy.com * Given a target cacheline, this function checks if the cachelines 13313554Sjavier.bueno@metempsy.com * that follow the provided stride have been accessed. If so, the line 13413554Sjavier.bueno@metempsy.com * is considered a good candidate. 13513554Sjavier.bueno@metempsy.com * @param states vector containing the states of three contiguous hot zones 13613554Sjavier.bueno@metempsy.com * @param current target block (cacheline) 13713554Sjavier.bueno@metempsy.com * @param stride access stride to obtain the reference cachelines 13813554Sjavier.bueno@metempsy.com * @return true if current is a prefetch candidate 13913554Sjavier.bueno@metempsy.com */ 14013554Sjavier.bueno@metempsy.com inline bool checkCandidate(std::vector<AccessMapState> const &states, 14113554Sjavier.bueno@metempsy.com Addr current, int stride) const 14213554Sjavier.bueno@metempsy.com { 14313554Sjavier.bueno@metempsy.com enum AccessMapState tgt = states[current - stride]; 14413554Sjavier.bueno@metempsy.com enum AccessMapState s = states[current + stride]; 14513554Sjavier.bueno@metempsy.com enum AccessMapState s2 = states[current + 2 * stride]; 14613554Sjavier.bueno@metempsy.com enum AccessMapState s2_p1 = states[current + 2 * stride + 1]; 14713554Sjavier.bueno@metempsy.com return (tgt != AM_INVALID && 14813554Sjavier.bueno@metempsy.com ((s == AM_ACCESS && s2 == AM_ACCESS) || 14913554Sjavier.bueno@metempsy.com (s == AM_ACCESS && s2_p1 == AM_ACCESS))); 15013554Sjavier.bueno@metempsy.com } 15113554Sjavier.bueno@metempsy.com 15213554Sjavier.bueno@metempsy.com /** 15313554Sjavier.bueno@metempsy.com * Obtain an AccessMapEntry from the AccessMapTable, if the entry is not 15413554Sjavier.bueno@metempsy.com * found a new one is initialized and inserted. 15513554Sjavier.bueno@metempsy.com * @param am_addr address of the hot zone 15613554Sjavier.bueno@metempsy.com * @param is_secure whether the address belongs to the secure memory area 15713554Sjavier.bueno@metempsy.com * @return the corresponding entry 15813554Sjavier.bueno@metempsy.com */ 15913554Sjavier.bueno@metempsy.com AccessMapEntry *getAccessMapEntry(Addr am_addr, bool is_secure); 16013554Sjavier.bueno@metempsy.com 16113554Sjavier.bueno@metempsy.com /** 16213554Sjavier.bueno@metempsy.com * Updates the state of a block within an AccessMapEntry, also updates 16313554Sjavier.bueno@metempsy.com * the prefetcher metrics. 16413554Sjavier.bueno@metempsy.com * @param entry AccessMapEntry to update 16513554Sjavier.bueno@metempsy.com * @param block cacheline within the hot zone 16613554Sjavier.bueno@metempsy.com * @param state new state 16713554Sjavier.bueno@metempsy.com */ 16813554Sjavier.bueno@metempsy.com void setEntryState(AccessMapEntry &entry, Addr block, 16913554Sjavier.bueno@metempsy.com enum AccessMapState state); 17013554Sjavier.bueno@metempsy.com 17113554Sjavier.bueno@metempsy.com /** 17213554Sjavier.bueno@metempsy.com * This event constitues the epoch of the statistics that keep track of 17313554Sjavier.bueno@metempsy.com * the prefetcher accuracy, when this event triggers, the prefetcher degree 17413554Sjavier.bueno@metempsy.com * is adjusted and the statistics counters are reset. 17513554Sjavier.bueno@metempsy.com */ 17613554Sjavier.bueno@metempsy.com void processEpochEvent(); 17713554Sjavier.bueno@metempsy.com EventFunctionWrapper epochEvent; 17813554Sjavier.bueno@metempsy.com 17913554Sjavier.bueno@metempsy.com public: 18013700Sjavier.bueno@metempsy.com AccessMapPatternMatching(const AccessMapPatternMatchingParams* p); 18113700Sjavier.bueno@metempsy.com ~AccessMapPatternMatching() 18213700Sjavier.bueno@metempsy.com {} 18313832Sjavier.bueno@metempsy.com void startup() override; 18413700Sjavier.bueno@metempsy.com void calculatePrefetch(const BasePrefetcher::PrefetchInfo &pfi, 18513700Sjavier.bueno@metempsy.com std::vector<QueuedPrefetcher::AddrPriority> &addresses); 18613700Sjavier.bueno@metempsy.com}; 18713700Sjavier.bueno@metempsy.com 18813700Sjavier.bueno@metempsy.comstruct AMPMPrefetcherParams; 18913700Sjavier.bueno@metempsy.com 19013700Sjavier.bueno@metempsy.comclass AMPMPrefetcher : public QueuedPrefetcher 19113700Sjavier.bueno@metempsy.com{ 19213700Sjavier.bueno@metempsy.com AccessMapPatternMatching &m; 19313700Sjavier.bueno@metempsy.com public: 19413700Sjavier.bueno@metempsy.com AMPMPrefetcher(const AMPMPrefetcherParams* p); 19513700Sjavier.bueno@metempsy.com ~AMPMPrefetcher() 19613700Sjavier.bueno@metempsy.com {} 19713554Sjavier.bueno@metempsy.com void calculatePrefetch(const PrefetchInfo &pfi, 19813554Sjavier.bueno@metempsy.com std::vector<AddrPriority> &addresses) override; 19913554Sjavier.bueno@metempsy.com}; 20013554Sjavier.bueno@metempsy.com#endif//__MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__ 201