src/mem/cache/prefetch/base.cc

   1 /*
   2  * Copyright (c) 2005 The Regents of The University of Michigan
   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: Ron Dreslinski
  29  */
  30
  31 /**
  32  * @file
  33  * Hardware Prefetcher Definition.
  34  */
  35
  36 #include <list>
  37
  38 #include "arch/isa_traits.hh"
  39 #include "base/trace.hh"
  40 #include "config/the_isa.hh"
  41 #include "mem/cache/base.hh"
  42 #include "mem/cache/prefetch/base.hh"
  43 #include "mem/request.hh"
  44
  45 BasePrefetcher::BasePrefetcher(const BaseCacheParams *p)
  46     : size(p->prefetcher_size), pageStop(!p->prefetch_past_page),
  47       serialSquash(p->prefetch_serial_squash),
  48       cacheCheckPush(p->prefetch_cache_check_push),
  49       onlyData(p->prefetch_data_accesses_only)
  50 {
  51 }
  52
  53 void
  54 BasePrefetcher::setCache(BaseCache *_cache)
  55 {
  56     cache = _cache;
  57     blkSize = cache->getBlockSize();
  58     _name = cache->name() + "-pf";
  59 }
  60
  61 void
  62 BasePrefetcher::regStats(const std::string &name)
  63 {
  64     pfIdentified
  65         .name(name + ".prefetcher.num_hwpf_identified")
  66         .desc("number of hwpf identified")
  67         ;
  68
  69     pfMSHRHit
  70         .name(name + ".prefetcher.num_hwpf_already_in_mshr")
  71         .desc("number of hwpf that were already in mshr")
  72         ;
  73
  74     pfCacheHit
  75         .name(name + ".prefetcher.num_hwpf_already_in_cache")
  76         .desc("number of hwpf that were already in the cache")
  77         ;
  78
  79     pfBufferHit
  80         .name(name + ".prefetcher.num_hwpf_already_in_prefetcher")
  81         .desc("number of hwpf that were already in the prefetch queue")
  82         ;
  83
  84     pfRemovedFull
  85         .name(name + ".prefetcher.num_hwpf_evicted")
  86         .desc("number of hwpf removed due to no buffer left")
  87         ;
  88
  89     pfRemovedMSHR
  90         .name(name + ".prefetcher.num_hwpf_removed_MSHR_hit")
  91         .desc("number of hwpf removed because MSHR allocated")
  92         ;
  93
  94     pfIssued
  95         .name(name + ".prefetcher.num_hwpf_issued")
  96         .desc("number of hwpf issued")
  97         ;
  98
  99     pfSpanPage
 100         .name(name + ".prefetcher.num_hwpf_span_page")
 101         .desc("number of hwpf spanning a virtual page")
 102         ;
 103
 104     pfSquashed
 105         .name(name + ".prefetcher.num_hwpf_squashed_from_miss")
 106         .desc("number of hwpf that got squashed due to a miss "
 107               "aborting calculation time")
 108         ;
 109 }
 110
 111 inline bool
 112 BasePrefetcher::inCache(Addr addr)
 113 {
 114     if (cache->inCache(addr)) {
 115         pfCacheHit++;
 116         return true;
 117     }
 118     return false;
 119 }
 120
 121 inline bool
 122 BasePrefetcher::inMissQueue(Addr addr)
 123 {
 124     if (cache->inMissQueue(addr)) {
 125         pfMSHRHit++;
 126         return true;
 127     }
 128     return false;
 129 }
 130
 131 PacketPtr
 132 BasePrefetcher::getPacket()
 133 {
 134     DPRINTF(HWPrefetch, "Requesting a hw_pf to issue\n");
 135
 136     if (pf.empty()) {
 137         DPRINTF(HWPrefetch, "No HW_PF found\n");
 138         return NULL;
 139     }
 140
 141     PacketPtr pkt;
 142     bool keep_trying = false;
 143     do {
 144         pkt = *pf.begin();
 145         pf.pop_front();
 146         if (!cacheCheckPush) {
 147             keep_trying = cache->inCache(pkt->getAddr());
 148         }
 149
 150         if (keep_trying) {
 151             DPRINTF(HWPrefetch, "addr 0x%x in cache, skipping\n",
 152                     pkt->getAddr());
 153             delete pkt->req;
 154             delete pkt;
 155         }
 156
 157         if (pf.empty()) {
 158             cache->deassertMemSideBusRequest(BaseCache::Request_PF);
 159             if (keep_trying) {
 160                 return NULL; // None left, all were in cache
 161             }
 162         }
 163     } while (keep_trying);
 164
 165     pfIssued++;
 166     assert(pkt != NULL);
 167     DPRINTF(HWPrefetch, "returning 0x%x\n", pkt->getAddr());
 168     return pkt;
 169 }
 170
 171
 172 Tick
 173 BasePrefetcher::notify(PacketPtr &pkt, Tick time)
 174 {
 175     if (!pkt->req->isUncacheable() && !(pkt->req->isInstFetch() && onlyData)) {
 176         // Calculate the blk address
 177         Addr blk_addr = pkt->getAddr() & ~(Addr)(blkSize-1);
 178
 179         // Check if miss is in pfq, if so remove it
 180         std::list<PacketPtr>::iterator iter = inPrefetch(blk_addr);
 181         if (iter != pf.end()) {
 182             DPRINTF(HWPrefetch, "Saw a miss to a queued prefetch addr: "
 183                     "0x%x, removing it\n", blk_addr);
 184             pfRemovedMSHR++;
 185             delete (*iter)->req;
 186             delete (*iter);
 187             pf.erase(iter);
 188             if (pf.empty())
 189                 cache->deassertMemSideBusRequest(BaseCache::Request_PF);
 190         }
 191
 192         // Remove anything in queue with delay older than time
 193         // since everything is inserted in time order, start from end
 194         // and work until pf.empty() or time is earlier
 195         // This is done to emulate Aborting the previous work on a new miss
 196         // Needed for serial calculators like GHB
 197         if (serialSquash) {
 198             iter = pf.end();
 199             iter--;
 200             while (!pf.empty() && ((*iter)->time >= time)) {
 201                 pfSquashed++;
 202                 DPRINTF(HWPrefetch, "Squashing old prefetch addr: 0x%x\n",
 203                         (*iter)->getAddr());
 204                 delete (*iter)->req;
 205                 delete (*iter);
 206                 pf.erase(iter);
 207                 iter--;
 208             }
 209             if (pf.empty())
 210                 cache->deassertMemSideBusRequest(BaseCache::Request_PF);
 211         }
 212
 213
 214         std::list<Addr> addresses;
 215         std::list<Tick> delays;
 216         calculatePrefetch(pkt, addresses, delays);
 217
 218         std::list<Addr>::iterator addrIter = addresses.begin();
 219         std::list<Tick>::iterator delayIter = delays.begin();
 220         for (; addrIter != addresses.end(); ++addrIter, ++delayIter) {
 221             Addr addr = *addrIter;
 222
 223             pfIdentified++;
 224
 225             DPRINTF(HWPrefetch, "Found a pf candidate addr: 0x%x, "
 226                     "inserting into prefetch queue with delay %d time %d\n",
 227                     addr, *delayIter, time);
 228
 229             // Check if it is already in the cache
 230             if (cacheCheckPush && cache->inCache(addr)) {
 231                 DPRINTF(HWPrefetch, "Prefetch addr already in cache\n");
 232                 continue;
 233             }
 234
 235             // Check if it is already in the miss_queue
 236             if (cache->inMissQueue(addr)) {
 237                 DPRINTF(HWPrefetch, "Prefetch addr already in miss queue\n");
 238                 continue;
 239             }
 240
 241             // Check if it is already in the pf buffer
 242             if (inPrefetch(addr) != pf.end()) {
 243                 pfBufferHit++;
 244                 DPRINTF(HWPrefetch, "Prefetch addr already in pf buffer\n");
 245                 continue;
 246             }
 247
 248             // create a prefetch memreq
 249             Request *prefetchReq = new Request(*addrIter, blkSize, 0);
 250             PacketPtr prefetch =
 251                 new Packet(prefetchReq, MemCmd::HardPFReq, Packet::Broadcast);
 252             prefetch->allocate();
 253             prefetch->req->setThreadContext(pkt->req->contextId(),
 254                                             pkt->req->threadId());
 255
 256             prefetch->time = time + (*delayIter); // @todo ADD LATENCY HERE
 257
 258             // We just remove the head if we are full
 259             if (pf.size() == size) {
 260                 pfRemovedFull++;
 261                 PacketPtr old_pkt = *pf.begin();
 262                 DPRINTF(HWPrefetch, "Prefetch queue full, "
 263                         "removing oldest 0x%x\n", old_pkt->getAddr());
 264                 delete old_pkt->req;
 265                 delete old_pkt;
 266                 pf.pop_front();
 267             }
 268
 269             pf.push_back(prefetch);
 270         }
 271     }
 272
 273     return pf.empty() ? 0 : pf.front()->time;
 274 }
 275
 276 std::list<PacketPtr>::iterator
 277 BasePrefetcher::inPrefetch(Addr address)
 278 {
 279     // Guaranteed to only be one match, we always check before inserting
 280     std::list<PacketPtr>::iterator iter;
 281     for (iter = pf.begin(); iter != pf.end(); iter++) {
 282         if (((*iter)->getAddr() & ~(Addr)(blkSize-1)) == address) {
 283             return iter;
 284         }
 285     }
 286     return pf.end();
 287 }
 288
 289 bool
 290 BasePrefetcher::samePage(Addr a, Addr b)
 291 {
 292     return roundDown(a, TheISA::VMPageSize) == roundDown(b, TheISA::VMPageSize);
 293 }