src/mem/ruby/structures/RubyPrefetcher.cc

   1 /*
   2  * Copyright (c) 2020 Inria
   3  * Copyright (c) 2020 ARM Limited
   4  * All rights reserved
   5  *
   6  * The license below extends only to copyright in the software and shall
   7  * not be construed as granting a license to any other intellectual
   8  * property including but not limited to intellectual property relating
   9  * to a hardware implementation of the functionality of the software
  10  * licensed hereunder.  You may use the software subject to the license
  11  * terms below provided that you ensure that this notice is replicated
  12  * unmodified and in its entirety in all distributions of the software,
  13  * modified or unmodified, in source code or in binary form.
  14  *
  15  * Copyright (c) 1999-2012 Mark D. Hill and David A. Wood
  16  * All rights reserved.
  17  *
  18  * Redistribution and use in source and binary forms, with or without
  19  * modification, are permitted provided that the following conditions are
  20  * met: redistributions of source code must retain the above copyright
  21  * notice, this list of conditions and the following disclaimer;
  22  * redistributions in binary form must reproduce the above copyright
  23  * notice, this list of conditions and the following disclaimer in the
  24  * documentation and/or other materials provided with the distribution;
  25  * neither the name of the copyright holders nor the names of its
  26  * contributors may be used to endorse or promote products derived from
  27  * this software without specific prior written permission.
  28  *
  29  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  30  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  31  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  32  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  33  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  34  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  35  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  36  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  37  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  38  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  39  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  40  */
  41
  42 #include "mem/ruby/structures/RubyPrefetcher.hh"
  43
  44 #include <cassert>
  45
  46 #include "base/bitfield.hh"
  47 #include "debug/RubyPrefetcher.hh"
  48 #include "mem/ruby/slicc_interface/RubySlicc_ComponentMapping.hh"
  49 #include "mem/ruby/system/RubySystem.hh"
  50
  51 RubyPrefetcher*
  52 RubyPrefetcherParams::create()
  53 {
  54     return new RubyPrefetcher(this);
  55 }
  56
  57 RubyPrefetcher::RubyPrefetcher(const Params *p)
  58     : SimObject(p), m_num_streams(p->num_streams),
  59     m_array(p->num_streams), m_train_misses(p->train_misses),
  60     m_num_startup_pfs(p->num_startup_pfs),
  61     unitFilter(p->unit_filter),
  62     negativeFilter(p->unit_filter),
  63     nonUnitFilter(p->nonunit_filter),
  64     m_prefetch_cross_pages(p->cross_page),
  65     m_page_shift(p->sys->getPageShift())
  66 {
  67     assert(m_num_streams > 0);
  68     assert(m_num_startup_pfs <= MAX_PF_INFLIGHT);
  69 }
  70
  71 void
  72 RubyPrefetcher::regStats()
  73 {
  74     SimObject::regStats();
  75
  76     numMissObserved
  77         .name(name() + ".miss_observed")
  78         .desc("number of misses observed")
  79         ;
  80
  81     numAllocatedStreams
  82         .name(name() + ".allocated_streams")
  83         .desc("number of streams allocated for prefetching")
  84         ;
  85
  86     numPrefetchRequested
  87         .name(name() + ".prefetches_requested")
  88         .desc("number of prefetch requests made")
  89         ;
  90
  91     numHits
  92         .name(name() + ".hits")
  93         .desc("number of prefetched blocks accessed (for the first time)")
  94         ;
  95
  96     numPartialHits
  97         .name(name() + ".partial_hits")
  98         .desc("number of misses observed for a block being prefetched")
  99         ;
 100
 101     numPagesCrossed
 102         .name(name() + ".pages_crossed")
 103         .desc("number of prefetches across pages")
 104         ;
 105
 106     numMissedPrefetchedBlocks
 107         .name(name() + ".misses_on_prefetched_blocks")
 108         .desc("number of misses for blocks that were prefetched, yet missed")
 109         ;
 110 }
 111
 112 void
 113 RubyPrefetcher::observeMiss(Addr address, const RubyRequestType& type)
 114 {
 115     DPRINTF(RubyPrefetcher, "Observed miss for %#x\n", address);
 116     Addr line_addr = makeLineAddress(address);
 117     numMissObserved++;
 118
 119     // check to see if we have already issued a prefetch for this block
 120     uint32_t index = 0;
 121     PrefetchEntry *pfEntry = getPrefetchEntry(line_addr, index);
 122     if (pfEntry != NULL) {
 123         if (pfEntry->requestIssued[index]) {
 124             if (pfEntry->requestCompleted[index]) {
 125                 // We prefetched too early and now the prefetch block no
 126                 // longer exists in the cache
 127                 numMissedPrefetchedBlocks++;
 128                 return;
 129             } else {
 130                 // The controller has issued the prefetch request,
 131                 // but the request for the block arrived earlier.
 132                 numPartialHits++;
 133                 observePfMiss(line_addr);
 134                 return;
 135             }
 136         } else {
 137             // The request is still in the prefetch queue of the controller.
 138             // Or was evicted because of other requests.
 139             return;
 140         }
 141     }
 142
 143     // Check if address is in any of the stride filters
 144     if (accessUnitFilter(&unitFilter, line_addr, 1, type)) {
 145         DPRINTF(RubyPrefetcher, "  *** hit in unit stride buffer\n");
 146         return;
 147     }
 148     if (accessUnitFilter(&negativeFilter, line_addr, -1, type)) {
 149         DPRINTF(RubyPrefetcher, "  *** hit in unit negative unit buffer\n");
 150         return;
 151     }
 152     if (accessNonunitFilter(line_addr, type)) {
 153         DPRINTF(RubyPrefetcher, "  *** hit in non-unit stride buffer\n");
 154         return;
 155     }
 156 }
 157
 158 void
 159 RubyPrefetcher::observePfMiss(Addr address)
 160 {
 161     numPartialHits++;
 162     DPRINTF(RubyPrefetcher, "Observed partial hit for %#x\n", address);
 163     issueNextPrefetch(address, NULL);
 164 }
 165
 166 void
 167 RubyPrefetcher::observePfHit(Addr address)
 168 {
 169     numHits++;
 170     DPRINTF(RubyPrefetcher, "Observed hit for %#x\n", address);
 171     issueNextPrefetch(address, NULL);
 172 }
 173
 174 void
 175 RubyPrefetcher::issueNextPrefetch(Addr address, PrefetchEntry *stream)
 176 {
 177     // get our corresponding stream fetcher
 178     if (stream == NULL) {
 179         uint32_t index = 0;
 180         stream = getPrefetchEntry(address, index);
 181     }
 182
 183     // if (for some reason), this stream is unallocated, return.
 184     if (stream == NULL) {
 185         DPRINTF(RubyPrefetcher, "Unallocated stream, returning\n");
 186         return;
 187     }
 188
 189     // extend this prefetching stream by 1 (or more)
 190     Addr page_addr = pageAddress(stream->m_address);
 191     Addr line_addr = makeNextStrideAddress(stream->m_address,
 192                                          stream->m_stride);
 193
 194     // possibly stop prefetching at page boundaries
 195     if (page_addr != pageAddress(line_addr)) {
 196         if (!m_prefetch_cross_pages) {
 197             // Deallocate the stream since we are not prefetching
 198             // across page boundries
 199             stream->m_is_valid = false;
 200             return;
 201         }
 202         numPagesCrossed++;
 203     }
 204
 205     // launch next prefetch
 206     numPrefetchRequested++;
 207     stream->m_address = line_addr;
 208     stream->m_use_time = m_controller->curCycle();
 209     DPRINTF(RubyPrefetcher, "Requesting prefetch for %#x\n", line_addr);
 210     m_controller->enqueuePrefetch(line_addr, stream->m_type);
 211 }
 212
 213 uint32_t
 214 RubyPrefetcher::getLRUindex(void)
 215 {
 216     uint32_t lru_index = 0;
 217     Cycles lru_access = m_array[lru_index].m_use_time;
 218
 219     for (uint32_t i = 0; i < m_num_streams; i++) {
 220         if (!m_array[i].m_is_valid) {
 221             return i;
 222         }
 223         if (m_array[i].m_use_time < lru_access) {
 224             lru_access = m_array[i].m_use_time;
 225             lru_index = i;
 226         }
 227     }
 228
 229     return lru_index;
 230 }
 231
 232 void
 233 RubyPrefetcher::initializeStream(Addr address, int stride,
 234      uint32_t index, const RubyRequestType& type)
 235 {
 236     numAllocatedStreams++;
 237
 238     // initialize the stream prefetcher
 239     PrefetchEntry *mystream = &(m_array[index]);
 240     mystream->m_address = makeLineAddress(address);
 241     mystream->m_stride = stride;
 242     mystream->m_use_time = m_controller->curCycle();
 243     mystream->m_is_valid = true;
 244     mystream->m_type = type;
 245
 246     // create a number of initial prefetches for this stream
 247     Addr page_addr = pageAddress(mystream->m_address);
 248     Addr line_addr = makeLineAddress(mystream->m_address);
 249
 250     // insert a number of prefetches into the prefetch table
 251     for (int k = 0; k < m_num_startup_pfs; k++) {
 252         line_addr = makeNextStrideAddress(line_addr, stride);
 253         // possibly stop prefetching at page boundaries
 254         if (page_addr != pageAddress(line_addr)) {
 255             if (!m_prefetch_cross_pages) {
 256                 // deallocate this stream prefetcher
 257                 mystream->m_is_valid = false;
 258                 return;
 259             }
 260             numPagesCrossed++;
 261         }
 262
 263         // launch prefetch
 264         numPrefetchRequested++;
 265         DPRINTF(RubyPrefetcher, "Requesting prefetch for %#x\n", line_addr);
 266         m_controller->enqueuePrefetch(line_addr, m_array[index].m_type);
 267     }
 268
 269     // update the address to be the last address prefetched
 270     mystream->m_address = line_addr;
 271 }
 272
 273 PrefetchEntry *
 274 RubyPrefetcher::getPrefetchEntry(Addr address, uint32_t &index)
 275 {
 276     // search all streams for a match
 277     for (int i = 0; i < m_num_streams; i++) {
 278         // search all the outstanding prefetches for this stream
 279         if (m_array[i].m_is_valid) {
 280             for (int j = 0; j < m_num_startup_pfs; j++) {
 281                 if (makeNextStrideAddress(m_array[i].m_address,
 282                     -(m_array[i].m_stride*j)) == address) {
 283                     return &(m_array[i]);
 284                 }
 285             }
 286         }
 287     }
 288     return NULL;
 289 }
 290
 291 bool
 292 RubyPrefetcher::accessUnitFilter(CircularQueue<UnitFilterEntry>* const filter,
 293     Addr line_addr, int stride, const RubyRequestType& type)
 294 {
 295     for (auto& entry : *filter) {
 296         if (entry.addr == line_addr) {
 297             entry.addr = makeNextStrideAddress(entry.addr, stride);
 298             entry.hits++;
 299             if (entry.hits >= m_train_misses) {
 300                 // Allocate a new prefetch stream
 301                 initializeStream(line_addr, stride, getLRUindex(), type);
 302             }
 303             return true;
 304         }
 305     }
 306
 307     // Enter this address in the filter
 308     filter->push_back(UnitFilterEntry(
 309         makeNextStrideAddress(line_addr, stride)));
 310
 311     return false;
 312 }
 313
 314 bool
 315 RubyPrefetcher::accessNonunitFilter(Addr line_addr,
 316     const RubyRequestType& type)
 317 {
 318     /// look for non-unit strides based on a (user-defined) page size
 319     Addr page_addr = pageAddress(line_addr);
 320
 321     for (auto& entry : nonUnitFilter) {
 322         if (pageAddress(entry.addr) == page_addr) {
 323             // hit in the non-unit filter
 324             // compute the actual stride (for this reference)
 325             int delta = line_addr - entry.addr;
 326
 327             if (delta != 0) {
 328                 // no zero stride prefetches
 329                 // check that the stride matches (for the last N times)
 330                 if (delta == entry.stride) {
 331                     // -> stride hit
 332                     // increment count (if > 2) allocate stream
 333                     entry.hits++;
 334                     if (entry.hits > m_train_misses) {
 335                         // This stride HAS to be the multiplicative constant of
 336                         // dataBlockBytes (bc makeNextStrideAddress is
 337                         // calculated based on this multiplicative constant!)
 338                         const int stride = entry.stride /
 339                             RubySystem::getBlockSizeBytes();
 340
 341                         // clear this filter entry
 342                         entry.clear();
 343
 344                         initializeStream(line_addr, stride, getLRUindex(),
 345                             type);
 346                     }
 347                 } else {
 348                     // If delta didn't match reset entry's hit count
 349                     entry.hits = 0;
 350                 }
 351
 352                 // update the last address seen & the stride
 353                 entry.addr = line_addr;
 354                 entry.stride = delta;
 355                 return true;
 356             } else {
 357                 return false;
 358             }
 359         }
 360     }
 361
 362     // not found: enter this address in the table
 363     nonUnitFilter.push_back(NonUnitFilterEntry(line_addr));
 364
 365     return false;
 366 }
 367
 368 void
 369 RubyPrefetcher::print(std::ostream& out) const
 370 {
 371     out << name() << " Prefetcher State\n";
 372     // print out unit filter
 373     out << "unit table:\n";
 374     for (const auto& entry : unitFilter) {
 375         out << entry.addr << std::endl;
 376     }
 377
 378     out << "negative table:\n";
 379     for (const auto& entry : negativeFilter) {
 380         out << entry.addr << std::endl;
 381     }
 382
 383     // print out non-unit stride filter
 384     out << "non-unit table:\n";
 385     for (const auto& entry : nonUnitFilter) {
 386         out << entry.addr << " "
 387             << entry.stride << " "
 388             << entry.hits << std::endl;
 389     }
 390
 391     // print out allocated stream buffers
 392     out << "streams:\n";
 393     for (int i = 0; i < m_num_streams; i++) {
 394         out << m_array[i].m_address << " "
 395             << m_array[i].m_stride << " "
 396             << m_array[i].m_is_valid << " "
 397             << m_array[i].m_use_time << std::endl;
 398     }
 399 }
 400
 401 Addr
 402 RubyPrefetcher::pageAddress(Addr addr) const
 403 {
 404     return mbits<Addr>(addr, 63, m_page_shift);
 405 }