spatio_temporal_memory_streaming.cc revision 13963:94555f0223ba
16691Stjones1@inf.ed.ac.uk/** 26691Stjones1@inf.ed.ac.uk * Copyright (c) 2019 Metempsy Technology Consulting 36691Stjones1@inf.ed.ac.uk * All rights reserved. 46691Stjones1@inf.ed.ac.uk * 56691Stjones1@inf.ed.ac.uk * Redistribution and use in source and binary forms, with or without 66691Stjones1@inf.ed.ac.uk * modification, are permitted provided that the following conditions are 76691Stjones1@inf.ed.ac.uk * met: redistributions of source code must retain the above copyright 86691Stjones1@inf.ed.ac.uk * notice, this list of conditions and the following disclaimer; 96691Stjones1@inf.ed.ac.uk * redistributions in binary form must reproduce the above copyright 106691Stjones1@inf.ed.ac.uk * notice, this list of conditions and the following disclaimer in the 116691Stjones1@inf.ed.ac.uk * documentation and/or other materials provided with the distribution; 126691Stjones1@inf.ed.ac.uk * neither the name of the copyright holders nor the names of its 136691Stjones1@inf.ed.ac.uk * contributors may be used to endorse or promote products derived from 146691Stjones1@inf.ed.ac.uk * this software without specific prior written permission. 156691Stjones1@inf.ed.ac.uk * 166691Stjones1@inf.ed.ac.uk * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 176691Stjones1@inf.ed.ac.uk * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 186691Stjones1@inf.ed.ac.uk * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 196691Stjones1@inf.ed.ac.uk * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 206691Stjones1@inf.ed.ac.uk * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 216691Stjones1@inf.ed.ac.uk * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 226691Stjones1@inf.ed.ac.uk * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 236691Stjones1@inf.ed.ac.uk * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 246691Stjones1@inf.ed.ac.uk * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 256691Stjones1@inf.ed.ac.uk * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 266691Stjones1@inf.ed.ac.uk * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 276691Stjones1@inf.ed.ac.uk * 286691Stjones1@inf.ed.ac.uk * Authors: Javier Bueno 296691Stjones1@inf.ed.ac.uk */ 306691Stjones1@inf.ed.ac.uk 316691Stjones1@inf.ed.ac.uk#include "mem/cache/prefetch/spatio_temporal_memory_streaming.hh" 326691Stjones1@inf.ed.ac.uk 336691Stjones1@inf.ed.ac.uk#include "debug/HWPrefetch.hh" 346691Stjones1@inf.ed.ac.uk#include "mem/cache/prefetch/associative_set_impl.hh" 356691Stjones1@inf.ed.ac.uk#include "params/STeMSPrefetcher.hh" 366691Stjones1@inf.ed.ac.uk 376691Stjones1@inf.ed.ac.ukSTeMSPrefetcher::STeMSPrefetcher(const STeMSPrefetcherParams *p) 386691Stjones1@inf.ed.ac.uk : QueuedPrefetcher(p), spatialRegionSize(p->spatial_region_size), 396691Stjones1@inf.ed.ac.uk spatialRegionSizeBits(floorLog2(p->spatial_region_size)), 406691Stjones1@inf.ed.ac.uk reconstructionEntries(p->reconstruction_entries), 416691Stjones1@inf.ed.ac.uk activeGenerationTable(p->active_generation_table_assoc, 426691Stjones1@inf.ed.ac.uk p->active_generation_table_entries, 436691Stjones1@inf.ed.ac.uk p->active_generation_table_indexing_policy, 446691Stjones1@inf.ed.ac.uk p->active_generation_table_replacement_policy, 456691Stjones1@inf.ed.ac.uk ActiveGenerationTableEntry( 466691Stjones1@inf.ed.ac.uk spatialRegionSize / blkSize)), 476691Stjones1@inf.ed.ac.uk patternSequenceTable(p->pattern_sequence_table_assoc, 486691Stjones1@inf.ed.ac.uk p->pattern_sequence_table_entries, 496691Stjones1@inf.ed.ac.uk p->pattern_sequence_table_indexing_policy, 506691Stjones1@inf.ed.ac.uk p->pattern_sequence_table_replacement_policy, 516691Stjones1@inf.ed.ac.uk ActiveGenerationTableEntry( 526691Stjones1@inf.ed.ac.uk spatialRegionSize / blkSize)), 536691Stjones1@inf.ed.ac.uk rmob(p->region_miss_order_buffer_entries), rmobHead(0) 546691Stjones1@inf.ed.ac.uk{ 556691Stjones1@inf.ed.ac.uk fatal_if(!isPowerOf2(spatialRegionSize), 566691Stjones1@inf.ed.ac.uk "The spatial region size must be a power of 2."); 576691Stjones1@inf.ed.ac.uk} 586691Stjones1@inf.ed.ac.uk 596691Stjones1@inf.ed.ac.ukvoid 606691Stjones1@inf.ed.ac.ukSTeMSPrefetcher::checkForActiveGenerationsEnd() { 616691Stjones1@inf.ed.ac.uk // This prefetcher operates attached to the L1 and it observes all 6212104Snathanael.premillieu@arm.com // accesses, this guarantees that no evictions are missed 636691Stjones1@inf.ed.ac.uk 646691Stjones1@inf.ed.ac.uk // Iterate over all entries, if any recorded cacheline has been evicted, 656691Stjones1@inf.ed.ac.uk // the generation finishes, move the entry to the PST 667720Sgblack@eecs.umich.edu for (auto &agt_entry : activeGenerationTable) { 677720Sgblack@eecs.umich.edu if (agt_entry.isValid()) { 687720Sgblack@eecs.umich.edu bool generation_ended = false; 697720Sgblack@eecs.umich.edu bool sr_is_secure = agt_entry.isSecure(); 707720Sgblack@eecs.umich.edu for (auto &seq_entry : agt_entry.sequence) { 717720Sgblack@eecs.umich.edu if (seq_entry.counter > 0) { 7212614Sgabeblack@google.com Addr cache_addr = 7312614Sgabeblack@google.com agt_entry.paddress + seq_entry.offset * blkSize; 7412614Sgabeblack@google.com if (!inCache(cache_addr, sr_is_secure) && 7512614Sgabeblack@google.com !inMissQueue(cache_addr, sr_is_secure)) { 7612614Sgabeblack@google.com generation_ended = true; 7712614Sgabeblack@google.com break; 786691Stjones1@inf.ed.ac.uk } 796691Stjones1@inf.ed.ac.uk } 807811Ssteve.reinhardt@amd.com } 816691Stjones1@inf.ed.ac.uk if (generation_ended) { 826691Stjones1@inf.ed.ac.uk // PST is indexed using the PC (secure bit is unused) 83 ActiveGenerationTableEntry *pst_entry = 84 patternSequenceTable.findEntry(agt_entry.pc, 85 false /*unused*/); 86 if (pst_entry == nullptr) { 87 // Tipically an entry will not exist 88 pst_entry = patternSequenceTable.findVictim(agt_entry.pc); 89 assert(pst_entry != nullptr); 90 patternSequenceTable.insertEntry(agt_entry.pc, 91 false /*unused*/, pst_entry); 92 } else { 93 patternSequenceTable.accessEntry(pst_entry); 94 } 95 // If the entry existed, this will update the values, if not, 96 // this also sets the values of the entry 97 pst_entry->update(agt_entry); 98 // Free the AGT entry 99 agt_entry.setInvalid(); 100 } 101 } 102 } 103} 104 105void 106STeMSPrefetcher::addToRMOB(Addr sr_addr, Addr pst_addr, unsigned int delta) 107{ 108 RegionMissOrderBufferEntry &rmob_entry = rmob[rmobHead]; 109 rmobHead = (rmobHead + 1) % rmob.size(); 110 111 rmob_entry.srAddress = sr_addr; 112 rmob_entry.pstAddress = pst_addr; 113 rmob_entry.delta = delta; 114 rmob_entry.valid = true; 115} 116 117void 118STeMSPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 119 std::vector<AddrPriority> &addresses) 120{ 121 if (!pfi.hasPC()) { 122 DPRINTF(HWPrefetch, "Ignoring request with no PC.\n"); 123 return; 124 } 125 126 Addr pc = pfi.getPC(); 127 bool is_secure = pfi.isSecure(); 128 // Spatial region address 129 Addr sr_addr = pfi.getAddr() / spatialRegionSize; 130 Addr paddr = pfi.getPaddr(); 131 132 // Offset in cachelines within the spatial region 133 Addr sr_offset = (pfi.getAddr() % spatialRegionSize) / blkSize; 134 135 // Check if any active generation has ended 136 checkForActiveGenerationsEnd(); 137 138 ActiveGenerationTableEntry *agt_entry = 139 activeGenerationTable.findEntry(sr_addr, is_secure); 140 if (agt_entry != nullptr) { 141 // found an entry in the AGT, entry is currently being recorded, 142 // add the offset 143 activeGenerationTable.accessEntry(agt_entry); 144 agt_entry->addOffset(sr_offset); 145 lastTriggerCounter += 1; 146 } else { 147 // Not found, this is the first access (Trigger access) 148 149 // Add entry to RMOB 150 Addr pst_addr = (pc << spatialRegionSizeBits) + sr_offset; 151 addToRMOB(sr_addr, pst_addr, lastTriggerCounter); 152 // Reset last trigger counter 153 lastTriggerCounter = 0; 154 155 // allocate a new AGT entry 156 agt_entry = activeGenerationTable.findVictim(sr_addr); 157 assert(agt_entry != nullptr); 158 activeGenerationTable.insertEntry(sr_addr, is_secure, agt_entry); 159 agt_entry->pc = pc; 160 agt_entry->paddress = paddr; 161 agt_entry->addOffset(sr_offset); 162 } 163 // increase the seq Counter for other entries 164 for (auto &agt_e : activeGenerationTable) { 165 if (agt_e.isValid() && agt_entry != &agt_e) { 166 agt_e.seqCounter += 1; 167 } 168 } 169 170 // Prefetch generation: if this is a miss, search for the most recent 171 // entry in the RMOB, and reconstruct the registered access sequence 172 if (pfi.isCacheMiss()) { 173 for (unsigned int idx = (rmobHead - 1) % rmob.size(); 174 idx != rmobHead && rmob[idx].valid; 175 idx = (idx - 1) % rmob.size()) 176 { 177 if (rmob[idx].srAddress == sr_addr) { 178 // reconstruct the access sequence 179 reconstructSequence(idx, addresses); 180 break; 181 } 182 } 183 } 184} 185 186void 187STeMSPrefetcher::reconstructSequence(unsigned int rmob_idx, 188 std::vector<AddrPriority> &addresses) 189{ 190 std::vector<Addr> reconstruction(reconstructionEntries, MaxAddr); 191 unsigned int idx = 0; 192 // process rmob entries from rmob_idx (most recent with 193 // address = sr_addr) to the last one (rmobHead) 194 for (int i = rmob_idx; 195 i != rmobHead && idx < reconstructionEntries; 196 i = (i + 1) % rmob.size()) 197 { 198 reconstruction[idx] = rmob[i].srAddress * spatialRegionSize; 199 unsigned int next_i = (i + 1) % rmob.size(); 200 idx += rmob[next_i].delta + 1; 201 } 202 // Now query the PST with the PC of each RMOB entry 203 idx = 0; 204 for (int i = rmob_idx; 205 i != rmobHead && idx < reconstructionEntries; 206 i = (i + 1) % rmob.size()) 207 { 208 ActiveGenerationTableEntry *pst_entry = 209 patternSequenceTable.findEntry(rmob[i].pstAddress, 210 false /* unused */); 211 if (pst_entry != nullptr) { 212 patternSequenceTable.accessEntry(pst_entry); 213 for (auto &seq_entry : pst_entry->sequence) { 214 if (seq_entry.counter > 1) { 215 // 2-bit counter: high enough confidence with a 216 // value greater than 1 217 Addr rec_addr = rmob[i].srAddress * spatialRegionSize + 218 seq_entry.offset; 219 unsigned ridx = idx + seq_entry.delta; 220 // Try to use the corresponding position, if it has been 221 // already used, look the surrounding positions 222 if (ridx < reconstructionEntries && 223 reconstruction[ridx] == MaxAddr) { 224 reconstruction[ridx] = rec_addr; 225 } else if ((ridx + 1) < reconstructionEntries && 226 reconstruction[ridx + 1] == MaxAddr) { 227 reconstruction[ridx + 1] = rec_addr; 228 } else if ((ridx + 2) < reconstructionEntries && 229 reconstruction[ridx + 2] == MaxAddr) { 230 reconstruction[ridx + 2] = rec_addr; 231 } else if ((ridx > 0) && 232 ((ridx - 1) < reconstructionEntries) && 233 reconstruction[ridx - 1] == MaxAddr) { 234 reconstruction[ridx - 1] = rec_addr; 235 } else if ((ridx > 1) && 236 ((ridx - 2) < reconstructionEntries) && 237 reconstruction[ridx - 2] == MaxAddr) { 238 reconstruction[ridx - 2] = rec_addr; 239 } 240 } 241 } 242 } 243 unsigned int next_i = (i + 1) % rmob.size(); 244 idx += rmob[next_i].delta + 1; 245 } 246 for (Addr pf_addr : reconstruction) { 247 if (pf_addr != MaxAddr) { 248 addresses.push_back(AddrPriority(pf_addr, 0)); 249 } 250 } 251} 252 253STeMSPrefetcher * 254STeMSPrefetcherParams::create() 255{ 256 return new STeMSPrefetcher(this); 257} 258