access_map_pattern_matching.cc revision 13554
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" 3513554Sjavier.bueno@metempsy.com#include "params/AccessMapPatternMatchingPrefetcher.hh" 3613554Sjavier.bueno@metempsy.com 3713554Sjavier.bueno@metempsy.comAccessMapPatternMatchingPrefetcher::AccessMapPatternMatchingPrefetcher( 3813554Sjavier.bueno@metempsy.com const AccessMapPatternMatchingPrefetcherParams *p) 3913554Sjavier.bueno@metempsy.com : QueuedPrefetcher(p), 4013554Sjavier.bueno@metempsy.com startDegree(p->start_degree), hotZoneSize(p->hot_zone_size), 4113554Sjavier.bueno@metempsy.com highCoverageThreshold(p->high_coverage_threshold), 4213554Sjavier.bueno@metempsy.com lowCoverageThreshold(p->low_coverage_threshold), 4313554Sjavier.bueno@metempsy.com highAccuracyThreshold(p->high_accuracy_threshold), 4413554Sjavier.bueno@metempsy.com lowAccuracyThreshold(p->low_accuracy_threshold), 4513554Sjavier.bueno@metempsy.com highCacheHitThreshold(p->high_cache_hit_threshold), 4613554Sjavier.bueno@metempsy.com lowCacheHitThreshold(p->low_cache_hit_threshold), 4713554Sjavier.bueno@metempsy.com epochCycles(p->epoch_cycles), 4813554Sjavier.bueno@metempsy.com offChipMemoryLatency(p->offchip_memory_latency), 4913554Sjavier.bueno@metempsy.com accessMapTable(p->access_map_table_assoc, p->access_map_table_entries, 5013554Sjavier.bueno@metempsy.com p->access_map_table_indexing_policy, 5113554Sjavier.bueno@metempsy.com p->access_map_table_replacement_policy, 5213554Sjavier.bueno@metempsy.com AccessMapEntry(hotZoneSize / blkSize)), 5313554Sjavier.bueno@metempsy.com numGoodPrefetches(0), numTotalPrefetches(0), numRawCacheMisses(0), 5413554Sjavier.bueno@metempsy.com numRawCacheHits(0), degree(startDegree), usefulDegree(startDegree), 5513554Sjavier.bueno@metempsy.com epochEvent([this]{ processEpochEvent(); }, name()) 5613554Sjavier.bueno@metempsy.com{ 5713554Sjavier.bueno@metempsy.com fatal_if(!isPowerOf2(hotZoneSize), 5813554Sjavier.bueno@metempsy.com "the hot zone size must be a power of 2"); 5913554Sjavier.bueno@metempsy.com if (!epochEvent.scheduled()) { 6013554Sjavier.bueno@metempsy.com schedule(epochEvent, clockEdge(epochCycles)); 6113554Sjavier.bueno@metempsy.com } 6213554Sjavier.bueno@metempsy.com} 6313554Sjavier.bueno@metempsy.com 6413554Sjavier.bueno@metempsy.comvoid 6513554Sjavier.bueno@metempsy.comAccessMapPatternMatchingPrefetcher::processEpochEvent() 6613554Sjavier.bueno@metempsy.com{ 6713554Sjavier.bueno@metempsy.com schedule(epochEvent, clockEdge(epochCycles)); 6813554Sjavier.bueno@metempsy.com double prefetch_accuracy = 6913554Sjavier.bueno@metempsy.com ((double) numGoodPrefetches) / ((double) numTotalPrefetches); 7013554Sjavier.bueno@metempsy.com double prefetch_coverage = 7113554Sjavier.bueno@metempsy.com ((double) numGoodPrefetches) / ((double) numRawCacheMisses); 7213554Sjavier.bueno@metempsy.com double cache_hit_ratio = ((double) numRawCacheHits) / 7313554Sjavier.bueno@metempsy.com ((double) (numRawCacheHits + numRawCacheMisses)); 7413554Sjavier.bueno@metempsy.com double num_requests = (double) (numRawCacheMisses - numGoodPrefetches + 7513554Sjavier.bueno@metempsy.com numTotalPrefetches); 7613554Sjavier.bueno@metempsy.com double memory_bandwidth = num_requests * offChipMemoryLatency / 7713554Sjavier.bueno@metempsy.com clockEdge(epochCycles); 7813554Sjavier.bueno@metempsy.com 7913554Sjavier.bueno@metempsy.com if (prefetch_coverage > highCoverageThreshold && 8013554Sjavier.bueno@metempsy.com (prefetch_accuracy > highAccuracyThreshold || 8113554Sjavier.bueno@metempsy.com cache_hit_ratio < lowCacheHitThreshold)) { 8213554Sjavier.bueno@metempsy.com usefulDegree += 1; 8313554Sjavier.bueno@metempsy.com } else if ((prefetch_coverage < lowCoverageThreshold && 8413554Sjavier.bueno@metempsy.com (prefetch_accuracy < lowAccuracyThreshold || 8513554Sjavier.bueno@metempsy.com cache_hit_ratio > highCacheHitThreshold)) || 8613554Sjavier.bueno@metempsy.com (prefetch_accuracy < lowAccuracyThreshold && 8713554Sjavier.bueno@metempsy.com cache_hit_ratio > highCacheHitThreshold)) { 8813554Sjavier.bueno@metempsy.com usefulDegree -= 1; 8913554Sjavier.bueno@metempsy.com } 9013554Sjavier.bueno@metempsy.com degree = std::min((unsigned) memory_bandwidth, usefulDegree); 9113554Sjavier.bueno@metempsy.com // reset epoch stats 9213554Sjavier.bueno@metempsy.com numGoodPrefetches = 0.0; 9313554Sjavier.bueno@metempsy.com numTotalPrefetches = 0.0; 9413554Sjavier.bueno@metempsy.com numRawCacheMisses = 0.0; 9513554Sjavier.bueno@metempsy.com numRawCacheHits = 0.0; 9613554Sjavier.bueno@metempsy.com} 9713554Sjavier.bueno@metempsy.com 9813554Sjavier.bueno@metempsy.comAccessMapPatternMatchingPrefetcher::AccessMapEntry * 9913554Sjavier.bueno@metempsy.comAccessMapPatternMatchingPrefetcher::getAccessMapEntry(Addr am_addr, 10013554Sjavier.bueno@metempsy.com bool is_secure) 10113554Sjavier.bueno@metempsy.com{ 10213554Sjavier.bueno@metempsy.com AccessMapEntry *am_entry = accessMapTable.findEntry(am_addr, is_secure); 10313554Sjavier.bueno@metempsy.com if (am_entry != nullptr) { 10413554Sjavier.bueno@metempsy.com accessMapTable.accessEntry(am_entry); 10513554Sjavier.bueno@metempsy.com } else { 10613554Sjavier.bueno@metempsy.com am_entry = accessMapTable.findVictim(am_addr); 10713554Sjavier.bueno@metempsy.com assert(am_entry != nullptr); 10813554Sjavier.bueno@metempsy.com 10913554Sjavier.bueno@metempsy.com accessMapTable.insertEntry(am_addr, is_secure, am_entry); 11013554Sjavier.bueno@metempsy.com } 11113554Sjavier.bueno@metempsy.com return am_entry; 11213554Sjavier.bueno@metempsy.com} 11313554Sjavier.bueno@metempsy.com 11413554Sjavier.bueno@metempsy.comvoid 11513554Sjavier.bueno@metempsy.comAccessMapPatternMatchingPrefetcher::setEntryState(AccessMapEntry &entry, 11613554Sjavier.bueno@metempsy.com Addr block, enum AccessMapState state) 11713554Sjavier.bueno@metempsy.com{ 11813554Sjavier.bueno@metempsy.com enum AccessMapState old = entry.states[block]; 11913554Sjavier.bueno@metempsy.com entry.states[block] = state; 12013554Sjavier.bueno@metempsy.com 12113554Sjavier.bueno@metempsy.com //do not update stats when initializing 12213554Sjavier.bueno@metempsy.com if (state == AM_INIT) return; 12313554Sjavier.bueno@metempsy.com 12413554Sjavier.bueno@metempsy.com switch (old) { 12513554Sjavier.bueno@metempsy.com case AM_INIT: 12613554Sjavier.bueno@metempsy.com if (state == AM_PREFETCH) { 12713554Sjavier.bueno@metempsy.com numTotalPrefetches += 1; 12813554Sjavier.bueno@metempsy.com } else if (state == AM_ACCESS) { 12913554Sjavier.bueno@metempsy.com numRawCacheMisses += 1; 13013554Sjavier.bueno@metempsy.com } 13113554Sjavier.bueno@metempsy.com break; 13213554Sjavier.bueno@metempsy.com case AM_PREFETCH: 13313554Sjavier.bueno@metempsy.com if (state == AM_ACCESS) { 13413554Sjavier.bueno@metempsy.com numGoodPrefetches += 1; 13513554Sjavier.bueno@metempsy.com numRawCacheMisses += 1; 13613554Sjavier.bueno@metempsy.com } 13713554Sjavier.bueno@metempsy.com break; 13813554Sjavier.bueno@metempsy.com case AM_ACCESS: 13913554Sjavier.bueno@metempsy.com if (state == AM_ACCESS) { 14013554Sjavier.bueno@metempsy.com numRawCacheHits += 1; 14113554Sjavier.bueno@metempsy.com } 14213554Sjavier.bueno@metempsy.com break; 14313554Sjavier.bueno@metempsy.com default: 14413554Sjavier.bueno@metempsy.com panic("Impossible path\n"); 14513554Sjavier.bueno@metempsy.com break; 14613554Sjavier.bueno@metempsy.com } 14713554Sjavier.bueno@metempsy.com} 14813554Sjavier.bueno@metempsy.com 14913554Sjavier.bueno@metempsy.comvoid 15013554Sjavier.bueno@metempsy.comAccessMapPatternMatchingPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 15113554Sjavier.bueno@metempsy.com std::vector<AddrPriority> &addresses) 15213554Sjavier.bueno@metempsy.com{ 15313554Sjavier.bueno@metempsy.com assert(addresses.empty()); 15413554Sjavier.bueno@metempsy.com bool is_secure = pfi.isSecure(); 15513554Sjavier.bueno@metempsy.com Addr am_addr = pfi.getAddr() / hotZoneSize; 15613554Sjavier.bueno@metempsy.com Addr current_block = (pfi.getAddr() % hotZoneSize) / blkSize; 15713554Sjavier.bueno@metempsy.com uint64_t lines_per_zone = hotZoneSize / blkSize; 15813554Sjavier.bueno@metempsy.com 15913554Sjavier.bueno@metempsy.com // Get the entries of the curent block (am_addr), the previous, and the 16013554Sjavier.bueno@metempsy.com // following ones 16113554Sjavier.bueno@metempsy.com AccessMapEntry *am_entry_curr = getAccessMapEntry(am_addr, is_secure); 16213554Sjavier.bueno@metempsy.com AccessMapEntry *am_entry_prev = (am_addr > 0) ? 16313554Sjavier.bueno@metempsy.com getAccessMapEntry(am_addr-1, is_secure) : nullptr; 16413554Sjavier.bueno@metempsy.com AccessMapEntry *am_entry_next = (am_addr < (MaxAddr/hotZoneSize)) ? 16513554Sjavier.bueno@metempsy.com getAccessMapEntry(am_addr+1, is_secure) : nullptr; 16613554Sjavier.bueno@metempsy.com assert(am_entry_curr != am_entry_prev); 16713554Sjavier.bueno@metempsy.com assert(am_entry_curr != am_entry_next); 16813554Sjavier.bueno@metempsy.com assert(am_entry_prev != am_entry_next); 16913554Sjavier.bueno@metempsy.com assert(am_entry_curr != nullptr); 17013554Sjavier.bueno@metempsy.com 17113554Sjavier.bueno@metempsy.com //Mark the current access as Accessed 17213554Sjavier.bueno@metempsy.com setEntryState(*am_entry_curr, current_block, AM_ACCESS); 17313554Sjavier.bueno@metempsy.com 17413554Sjavier.bueno@metempsy.com /** 17513554Sjavier.bueno@metempsy.com * Create a contiguous copy of the 3 entries states. 17613554Sjavier.bueno@metempsy.com * With this, we avoid doing boundaries checking in the loop that looks 17713554Sjavier.bueno@metempsy.com * for prefetch candidates, mark out of range positions with AM_INVALID 17813554Sjavier.bueno@metempsy.com */ 17913554Sjavier.bueno@metempsy.com std::vector<AccessMapState> states(3 * lines_per_zone); 18013554Sjavier.bueno@metempsy.com for (unsigned idx = 0; idx < lines_per_zone; idx += 1) { 18113554Sjavier.bueno@metempsy.com states[idx] = 18213554Sjavier.bueno@metempsy.com am_entry_prev != nullptr ? am_entry_prev->states[idx] : AM_INVALID; 18313554Sjavier.bueno@metempsy.com states[idx + lines_per_zone] = am_entry_curr->states[idx]; 18413554Sjavier.bueno@metempsy.com states[idx + 2 * lines_per_zone] = 18513554Sjavier.bueno@metempsy.com am_entry_next != nullptr ? am_entry_next->states[idx] : AM_INVALID; 18613554Sjavier.bueno@metempsy.com } 18713554Sjavier.bueno@metempsy.com 18813554Sjavier.bueno@metempsy.com /** 18913554Sjavier.bueno@metempsy.com * am_entry_prev->states => states[ 0 .. lines_per_zone-1] 19013554Sjavier.bueno@metempsy.com * am_entry_curr->states => states[ lines_per_zone .. 2*lines_per_zone-1] 19113554Sjavier.bueno@metempsy.com * am_entry_next->states => states[2*lines_per_zone .. 3*lines_per_zone-1] 19213554Sjavier.bueno@metempsy.com */ 19313554Sjavier.bueno@metempsy.com 19413554Sjavier.bueno@metempsy.com // index of the current_block in the new vector 19513554Sjavier.bueno@metempsy.com Addr states_current_block = current_block + lines_per_zone; 19613554Sjavier.bueno@metempsy.com // consider strides 1..lines_per_zone/2 19713554Sjavier.bueno@metempsy.com for (int stride = 1; stride < lines_per_zone/2; stride += 1) { 19813554Sjavier.bueno@metempsy.com // Test accessed positive strides 19913554Sjavier.bueno@metempsy.com if (checkCandidate(states, states_current_block, stride)) { 20013554Sjavier.bueno@metempsy.com // candidate found, current_block - stride 20113554Sjavier.bueno@metempsy.com Addr pf_addr; 20213554Sjavier.bueno@metempsy.com if (stride > current_block) { 20313554Sjavier.bueno@metempsy.com // The index (current_block - stride) falls in the range of 20413554Sjavier.bueno@metempsy.com // the previous zone (am_entry_prev), adjust the address 20513554Sjavier.bueno@metempsy.com // accordingly 20613554Sjavier.bueno@metempsy.com Addr blk = states_current_block - stride; 20713554Sjavier.bueno@metempsy.com pf_addr = (am_addr - 1) * hotZoneSize + blk * blkSize; 20813554Sjavier.bueno@metempsy.com setEntryState(*am_entry_prev, blk, AM_PREFETCH); 20913554Sjavier.bueno@metempsy.com } else { 21013554Sjavier.bueno@metempsy.com // The index (current_block - stride) falls within 21113554Sjavier.bueno@metempsy.com // am_entry_curr 21213554Sjavier.bueno@metempsy.com Addr blk = current_block - stride; 21313554Sjavier.bueno@metempsy.com pf_addr = am_addr * hotZoneSize + blk * blkSize; 21413554Sjavier.bueno@metempsy.com setEntryState(*am_entry_curr, blk, AM_PREFETCH); 21513554Sjavier.bueno@metempsy.com } 21613554Sjavier.bueno@metempsy.com addresses.push_back(AddrPriority(pf_addr, 0)); 21713554Sjavier.bueno@metempsy.com if (addresses.size() == degree) { 21813554Sjavier.bueno@metempsy.com break; 21913554Sjavier.bueno@metempsy.com } 22013554Sjavier.bueno@metempsy.com } 22113554Sjavier.bueno@metempsy.com 22213554Sjavier.bueno@metempsy.com // Test accessed negative strides 22313554Sjavier.bueno@metempsy.com if (checkCandidate(states, states_current_block, -stride)) { 22413554Sjavier.bueno@metempsy.com // candidate found, current_block + stride 22513554Sjavier.bueno@metempsy.com Addr pf_addr; 22613554Sjavier.bueno@metempsy.com if (current_block + stride >= lines_per_zone) { 22713554Sjavier.bueno@metempsy.com // The index (current_block + stride) falls in the range of 22813554Sjavier.bueno@metempsy.com // the next zone (am_entry_next), adjust the address 22913554Sjavier.bueno@metempsy.com // accordingly 23013554Sjavier.bueno@metempsy.com Addr blk = (states_current_block + stride) % lines_per_zone; 23113554Sjavier.bueno@metempsy.com pf_addr = (am_addr + 1) * hotZoneSize + blk * blkSize; 23213554Sjavier.bueno@metempsy.com setEntryState(*am_entry_next, blk, AM_PREFETCH); 23313554Sjavier.bueno@metempsy.com } else { 23413554Sjavier.bueno@metempsy.com // The index (current_block + stride) falls within 23513554Sjavier.bueno@metempsy.com // am_entry_curr 23613554Sjavier.bueno@metempsy.com Addr blk = current_block + stride; 23713554Sjavier.bueno@metempsy.com pf_addr = am_addr * hotZoneSize + blk * blkSize; 23813554Sjavier.bueno@metempsy.com setEntryState(*am_entry_curr, blk, AM_PREFETCH); 23913554Sjavier.bueno@metempsy.com } 24013554Sjavier.bueno@metempsy.com addresses.push_back(AddrPriority(pf_addr, 0)); 24113554Sjavier.bueno@metempsy.com if (addresses.size() == degree) { 24213554Sjavier.bueno@metempsy.com break; 24313554Sjavier.bueno@metempsy.com } 24413554Sjavier.bueno@metempsy.com } 24513554Sjavier.bueno@metempsy.com } 24613554Sjavier.bueno@metempsy.com} 24713554Sjavier.bueno@metempsy.com 24813554Sjavier.bueno@metempsy.comAccessMapPatternMatchingPrefetcher* 24913554Sjavier.bueno@metempsy.comAccessMapPatternMatchingPrefetcherParams::create() 25013554Sjavier.bueno@metempsy.com{ 25113554Sjavier.bueno@metempsy.com return new AccessMapPatternMatchingPrefetcher(this); 25213554Sjavier.bueno@metempsy.com} 253