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#include "mem/cache/prefetch/access_map_pattern_matching.hh" 3213554Sjavier.bueno@metempsy.com 3313554Sjavier.bueno@metempsy.com#include "debug/HWPrefetch.hh" 3413554Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/associative_set_impl.hh" 3513700Sjavier.bueno@metempsy.com#include "params/AMPMPrefetcher.hh" 3613700Sjavier.bueno@metempsy.com#include "params/AccessMapPatternMatching.hh" 3713554Sjavier.bueno@metempsy.com 3813700Sjavier.bueno@metempsy.comAccessMapPatternMatching::AccessMapPatternMatching( 3913700Sjavier.bueno@metempsy.com const AccessMapPatternMatchingParams *p) 4013700Sjavier.bueno@metempsy.com : ClockedObject(p), blkSize(p->block_size), limitStride(p->limit_stride), 4113554Sjavier.bueno@metempsy.com startDegree(p->start_degree), hotZoneSize(p->hot_zone_size), 4213554Sjavier.bueno@metempsy.com highCoverageThreshold(p->high_coverage_threshold), 4313554Sjavier.bueno@metempsy.com lowCoverageThreshold(p->low_coverage_threshold), 4413554Sjavier.bueno@metempsy.com highAccuracyThreshold(p->high_accuracy_threshold), 4513554Sjavier.bueno@metempsy.com lowAccuracyThreshold(p->low_accuracy_threshold), 4613554Sjavier.bueno@metempsy.com highCacheHitThreshold(p->high_cache_hit_threshold), 4713554Sjavier.bueno@metempsy.com lowCacheHitThreshold(p->low_cache_hit_threshold), 4813554Sjavier.bueno@metempsy.com epochCycles(p->epoch_cycles), 4913554Sjavier.bueno@metempsy.com offChipMemoryLatency(p->offchip_memory_latency), 5013554Sjavier.bueno@metempsy.com accessMapTable(p->access_map_table_assoc, p->access_map_table_entries, 5113554Sjavier.bueno@metempsy.com p->access_map_table_indexing_policy, 5213554Sjavier.bueno@metempsy.com p->access_map_table_replacement_policy, 5313554Sjavier.bueno@metempsy.com AccessMapEntry(hotZoneSize / blkSize)), 5413554Sjavier.bueno@metempsy.com numGoodPrefetches(0), numTotalPrefetches(0), numRawCacheMisses(0), 5513554Sjavier.bueno@metempsy.com numRawCacheHits(0), degree(startDegree), usefulDegree(startDegree), 5613554Sjavier.bueno@metempsy.com epochEvent([this]{ processEpochEvent(); }, name()) 5713554Sjavier.bueno@metempsy.com{ 5813554Sjavier.bueno@metempsy.com fatal_if(!isPowerOf2(hotZoneSize), 5913554Sjavier.bueno@metempsy.com "the hot zone size must be a power of 2"); 6013832Sjavier.bueno@metempsy.com} 6113832Sjavier.bueno@metempsy.com 6213832Sjavier.bueno@metempsy.comvoid 6313832Sjavier.bueno@metempsy.comAccessMapPatternMatching::startup() 6413832Sjavier.bueno@metempsy.com{ 6513832Sjavier.bueno@metempsy.com schedule(epochEvent, clockEdge(epochCycles)); 6613554Sjavier.bueno@metempsy.com} 6713554Sjavier.bueno@metempsy.com 6813554Sjavier.bueno@metempsy.comvoid 6913700Sjavier.bueno@metempsy.comAccessMapPatternMatching::processEpochEvent() 7013554Sjavier.bueno@metempsy.com{ 7113554Sjavier.bueno@metempsy.com schedule(epochEvent, clockEdge(epochCycles)); 7213554Sjavier.bueno@metempsy.com double prefetch_accuracy = 7313554Sjavier.bueno@metempsy.com ((double) numGoodPrefetches) / ((double) numTotalPrefetches); 7413554Sjavier.bueno@metempsy.com double prefetch_coverage = 7513554Sjavier.bueno@metempsy.com ((double) numGoodPrefetches) / ((double) numRawCacheMisses); 7613554Sjavier.bueno@metempsy.com double cache_hit_ratio = ((double) numRawCacheHits) / 7713554Sjavier.bueno@metempsy.com ((double) (numRawCacheHits + numRawCacheMisses)); 7813554Sjavier.bueno@metempsy.com double num_requests = (double) (numRawCacheMisses - numGoodPrefetches + 7913554Sjavier.bueno@metempsy.com numTotalPrefetches); 8013554Sjavier.bueno@metempsy.com double memory_bandwidth = num_requests * offChipMemoryLatency / 8113554Sjavier.bueno@metempsy.com clockEdge(epochCycles); 8213554Sjavier.bueno@metempsy.com 8313554Sjavier.bueno@metempsy.com if (prefetch_coverage > highCoverageThreshold && 8413554Sjavier.bueno@metempsy.com (prefetch_accuracy > highAccuracyThreshold || 8513554Sjavier.bueno@metempsy.com cache_hit_ratio < lowCacheHitThreshold)) { 8613554Sjavier.bueno@metempsy.com usefulDegree += 1; 8713554Sjavier.bueno@metempsy.com } else if ((prefetch_coverage < lowCoverageThreshold && 8813554Sjavier.bueno@metempsy.com (prefetch_accuracy < lowAccuracyThreshold || 8913554Sjavier.bueno@metempsy.com cache_hit_ratio > highCacheHitThreshold)) || 9013554Sjavier.bueno@metempsy.com (prefetch_accuracy < lowAccuracyThreshold && 9113554Sjavier.bueno@metempsy.com cache_hit_ratio > highCacheHitThreshold)) { 9213554Sjavier.bueno@metempsy.com usefulDegree -= 1; 9313554Sjavier.bueno@metempsy.com } 9413554Sjavier.bueno@metempsy.com degree = std::min((unsigned) memory_bandwidth, usefulDegree); 9513554Sjavier.bueno@metempsy.com // reset epoch stats 9613554Sjavier.bueno@metempsy.com numGoodPrefetches = 0.0; 9713554Sjavier.bueno@metempsy.com numTotalPrefetches = 0.0; 9813554Sjavier.bueno@metempsy.com numRawCacheMisses = 0.0; 9913554Sjavier.bueno@metempsy.com numRawCacheHits = 0.0; 10013554Sjavier.bueno@metempsy.com} 10113554Sjavier.bueno@metempsy.com 10213700Sjavier.bueno@metempsy.comAccessMapPatternMatching::AccessMapEntry * 10313700Sjavier.bueno@metempsy.comAccessMapPatternMatching::getAccessMapEntry(Addr am_addr, 10413554Sjavier.bueno@metempsy.com bool is_secure) 10513554Sjavier.bueno@metempsy.com{ 10613554Sjavier.bueno@metempsy.com AccessMapEntry *am_entry = accessMapTable.findEntry(am_addr, is_secure); 10713554Sjavier.bueno@metempsy.com if (am_entry != nullptr) { 10813554Sjavier.bueno@metempsy.com accessMapTable.accessEntry(am_entry); 10913554Sjavier.bueno@metempsy.com } else { 11013554Sjavier.bueno@metempsy.com am_entry = accessMapTable.findVictim(am_addr); 11113554Sjavier.bueno@metempsy.com assert(am_entry != nullptr); 11213554Sjavier.bueno@metempsy.com 11313554Sjavier.bueno@metempsy.com accessMapTable.insertEntry(am_addr, is_secure, am_entry); 11413554Sjavier.bueno@metempsy.com } 11513554Sjavier.bueno@metempsy.com return am_entry; 11613554Sjavier.bueno@metempsy.com} 11713554Sjavier.bueno@metempsy.com 11813554Sjavier.bueno@metempsy.comvoid 11913700Sjavier.bueno@metempsy.comAccessMapPatternMatching::setEntryState(AccessMapEntry &entry, 12013554Sjavier.bueno@metempsy.com Addr block, enum AccessMapState state) 12113554Sjavier.bueno@metempsy.com{ 12213554Sjavier.bueno@metempsy.com enum AccessMapState old = entry.states[block]; 12313554Sjavier.bueno@metempsy.com entry.states[block] = state; 12413554Sjavier.bueno@metempsy.com 12513554Sjavier.bueno@metempsy.com //do not update stats when initializing 12613554Sjavier.bueno@metempsy.com if (state == AM_INIT) return; 12713554Sjavier.bueno@metempsy.com 12813554Sjavier.bueno@metempsy.com switch (old) { 12913554Sjavier.bueno@metempsy.com case AM_INIT: 13013554Sjavier.bueno@metempsy.com if (state == AM_PREFETCH) { 13113554Sjavier.bueno@metempsy.com numTotalPrefetches += 1; 13213554Sjavier.bueno@metempsy.com } else if (state == AM_ACCESS) { 13313554Sjavier.bueno@metempsy.com numRawCacheMisses += 1; 13413554Sjavier.bueno@metempsy.com } 13513554Sjavier.bueno@metempsy.com break; 13613554Sjavier.bueno@metempsy.com case AM_PREFETCH: 13713554Sjavier.bueno@metempsy.com if (state == AM_ACCESS) { 13813554Sjavier.bueno@metempsy.com numGoodPrefetches += 1; 13913554Sjavier.bueno@metempsy.com numRawCacheMisses += 1; 14013554Sjavier.bueno@metempsy.com } 14113554Sjavier.bueno@metempsy.com break; 14213554Sjavier.bueno@metempsy.com case AM_ACCESS: 14313554Sjavier.bueno@metempsy.com if (state == AM_ACCESS) { 14413554Sjavier.bueno@metempsy.com numRawCacheHits += 1; 14513554Sjavier.bueno@metempsy.com } 14613554Sjavier.bueno@metempsy.com break; 14713554Sjavier.bueno@metempsy.com default: 14813554Sjavier.bueno@metempsy.com panic("Impossible path\n"); 14913554Sjavier.bueno@metempsy.com break; 15013554Sjavier.bueno@metempsy.com } 15113554Sjavier.bueno@metempsy.com} 15213554Sjavier.bueno@metempsy.com 15313554Sjavier.bueno@metempsy.comvoid 15413700Sjavier.bueno@metempsy.comAccessMapPatternMatching::calculatePrefetch( 15513700Sjavier.bueno@metempsy.com const BasePrefetcher::PrefetchInfo &pfi, 15613700Sjavier.bueno@metempsy.com std::vector<QueuedPrefetcher::AddrPriority> &addresses) 15713554Sjavier.bueno@metempsy.com{ 15813554Sjavier.bueno@metempsy.com assert(addresses.empty()); 15913832Sjavier.bueno@metempsy.com 16013554Sjavier.bueno@metempsy.com bool is_secure = pfi.isSecure(); 16113554Sjavier.bueno@metempsy.com Addr am_addr = pfi.getAddr() / hotZoneSize; 16213554Sjavier.bueno@metempsy.com Addr current_block = (pfi.getAddr() % hotZoneSize) / blkSize; 16313554Sjavier.bueno@metempsy.com uint64_t lines_per_zone = hotZoneSize / blkSize; 16413554Sjavier.bueno@metempsy.com 16513554Sjavier.bueno@metempsy.com // Get the entries of the curent block (am_addr), the previous, and the 16613554Sjavier.bueno@metempsy.com // following ones 16713554Sjavier.bueno@metempsy.com AccessMapEntry *am_entry_curr = getAccessMapEntry(am_addr, is_secure); 16813554Sjavier.bueno@metempsy.com AccessMapEntry *am_entry_prev = (am_addr > 0) ? 16913554Sjavier.bueno@metempsy.com getAccessMapEntry(am_addr-1, is_secure) : nullptr; 17013554Sjavier.bueno@metempsy.com AccessMapEntry *am_entry_next = (am_addr < (MaxAddr/hotZoneSize)) ? 17113554Sjavier.bueno@metempsy.com getAccessMapEntry(am_addr+1, is_secure) : nullptr; 17213554Sjavier.bueno@metempsy.com assert(am_entry_curr != am_entry_prev); 17313554Sjavier.bueno@metempsy.com assert(am_entry_curr != am_entry_next); 17413554Sjavier.bueno@metempsy.com assert(am_entry_prev != am_entry_next); 17513554Sjavier.bueno@metempsy.com assert(am_entry_curr != nullptr); 17613554Sjavier.bueno@metempsy.com 17713554Sjavier.bueno@metempsy.com //Mark the current access as Accessed 17813554Sjavier.bueno@metempsy.com setEntryState(*am_entry_curr, current_block, AM_ACCESS); 17913554Sjavier.bueno@metempsy.com 18013554Sjavier.bueno@metempsy.com /** 18113554Sjavier.bueno@metempsy.com * Create a contiguous copy of the 3 entries states. 18213554Sjavier.bueno@metempsy.com * With this, we avoid doing boundaries checking in the loop that looks 18313554Sjavier.bueno@metempsy.com * for prefetch candidates, mark out of range positions with AM_INVALID 18413554Sjavier.bueno@metempsy.com */ 18513554Sjavier.bueno@metempsy.com std::vector<AccessMapState> states(3 * lines_per_zone); 18613554Sjavier.bueno@metempsy.com for (unsigned idx = 0; idx < lines_per_zone; idx += 1) { 18713554Sjavier.bueno@metempsy.com states[idx] = 18813554Sjavier.bueno@metempsy.com am_entry_prev != nullptr ? am_entry_prev->states[idx] : AM_INVALID; 18913554Sjavier.bueno@metempsy.com states[idx + lines_per_zone] = am_entry_curr->states[idx]; 19013554Sjavier.bueno@metempsy.com states[idx + 2 * lines_per_zone] = 19113554Sjavier.bueno@metempsy.com am_entry_next != nullptr ? am_entry_next->states[idx] : AM_INVALID; 19213554Sjavier.bueno@metempsy.com } 19313554Sjavier.bueno@metempsy.com 19413554Sjavier.bueno@metempsy.com /** 19513554Sjavier.bueno@metempsy.com * am_entry_prev->states => states[ 0 .. lines_per_zone-1] 19613554Sjavier.bueno@metempsy.com * am_entry_curr->states => states[ lines_per_zone .. 2*lines_per_zone-1] 19713554Sjavier.bueno@metempsy.com * am_entry_next->states => states[2*lines_per_zone .. 3*lines_per_zone-1] 19813554Sjavier.bueno@metempsy.com */ 19913554Sjavier.bueno@metempsy.com 20013554Sjavier.bueno@metempsy.com // index of the current_block in the new vector 20113554Sjavier.bueno@metempsy.com Addr states_current_block = current_block + lines_per_zone; 20213554Sjavier.bueno@metempsy.com // consider strides 1..lines_per_zone/2 20313700Sjavier.bueno@metempsy.com int max_stride = limitStride == 0 ? lines_per_zone / 2 : limitStride + 1; 20413700Sjavier.bueno@metempsy.com for (int stride = 1; stride < max_stride; stride += 1) { 20513554Sjavier.bueno@metempsy.com // Test accessed positive strides 20613554Sjavier.bueno@metempsy.com if (checkCandidate(states, states_current_block, stride)) { 20713554Sjavier.bueno@metempsy.com // candidate found, current_block - stride 20813554Sjavier.bueno@metempsy.com Addr pf_addr; 20913554Sjavier.bueno@metempsy.com if (stride > current_block) { 21013554Sjavier.bueno@metempsy.com // The index (current_block - stride) falls in the range of 21113554Sjavier.bueno@metempsy.com // the previous zone (am_entry_prev), adjust the address 21213554Sjavier.bueno@metempsy.com // accordingly 21313554Sjavier.bueno@metempsy.com Addr blk = states_current_block - stride; 21413554Sjavier.bueno@metempsy.com pf_addr = (am_addr - 1) * hotZoneSize + blk * blkSize; 21513554Sjavier.bueno@metempsy.com setEntryState(*am_entry_prev, blk, AM_PREFETCH); 21613554Sjavier.bueno@metempsy.com } else { 21713554Sjavier.bueno@metempsy.com // The index (current_block - stride) falls within 21813554Sjavier.bueno@metempsy.com // am_entry_curr 21913554Sjavier.bueno@metempsy.com Addr blk = current_block - stride; 22013554Sjavier.bueno@metempsy.com pf_addr = am_addr * hotZoneSize + blk * blkSize; 22113554Sjavier.bueno@metempsy.com setEntryState(*am_entry_curr, blk, AM_PREFETCH); 22213554Sjavier.bueno@metempsy.com } 22313700Sjavier.bueno@metempsy.com addresses.push_back(QueuedPrefetcher::AddrPriority(pf_addr, 0)); 22413554Sjavier.bueno@metempsy.com if (addresses.size() == degree) { 22513554Sjavier.bueno@metempsy.com break; 22613554Sjavier.bueno@metempsy.com } 22713554Sjavier.bueno@metempsy.com } 22813554Sjavier.bueno@metempsy.com 22913554Sjavier.bueno@metempsy.com // Test accessed negative strides 23013554Sjavier.bueno@metempsy.com if (checkCandidate(states, states_current_block, -stride)) { 23113554Sjavier.bueno@metempsy.com // candidate found, current_block + stride 23213554Sjavier.bueno@metempsy.com Addr pf_addr; 23313554Sjavier.bueno@metempsy.com if (current_block + stride >= lines_per_zone) { 23413554Sjavier.bueno@metempsy.com // The index (current_block + stride) falls in the range of 23513554Sjavier.bueno@metempsy.com // the next zone (am_entry_next), adjust the address 23613554Sjavier.bueno@metempsy.com // accordingly 23713554Sjavier.bueno@metempsy.com Addr blk = (states_current_block + stride) % lines_per_zone; 23813554Sjavier.bueno@metempsy.com pf_addr = (am_addr + 1) * hotZoneSize + blk * blkSize; 23913554Sjavier.bueno@metempsy.com setEntryState(*am_entry_next, blk, AM_PREFETCH); 24013554Sjavier.bueno@metempsy.com } else { 24113554Sjavier.bueno@metempsy.com // The index (current_block + stride) falls within 24213554Sjavier.bueno@metempsy.com // am_entry_curr 24313554Sjavier.bueno@metempsy.com Addr blk = current_block + stride; 24413554Sjavier.bueno@metempsy.com pf_addr = am_addr * hotZoneSize + blk * blkSize; 24513554Sjavier.bueno@metempsy.com setEntryState(*am_entry_curr, blk, AM_PREFETCH); 24613554Sjavier.bueno@metempsy.com } 24713700Sjavier.bueno@metempsy.com addresses.push_back(QueuedPrefetcher::AddrPriority(pf_addr, 0)); 24813554Sjavier.bueno@metempsy.com if (addresses.size() == degree) { 24913554Sjavier.bueno@metempsy.com break; 25013554Sjavier.bueno@metempsy.com } 25113554Sjavier.bueno@metempsy.com } 25213554Sjavier.bueno@metempsy.com } 25313554Sjavier.bueno@metempsy.com} 25413554Sjavier.bueno@metempsy.com 25513700Sjavier.bueno@metempsy.comAccessMapPatternMatching* 25613700Sjavier.bueno@metempsy.comAccessMapPatternMatchingParams::create() 25713554Sjavier.bueno@metempsy.com{ 25813700Sjavier.bueno@metempsy.com return new AccessMapPatternMatching(this); 25913554Sjavier.bueno@metempsy.com} 26013700Sjavier.bueno@metempsy.com 26113700Sjavier.bueno@metempsy.comAMPMPrefetcher::AMPMPrefetcher(const AMPMPrefetcherParams *p) 26213700Sjavier.bueno@metempsy.com : QueuedPrefetcher(p), ampm(*p->ampm) 26313700Sjavier.bueno@metempsy.com{ 26413700Sjavier.bueno@metempsy.com} 26513700Sjavier.bueno@metempsy.com 26613700Sjavier.bueno@metempsy.comvoid 26713700Sjavier.bueno@metempsy.comAMPMPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 26813700Sjavier.bueno@metempsy.com std::vector<AddrPriority> &addresses) 26913700Sjavier.bueno@metempsy.com{ 27013700Sjavier.bueno@metempsy.com ampm.calculatePrefetch(pfi, addresses); 27113700Sjavier.bueno@metempsy.com} 27213700Sjavier.bueno@metempsy.com 27313700Sjavier.bueno@metempsy.comAMPMPrefetcher* 27413700Sjavier.bueno@metempsy.comAMPMPrefetcherParams::create() 27513700Sjavier.bueno@metempsy.com{ 27613700Sjavier.bueno@metempsy.com return new AMPMPrefetcher(this); 27713700Sjavier.bueno@metempsy.com} 278