spatio_temporal_memory_streaming.cc revision 13786
113786Sjavier.bueno@metempsy.com/** 213786Sjavier.bueno@metempsy.com * Copyright (c) 2019 Metempsy Technology Consulting 313786Sjavier.bueno@metempsy.com * All rights reserved. 413786Sjavier.bueno@metempsy.com * 513786Sjavier.bueno@metempsy.com * Redistribution and use in source and binary forms, with or without 613786Sjavier.bueno@metempsy.com * modification, are permitted provided that the following conditions are 713786Sjavier.bueno@metempsy.com * met: redistributions of source code must retain the above copyright 813786Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer; 913786Sjavier.bueno@metempsy.com * redistributions in binary form must reproduce the above copyright 1013786Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer in the 1113786Sjavier.bueno@metempsy.com * documentation and/or other materials provided with the distribution; 1213786Sjavier.bueno@metempsy.com * neither the name of the copyright holders nor the names of its 1313786Sjavier.bueno@metempsy.com * contributors may be used to endorse or promote products derived from 1413786Sjavier.bueno@metempsy.com * this software without specific prior written permission. 1513786Sjavier.bueno@metempsy.com * 1613786Sjavier.bueno@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713786Sjavier.bueno@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813786Sjavier.bueno@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913786Sjavier.bueno@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013786Sjavier.bueno@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113786Sjavier.bueno@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213786Sjavier.bueno@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313786Sjavier.bueno@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413786Sjavier.bueno@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513786Sjavier.bueno@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613786Sjavier.bueno@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713786Sjavier.bueno@metempsy.com * 2813786Sjavier.bueno@metempsy.com * Authors: Javier Bueno 2913786Sjavier.bueno@metempsy.com */ 3013786Sjavier.bueno@metempsy.com 3113786Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/spatio_temporal_memory_streaming.hh" 3213786Sjavier.bueno@metempsy.com 3313786Sjavier.bueno@metempsy.com#include "debug/HWPrefetch.hh" 3413786Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/associative_set_impl.hh" 3513786Sjavier.bueno@metempsy.com#include "params/STeMSPrefetcher.hh" 3613786Sjavier.bueno@metempsy.com 3713786Sjavier.bueno@metempsy.comSTeMSPrefetcher::STeMSPrefetcher(const STeMSPrefetcherParams *p) 3813786Sjavier.bueno@metempsy.com : QueuedPrefetcher(p), spatialRegionSize(p->spatial_region_size), 3913786Sjavier.bueno@metempsy.com spatialRegionSizeBits(floorLog2(p->spatial_region_size)), 4013786Sjavier.bueno@metempsy.com reconstructionEntries(p->reconstruction_entries), 4113786Sjavier.bueno@metempsy.com activeGenerationTable(p->active_generation_table_assoc, 4213786Sjavier.bueno@metempsy.com p->active_generation_table_entries, 4313786Sjavier.bueno@metempsy.com p->active_generation_table_indexing_policy, 4413786Sjavier.bueno@metempsy.com p->active_generation_table_replacement_policy, 4513786Sjavier.bueno@metempsy.com ActiveGenerationTableEntry( 4613786Sjavier.bueno@metempsy.com spatialRegionSize / blkSize)), 4713786Sjavier.bueno@metempsy.com patternSequenceTable(p->pattern_sequence_table_assoc, 4813786Sjavier.bueno@metempsy.com p->pattern_sequence_table_entries, 4913786Sjavier.bueno@metempsy.com p->pattern_sequence_table_indexing_policy, 5013786Sjavier.bueno@metempsy.com p->pattern_sequence_table_replacement_policy, 5113786Sjavier.bueno@metempsy.com ActiveGenerationTableEntry( 5213786Sjavier.bueno@metempsy.com spatialRegionSize / blkSize)), 5313786Sjavier.bueno@metempsy.com rmob(p->region_miss_order_buffer_entries), rmobHead(0) 5413786Sjavier.bueno@metempsy.com{ 5513786Sjavier.bueno@metempsy.com fatal_if(!isPowerOf2(spatialRegionSize), 5613786Sjavier.bueno@metempsy.com "The spatial region size must be a power of 2."); 5713786Sjavier.bueno@metempsy.com} 5813786Sjavier.bueno@metempsy.com 5913786Sjavier.bueno@metempsy.comvoid 6013786Sjavier.bueno@metempsy.comSTeMSPrefetcher::checkForActiveGenerationsEnd() { 6113786Sjavier.bueno@metempsy.com // This prefetcher operates attached to the L1 and it observes all 6213786Sjavier.bueno@metempsy.com // accesses, this guarantees that no evictions are missed 6313786Sjavier.bueno@metempsy.com 6413786Sjavier.bueno@metempsy.com // Iterate over all entries, if any recorded cacheline has been evicted, 6513786Sjavier.bueno@metempsy.com // the generation finishes, move the entry to the PST 6613786Sjavier.bueno@metempsy.com for (auto &agt_entry : activeGenerationTable) { 6713786Sjavier.bueno@metempsy.com if (agt_entry.isValid()) { 6813786Sjavier.bueno@metempsy.com bool generation_ended = false; 6913786Sjavier.bueno@metempsy.com bool sr_is_secure = agt_entry.isSecure(); 7013786Sjavier.bueno@metempsy.com for (auto &seq_entry : agt_entry.sequence) { 7113786Sjavier.bueno@metempsy.com if (seq_entry.counter > 0) { 7213786Sjavier.bueno@metempsy.com Addr cache_addr = 7313786Sjavier.bueno@metempsy.com agt_entry.paddress + seq_entry.offset * blkSize; 7413786Sjavier.bueno@metempsy.com if (!inCache(cache_addr, sr_is_secure) && 7513786Sjavier.bueno@metempsy.com !inMissQueue(cache_addr, sr_is_secure)) { 7613786Sjavier.bueno@metempsy.com generation_ended = true; 7713786Sjavier.bueno@metempsy.com break; 7813786Sjavier.bueno@metempsy.com } 7913786Sjavier.bueno@metempsy.com } 8013786Sjavier.bueno@metempsy.com } 8113786Sjavier.bueno@metempsy.com if (generation_ended) { 8213786Sjavier.bueno@metempsy.com // PST is indexed using the PC (secure bit is unused) 8313786Sjavier.bueno@metempsy.com ActiveGenerationTableEntry *pst_entry = 8413786Sjavier.bueno@metempsy.com patternSequenceTable.findEntry(agt_entry.pc, 8513786Sjavier.bueno@metempsy.com false /*unused*/); 8613786Sjavier.bueno@metempsy.com if (pst_entry == nullptr) { 8713786Sjavier.bueno@metempsy.com // Tipically an entry will not exist 8813786Sjavier.bueno@metempsy.com pst_entry = patternSequenceTable.findVictim(agt_entry.pc); 8913786Sjavier.bueno@metempsy.com assert(pst_entry != nullptr); 9013786Sjavier.bueno@metempsy.com patternSequenceTable.insertEntry(agt_entry.pc, 9113786Sjavier.bueno@metempsy.com false /*unused*/, pst_entry); 9213786Sjavier.bueno@metempsy.com } else { 9313786Sjavier.bueno@metempsy.com patternSequenceTable.accessEntry(pst_entry); 9413786Sjavier.bueno@metempsy.com } 9513786Sjavier.bueno@metempsy.com // If the entry existed, this will update the values, if not, 9613786Sjavier.bueno@metempsy.com // this also sets the values of the entry 9713786Sjavier.bueno@metempsy.com pst_entry->update(agt_entry); 9813786Sjavier.bueno@metempsy.com // Free the AGT entry 9913786Sjavier.bueno@metempsy.com agt_entry.setInvalid(); 10013786Sjavier.bueno@metempsy.com } 10113786Sjavier.bueno@metempsy.com } 10213786Sjavier.bueno@metempsy.com } 10313786Sjavier.bueno@metempsy.com} 10413786Sjavier.bueno@metempsy.com 10513786Sjavier.bueno@metempsy.comvoid 10613786Sjavier.bueno@metempsy.comSTeMSPrefetcher::addToRMOB(Addr sr_addr, Addr pst_addr, unsigned int delta) 10713786Sjavier.bueno@metempsy.com{ 10813786Sjavier.bueno@metempsy.com RegionMissOrderBufferEntry &rmob_entry = rmob[rmobHead]; 10913786Sjavier.bueno@metempsy.com rmobHead = (rmobHead + 1) % rmob.size(); 11013786Sjavier.bueno@metempsy.com 11113786Sjavier.bueno@metempsy.com rmob_entry.srAddress = sr_addr; 11213786Sjavier.bueno@metempsy.com rmob_entry.pstAddress = pst_addr; 11313786Sjavier.bueno@metempsy.com rmob_entry.delta = delta; 11413786Sjavier.bueno@metempsy.com rmob_entry.valid = true; 11513786Sjavier.bueno@metempsy.com} 11613786Sjavier.bueno@metempsy.com 11713786Sjavier.bueno@metempsy.comvoid 11813786Sjavier.bueno@metempsy.comSTeMSPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 11913786Sjavier.bueno@metempsy.com std::vector<AddrPriority> &addresses) 12013786Sjavier.bueno@metempsy.com{ 12113786Sjavier.bueno@metempsy.com if (!pfi.hasPC()) { 12213786Sjavier.bueno@metempsy.com DPRINTF(HWPrefetch, "Ignoring request with no PC.\n"); 12313786Sjavier.bueno@metempsy.com return; 12413786Sjavier.bueno@metempsy.com } 12513786Sjavier.bueno@metempsy.com 12613786Sjavier.bueno@metempsy.com Addr pc = pfi.getPC(); 12713786Sjavier.bueno@metempsy.com bool is_secure = pfi.isSecure(); 12813786Sjavier.bueno@metempsy.com // Spatial region address 12913786Sjavier.bueno@metempsy.com Addr sr_addr = pfi.getAddr() / spatialRegionSize; 13013786Sjavier.bueno@metempsy.com Addr paddr = pfi.getPaddr(); 13113786Sjavier.bueno@metempsy.com 13213786Sjavier.bueno@metempsy.com // Offset in cachelines within the spatial region 13313786Sjavier.bueno@metempsy.com Addr sr_offset = (pfi.getAddr() % spatialRegionSize) / blkSize; 13413786Sjavier.bueno@metempsy.com 13513786Sjavier.bueno@metempsy.com // Check if any active generation has ended 13613786Sjavier.bueno@metempsy.com checkForActiveGenerationsEnd(); 13713786Sjavier.bueno@metempsy.com 13813786Sjavier.bueno@metempsy.com ActiveGenerationTableEntry *agt_entry = 13913786Sjavier.bueno@metempsy.com activeGenerationTable.findEntry(sr_addr, is_secure); 14013786Sjavier.bueno@metempsy.com if (agt_entry != nullptr) { 14113786Sjavier.bueno@metempsy.com // found an entry in the AGT, entry is currently being recorded, 14213786Sjavier.bueno@metempsy.com // add the offset 14313786Sjavier.bueno@metempsy.com activeGenerationTable.accessEntry(agt_entry); 14413786Sjavier.bueno@metempsy.com agt_entry->addOffset(sr_offset); 14513786Sjavier.bueno@metempsy.com lastTriggerCounter += 1; 14613786Sjavier.bueno@metempsy.com } else { 14713786Sjavier.bueno@metempsy.com // Not found, this is the first access (Trigger access) 14813786Sjavier.bueno@metempsy.com 14913786Sjavier.bueno@metempsy.com // Add entry to RMOB 15013786Sjavier.bueno@metempsy.com Addr pst_addr = (pc << spatialRegionSizeBits) + sr_offset; 15113786Sjavier.bueno@metempsy.com addToRMOB(sr_addr, pst_addr, lastTriggerCounter); 15213786Sjavier.bueno@metempsy.com // Reset last trigger counter 15313786Sjavier.bueno@metempsy.com lastTriggerCounter = 0; 15413786Sjavier.bueno@metempsy.com 15513786Sjavier.bueno@metempsy.com // allocate a new AGT entry 15613786Sjavier.bueno@metempsy.com agt_entry = activeGenerationTable.findVictim(sr_addr); 15713786Sjavier.bueno@metempsy.com assert(agt_entry != nullptr); 15813786Sjavier.bueno@metempsy.com activeGenerationTable.insertEntry(sr_addr, is_secure, agt_entry); 15913786Sjavier.bueno@metempsy.com agt_entry->pc = pc; 16013786Sjavier.bueno@metempsy.com agt_entry->paddress = paddr; 16113786Sjavier.bueno@metempsy.com agt_entry->addOffset(sr_offset); 16213786Sjavier.bueno@metempsy.com } 16313786Sjavier.bueno@metempsy.com // increase the seq Counter for other entries 16413786Sjavier.bueno@metempsy.com for (auto &agt_e : activeGenerationTable) { 16513786Sjavier.bueno@metempsy.com if (agt_e.isValid() && agt_entry != &agt_e) { 16613786Sjavier.bueno@metempsy.com agt_e.seqCounter += 1; 16713786Sjavier.bueno@metempsy.com } 16813786Sjavier.bueno@metempsy.com } 16913786Sjavier.bueno@metempsy.com 17013786Sjavier.bueno@metempsy.com // Prefetch generation: if this is a miss, search for the most recent 17113786Sjavier.bueno@metempsy.com // entry in the RMOB, and reconstruct the registered access sequence 17213786Sjavier.bueno@metempsy.com if (pfi.isCacheMiss()) { 17313786Sjavier.bueno@metempsy.com for (unsigned int idx = (rmobHead - 1) % rmob.size(); 17413786Sjavier.bueno@metempsy.com idx != rmobHead && rmob[idx].valid; 17513786Sjavier.bueno@metempsy.com idx = (idx - 1) % rmob.size()) 17613786Sjavier.bueno@metempsy.com { 17713786Sjavier.bueno@metempsy.com if (rmob[idx].srAddress == sr_addr) { 17813786Sjavier.bueno@metempsy.com // reconstruct the access sequence 17913786Sjavier.bueno@metempsy.com reconstructSequence(idx, addresses); 18013786Sjavier.bueno@metempsy.com break; 18113786Sjavier.bueno@metempsy.com } 18213786Sjavier.bueno@metempsy.com } 18313786Sjavier.bueno@metempsy.com } 18413786Sjavier.bueno@metempsy.com} 18513786Sjavier.bueno@metempsy.com 18613786Sjavier.bueno@metempsy.comvoid 18713786Sjavier.bueno@metempsy.comSTeMSPrefetcher::reconstructSequence(unsigned int rmob_idx, 18813786Sjavier.bueno@metempsy.com std::vector<AddrPriority> &addresses) 18913786Sjavier.bueno@metempsy.com{ 19013786Sjavier.bueno@metempsy.com std::vector<Addr> reconstruction(reconstructionEntries, MaxAddr); 19113786Sjavier.bueno@metempsy.com unsigned int idx = 0; 19213786Sjavier.bueno@metempsy.com // process rmob entries from rmob_idx (most recent with 19313786Sjavier.bueno@metempsy.com // address = sr_addr) to the last one (rmobHead) 19413786Sjavier.bueno@metempsy.com for (int i = rmob_idx; 19513786Sjavier.bueno@metempsy.com i != rmobHead && idx < reconstructionEntries; 19613786Sjavier.bueno@metempsy.com i = (i + 1) % rmob.size()) 19713786Sjavier.bueno@metempsy.com { 19813786Sjavier.bueno@metempsy.com reconstruction[idx] = rmob[i].srAddress * spatialRegionSize; 19913786Sjavier.bueno@metempsy.com unsigned int next_i = (i + 1) % rmob.size(); 20013786Sjavier.bueno@metempsy.com idx += rmob[next_i].delta + 1; 20113786Sjavier.bueno@metempsy.com } 20213786Sjavier.bueno@metempsy.com // Now query the PST with the PC of each RMOB entry 20313786Sjavier.bueno@metempsy.com idx = 0; 20413786Sjavier.bueno@metempsy.com for (int i = rmob_idx; 20513786Sjavier.bueno@metempsy.com i != rmobHead && idx < reconstructionEntries; 20613786Sjavier.bueno@metempsy.com i = (i + 1) % rmob.size()) 20713786Sjavier.bueno@metempsy.com { 20813786Sjavier.bueno@metempsy.com ActiveGenerationTableEntry *pst_entry = 20913786Sjavier.bueno@metempsy.com patternSequenceTable.findEntry(rmob[i].pstAddress, 21013786Sjavier.bueno@metempsy.com false /* unused */); 21113786Sjavier.bueno@metempsy.com if (pst_entry != nullptr) { 21213786Sjavier.bueno@metempsy.com patternSequenceTable.accessEntry(pst_entry); 21313786Sjavier.bueno@metempsy.com for (auto &seq_entry : pst_entry->sequence) { 21413786Sjavier.bueno@metempsy.com if (seq_entry.counter > 1) { 21513786Sjavier.bueno@metempsy.com // 3-bit counter: high enough confidence with a 21613786Sjavier.bueno@metempsy.com // value greater than 1 21713786Sjavier.bueno@metempsy.com Addr rec_addr = rmob[i].srAddress * spatialRegionSize + 21813786Sjavier.bueno@metempsy.com seq_entry.offset; 21913786Sjavier.bueno@metempsy.com unsigned ridx = idx + seq_entry.delta; 22013786Sjavier.bueno@metempsy.com // Try to use the corresponding position, if it has been 22113786Sjavier.bueno@metempsy.com // already used, look the surrounding positions 22213786Sjavier.bueno@metempsy.com if (ridx < reconstructionEntries && 22313786Sjavier.bueno@metempsy.com reconstruction[ridx] == MaxAddr) { 22413786Sjavier.bueno@metempsy.com reconstruction[ridx] = rec_addr; 22513786Sjavier.bueno@metempsy.com } else if ((ridx + 1) < reconstructionEntries && 22613786Sjavier.bueno@metempsy.com reconstruction[ridx + 1] == MaxAddr) { 22713786Sjavier.bueno@metempsy.com reconstruction[ridx + 1] = rec_addr; 22813786Sjavier.bueno@metempsy.com } else if ((ridx + 2) < reconstructionEntries && 22913786Sjavier.bueno@metempsy.com reconstruction[ridx + 2] == MaxAddr) { 23013786Sjavier.bueno@metempsy.com reconstruction[ridx + 2] = rec_addr; 23113786Sjavier.bueno@metempsy.com } else if ((ridx > 0) && 23213786Sjavier.bueno@metempsy.com ((ridx - 1) < reconstructionEntries) && 23313786Sjavier.bueno@metempsy.com reconstruction[ridx - 1] == MaxAddr) { 23413786Sjavier.bueno@metempsy.com reconstruction[ridx - 1] = rec_addr; 23513786Sjavier.bueno@metempsy.com } else if ((ridx > 1) && 23613786Sjavier.bueno@metempsy.com ((ridx - 2) < reconstructionEntries) && 23713786Sjavier.bueno@metempsy.com reconstruction[ridx - 2] == MaxAddr) { 23813786Sjavier.bueno@metempsy.com reconstruction[ridx - 2] = rec_addr; 23913786Sjavier.bueno@metempsy.com } 24013786Sjavier.bueno@metempsy.com } 24113786Sjavier.bueno@metempsy.com } 24213786Sjavier.bueno@metempsy.com } 24313786Sjavier.bueno@metempsy.com unsigned int next_i = (i + 1) % rmob.size(); 24413786Sjavier.bueno@metempsy.com idx += rmob[next_i].delta + 1; 24513786Sjavier.bueno@metempsy.com } 24613786Sjavier.bueno@metempsy.com for (Addr pf_addr : reconstruction) { 24713786Sjavier.bueno@metempsy.com if (pf_addr != MaxAddr) { 24813786Sjavier.bueno@metempsy.com addresses.push_back(AddrPriority(pf_addr, 0)); 24913786Sjavier.bueno@metempsy.com } 25013786Sjavier.bueno@metempsy.com } 25113786Sjavier.bueno@metempsy.com} 25213786Sjavier.bueno@metempsy.com 25313786Sjavier.bueno@metempsy.comSTeMSPrefetcher * 25413786Sjavier.bueno@metempsy.comSTeMSPrefetcherParams::create() 25513786Sjavier.bueno@metempsy.com{ 25613786Sjavier.bueno@metempsy.com return new STeMSPrefetcher(this); 25713786Sjavier.bueno@metempsy.com} 258