diff options
| -rw-r--r-- | src/mem/cache/prefetch/Prefetcher.py | 34 | ||||
| -rw-r--r-- | src/mem/cache/prefetch/SConscript | 1 | ||||
| -rw-r--r-- | src/mem/cache/prefetch/access_map_pattern_matching.cc | 252 | ||||
| -rw-r--r-- | src/mem/cache/prefetch/access_map_pattern_matching.hh | 182 |
4 files changed, 469 insertions, 0 deletions
diff --git a/src/mem/cache/prefetch/Prefetcher.py b/src/mem/cache/prefetch/Prefetcher.py index a868a2583..3d9c66565 100644 --- a/src/mem/cache/prefetch/Prefetcher.py +++ b/src/mem/cache/prefetch/Prefetcher.py @@ -179,3 +179,37 @@ class SignaturePathPrefetcher(QueuedPrefetcher): "Minimum confidence to issue prefetches") lookahead_confidence_threshold = Param.Float(0.75, "Minimum confidence to continue exploring lookahead entries") + +class AccessMapPatternMatchingPrefetcher(QueuedPrefetcher): + type = 'AccessMapPatternMatchingPrefetcher' + cxx_class = 'AccessMapPatternMatchingPrefetcher' + cxx_header = "mem/cache/prefetch/access_map_pattern_matching.hh" + + start_degree = Param.Unsigned(4, + "Initial degree (Maximum number of prefetches generated") + hot_zone_size = Param.MemorySize("2kB", "Memory covered by a hot zone") + access_map_table_entries = Param.MemorySize("256", + "Number of entries in the access map table") + access_map_table_assoc = Param.Unsigned(8, + "Associativity of the access map table") + access_map_table_indexing_policy = Param.BaseIndexingPolicy( + SetAssociative(entry_size = 1, assoc = Parent.access_map_table_assoc, + size = Parent.access_map_table_entries), + "Indexing policy of the access map table") + access_map_table_replacement_policy = Param.BaseReplacementPolicy(LRURP(), + "Replacement policy of the access map table") + high_coverage_threshold = Param.Float(0.25, + "A prefetch coverage factor bigger than this is considered high") + low_coverage_threshold = Param.Float(0.125, + "A prefetch coverage factor smaller than this is considered low") + high_accuracy_threshold = Param.Float(0.5, + "A prefetch accuracy factor bigger than this is considered high") + low_accuracy_threshold = Param.Float(0.25, + "A prefetch accuracy factor smaller than this is considered low") + high_cache_hit_threshold = Param.Float(0.875, + "A cache hit ratio bigger than this is considered high") + low_cache_hit_threshold = Param.Float(0.75, + "A cache hit ratio smaller than this is considered low") + epoch_cycles = Param.Cycles(256000, "Cycles in an epoch period") + offchip_memory_latency = Param.Latency("30ns", + "Memory latency used to compute the required memory bandwidth") diff --git a/src/mem/cache/prefetch/SConscript b/src/mem/cache/prefetch/SConscript index ccbc2e3b8..b46158624 100644 --- a/src/mem/cache/prefetch/SConscript +++ b/src/mem/cache/prefetch/SConscript @@ -32,6 +32,7 @@ Import('*') SimObject('Prefetcher.py') +Source('access_map_pattern_matching.cc') Source('base.cc') Source('queued.cc') Source('signature_path.cc') diff --git a/src/mem/cache/prefetch/access_map_pattern_matching.cc b/src/mem/cache/prefetch/access_map_pattern_matching.cc new file mode 100644 index 000000000..0f46effbf --- /dev/null +++ b/src/mem/cache/prefetch/access_map_pattern_matching.cc @@ -0,0 +1,252 @@ +/** + * Copyright (c) 2018 Metempsy Technology Consulting + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * Authors: Javier Bueno + */ + +#include "mem/cache/prefetch/access_map_pattern_matching.hh" + +#include "debug/HWPrefetch.hh" +#include "mem/cache/prefetch/associative_set_impl.hh" +#include "params/AccessMapPatternMatchingPrefetcher.hh" + +AccessMapPatternMatchingPrefetcher::AccessMapPatternMatchingPrefetcher( + const AccessMapPatternMatchingPrefetcherParams *p) + : QueuedPrefetcher(p), + startDegree(p->start_degree), hotZoneSize(p->hot_zone_size), + highCoverageThreshold(p->high_coverage_threshold), + lowCoverageThreshold(p->low_coverage_threshold), + highAccuracyThreshold(p->high_accuracy_threshold), + lowAccuracyThreshold(p->low_accuracy_threshold), + highCacheHitThreshold(p->high_cache_hit_threshold), + lowCacheHitThreshold(p->low_cache_hit_threshold), + epochCycles(p->epoch_cycles), + offChipMemoryLatency(p->offchip_memory_latency), + accessMapTable(p->access_map_table_assoc, p->access_map_table_entries, + p->access_map_table_indexing_policy, + p->access_map_table_replacement_policy, + AccessMapEntry(hotZoneSize / blkSize)), + numGoodPrefetches(0), numTotalPrefetches(0), numRawCacheMisses(0), + numRawCacheHits(0), degree(startDegree), usefulDegree(startDegree), + epochEvent([this]{ processEpochEvent(); }, name()) +{ + fatal_if(!isPowerOf2(hotZoneSize), + "the hot zone size must be a power of 2"); + if (!epochEvent.scheduled()) { + schedule(epochEvent, clockEdge(epochCycles)); + } +} + +void +AccessMapPatternMatchingPrefetcher::processEpochEvent() +{ + schedule(epochEvent, clockEdge(epochCycles)); + double prefetch_accuracy = + ((double) numGoodPrefetches) / ((double) numTotalPrefetches); + double prefetch_coverage = + ((double) numGoodPrefetches) / ((double) numRawCacheMisses); + double cache_hit_ratio = ((double) numRawCacheHits) / + ((double) (numRawCacheHits + numRawCacheMisses)); + double num_requests = (double) (numRawCacheMisses - numGoodPrefetches + + numTotalPrefetches); + double memory_bandwidth = num_requests * offChipMemoryLatency / + clockEdge(epochCycles); + + if (prefetch_coverage > highCoverageThreshold && + (prefetch_accuracy > highAccuracyThreshold || + cache_hit_ratio < lowCacheHitThreshold)) { + usefulDegree += 1; + } else if ((prefetch_coverage < lowCoverageThreshold && + (prefetch_accuracy < lowAccuracyThreshold || + cache_hit_ratio > highCacheHitThreshold)) || + (prefetch_accuracy < lowAccuracyThreshold && + cache_hit_ratio > highCacheHitThreshold)) { + usefulDegree -= 1; + } + degree = std::min((unsigned) memory_bandwidth, usefulDegree); + // reset epoch stats + numGoodPrefetches = 0.0; + numTotalPrefetches = 0.0; + numRawCacheMisses = 0.0; + numRawCacheHits = 0.0; +} + +AccessMapPatternMatchingPrefetcher::AccessMapEntry * +AccessMapPatternMatchingPrefetcher::getAccessMapEntry(Addr am_addr, + bool is_secure) +{ + AccessMapEntry *am_entry = accessMapTable.findEntry(am_addr, is_secure); + if (am_entry != nullptr) { + accessMapTable.accessEntry(am_entry); + } else { + am_entry = accessMapTable.findVictim(am_addr); + assert(am_entry != nullptr); + + accessMapTable.insertEntry(am_addr, is_secure, am_entry); + } + return am_entry; +} + +void +AccessMapPatternMatchingPrefetcher::setEntryState(AccessMapEntry &entry, + Addr block, enum AccessMapState state) +{ + enum AccessMapState old = entry.states[block]; + entry.states[block] = state; + + //do not update stats when initializing + if (state == AM_INIT) return; + + switch (old) { + case AM_INIT: + if (state == AM_PREFETCH) { + numTotalPrefetches += 1; + } else if (state == AM_ACCESS) { + numRawCacheMisses += 1; + } + break; + case AM_PREFETCH: + if (state == AM_ACCESS) { + numGoodPrefetches += 1; + numRawCacheMisses += 1; + } + break; + case AM_ACCESS: + if (state == AM_ACCESS) { + numRawCacheHits += 1; + } + break; + default: + panic("Impossible path\n"); + break; + } +} + +void +AccessMapPatternMatchingPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, + std::vector<AddrPriority> &addresses) +{ + assert(addresses.empty()); + bool is_secure = pfi.isSecure(); + Addr am_addr = pfi.getAddr() / hotZoneSize; + Addr current_block = (pfi.getAddr() % hotZoneSize) / blkSize; + uint64_t lines_per_zone = hotZoneSize / blkSize; + + // Get the entries of the curent block (am_addr), the previous, and the + // following ones + AccessMapEntry *am_entry_curr = getAccessMapEntry(am_addr, is_secure); + AccessMapEntry *am_entry_prev = (am_addr > 0) ? + getAccessMapEntry(am_addr-1, is_secure) : nullptr; + AccessMapEntry *am_entry_next = (am_addr < (MaxAddr/hotZoneSize)) ? + getAccessMapEntry(am_addr+1, is_secure) : nullptr; + assert(am_entry_curr != am_entry_prev); + assert(am_entry_curr != am_entry_next); + assert(am_entry_prev != am_entry_next); + assert(am_entry_curr != nullptr); + + //Mark the current access as Accessed + setEntryState(*am_entry_curr, current_block, AM_ACCESS); + + /** + * Create a contiguous copy of the 3 entries states. + * With this, we avoid doing boundaries checking in the loop that looks + * for prefetch candidates, mark out of range positions with AM_INVALID + */ + std::vector<AccessMapState> states(3 * lines_per_zone); + for (unsigned idx = 0; idx < lines_per_zone; idx += 1) { + states[idx] = + am_entry_prev != nullptr ? am_entry_prev->states[idx] : AM_INVALID; + states[idx + lines_per_zone] = am_entry_curr->states[idx]; + states[idx + 2 * lines_per_zone] = + am_entry_next != nullptr ? am_entry_next->states[idx] : AM_INVALID; + } + + /** + * am_entry_prev->states => states[ 0 .. lines_per_zone-1] + * am_entry_curr->states => states[ lines_per_zone .. 2*lines_per_zone-1] + * am_entry_next->states => states[2*lines_per_zone .. 3*lines_per_zone-1] + */ + + // index of the current_block in the new vector + Addr states_current_block = current_block + lines_per_zone; + // consider strides 1..lines_per_zone/2 + for (int stride = 1; stride < lines_per_zone/2; stride += 1) { + // Test accessed positive strides + if (checkCandidate(states, states_current_block, stride)) { + // candidate found, current_block - stride + Addr pf_addr; + if (stride > current_block) { + // The index (current_block - stride) falls in the range of + // the previous zone (am_entry_prev), adjust the address + // accordingly + Addr blk = states_current_block - stride; + pf_addr = (am_addr - 1) * hotZoneSize + blk * blkSize; + setEntryState(*am_entry_prev, blk, AM_PREFETCH); + } else { + // The index (current_block - stride) falls within + // am_entry_curr + Addr blk = current_block - stride; + pf_addr = am_addr * hotZoneSize + blk * blkSize; + setEntryState(*am_entry_curr, blk, AM_PREFETCH); + } + addresses.push_back(AddrPriority(pf_addr, 0)); + if (addresses.size() == degree) { + break; + } + } + + // Test accessed negative strides + if (checkCandidate(states, states_current_block, -stride)) { + // candidate found, current_block + stride + Addr pf_addr; + if (current_block + stride >= lines_per_zone) { + // The index (current_block + stride) falls in the range of + // the next zone (am_entry_next), adjust the address + // accordingly + Addr blk = (states_current_block + stride) % lines_per_zone; + pf_addr = (am_addr + 1) * hotZoneSize + blk * blkSize; + setEntryState(*am_entry_next, blk, AM_PREFETCH); + } else { + // The index (current_block + stride) falls within + // am_entry_curr + Addr blk = current_block + stride; + pf_addr = am_addr * hotZoneSize + blk * blkSize; + setEntryState(*am_entry_curr, blk, AM_PREFETCH); + } + addresses.push_back(AddrPriority(pf_addr, 0)); + if (addresses.size() == degree) { + break; + } + } + } +} + +AccessMapPatternMatchingPrefetcher* +AccessMapPatternMatchingPrefetcherParams::create() +{ + return new AccessMapPatternMatchingPrefetcher(this); +} diff --git a/src/mem/cache/prefetch/access_map_pattern_matching.hh b/src/mem/cache/prefetch/access_map_pattern_matching.hh new file mode 100644 index 000000000..33a20a27e --- /dev/null +++ b/src/mem/cache/prefetch/access_map_pattern_matching.hh @@ -0,0 +1,182 @@ +/** + * Copyright (c) 2018 Metempsy Technology Consulting + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * Authors: Javier Bueno + */ + + /** + * Implementation of the Access Map Pattern Matching Prefetcher + * + * References: + * Access map pattern matching for high performance data cache prefetch. + * Ishii, Y., Inaba, M., & Hiraki, K. (2011). + * Journal of Instruction-Level Parallelism, 13, 1-24. + */ + +#ifndef __MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__ +#define __MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__ + +#include "mem/cache/base.hh" +#include "mem/cache/prefetch/associative_set.hh" +#include "mem/cache/prefetch/queued.hh" +#include "mem/packet.hh" + +struct AccessMapPatternMatchingPrefetcherParams; + +class AccessMapPatternMatchingPrefetcher : public QueuedPrefetcher +{ + /** Maximum number of prefetch generated */ + const unsigned startDegree; + /** Amount of memory covered by a hot zone */ + const uint64_t hotZoneSize; + /** A prefetch coverage factor bigger than this is considered high */ + const double highCoverageThreshold; + /** A prefetch coverage factor smaller than this is considered low */ + const double lowCoverageThreshold; + /** A prefetch accuracy factor bigger than this is considered high */ + const double highAccuracyThreshold; + /** A prefetch accuracy factor smaller than this is considered low */ + const double lowAccuracyThreshold; + /** A cache hit ratio bigger than this is considered high */ + const double highCacheHitThreshold; + /** A cache hit ratio smaller than this is considered low */ + const double lowCacheHitThreshold; + /** Cycles in an epoch period */ + const Cycles epochCycles; + /** Off chip memory latency to use for the epoch bandwidth calculation */ + const Tick offChipMemoryLatency; + + /** Data type representing the state of a cacheline in the access map */ + enum AccessMapState + { + AM_INIT, + AM_PREFETCH, + AM_ACCESS, + AM_INVALID + }; + + /** AccessMapEntry data type */ + struct AccessMapEntry : public TaggedEntry + { + /** vector containing the state of the cachelines in this zone */ + std::vector<AccessMapState> states; + + AccessMapEntry(size_t num_entries) : states(num_entries, AM_INIT) + {} + + /** Reset the entries to their initial values */ + void reset() override + { + for (auto &entry : states) { + entry = AM_INIT; + } + } + }; + /** Access map table */ + AssociativeSet<AccessMapEntry> accessMapTable; + + /** + * Number of good prefetches + * - State transitions from PREFETCH to ACCESS + */ + uint64_t numGoodPrefetches; + /** + * Number of prefetches issued + * - State transitions from INIT to PREFETCH + */ + uint64_t numTotalPrefetches; + /** + * Number of raw cache misses + * - State transitions from INIT or PREFETCH to ACCESS + */ + uint64_t numRawCacheMisses; + /** + * Number of raw cache hits + * - State transitions from ACCESS to ACCESS + */ + uint64_t numRawCacheHits; + /** Current degree */ + unsigned degree; + /** Current useful degree */ + unsigned usefulDegree; + + /** + * Given a target cacheline, this function checks if the cachelines + * that follow the provided stride have been accessed. If so, the line + * is considered a good candidate. + * @param states vector containing the states of three contiguous hot zones + * @param current target block (cacheline) + * @param stride access stride to obtain the reference cachelines + * @return true if current is a prefetch candidate + */ + inline bool checkCandidate(std::vector<AccessMapState> const &states, + Addr current, int stride) const + { + enum AccessMapState tgt = states[current - stride]; + enum AccessMapState s = states[current + stride]; + enum AccessMapState s2 = states[current + 2 * stride]; + enum AccessMapState s2_p1 = states[current + 2 * stride + 1]; + return (tgt != AM_INVALID && + ((s == AM_ACCESS && s2 == AM_ACCESS) || + (s == AM_ACCESS && s2_p1 == AM_ACCESS))); + } + + /** + * Obtain an AccessMapEntry from the AccessMapTable, if the entry is not + * found a new one is initialized and inserted. + * @param am_addr address of the hot zone + * @param is_secure whether the address belongs to the secure memory area + * @return the corresponding entry + */ + AccessMapEntry *getAccessMapEntry(Addr am_addr, bool is_secure); + + /** + * Updates the state of a block within an AccessMapEntry, also updates + * the prefetcher metrics. + * @param entry AccessMapEntry to update + * @param block cacheline within the hot zone + * @param state new state + */ + void setEntryState(AccessMapEntry &entry, Addr block, + enum AccessMapState state); + + /** + * This event constitues the epoch of the statistics that keep track of + * the prefetcher accuracy, when this event triggers, the prefetcher degree + * is adjusted and the statistics counters are reset. + */ + void processEpochEvent(); + EventFunctionWrapper epochEvent; + + public: + AccessMapPatternMatchingPrefetcher( + const AccessMapPatternMatchingPrefetcherParams* p); + ~AccessMapPatternMatchingPrefetcher() {} + void calculatePrefetch(const PrefetchInfo &pfi, + std::vector<AddrPriority> &addresses) override; +}; +#endif//__MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__ |