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