1/* 2 * Copyright (c) 2014-2015 ARM Limited 3 * All rights reserved 4 * 5 * The license below extends only to copyright in the software and shall 6 * not be construed as granting a license to any other intellectual 7 * property including but not limited to intellectual property relating 8 * to a hardware implementation of the functionality of the software 9 * licensed hereunder. You may use the software subject to the license 10 * terms below provided that you ensure that this notice is replicated 11 * unmodified and in its entirety in all distributions of the software, 12 * modified or unmodified, in source code or in binary form. 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions are 16 * met: redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer; 18 * redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution; 21 * neither the name of the copyright holders nor the names of its 22 * contributors may be used to endorse or promote products derived from 23 * this software without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36 * 37 * Authors: Mitch Hayenga 38 */ 39 40#include "mem/cache/prefetch/queued.hh" 41 42#include <cassert> 43 44#include "base/logging.hh" 45#include "base/trace.hh" 46#include "debug/HWPrefetch.hh" 47#include "mem/request.hh" 48#include "params/QueuedPrefetcher.hh" 49 50QueuedPrefetcher::QueuedPrefetcher(const QueuedPrefetcherParams *p) 51 : BasePrefetcher(p), queueSize(p->queue_size), latency(p->latency), 52 queueSquash(p->queue_squash), queueFilter(p->queue_filter), 53 cacheSnoop(p->cache_snoop), tagPrefetch(p->tag_prefetch) 54{ 55 56} 57 58QueuedPrefetcher::~QueuedPrefetcher() 59{ 60 // Delete the queued prefetch packets 61 for (DeferredPacket &p : pfq) { 62 delete p.pkt; 63 } 64} 65 66void 67QueuedPrefetcher::notify(const PacketPtr &pkt, const PrefetchInfo &pfi) 68{ 69 Addr blk_addr = blockAddress(pfi.getAddr()); 70 bool is_secure = pfi.isSecure(); 71 72 // Squash queued prefetches if demand miss to same line 73 if (queueSquash) { 74 auto itr = pfq.begin(); 75 while (itr != pfq.end()) { 76 if (itr->pfInfo.getAddr() == blk_addr && 77 itr->pfInfo.isSecure() == is_secure) { 78 delete itr->pkt; 79 itr = pfq.erase(itr); 80 } else { 81 ++itr; 82 } 83 } 84 } 85 86 // Calculate prefetches given this access 87 std::vector<AddrPriority> addresses; 88 calculatePrefetch(pfi, addresses); 89 90 // Queue up generated prefetches 91 for (AddrPriority& addr_prio : addresses) { 92 93 // Block align prefetch address 94 addr_prio.first = blockAddress(addr_prio.first); 95 96 if (samePage(pfi.getAddr(), addr_prio.first)) { 97 PrefetchInfo new_pfi(pfi,addr_prio.first); 98 99 pfIdentified++; 100 DPRINTF(HWPrefetch, "Found a pf candidate addr: %#x, " 101 "inserting into prefetch queue.\n", new_pfi.getAddr()); 102 103 // Create and insert the request 104 insert(pkt, new_pfi, addr_prio.second); 105 } else { 106 // Record the number of page crossing prefetches generate 107 pfSpanPage += 1; 108 DPRINTF(HWPrefetch, "Ignoring page crossing prefetch.\n"); 109 } 110 } 111} 112 113PacketPtr 114QueuedPrefetcher::getPacket() 115{ 116 DPRINTF(HWPrefetch, "Requesting a prefetch to issue.\n"); 117 118 if (pfq.empty()) { 119 DPRINTF(HWPrefetch, "No hardware prefetches available.\n"); 120 return nullptr; 121 } 122 123 PacketPtr pkt = pfq.front().pkt; 124 pfq.pop_front(); 125 126 pfIssued++;
| 1/* 2 * Copyright (c) 2014-2015 ARM Limited 3 * All rights reserved 4 * 5 * The license below extends only to copyright in the software and shall 6 * not be construed as granting a license to any other intellectual 7 * property including but not limited to intellectual property relating 8 * to a hardware implementation of the functionality of the software 9 * licensed hereunder. You may use the software subject to the license 10 * terms below provided that you ensure that this notice is replicated 11 * unmodified and in its entirety in all distributions of the software, 12 * modified or unmodified, in source code or in binary form. 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions are 16 * met: redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer; 18 * redistributions in binary form must reproduce the above copyright 19 * notice, this list of conditions and the following disclaimer in the 20 * documentation and/or other materials provided with the distribution; 21 * neither the name of the copyright holders nor the names of its 22 * contributors may be used to endorse or promote products derived from 23 * this software without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 29 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 31 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 35 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36 * 37 * Authors: Mitch Hayenga 38 */ 39 40#include "mem/cache/prefetch/queued.hh" 41 42#include <cassert> 43 44#include "base/logging.hh" 45#include "base/trace.hh" 46#include "debug/HWPrefetch.hh" 47#include "mem/request.hh" 48#include "params/QueuedPrefetcher.hh" 49 50QueuedPrefetcher::QueuedPrefetcher(const QueuedPrefetcherParams *p) 51 : BasePrefetcher(p), queueSize(p->queue_size), latency(p->latency), 52 queueSquash(p->queue_squash), queueFilter(p->queue_filter), 53 cacheSnoop(p->cache_snoop), tagPrefetch(p->tag_prefetch) 54{ 55 56} 57 58QueuedPrefetcher::~QueuedPrefetcher() 59{ 60 // Delete the queued prefetch packets 61 for (DeferredPacket &p : pfq) { 62 delete p.pkt; 63 } 64} 65 66void 67QueuedPrefetcher::notify(const PacketPtr &pkt, const PrefetchInfo &pfi) 68{ 69 Addr blk_addr = blockAddress(pfi.getAddr()); 70 bool is_secure = pfi.isSecure(); 71 72 // Squash queued prefetches if demand miss to same line 73 if (queueSquash) { 74 auto itr = pfq.begin(); 75 while (itr != pfq.end()) { 76 if (itr->pfInfo.getAddr() == blk_addr && 77 itr->pfInfo.isSecure() == is_secure) { 78 delete itr->pkt; 79 itr = pfq.erase(itr); 80 } else { 81 ++itr; 82 } 83 } 84 } 85 86 // Calculate prefetches given this access 87 std::vector<AddrPriority> addresses; 88 calculatePrefetch(pfi, addresses); 89 90 // Queue up generated prefetches 91 for (AddrPriority& addr_prio : addresses) { 92 93 // Block align prefetch address 94 addr_prio.first = blockAddress(addr_prio.first); 95 96 if (samePage(pfi.getAddr(), addr_prio.first)) { 97 PrefetchInfo new_pfi(pfi,addr_prio.first); 98 99 pfIdentified++; 100 DPRINTF(HWPrefetch, "Found a pf candidate addr: %#x, " 101 "inserting into prefetch queue.\n", new_pfi.getAddr()); 102 103 // Create and insert the request 104 insert(pkt, new_pfi, addr_prio.second); 105 } else { 106 // Record the number of page crossing prefetches generate 107 pfSpanPage += 1; 108 DPRINTF(HWPrefetch, "Ignoring page crossing prefetch.\n"); 109 } 110 } 111} 112 113PacketPtr 114QueuedPrefetcher::getPacket() 115{ 116 DPRINTF(HWPrefetch, "Requesting a prefetch to issue.\n"); 117 118 if (pfq.empty()) { 119 DPRINTF(HWPrefetch, "No hardware prefetches available.\n"); 120 return nullptr; 121 } 122 123 PacketPtr pkt = pfq.front().pkt; 124 pfq.pop_front(); 125 126 pfIssued++;
|
127 assert(pkt != nullptr); 128 DPRINTF(HWPrefetch, "Generating prefetch for %#x.\n", pkt->getAddr()); 129 return pkt; 130} 131 132QueuedPrefetcher::const_iterator 133QueuedPrefetcher::inPrefetch(const PrefetchInfo &pfi) const 134{ 135 for (const_iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 136 if (dp->pfInfo.sameAddr(pfi)) return dp; 137 } 138 139 return pfq.end(); 140} 141 142QueuedPrefetcher::iterator 143QueuedPrefetcher::inPrefetch(const PrefetchInfo &pfi) 144{ 145 for (iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 146 if (dp->pfInfo.sameAddr(pfi)) return dp; 147 } 148 149 return pfq.end(); 150} 151 152void 153QueuedPrefetcher::regStats() 154{ 155 BasePrefetcher::regStats(); 156 157 pfIdentified 158 .name(name() + ".pfIdentified") 159 .desc("number of prefetch candidates identified"); 160 161 pfBufferHit 162 .name(name() + ".pfBufferHit") 163 .desc("number of redundant prefetches already in prefetch queue"); 164 165 pfInCache 166 .name(name() + ".pfInCache") 167 .desc("number of redundant prefetches already in cache/mshr dropped"); 168 169 pfRemovedFull 170 .name(name() + ".pfRemovedFull") 171 .desc("number of prefetches dropped due to prefetch queue size"); 172 173 pfSpanPage 174 .name(name() + ".pfSpanPage") 175 .desc("number of prefetches not generated due to page crossing"); 176} 177 178void 179QueuedPrefetcher::insert(const PacketPtr &pkt, PrefetchInfo &new_pfi, 180 int32_t priority) 181{ 182 if (queueFilter) { 183 iterator it = inPrefetch(new_pfi); 184 /* If the address is already in the queue, update priority and leave */ 185 if (it != pfq.end()) { 186 pfBufferHit++; 187 if (it->priority < priority) { 188 /* Update priority value and position in the queue */ 189 it->priority = priority; 190 iterator prev = it; 191 bool cont = true; 192 while (cont && prev != pfq.begin()) { 193 prev--; 194 /* If the packet has higher priority, swap */ 195 if (*it > *prev) { 196 std::swap(*it, *prev); 197 it = prev; 198 } 199 } 200 DPRINTF(HWPrefetch, "Prefetch addr already in " 201 "prefetch queue, priority updated\n"); 202 } else { 203 DPRINTF(HWPrefetch, "Prefetch addr already in " 204 "prefetch queue\n"); 205 } 206 return; 207 } 208 } 209 210 Addr target_addr = new_pfi.getAddr(); 211 if (useVirtualAddresses) { 212 assert(pkt->req->hasPaddr()); 213 //if we trained with virtual addresses, compute the phsysical address 214 if (new_pfi.getAddr() >= pkt->req->getVaddr()) { 215 //positive stride 216 target_addr = pkt->req->getPaddr() + 217 (new_pfi.getAddr() - pkt->req->getVaddr()); 218 } else { 219 //negative stride 220 target_addr = pkt->req->getPaddr() - 221 (pkt->req->getVaddr() - new_pfi.getAddr()); 222 } 223 } 224 225 if (cacheSnoop && (inCache(target_addr, new_pfi.isSecure()) || 226 inMissQueue(target_addr, new_pfi.isSecure()))) { 227 pfInCache++; 228 DPRINTF(HWPrefetch, "Dropping redundant in " 229 "cache/MSHR prefetch addr:%#x\n", target_addr); 230 return; 231 } 232 233 /* Create a prefetch memory request */ 234 RequestPtr pf_req = 235 std::make_shared<Request>(target_addr, blkSize, 0, masterId); 236 237 if (new_pfi.isSecure()) { 238 pf_req->setFlags(Request::SECURE); 239 } 240 pf_req->taskId(ContextSwitchTaskId::Prefetcher); 241 PacketPtr pf_pkt = new Packet(pf_req, MemCmd::HardPFReq); 242 pf_pkt->allocate(); 243 if (tagPrefetch && new_pfi.hasPC()) { 244 // Tag prefetch packet with accessing pc 245 pf_pkt->req->setPC(new_pfi.getPC()); 246 } 247 248 /* Verify prefetch buffer space for request */ 249 if (pfq.size() == queueSize) { 250 pfRemovedFull++; 251 /* Lowest priority packet */ 252 iterator it = pfq.end(); 253 panic_if (it == pfq.begin(), "Prefetch queue is both full and empty!"); 254 --it; 255 /* Look for oldest in that level of priority */ 256 panic_if (it == pfq.begin(), "Prefetch queue is full with 1 element!"); 257 iterator prev = it; 258 bool cont = true; 259 /* While not at the head of the queue */ 260 while (cont && prev != pfq.begin()) { 261 prev--; 262 /* While at the same level of priority */ 263 cont = prev->priority == it->priority; 264 if (cont) 265 /* update pointer */ 266 it = prev; 267 } 268 DPRINTF(HWPrefetch, "Prefetch queue full, removing lowest priority " 269 "oldest packet, addr: %#x", it->pfInfo.getAddr()); 270 delete it->pkt; 271 pfq.erase(it); 272 } 273 274 Tick pf_time = curTick() + clockPeriod() * latency; 275 DPRINTF(HWPrefetch, "Prefetch queued. " 276 "addr:%#x priority: %3d tick:%lld.\n", 277 target_addr, priority, pf_time); 278 279 /* Create the packet and find the spot to insert it */ 280 DeferredPacket dpp(new_pfi, pf_time, pf_pkt, priority); 281 if (pfq.size() == 0) { 282 pfq.emplace_back(dpp); 283 } else { 284 iterator it = pfq.end(); 285 do { 286 --it; 287 } while (it != pfq.begin() && dpp > *it); 288 /* If we reach the head, we have to see if the new element is new head 289 * or not */ 290 if (it == pfq.begin() && dpp <= *it) 291 it++; 292 pfq.insert(it, dpp); 293 } 294}
| 128 assert(pkt != nullptr); 129 DPRINTF(HWPrefetch, "Generating prefetch for %#x.\n", pkt->getAddr()); 130 return pkt; 131} 132 133QueuedPrefetcher::const_iterator 134QueuedPrefetcher::inPrefetch(const PrefetchInfo &pfi) const 135{ 136 for (const_iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 137 if (dp->pfInfo.sameAddr(pfi)) return dp; 138 } 139 140 return pfq.end(); 141} 142 143QueuedPrefetcher::iterator 144QueuedPrefetcher::inPrefetch(const PrefetchInfo &pfi) 145{ 146 for (iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 147 if (dp->pfInfo.sameAddr(pfi)) return dp; 148 } 149 150 return pfq.end(); 151} 152 153void 154QueuedPrefetcher::regStats() 155{ 156 BasePrefetcher::regStats(); 157 158 pfIdentified 159 .name(name() + ".pfIdentified") 160 .desc("number of prefetch candidates identified"); 161 162 pfBufferHit 163 .name(name() + ".pfBufferHit") 164 .desc("number of redundant prefetches already in prefetch queue"); 165 166 pfInCache 167 .name(name() + ".pfInCache") 168 .desc("number of redundant prefetches already in cache/mshr dropped"); 169 170 pfRemovedFull 171 .name(name() + ".pfRemovedFull") 172 .desc("number of prefetches dropped due to prefetch queue size"); 173 174 pfSpanPage 175 .name(name() + ".pfSpanPage") 176 .desc("number of prefetches not generated due to page crossing"); 177} 178 179void 180QueuedPrefetcher::insert(const PacketPtr &pkt, PrefetchInfo &new_pfi, 181 int32_t priority) 182{ 183 if (queueFilter) { 184 iterator it = inPrefetch(new_pfi); 185 /* If the address is already in the queue, update priority and leave */ 186 if (it != pfq.end()) { 187 pfBufferHit++; 188 if (it->priority < priority) { 189 /* Update priority value and position in the queue */ 190 it->priority = priority; 191 iterator prev = it; 192 bool cont = true; 193 while (cont && prev != pfq.begin()) { 194 prev--; 195 /* If the packet has higher priority, swap */ 196 if (*it > *prev) { 197 std::swap(*it, *prev); 198 it = prev; 199 } 200 } 201 DPRINTF(HWPrefetch, "Prefetch addr already in " 202 "prefetch queue, priority updated\n"); 203 } else { 204 DPRINTF(HWPrefetch, "Prefetch addr already in " 205 "prefetch queue\n"); 206 } 207 return; 208 } 209 } 210 211 Addr target_addr = new_pfi.getAddr(); 212 if (useVirtualAddresses) { 213 assert(pkt->req->hasPaddr()); 214 //if we trained with virtual addresses, compute the phsysical address 215 if (new_pfi.getAddr() >= pkt->req->getVaddr()) { 216 //positive stride 217 target_addr = pkt->req->getPaddr() + 218 (new_pfi.getAddr() - pkt->req->getVaddr()); 219 } else { 220 //negative stride 221 target_addr = pkt->req->getPaddr() - 222 (pkt->req->getVaddr() - new_pfi.getAddr()); 223 } 224 } 225 226 if (cacheSnoop && (inCache(target_addr, new_pfi.isSecure()) || 227 inMissQueue(target_addr, new_pfi.isSecure()))) { 228 pfInCache++; 229 DPRINTF(HWPrefetch, "Dropping redundant in " 230 "cache/MSHR prefetch addr:%#x\n", target_addr); 231 return; 232 } 233 234 /* Create a prefetch memory request */ 235 RequestPtr pf_req = 236 std::make_shared<Request>(target_addr, blkSize, 0, masterId); 237 238 if (new_pfi.isSecure()) { 239 pf_req->setFlags(Request::SECURE); 240 } 241 pf_req->taskId(ContextSwitchTaskId::Prefetcher); 242 PacketPtr pf_pkt = new Packet(pf_req, MemCmd::HardPFReq); 243 pf_pkt->allocate(); 244 if (tagPrefetch && new_pfi.hasPC()) { 245 // Tag prefetch packet with accessing pc 246 pf_pkt->req->setPC(new_pfi.getPC()); 247 } 248 249 /* Verify prefetch buffer space for request */ 250 if (pfq.size() == queueSize) { 251 pfRemovedFull++; 252 /* Lowest priority packet */ 253 iterator it = pfq.end(); 254 panic_if (it == pfq.begin(), "Prefetch queue is both full and empty!"); 255 --it; 256 /* Look for oldest in that level of priority */ 257 panic_if (it == pfq.begin(), "Prefetch queue is full with 1 element!"); 258 iterator prev = it; 259 bool cont = true; 260 /* While not at the head of the queue */ 261 while (cont && prev != pfq.begin()) { 262 prev--; 263 /* While at the same level of priority */ 264 cont = prev->priority == it->priority; 265 if (cont) 266 /* update pointer */ 267 it = prev; 268 } 269 DPRINTF(HWPrefetch, "Prefetch queue full, removing lowest priority " 270 "oldest packet, addr: %#x", it->pfInfo.getAddr()); 271 delete it->pkt; 272 pfq.erase(it); 273 } 274 275 Tick pf_time = curTick() + clockPeriod() * latency; 276 DPRINTF(HWPrefetch, "Prefetch queued. " 277 "addr:%#x priority: %3d tick:%lld.\n", 278 target_addr, priority, pf_time); 279 280 /* Create the packet and find the spot to insert it */ 281 DeferredPacket dpp(new_pfi, pf_time, pf_pkt, priority); 282 if (pfq.size() == 0) { 283 pfq.emplace_back(dpp); 284 } else { 285 iterator it = pfq.end(); 286 do { 287 --it; 288 } while (it != pfq.begin() && dpp > *it); 289 /* If we reach the head, we have to see if the new element is new head 290 * or not */ 291 if (it == pfq.begin() && dpp <= *it) 292 it++; 293 pfq.insert(it, dpp); 294 } 295}
|