1/*
| 1/*
|
2 * Copyright (c) 2014 ARM Limited
| 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 "debug/HWPrefetch.hh" 41#include "mem/cache/prefetch/queued.hh" 42#include "mem/cache/base.hh" 43 44QueuedPrefetcher::QueuedPrefetcher(const QueuedPrefetcherParams *p) 45 : BasePrefetcher(p), queueSize(p->queue_size), latency(p->latency), 46 queueSquash(p->queue_squash), queueFilter(p->queue_filter), 47 cacheSnoop(p->cache_snoop), tagPrefetch(p->tag_prefetch) 48{ 49 50} 51 52QueuedPrefetcher::~QueuedPrefetcher() 53{ 54 // Delete the queued prefetch packets 55 for (DeferredPacket &p : pfq) { 56 delete p.pkt->req; 57 delete p.pkt; 58 } 59} 60 61Tick 62QueuedPrefetcher::notify(const PacketPtr &pkt) 63{ 64 // Verify this access type is observed by prefetcher 65 if (observeAccess(pkt)) {
| 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 "debug/HWPrefetch.hh" 41#include "mem/cache/prefetch/queued.hh" 42#include "mem/cache/base.hh" 43 44QueuedPrefetcher::QueuedPrefetcher(const QueuedPrefetcherParams *p) 45 : BasePrefetcher(p), queueSize(p->queue_size), latency(p->latency), 46 queueSquash(p->queue_squash), queueFilter(p->queue_filter), 47 cacheSnoop(p->cache_snoop), tagPrefetch(p->tag_prefetch) 48{ 49 50} 51 52QueuedPrefetcher::~QueuedPrefetcher() 53{ 54 // Delete the queued prefetch packets 55 for (DeferredPacket &p : pfq) { 56 delete p.pkt->req; 57 delete p.pkt; 58 } 59} 60 61Tick 62QueuedPrefetcher::notify(const PacketPtr &pkt) 63{ 64 // Verify this access type is observed by prefetcher 65 if (observeAccess(pkt)) {
|
66 Addr blk_addr = pkt->getAddr() & ~(Addr)(blkSize - 1);
| 66 Addr blk_addr = pkt->getBlockAddr(blkSize);
|
67 bool is_secure = pkt->isSecure(); 68 69 // Squash queued prefetches if demand miss to same line 70 if (queueSquash) { 71 auto itr = pfq.begin(); 72 while (itr != pfq.end()) { 73 if (itr->pkt->getAddr() == blk_addr && 74 itr->pkt->isSecure() == is_secure) { 75 delete itr->pkt->req; 76 delete itr->pkt; 77 itr = pfq.erase(itr); 78 } else { 79 ++itr; 80 } 81 } 82 } 83 84 // Calculate prefetches given this access
| 67 bool is_secure = pkt->isSecure(); 68 69 // Squash queued prefetches if demand miss to same line 70 if (queueSquash) { 71 auto itr = pfq.begin(); 72 while (itr != pfq.end()) { 73 if (itr->pkt->getAddr() == blk_addr && 74 itr->pkt->isSecure() == is_secure) { 75 delete itr->pkt->req; 76 delete itr->pkt; 77 itr = pfq.erase(itr); 78 } else { 79 ++itr; 80 } 81 } 82 } 83 84 // Calculate prefetches given this access
|
85 std::vector addresses;
| 85 std::vector<AddrPriority> addresses;
|
86 calculatePrefetch(pkt, addresses); 87 88 // Queue up generated prefetches
| 86 calculatePrefetch(pkt, addresses); 87 88 // Queue up generated prefetches
|
89 for (Addr pf_addr : addresses) {
| 89 for (AddrPriority& pf_info : addresses) {
|
90 91 // Block align prefetch address
| 90 91 // Block align prefetch address
|
92 pf_addr = pf_addr & ~(Addr)(blkSize - 1);
| 92 pf_info.first &= ~(Addr)(blkSize - 1);
|
93 94 pfIdentified++; 95 DPRINTF(HWPrefetch, "Found a pf candidate addr: %#x, "
| 93 94 pfIdentified++; 95 DPRINTF(HWPrefetch, "Found a pf candidate addr: %#x, "
|
96 "inserting into prefetch queue.\n", pf_addr);
| 96 "inserting into prefetch queue.\n", pf_info.first);
|
97
| 97
|
98 if (queueFilter && inPrefetch(pf_addr, is_secure)) { 99 pfBufferHit++; 100 DPRINTF(HWPrefetch, "Prefetch addr already in " 101 "prefetch queue\n"); 102 continue; 103 }
| 98 // Create and insert the request 99 PacketPtr pf_pkt = insert(pf_info, is_secure);
|
104
| 100
|
105 if (cacheSnoop && (inCache(pf_addr, is_secure) || 106 inMissQueue(pf_addr, is_secure))) { 107 pfInCache++; 108 DPRINTF(HWPrefetch, "Dropping redundant in " 109 "cache/MSHR prefetch addr:%#x\n", pf_addr); 110 continue;
| 101 if (pf_pkt != nullptr) { 102 if (tagPrefetch && pkt->req->hasPC()) { 103 // Tag prefetch packet with accessing pc 104 pf_pkt->req->setPC(pkt->req->getPC()); 105 }
|
111 }
| 106 }
|
112 113 // Create a prefetch memory request 114 Request *pf_req = 115 new Request(pf_addr, blkSize, 0, masterId); 116 117 if (is_secure) { 118 pf_req->setFlags(Request::SECURE); 119 } 120 pf_req->taskId(ContextSwitchTaskId::Prefetcher); 121 PacketPtr pf_pkt = new Packet(pf_req, MemCmd::HardPFReq); 122 pf_pkt->allocate(); 123 124 if (pkt->req->hasContextId()) { 125 pf_req->setContext(pkt->req->contextId()); 126 } 127 128 if (tagPrefetch && pkt->req->hasPC()) { 129 // Tag prefetch packet with accessing pc 130 pf_pkt->req->setPC(pkt->req->getPC()); 131 } 132 133 // Verify prefetch buffer space for request 134 if (pfq.size() == queueSize) { 135 pfRemovedFull++; 136 PacketPtr old_pkt = pfq.begin()->pkt; 137 DPRINTF(HWPrefetch, "Prefetch queue full, removing " 138 "oldest packet addr: %#x", old_pkt->getAddr()); 139 delete old_pkt->req; 140 delete old_pkt; 141 pfq.pop_front(); 142 } 143 144 Tick pf_time = curTick() + clockPeriod() * latency; 145 DPRINTF(HWPrefetch, "Prefetch queued. " 146 "addr:%#x tick:%lld.\n", pf_addr, pf_time); 147 148 pfq.emplace_back(pf_time, pf_pkt);
| |
149 } 150 } 151 152 return pfq.empty() ? MaxTick : pfq.front().tick; 153} 154 155PacketPtr 156QueuedPrefetcher::getPacket() 157{ 158 DPRINTF(HWPrefetch, "Requesting a prefetch to issue.\n"); 159 160 if (pfq.empty()) { 161 DPRINTF(HWPrefetch, "No hardware prefetches available.\n"); 162 return NULL; 163 } 164 165 PacketPtr pkt = pfq.begin()->pkt; 166 pfq.pop_front(); 167 168 pfIssued++; 169 assert(pkt != NULL); 170 DPRINTF(HWPrefetch, "Generating prefetch for %#x.\n", pkt->getAddr()); 171 return pkt; 172} 173
| 107 } 108 } 109 110 return pfq.empty() ? MaxTick : pfq.front().tick; 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 NULL; 121 } 122 123 PacketPtr pkt = pfq.begin()->pkt; 124 pfq.pop_front(); 125 126 pfIssued++; 127 assert(pkt != NULL); 128 DPRINTF(HWPrefetch, "Generating prefetch for %#x.\n", pkt->getAddr()); 129 return pkt; 130} 131
|
174bool
| 132std::list<QueuedPrefetcher::DeferredPacket>::const_iterator
|
175QueuedPrefetcher::inPrefetch(Addr address, bool is_secure) const 176{
| 133QueuedPrefetcher::inPrefetch(Addr address, bool is_secure) const 134{
|
177 for (const DeferredPacket &dp : pfq) { 178 if (dp.pkt->getAddr() == address && 179 dp.pkt->isSecure() == is_secure) return true;
| 135 for (const_iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 136 if ((*dp).pkt->getAddr() == address && 137 (*dp).pkt->isSecure() == is_secure) return dp;
|
180 } 181
| 138 } 139
|
182 return false;
| 140 return pfq.end();
|
183} 184
| 141} 142
|
| 143QueuedPrefetcher::iterator 144QueuedPrefetcher::inPrefetch(Addr address, bool is_secure) 145{ 146 for (iterator dp = pfq.begin(); dp != pfq.end(); dp++) { 147 if (dp->pkt->getAddr() == address && 148 dp->pkt->isSecure() == is_secure) return dp; 149 } 150 151 return pfq.end(); 152} 153
|
185void 186QueuedPrefetcher::regStats() 187{ 188 BasePrefetcher::regStats(); 189 190 pfIdentified 191 .name(name() + ".pfIdentified") 192 .desc("number of prefetch candidates identified"); 193 194 pfBufferHit 195 .name(name() + ".pfBufferHit") 196 .desc("number of redundant prefetches already in prefetch queue"); 197 198 pfInCache 199 .name(name() + ".pfInCache") 200 .desc("number of redundant prefetches already in cache/mshr dropped"); 201 202 pfRemovedFull 203 .name(name() + ".pfRemovedFull") 204 .desc("number of prefetches dropped due to prefetch queue size"); 205 206 pfSpanPage 207 .name(name() + ".pfSpanPage") 208 .desc("number of prefetches not generated due to page crossing"); 209}
| 154void 155QueuedPrefetcher::regStats() 156{ 157 BasePrefetcher::regStats(); 158 159 pfIdentified 160 .name(name() + ".pfIdentified") 161 .desc("number of prefetch candidates identified"); 162 163 pfBufferHit 164 .name(name() + ".pfBufferHit") 165 .desc("number of redundant prefetches already in prefetch queue"); 166 167 pfInCache 168 .name(name() + ".pfInCache") 169 .desc("number of redundant prefetches already in cache/mshr dropped"); 170 171 pfRemovedFull 172 .name(name() + ".pfRemovedFull") 173 .desc("number of prefetches dropped due to prefetch queue size"); 174 175 pfSpanPage 176 .name(name() + ".pfSpanPage") 177 .desc("number of prefetches not generated due to page crossing"); 178}
|
| 179 180PacketPtr 181QueuedPrefetcher::insert(AddrPriority &pf_info, bool is_secure) 182{ 183 if (queueFilter) { 184 iterator it = inPrefetch(pf_info.first, is_secure); 185 /* If the address is already in the queue, update priority and leave */ 186 if (it != pfq.end()) { 187 pfBufferHit++; 188 if (it->priority < pf_info.second) { 189 /* Update priority value and position in the queue */ 190 it->priority = pf_info.second; 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 nullptr; 208 } 209 } 210 211 if (cacheSnoop && (inCache(pf_info.first, is_secure) || 212 inMissQueue(pf_info.first, is_secure))) { 213 pfInCache++; 214 DPRINTF(HWPrefetch, "Dropping redundant in " 215 "cache/MSHR prefetch addr:%#x\n", pf_info.first); 216 return nullptr; 217 } 218 219 /* Create a prefetch memory request */ 220 Request *pf_req = 221 new Request(pf_info.first, blkSize, 0, masterId); 222 223 if (is_secure) { 224 pf_req->setFlags(Request::SECURE); 225 } 226 pf_req->taskId(ContextSwitchTaskId::Prefetcher); 227 PacketPtr pf_pkt = new Packet(pf_req, MemCmd::HardPFReq); 228 pf_pkt->allocate(); 229 230 /* Verify prefetch buffer space for request */ 231 if (pfq.size() == queueSize) { 232 pfRemovedFull++; 233 /* Lowest priority packet */ 234 iterator it = pfq.end(); 235 panic_if (it == pfq.begin(), "Prefetch queue is both full and empty!"); 236 --it; 237 /* Look for oldest in that level of priority */ 238 panic_if (it == pfq.begin(), "Prefetch queue is full with 1 element!"); 239 iterator prev = it; 240 bool cont = true; 241 /* While not at the head of the queue */ 242 while (cont && prev != pfq.begin()) { 243 prev--; 244 /* While at the same level of priority */ 245 cont = (*prev).priority == (*it).priority; 246 if (cont) 247 /* update pointer */ 248 it = prev; 249 } 250 DPRINTF(HWPrefetch, "Prefetch queue full, removing lowest priority " 251 "oldest packet, addr: %#x", it->pkt->getAddr()); 252 delete it->pkt->req; 253 delete it->pkt; 254 pfq.erase(it); 255 } 256 257 Tick pf_time = curTick() + clockPeriod() * latency; 258 DPRINTF(HWPrefetch, "Prefetch queued. " 259 "addr:%#x priority: %3d tick:%lld.\n", 260 pf_info.first, pf_info.second, pf_time); 261 262 /* Create the packet and find the spot to insert it */ 263 DeferredPacket dpp(pf_time, pf_pkt, pf_info.second); 264 if (pfq.size() == 0) { 265 pfq.emplace_back(dpp); 266 } else { 267 iterator it = pfq.end(); 268 while (it != pfq.begin() && dpp > *it) 269 --it; 270 /* If we reach the head, we have to see if the new element is new head 271 * or not */ 272 if (it == pfq.begin() && dpp <= *it) 273 it++; 274 pfq.insert(it, dpp); 275 } 276 277 return pf_pkt; 278}
|
| |