pif.cc revision 13825
1/** 2 * Copyright (c) 2019 Metempsy Technology Consulting 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * Authors: Ivan Pizarro 29 */ 30 31#include "mem/cache/prefetch/pif.hh" 32 33#include <cmath> 34#include <utility> 35 36#include "debug/HWPrefetch.hh" 37#include "mem/cache/prefetch/associative_set_impl.hh" 38#include "params/PIFPrefetcher.hh" 39 40PIFPrefetcher::PIFPrefetcher(const PIFPrefetcherParams *p) 41 : QueuedPrefetcher(p), 42 precSize(p->prec_spatial_region_bits), 43 succSize(p->succ_spatial_region_bits), 44 maxCompactorEntries(p->compactor_entries), 45 maxStreamAddressBufferEntries(p->stream_address_buffer_entries), 46 historyBuffer(p->history_buffer_size), 47 historyBufferTail(0), 48 index(p->index_assoc, p->index_entries, p->index_indexing_policy, 49 p->index_replacement_policy), 50 streamAddressBuffer(), listenersPC() 51{ 52} 53 54PIFPrefetcher::CompactorEntry::CompactorEntry(Addr addr, 55 unsigned int prec_size, unsigned int succ_size) 56{ 57 trigger = addr; 58 prec.resize(prec_size, false); 59 succ.resize(succ_size, false); 60} 61 62unsigned int 63PIFPrefetcher::CompactorEntry::distanceFromTrigger(Addr target, 64 unsigned int log_blk_size) const { 65 const Addr target_blk = target >> log_blk_size; 66 const Addr trigger_blk = trigger >> log_blk_size; 67 68 return std::abs(target_blk - trigger_blk); 69} 70 71bool 72PIFPrefetcher::CompactorEntry::inSameSpatialRegion(Addr pc, 73 unsigned int log_blk_size, bool update) 74{ 75 unsigned int blk_distance = distanceFromTrigger(pc, log_blk_size); 76 77 bool hit = (pc > trigger) ? 78 (succ.size() >= blk_distance) : (prec.size() >= blk_distance); 79 if (hit && update) { 80 if (pc > trigger) { 81 succ[blk_distance - 1] = true; 82 } else if (pc < trigger) { 83 prec[blk_distance - 1] = true; 84 } 85 } 86 return hit; 87} 88 89bool 90PIFPrefetcher::CompactorEntry::hasAddress(Addr target, 91 unsigned int log_blk_size) const 92{ 93 unsigned int blk_distance = distanceFromTrigger(target, log_blk_size); 94 bool hit = false; 95 if (target > trigger) { 96 hit = blk_distance <= succ.size() && succ[blk_distance - 1]; 97 } else if (target < trigger) { 98 hit = blk_distance <= prec.size() && succ[blk_distance - 1]; 99 } else { 100 hit = true; 101 } 102 return hit; 103} 104 105void 106PIFPrefetcher::CompactorEntry::getPredictedAddresses(unsigned int log_blk_size, 107 std::vector<AddrPriority> &addresses) const 108{ 109 // Calculate the addresses of the instruction blocks that are encoded 110 // by the bit vector and issue prefetch requests for these addresses. 111 // Predictions are made by traversing the bit vector from left to right 112 // as this typically predicts the accesses in the order they will be 113 // issued in the core. 114 const Addr trigger_blk = trigger >> log_blk_size; 115 for (int i = prec.size()-1; i >= 0; i--) { 116 // Address from the preceding blocks to issue a prefetch 117 if (prec[i]) { 118 const Addr prec_addr = (trigger_blk - (i+1)) << log_blk_size; 119 addresses.push_back(AddrPriority(prec_addr, 0)); 120 } 121 } 122 for (int i = 0; i < succ.size(); i++) { 123 // Address from the succeding blocks to issue a prefetch 124 if (succ[i]) { 125 const Addr succ_addr = (trigger_blk + (i+1)) << log_blk_size; 126 addresses.push_back(AddrPriority(succ_addr, 0)); 127 } 128 } 129} 130 131void 132PIFPrefetcher::notifyRetiredInst(const Addr pc) 133{ 134 // First access to the prefetcher 135 if (temporalCompactor.size() == 0) { 136 spatialCompactor = CompactorEntry(pc, precSize, succSize); 137 } else { 138 // If the PC of the instruction retired is in the same spatial region 139 // than the last trigger address, update the bit vectors based on the 140 // distance between them 141 if (spatialCompactor.inSameSpatialRegion(pc, lBlkSize, true)) { 142 // If the PC of the instruction retired is outside the latest spatial 143 // region, check if it matches in any of the regions in the temporal 144 // compactor and update it to the MRU position 145 } else { 146 bool is_in_temporal_compactor = false; 147 148 // Check if the PC is in the temporal compactor 149 for (auto it = temporalCompactor.begin(); 150 it != temporalCompactor.end(); it++) 151 { 152 if (it->inSameSpatialRegion(pc, lBlkSize, false)) { 153 spatialCompactor = (*it); 154 temporalCompactor.erase(it); 155 is_in_temporal_compactor = true; 156 break; 157 } 158 } 159 160 if (temporalCompactor.size() == maxCompactorEntries) { 161 temporalCompactor.pop_front(); // Discard the LRU entry 162 } 163 164 temporalCompactor.push_back(spatialCompactor); 165 166 // If the compactor entry is neither the spatial or can't be 167 // found in the temporal compactor, reset the spatial compactor 168 // updating the trigger address and resetting the vector bits 169 if (!is_in_temporal_compactor) { 170 // Insert the spatial entry into the history buffer and update 171 // the 'index' table to point to the new entry 172 historyBuffer[historyBufferTail] = spatialCompactor; 173 174 IndexEntry *idx_entry = 175 index.findEntry(spatialCompactor.trigger, false); 176 if (idx_entry != nullptr) { 177 index.accessEntry(idx_entry); 178 } else { 179 idx_entry = index.findVictim(spatialCompactor.trigger); 180 assert(idx_entry != nullptr); 181 index.insertEntry(spatialCompactor.trigger, false, 182 idx_entry); 183 } 184 idx_entry->historyIndex = historyBufferTail; 185 186 historyBufferTail++; 187 if (historyBufferTail == historyBuffer.size()) { 188 historyBufferTail = 0; 189 } 190 191 // Reset the spatial compactor fields with the new address 192 spatialCompactor = CompactorEntry(pc, precSize, succSize); 193 } 194 } 195 } 196} 197 198void 199PIFPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 200 std::vector<AddrPriority> &addresses) 201{ 202 const Addr addr = pfi.getAddr(); 203 204 // First check if the access has been prefetched, this is done by 205 // comparing the access against the active Stream Address Buffers 206 for (auto &sabEntry : streamAddressBuffer) { 207 if (sabEntry->hasAddress(addr, lBlkSize)) { 208 // Advance to the next entry (first check if we have reached the 209 // end of the history buffer) 210 if (sabEntry == &(historyBuffer[historyBuffer.size() - 1])) { 211 sabEntry = &(historyBuffer[0]); 212 } else { 213 sabEntry++; 214 } 215 sabEntry->getPredictedAddresses(lBlkSize, addresses); 216 // We are done 217 return; 218 } 219 } 220 221 // Check if a valid entry in the 'index' table is found and allocate a new 222 // active prediction stream 223 IndexEntry *idx_entry = index.findEntry(addr, /* unused */ false); 224 225 if (idx_entry != nullptr) { 226 index.accessEntry(idx_entry); 227 // Trigger address from the 'index' table and index to the history 228 // buffer 229 const unsigned int hb_entry = idx_entry->historyIndex; 230 CompactorEntry *entry = &historyBuffer[hb_entry]; 231 232 // Track the block in the Stream Address Buffer 233 if (streamAddressBuffer.size() == maxStreamAddressBufferEntries) { 234 streamAddressBuffer.pop_front(); 235 } 236 streamAddressBuffer.push_back(entry); 237 238 entry->getPredictedAddresses(lBlkSize, addresses); 239 } 240} 241 242void 243PIFPrefetcher::PrefetchListenerPC::notify(const Addr& pc) 244{ 245 parent.notifyRetiredInst(pc); 246} 247 248void 249PIFPrefetcher::addEventProbeRetiredInsts(SimObject *obj, const char *name) 250{ 251 ProbeManager *pm(obj->getProbeManager()); 252 listenersPC.push_back(new PrefetchListenerPC(*this, pm, name)); 253} 254 255PIFPrefetcher* 256PIFPrefetcherParams::create() 257{ 258 return new PIFPrefetcher(this); 259} 260