spatio_temporal_memory_streaming.cc revision 13963:94555f0223ba
111598Sandreas.sandberg@arm.com/** 27586SAli.Saidi@arm.com * Copyright (c) 2019 Metempsy Technology Consulting 37586SAli.Saidi@arm.com * All rights reserved. 47586SAli.Saidi@arm.com * 57586SAli.Saidi@arm.com * Redistribution and use in source and binary forms, with or without 67586SAli.Saidi@arm.com * modification, are permitted provided that the following conditions are 77586SAli.Saidi@arm.com * met: redistributions of source code must retain the above copyright 87586SAli.Saidi@arm.com * notice, this list of conditions and the following disclaimer; 97586SAli.Saidi@arm.com * redistributions in binary form must reproduce the above copyright 107586SAli.Saidi@arm.com * notice, this list of conditions and the following disclaimer in the 117586SAli.Saidi@arm.com * documentation and/or other materials provided with the distribution; 127586SAli.Saidi@arm.com * neither the name of the copyright holders nor the names of its 1310118Snilay@cs.wisc.edu * contributors may be used to endorse or promote products derived from 1410118Snilay@cs.wisc.edu * this software without specific prior written permission. 153970Sgblack@eecs.umich.edu * 163005Sstever@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 173005Sstever@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 183005Sstever@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 193005Sstever@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 203005Sstever@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 213005Sstever@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 223005Sstever@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 233005Sstever@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 243005Sstever@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 253005Sstever@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 263005Sstever@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 273005Sstever@eecs.umich.edu * 283005Sstever@eecs.umich.edu * Authors: Javier Bueno 293005Sstever@eecs.umich.edu */ 303005Sstever@eecs.umich.edu 313005Sstever@eecs.umich.edu#include "mem/cache/prefetch/spatio_temporal_memory_streaming.hh" 323005Sstever@eecs.umich.edu 333005Sstever@eecs.umich.edu#include "debug/HWPrefetch.hh" 343005Sstever@eecs.umich.edu#include "mem/cache/prefetch/associative_set_impl.hh" 353005Sstever@eecs.umich.edu#include "params/STeMSPrefetcher.hh" 363005Sstever@eecs.umich.edu 373005Sstever@eecs.umich.eduSTeMSPrefetcher::STeMSPrefetcher(const STeMSPrefetcherParams *p) 383005Sstever@eecs.umich.edu : QueuedPrefetcher(p), spatialRegionSize(p->spatial_region_size), 393005Sstever@eecs.umich.edu spatialRegionSizeBits(floorLog2(p->spatial_region_size)), 403005Sstever@eecs.umich.edu reconstructionEntries(p->reconstruction_entries), 413005Sstever@eecs.umich.edu activeGenerationTable(p->active_generation_table_assoc, 4210118Snilay@cs.wisc.edu p->active_generation_table_entries, 433005Sstever@eecs.umich.edu p->active_generation_table_indexing_policy, 446654Snate@binkert.org p->active_generation_table_replacement_policy, 456654Snate@binkert.org ActiveGenerationTableEntry( 462889SN/A spatialRegionSize / blkSize)), 472710SN/A patternSequenceTable(p->pattern_sequence_table_assoc, 486654Snate@binkert.org p->pattern_sequence_table_entries, 496654Snate@binkert.org p->pattern_sequence_table_indexing_policy, 506654Snate@binkert.org p->pattern_sequence_table_replacement_policy, 515457Ssaidi@eecs.umich.edu ActiveGenerationTableEntry( 5211670Sandreas.hansson@arm.com spatialRegionSize / blkSize)), 536654Snate@binkert.org rmob(p->region_miss_order_buffer_entries), rmobHead(0) 5410118Snilay@cs.wisc.edu{ 5511670Sandreas.hansson@arm.com fatal_if(!isPowerOf2(spatialRegionSize), 566654Snate@binkert.org "The spatial region size must be a power of 2."); 572934SN/A} 582549SN/A 592995SN/Avoid 603395Shsul@eecs.umich.eduSTeMSPrefetcher::checkForActiveGenerationsEnd() { 616981SLisa.Hsu@amd.com // This prefetcher operates attached to the L1 and it observes all 629836Sandreas.hansson@arm.com // accesses, this guarantees that no evictions are missed 633448Shsul@eecs.umich.edu 648920Snilay@cs.wisc.edu // Iterate over all entries, if any recorded cacheline has been evicted, 653444Sktlim@umich.edu // the generation finishes, move the entry to the PST 663304Sstever@eecs.umich.edu for (auto &agt_entry : activeGenerationTable) { 679653SAndreas.Sandberg@ARM.com if (agt_entry.isValid()) { 689653SAndreas.Sandberg@ARM.com bool generation_ended = false; 699653SAndreas.Sandberg@ARM.com bool sr_is_secure = agt_entry.isSecure(); 709653SAndreas.Sandberg@ARM.com for (auto &seq_entry : agt_entry.sequence) { 719653SAndreas.Sandberg@ARM.com if (seq_entry.counter > 0) { 729653SAndreas.Sandberg@ARM.com Addr cache_addr = 739653SAndreas.Sandberg@ARM.com agt_entry.paddress + seq_entry.offset * blkSize; 7410594Sgabeblack@google.com if (!inCache(cache_addr, sr_is_secure) && 7510594Sgabeblack@google.com !inMissQueue(cache_addr, sr_is_secure)) { 7610594Sgabeblack@google.com generation_ended = true; 7710594Sgabeblack@google.com break; 7810594Sgabeblack@google.com } 7910594Sgabeblack@google.com } 8010594Sgabeblack@google.com } 8110594Sgabeblack@google.com if (generation_ended) { 8210594Sgabeblack@google.com // PST is indexed using the PC (secure bit is unused) 8310594Sgabeblack@google.com ActiveGenerationTableEntry *pst_entry = 8410594Sgabeblack@google.com patternSequenceTable.findEntry(agt_entry.pc, 8510119Snilay@cs.wisc.edu false /*unused*/); 8610594Sgabeblack@google.com if (pst_entry == nullptr) { 8710119Snilay@cs.wisc.edu // Tipically an entry will not exist 8810594Sgabeblack@google.com pst_entry = patternSequenceTable.findVictim(agt_entry.pc); 8910594Sgabeblack@google.com assert(pst_entry != nullptr); 9010119Snilay@cs.wisc.edu patternSequenceTable.insertEntry(agt_entry.pc, 9110594Sgabeblack@google.com false /*unused*/, pst_entry); 9210119Snilay@cs.wisc.edu } else { 9310594Sgabeblack@google.com patternSequenceTable.accessEntry(pst_entry); 9410119Snilay@cs.wisc.edu } 9510119Snilay@cs.wisc.edu // If the entry existed, this will update the values, if not, 9610594Sgabeblack@google.com // this also sets the values of the entry 9710119Snilay@cs.wisc.edu pst_entry->update(agt_entry); 9810512SAli.Saidi@ARM.com // Free the AGT entry 9910512SAli.Saidi@ARM.com agt_entry.setInvalid(); 10010594Sgabeblack@google.com } 10110780SCurtis.Dunham@arm.com } 10211598Sandreas.sandberg@arm.com } 10311598Sandreas.sandberg@arm.com} 10410119Snilay@cs.wisc.edu 10510119Snilay@cs.wisc.eduvoid 10610119Snilay@cs.wisc.eduSTeMSPrefetcher::addToRMOB(Addr sr_addr, Addr pst_addr, unsigned int delta) 10710119Snilay@cs.wisc.edu{ 1082566SN/A RegionMissOrderBufferEntry &rmob_entry = rmob[rmobHead]; 10910119Snilay@cs.wisc.edu rmobHead = (rmobHead + 1) % rmob.size(); 11010119Snilay@cs.wisc.edu 1119665Sandreas.hansson@arm.com rmob_entry.srAddress = sr_addr; 11210119Snilay@cs.wisc.edu rmob_entry.pstAddress = pst_addr; 11310119Snilay@cs.wisc.edu rmob_entry.delta = delta; 11410119Snilay@cs.wisc.edu rmob_entry.valid = true; 11510119Snilay@cs.wisc.edu} 11610119Snilay@cs.wisc.edu 11710119Snilay@cs.wisc.eduvoid 11810119Snilay@cs.wisc.eduSTeMSPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 11910119Snilay@cs.wisc.edu std::vector<AddrPriority> &addresses) 12010119Snilay@cs.wisc.edu{ 12110119Snilay@cs.wisc.edu if (!pfi.hasPC()) { 12210119Snilay@cs.wisc.edu DPRINTF(HWPrefetch, "Ignoring request with no PC.\n"); 12310119Snilay@cs.wisc.edu return; 12410119Snilay@cs.wisc.edu } 12510119Snilay@cs.wisc.edu 12610119Snilay@cs.wisc.edu Addr pc = pfi.getPC(); 12710119Snilay@cs.wisc.edu bool is_secure = pfi.isSecure(); 12810119Snilay@cs.wisc.edu // Spatial region address 12910119Snilay@cs.wisc.edu Addr sr_addr = pfi.getAddr() / spatialRegionSize; 13010119Snilay@cs.wisc.edu Addr paddr = pfi.getPaddr(); 13110119Snilay@cs.wisc.edu 13210119Snilay@cs.wisc.edu // Offset in cachelines within the spatial region 13310119Snilay@cs.wisc.edu Addr sr_offset = (pfi.getAddr() % spatialRegionSize) / blkSize; 13410119Snilay@cs.wisc.edu 13510119Snilay@cs.wisc.edu // Check if any active generation has ended 13610119Snilay@cs.wisc.edu checkForActiveGenerationsEnd(); 13710119Snilay@cs.wisc.edu 13810119Snilay@cs.wisc.edu ActiveGenerationTableEntry *agt_entry = 13910119Snilay@cs.wisc.edu activeGenerationTable.findEntry(sr_addr, is_secure); 14010119Snilay@cs.wisc.edu if (agt_entry != nullptr) { 14110119Snilay@cs.wisc.edu // found an entry in the AGT, entry is currently being recorded, 14210119Snilay@cs.wisc.edu // add the offset 14310119Snilay@cs.wisc.edu activeGenerationTable.accessEntry(agt_entry); 14410119Snilay@cs.wisc.edu agt_entry->addOffset(sr_offset); 14510119Snilay@cs.wisc.edu lastTriggerCounter += 1; 14610119Snilay@cs.wisc.edu } else { 14710119Snilay@cs.wisc.edu // Not found, this is the first access (Trigger access) 14810119Snilay@cs.wisc.edu 14910119Snilay@cs.wisc.edu // Add entry to RMOB 15010119Snilay@cs.wisc.edu Addr pst_addr = (pc << spatialRegionSizeBits) + sr_offset; 15110119Snilay@cs.wisc.edu addToRMOB(sr_addr, pst_addr, lastTriggerCounter); 15210119Snilay@cs.wisc.edu // Reset last trigger counter 15310119Snilay@cs.wisc.edu lastTriggerCounter = 0; 15410519Snilay@cs.wisc.edu 15510519Snilay@cs.wisc.edu // allocate a new AGT entry 15610119Snilay@cs.wisc.edu agt_entry = activeGenerationTable.findVictim(sr_addr); 15710119Snilay@cs.wisc.edu assert(agt_entry != nullptr); 15810119Snilay@cs.wisc.edu activeGenerationTable.insertEntry(sr_addr, is_secure, agt_entry); 15910119Snilay@cs.wisc.edu agt_entry->pc = pc; 16010119Snilay@cs.wisc.edu agt_entry->paddress = paddr; 16110547Snilay@cs.wisc.edu agt_entry->addOffset(sr_offset); 16210547Snilay@cs.wisc.edu } 16310547Snilay@cs.wisc.edu // increase the seq Counter for other entries 16410547Snilay@cs.wisc.edu for (auto &agt_e : activeGenerationTable) { 16510119Snilay@cs.wisc.edu if (agt_e.isValid() && agt_entry != &agt_e) { 16610119Snilay@cs.wisc.edu agt_e.seqCounter += 1; 16710119Snilay@cs.wisc.edu } 16810119Snilay@cs.wisc.edu } 16910119Snilay@cs.wisc.edu 17010119Snilay@cs.wisc.edu // Prefetch generation: if this is a miss, search for the most recent 17110119Snilay@cs.wisc.edu // entry in the RMOB, and reconstruct the registered access sequence 17210119Snilay@cs.wisc.edu if (pfi.isCacheMiss()) { 17310120Snilay@cs.wisc.edu for (unsigned int idx = (rmobHead - 1) % rmob.size(); 17410120Snilay@cs.wisc.edu idx != rmobHead && rmob[idx].valid; 17510119Snilay@cs.wisc.edu idx = (idx - 1) % rmob.size()) 17611598Sandreas.sandberg@arm.com { 17710120Snilay@cs.wisc.edu if (rmob[idx].srAddress == sr_addr) { 17810120Snilay@cs.wisc.edu // reconstruct the access sequence 17910119Snilay@cs.wisc.edu reconstructSequence(idx, addresses); 18011598Sandreas.sandberg@arm.com break; 18111150Smitch.hayenga@arm.com } 18211150Smitch.hayenga@arm.com } 18311150Smitch.hayenga@arm.com } 18410119Snilay@cs.wisc.edu} 1852995SN/A 18610119Snilay@cs.wisc.eduvoid 18710119Snilay@cs.wisc.eduSTeMSPrefetcher::reconstructSequence(unsigned int rmob_idx, 18810119Snilay@cs.wisc.edu std::vector<AddrPriority> &addresses) 18910119Snilay@cs.wisc.edu{ 19010119Snilay@cs.wisc.edu std::vector<Addr> reconstruction(reconstructionEntries, MaxAddr); 19110780SCurtis.Dunham@arm.com unsigned int idx = 0; 19210119Snilay@cs.wisc.edu // process rmob entries from rmob_idx (most recent with 19310119Snilay@cs.wisc.edu // address = sr_addr) to the last one (rmobHead) 19410119Snilay@cs.wisc.edu for (int i = rmob_idx; 1953304Sstever@eecs.umich.edu i != rmobHead && idx < reconstructionEntries; 19610119Snilay@cs.wisc.edu i = (i + 1) % rmob.size()) 19710119Snilay@cs.wisc.edu { 19810119Snilay@cs.wisc.edu reconstruction[idx] = rmob[i].srAddress * spatialRegionSize; 19910119Snilay@cs.wisc.edu unsigned int next_i = (i + 1) % rmob.size(); 20010119Snilay@cs.wisc.edu idx += rmob[next_i].delta + 1; 20110119Snilay@cs.wisc.edu } 2026135Sgblack@eecs.umich.edu // Now query the PST with the PC of each RMOB entry 20310608Sdam.sunwoo@arm.com idx = 0; 20410608Sdam.sunwoo@arm.com for (int i = rmob_idx; 20510608Sdam.sunwoo@arm.com i != rmobHead && idx < reconstructionEntries; 20610608Sdam.sunwoo@arm.com i = (i + 1) % rmob.size()) 20710608Sdam.sunwoo@arm.com { 20810608Sdam.sunwoo@arm.com ActiveGenerationTableEntry *pst_entry = 20910608Sdam.sunwoo@arm.com patternSequenceTable.findEntry(rmob[i].pstAddress, 21010119Snilay@cs.wisc.edu false /* unused */); 21110119Snilay@cs.wisc.edu if (pst_entry != nullptr) { 21210119Snilay@cs.wisc.edu patternSequenceTable.accessEntry(pst_entry); 21310608Sdam.sunwoo@arm.com for (auto &seq_entry : pst_entry->sequence) { 21410608Sdam.sunwoo@arm.com if (seq_entry.counter > 1) { 21510119Snilay@cs.wisc.edu // 2-bit counter: high enough confidence with a 21610119Snilay@cs.wisc.edu // value greater than 1 21710119Snilay@cs.wisc.edu Addr rec_addr = rmob[i].srAddress * spatialRegionSize + 2183819Shsul@eecs.umich.edu seq_entry.offset; 21911251Sradhika.jagtap@ARM.com unsigned ridx = idx + seq_entry.delta; 22011251Sradhika.jagtap@ARM.com // Try to use the corresponding position, if it has been 22111251Sradhika.jagtap@ARM.com // already used, look the surrounding positions 22211251Sradhika.jagtap@ARM.com if (ridx < reconstructionEntries && 22311251Sradhika.jagtap@ARM.com reconstruction[ridx] == MaxAddr) { 22411251Sradhika.jagtap@ARM.com reconstruction[ridx] = rec_addr; 22511251Sradhika.jagtap@ARM.com } else if ((ridx + 1) < reconstructionEntries && 22611251Sradhika.jagtap@ARM.com reconstruction[ridx + 1] == MaxAddr) { 22711251Sradhika.jagtap@ARM.com reconstruction[ridx + 1] = rec_addr; 22811251Sradhika.jagtap@ARM.com } else if ((ridx + 2) < reconstructionEntries && 22911251Sradhika.jagtap@ARM.com reconstruction[ridx + 2] == MaxAddr) { 23010119Snilay@cs.wisc.edu reconstruction[ridx + 2] = rec_addr; 23111183Serfan.azarkhish@unibo.it } else if ((ridx > 0) && 23210119Snilay@cs.wisc.edu ((ridx - 1) < reconstructionEntries) && 23310118Snilay@cs.wisc.edu reconstruction[ridx - 1] == MaxAddr) { 23410119Snilay@cs.wisc.edu reconstruction[ridx - 1] = rec_addr; 2359827Sakash.bagdia@arm.com } else if ((ridx > 1) && 23610119Snilay@cs.wisc.edu ((ridx - 2) < reconstructionEntries) && 23710119Snilay@cs.wisc.edu reconstruction[ridx - 2] == MaxAddr) { 23810119Snilay@cs.wisc.edu reconstruction[ridx - 2] = rec_addr; 23910119Snilay@cs.wisc.edu } 24010119Snilay@cs.wisc.edu } 24110119Snilay@cs.wisc.edu } 2429827Sakash.bagdia@arm.com } 24310594Sgabeblack@google.com unsigned int next_i = (i + 1) % rmob.size(); 2446654Snate@binkert.org idx += rmob[next_i].delta + 1; 24510594Sgabeblack@google.com } 2466654Snate@binkert.org for (Addr pf_addr : reconstruction) { 24710594Sgabeblack@google.com if (pf_addr != MaxAddr) { 2486654Snate@binkert.org addresses.push_back(AddrPriority(pf_addr, 0)); 24910594Sgabeblack@google.com } 2506654Snate@binkert.org } 25110594Sgabeblack@google.com} 25210594Sgabeblack@google.com 2537586SAli.Saidi@arm.comSTeMSPrefetcher * 25410635Satgutier@umich.eduSTeMSPrefetcherParams::create() 25510635Satgutier@umich.edu{ 2568661SAli.Saidi@ARM.com return new STeMSPrefetcher(this); 2579827Sakash.bagdia@arm.com} 2589827Sakash.bagdia@arm.com