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::RubyPrefetcher(const Params &p)
  52     : SimObject(p), m_num_streams(p.num_streams),
  53     m_array(p.num_streams), m_train_misses(p.train_misses),
  54     m_num_startup_pfs(p.num_startup_pfs),
  55     unitFilter(p.unit_filter),
  56     negativeFilter(p.unit_filter),
  57     nonUnitFilter(p.nonunit_filter),
  58     m_prefetch_cross_pages(p.cross_page),
  59     m_page_shift(p.sys->getPageShift())
  60 {
  61     assert(m_num_streams > 0);
  62     assert(m_num_startup_pfs <= MAX_PF_INFLIGHT);
  63 }
  64
  65 void
  66 RubyPrefetcher::regStats()
  67 {
  68     SimObject::regStats();
  69
  70     numMissObserved
  71         .name(name() + ".miss_observed")
  72         .desc("number of misses observed")
  73         ;
  74
  75     numAllocatedStreams
  76         .name(name() + ".allocated_streams")
  77         .desc("number of streams allocated for prefetching")
  78         ;
  79
  80     numPrefetchRequested
  81         .name(name() + ".prefetches_requested")
  82         .desc("number of prefetch requests made")
  83         ;
  84
  85     numHits
  86         .name(name() + ".hits")
  87         .desc("number of prefetched blocks accessed (for the first time)")
  88         ;
  89
  90     numPartialHits
  91         .name(name() + ".partial_hits")
  92         .desc("number of misses observed for a block being prefetched")
  93         ;
  94
  95     numPagesCrossed
  96         .name(name() + ".pages_crossed")
  97         .desc("number of prefetches across pages")
  98         ;
  99
 100     numMissedPrefetchedBlocks
 101         .name(name() + ".misses_on_prefetched_blocks")
 102         .desc("number of misses for blocks that were prefetched, yet missed")
 103         ;
 104 }
 105
 106 void
 107 RubyPrefetcher::observeMiss(Addr address, const RubyRequestType& type)
 108 {
 109     DPRINTF(RubyPrefetcher, "Observed miss for %#x\n", address);
 110     Addr line_addr = makeLineAddress(address);
 111     numMissObserved++;
 112
 113     // check to see if we have already issued a prefetch for this block
 114     uint32_t index = 0;
 115     PrefetchEntry *pfEntry = getPrefetchEntry(line_addr, index);
 116     if (pfEntry != NULL) {
 117         if (pfEntry->requestIssued[index]) {
 118             if (pfEntry->requestCompleted[index]) {
 119                 // We prefetched too early and now the prefetch block no
 120                 // longer exists in the cache
 121                 numMissedPrefetchedBlocks++;
 122                 return;
 123             } else {
 124                 // The controller has issued the prefetch request,
 125                 // but the request for the block arrived earlier.
 126                 numPartialHits++;
 127                 observePfMiss(line_addr);
 128                 return;
 129             }
 130         } else {
 131             // The request is still in the prefetch queue of the controller.
 132             // Or was evicted because of other requests.
 133             return;
 134         }
 135     }
 136
 137     // Check if address is in any of the stride filters
 138     if (accessUnitFilter(&unitFilter, line_addr, 1, type)) {
 139         DPRINTF(RubyPrefetcher, "  *** hit in unit stride buffer\n");
 140         return;
 141     }
 142     if (accessUnitFilter(&negativeFilter, line_addr, -1, type)) {
 143         DPRINTF(RubyPrefetcher, "  *** hit in unit negative unit buffer\n");
 144         return;
 145     }
 146     if (accessNonunitFilter(line_addr, type)) {
 147         DPRINTF(RubyPrefetcher, "  *** hit in non-unit stride buffer\n");
 148         return;
 149     }
 150 }
 151
 152 void
 153 RubyPrefetcher::observePfMiss(Addr address)
 154 {
 155     numPartialHits++;
 156     DPRINTF(RubyPrefetcher, "Observed partial hit for %#x\n", address);
 157     issueNextPrefetch(address, NULL);
 158 }
 159
 160 void
 161 RubyPrefetcher::observePfHit(Addr address)
 162 {
 163     numHits++;
 164     DPRINTF(RubyPrefetcher, "Observed hit for %#x\n", address);
 165     issueNextPrefetch(address, NULL);
 166 }
 167
 168 void
 169 RubyPrefetcher::issueNextPrefetch(Addr address, PrefetchEntry *stream)
 170 {
 171     // get our corresponding stream fetcher
 172     if (stream == NULL) {
 173         uint32_t index = 0;
 174         stream = getPrefetchEntry(address, index);
 175     }
 176
 177     // if (for some reason), this stream is unallocated, return.
 178     if (stream == NULL) {
 179         DPRINTF(RubyPrefetcher, "Unallocated stream, returning\n");
 180         return;
 181     }
 182
 183     // extend this prefetching stream by 1 (or more)
 184     Addr page_addr = pageAddress(stream->m_address);
 185     Addr line_addr = makeNextStrideAddress(stream->m_address,
 186                                          stream->m_stride);
 187
 188     // possibly stop prefetching at page boundaries
 189     if (page_addr != pageAddress(line_addr)) {
 190         if (!m_prefetch_cross_pages) {
 191             // Deallocate the stream since we are not prefetching
 192             // across page boundries
 193             stream->m_is_valid = false;
 194             return;
 195         }
 196         numPagesCrossed++;
 197     }
 198
 199     // launch next prefetch
 200     numPrefetchRequested++;
 201     stream->m_address = line_addr;
 202     stream->m_use_time = m_controller->curCycle();
 203     DPRINTF(RubyPrefetcher, "Requesting prefetch for %#x\n", line_addr);
 204     m_controller->enqueuePrefetch(line_addr, stream->m_type);
 205 }
 206
 207 uint32_t
 208 RubyPrefetcher::getLRUindex(void)
 209 {
 210     uint32_t lru_index = 0;
 211     Cycles lru_access = m_array[lru_index].m_use_time;
 212
 213     for (uint32_t i = 0; i < m_num_streams; i++) {
 214         if (!m_array[i].m_is_valid) {
 215             return i;
 216         }
 217         if (m_array[i].m_use_time < lru_access) {
 218             lru_access = m_array[i].m_use_time;
 219             lru_index = i;
 220         }
 221     }
 222
 223     return lru_index;
 224 }
 225
 226 void
 227 RubyPrefetcher::initializeStream(Addr address, int stride,
 228      uint32_t index, const RubyRequestType& type)
 229 {
 230     numAllocatedStreams++;
 231
 232     // initialize the stream prefetcher
 233     PrefetchEntry *mystream = &(m_array[index]);
 234     mystream->m_address = makeLineAddress(address);
 235     mystream->m_stride = stride;
 236     mystream->m_use_time = m_controller->curCycle();
 237     mystream->m_is_valid = true;
 238     mystream->m_type = type;
 239
 240     // create a number of initial prefetches for this stream
 241     Addr page_addr = pageAddress(mystream->m_address);
 242     Addr line_addr = makeLineAddress(mystream->m_address);
 243
 244     // insert a number of prefetches into the prefetch table
 245     for (int k = 0; k < m_num_startup_pfs; k++) {
 246         line_addr = makeNextStrideAddress(line_addr, stride);
 247         // possibly stop prefetching at page boundaries
 248         if (page_addr != pageAddress(line_addr)) {
 249             if (!m_prefetch_cross_pages) {
 250                 // deallocate this stream prefetcher
 251                 mystream->m_is_valid = false;
 252                 return;
 253             }
 254             numPagesCrossed++;
 255         }
 256
 257         // launch prefetch
 258         numPrefetchRequested++;
 259         DPRINTF(RubyPrefetcher, "Requesting prefetch for %#x\n", line_addr);
 260         m_controller->enqueuePrefetch(line_addr, m_array[index].m_type);
 261     }
 262
 263     // update the address to be the last address prefetched
 264     mystream->m_address = line_addr;
 265 }
 266
 267 PrefetchEntry *
 268 RubyPrefetcher::getPrefetchEntry(Addr address, uint32_t &index)
 269 {
 270     // search all streams for a match
 271     for (int i = 0; i < m_num_streams; i++) {
 272         // search all the outstanding prefetches for this stream
 273         if (m_array[i].m_is_valid) {
 274             for (int j = 0; j < m_num_startup_pfs; j++) {
 275                 if (makeNextStrideAddress(m_array[i].m_address,
 276                     -(m_array[i].m_stride*j)) == address) {
 277                     return &(m_array[i]);
 278                 }
 279             }
 280         }
 281     }
 282     return NULL;
 283 }
 284
 285 bool
 286 RubyPrefetcher::accessUnitFilter(CircularQueue<UnitFilterEntry>* const filter,
 287     Addr line_addr, int stride, const RubyRequestType& type)
 288 {
 289     for (auto& entry : *filter) {
 290         if (entry.addr == line_addr) {
 291             entry.addr = makeNextStrideAddress(entry.addr, stride);
 292             entry.hits++;
 293             if (entry.hits >= m_train_misses) {
 294                 // Allocate a new prefetch stream
 295                 initializeStream(line_addr, stride, getLRUindex(), type);
 296             }
 297             return true;
 298         }
 299     }
 300
 301     // Enter this address in the filter
 302     filter->push_back(UnitFilterEntry(
 303         makeNextStrideAddress(line_addr, stride)));
 304
 305     return false;
 306 }
 307
 308 bool
 309 RubyPrefetcher::accessNonunitFilter(Addr line_addr,
 310     const RubyRequestType& type)
 311 {
 312     /// look for non-unit strides based on a (user-defined) page size
 313     Addr page_addr = pageAddress(line_addr);
 314
 315     for (auto& entry : nonUnitFilter) {
 316         if (pageAddress(entry.addr) == page_addr) {
 317             // hit in the non-unit filter
 318             // compute the actual stride (for this reference)
 319             int delta = line_addr - entry.addr;
 320
 321             if (delta != 0) {
 322                 // no zero stride prefetches
 323                 // check that the stride matches (for the last N times)
 324                 if (delta == entry.stride) {
 325                     // -> stride hit
 326                     // increment count (if > 2) allocate stream
 327                     entry.hits++;
 328                     if (entry.hits > m_train_misses) {
 329                         // This stride HAS to be the multiplicative constant of
 330                         // dataBlockBytes (bc makeNextStrideAddress is
 331                         // calculated based on this multiplicative constant!)
 332                         const int stride = entry.stride /
 333                             RubySystem::getBlockSizeBytes();
 334
 335                         // clear this filter entry
 336                         entry.clear();
 337
 338                         initializeStream(line_addr, stride, getLRUindex(),
 339                             type);
 340                     }
 341                 } else {
 342                     // If delta didn't match reset entry's hit count
 343                     entry.hits = 0;
 344                 }
 345
 346                 // update the last address seen & the stride
 347                 entry.addr = line_addr;
 348                 entry.stride = delta;
 349                 return true;
 350             } else {
 351                 return false;
 352             }
 353         }
 354     }
 355
 356     // not found: enter this address in the table
 357     nonUnitFilter.push_back(NonUnitFilterEntry(line_addr));
 358
 359     return false;
 360 }
 361
 362 void
 363 RubyPrefetcher::print(std::ostream& out) const
 364 {
 365     out << name() << " Prefetcher State\n";
 366     // print out unit filter
 367     out << "unit table:\n";
 368     for (const auto& entry : unitFilter) {
 369         out << entry.addr << std::endl;
 370     }
 371
 372     out << "negative table:\n";
 373     for (const auto& entry : negativeFilter) {
 374         out << entry.addr << std::endl;
 375     }
 376
 377     // print out non-unit stride filter
 378     out << "non-unit table:\n";
 379     for (const auto& entry : nonUnitFilter) {
 380         out << entry.addr << " "
 381             << entry.stride << " "
 382             << entry.hits << std::endl;
 383     }
 384
 385     // print out allocated stream buffers
 386     out << "streams:\n";
 387     for (int i = 0; i < m_num_streams; i++) {
 388         out << m_array[i].m_address << " "
 389             << m_array[i].m_stride << " "
 390             << m_array[i].m_is_valid << " "
 391             << m_array[i].m_use_time << std::endl;
 392     }
 393 }
 394
 395 Addr
 396 RubyPrefetcher::pageAddress(Addr addr) const
 397 {
 398     return mbits<Addr>(addr, 63, m_page_shift);
 399 }