src/mem/cache/prefetch/access_map_pattern_matching.cc

   1 /**
   2  * Copyright (c) 2018 Metempsy Technology Consulting
   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
  29 #include "mem/cache/prefetch/access_map_pattern_matching.hh"
  30
  31 #include "debug/HWPrefetch.hh"
  32 #include "mem/cache/prefetch/associative_set_impl.hh"
  33 #include "params/AMPMPrefetcher.hh"
  34 #include "params/AccessMapPatternMatching.hh"
  35
  36 namespace Prefetcher {
  37
  38 AccessMapPatternMatching::AccessMapPatternMatching(
  39     const AccessMapPatternMatchingParams &p)
  40     : ClockedObject(p), blkSize(p.block_size), limitStride(p.limit_stride),
  41       startDegree(p.start_degree), hotZoneSize(p.hot_zone_size),
  42       highCoverageThreshold(p.high_coverage_threshold),
  43       lowCoverageThreshold(p.low_coverage_threshold),
  44       highAccuracyThreshold(p.high_accuracy_threshold),
  45       lowAccuracyThreshold(p.low_accuracy_threshold),
  46       highCacheHitThreshold(p.high_cache_hit_threshold),
  47       lowCacheHitThreshold(p.low_cache_hit_threshold),
  48       epochCycles(p.epoch_cycles),
  49       offChipMemoryLatency(p.offchip_memory_latency),
  50       accessMapTable(p.access_map_table_assoc, p.access_map_table_entries,
  51                      p.access_map_table_indexing_policy,
  52                      p.access_map_table_replacement_policy,
  53                      AccessMapEntry(hotZoneSize / blkSize)),
  54       numGoodPrefetches(0), numTotalPrefetches(0), numRawCacheMisses(0),
  55       numRawCacheHits(0), degree(startDegree), usefulDegree(startDegree),
  56       epochEvent([this]{ processEpochEvent(); }, name())
  57 {
  58     fatal_if(!isPowerOf2(hotZoneSize),
  59         "the hot zone size must be a power of 2");
  60 }
  61
  62 void
  63 AccessMapPatternMatching::startup()
  64 {
  65     schedule(epochEvent, clockEdge(epochCycles));
  66 }
  67
  68 void
  69 AccessMapPatternMatching::processEpochEvent()
  70 {
  71     schedule(epochEvent, clockEdge(epochCycles));
  72     double prefetch_accuracy =
  73         ((double) numGoodPrefetches) / ((double) numTotalPrefetches);
  74     double prefetch_coverage =
  75         ((double) numGoodPrefetches) / ((double) numRawCacheMisses);
  76     double cache_hit_ratio = ((double) numRawCacheHits) /
  77         ((double) (numRawCacheHits + numRawCacheMisses));
  78     double num_requests = (double) (numRawCacheMisses - numGoodPrefetches +
  79         numTotalPrefetches);
  80     double memory_bandwidth = num_requests * offChipMemoryLatency /
  81         clockEdge(epochCycles);
  82
  83     if (prefetch_coverage > highCoverageThreshold &&
  84         (prefetch_accuracy > highAccuracyThreshold ||
  85         cache_hit_ratio < lowCacheHitThreshold)) {
  86         usefulDegree += 1;
  87     } else if ((prefetch_coverage < lowCoverageThreshold &&
  88                (prefetch_accuracy < lowAccuracyThreshold ||
  89                 cache_hit_ratio > highCacheHitThreshold)) ||
  90                (prefetch_accuracy < lowAccuracyThreshold &&
  91                 cache_hit_ratio > highCacheHitThreshold)) {
  92         usefulDegree -= 1;
  93     }
  94     degree = std::min((unsigned) memory_bandwidth, usefulDegree);
  95     // reset epoch stats
  96     numGoodPrefetches = 0.0;
  97     numTotalPrefetches = 0.0;
  98     numRawCacheMisses = 0.0;
  99     numRawCacheHits = 0.0;
 100 }
 101
 102 AccessMapPatternMatching::AccessMapEntry *
 103 AccessMapPatternMatching::getAccessMapEntry(Addr am_addr,
 104                 bool is_secure)
 105 {
 106     AccessMapEntry *am_entry = accessMapTable.findEntry(am_addr, is_secure);
 107     if (am_entry != nullptr) {
 108         accessMapTable.accessEntry(am_entry);
 109     } else {
 110         am_entry = accessMapTable.findVictim(am_addr);
 111         assert(am_entry != nullptr);
 112
 113         accessMapTable.insertEntry(am_addr, is_secure, am_entry);
 114     }
 115     return am_entry;
 116 }
 117
 118 void
 119 AccessMapPatternMatching::setEntryState(AccessMapEntry &entry,
 120     Addr block, enum AccessMapState state)
 121 {
 122     enum AccessMapState old = entry.states[block];
 123     entry.states[block] = state;
 124
 125     //do not update stats when initializing
 126     if (state == AM_INIT) return;
 127
 128     switch (old) {
 129         case AM_INIT:
 130             if (state == AM_PREFETCH) {
 131                 numTotalPrefetches += 1;
 132             } else if (state == AM_ACCESS) {
 133                 numRawCacheMisses += 1;
 134             }
 135             break;
 136         case AM_PREFETCH:
 137             if (state == AM_ACCESS) {
 138                 numGoodPrefetches += 1;
 139                 numRawCacheMisses += 1;
 140             }
 141             break;
 142         case AM_ACCESS:
 143             if (state == AM_ACCESS) {
 144                 numRawCacheHits += 1;
 145             }
 146             break;
 147         default:
 148             panic("Impossible path\n");
 149             break;
 150     }
 151 }
 152
 153 void
 154 AccessMapPatternMatching::calculatePrefetch(const Base::PrefetchInfo &pfi,
 155     std::vector<Queued::AddrPriority> &addresses)
 156 {
 157     assert(addresses.empty());
 158
 159     bool is_secure = pfi.isSecure();
 160     Addr am_addr = pfi.getAddr() / hotZoneSize;
 161     Addr current_block = (pfi.getAddr() % hotZoneSize) / blkSize;
 162     uint64_t lines_per_zone = hotZoneSize / blkSize;
 163
 164     // Get the entries of the curent block (am_addr), the previous, and the
 165     // following ones
 166     AccessMapEntry *am_entry_curr = getAccessMapEntry(am_addr, is_secure);
 167     AccessMapEntry *am_entry_prev = (am_addr > 0) ?
 168         getAccessMapEntry(am_addr-1, is_secure) : nullptr;
 169     AccessMapEntry *am_entry_next = (am_addr < (MaxAddr/hotZoneSize)) ?
 170         getAccessMapEntry(am_addr+1, is_secure) : nullptr;
 171     assert(am_entry_curr != am_entry_prev);
 172     assert(am_entry_curr != am_entry_next);
 173     assert(am_entry_prev != am_entry_next);
 174     assert(am_entry_curr != nullptr);
 175
 176     //Mark the current access as Accessed
 177     setEntryState(*am_entry_curr, current_block, AM_ACCESS);
 178
 179     /**
 180      * Create a contiguous copy of the 3 entries states.
 181      * With this, we avoid doing boundaries checking in the loop that looks
 182      * for prefetch candidates, mark out of range positions with AM_INVALID
 183      */
 184     std::vector<AccessMapState> states(3 * lines_per_zone);
 185     for (unsigned idx = 0; idx < lines_per_zone; idx += 1) {
 186         states[idx] =
 187             am_entry_prev != nullptr ? am_entry_prev->states[idx] : AM_INVALID;
 188         states[idx + lines_per_zone] = am_entry_curr->states[idx];
 189         states[idx + 2 * lines_per_zone] =
 190             am_entry_next != nullptr ? am_entry_next->states[idx] : AM_INVALID;
 191     }
 192
 193     /**
 194      * am_entry_prev->states => states[               0 ..   lines_per_zone-1]
 195      * am_entry_curr->states => states[  lines_per_zone .. 2*lines_per_zone-1]
 196      * am_entry_next->states => states[2*lines_per_zone .. 3*lines_per_zone-1]
 197      */
 198
 199     // index of the current_block in the new vector
 200     Addr states_current_block = current_block + lines_per_zone;
 201     // consider strides 1..lines_per_zone/2
 202     int max_stride = limitStride == 0 ? lines_per_zone / 2 : limitStride + 1;
 203     for (int stride = 1; stride < max_stride; stride += 1) {
 204         // Test accessed positive strides
 205         if (checkCandidate(states, states_current_block, stride)) {
 206             // candidate found, current_block - stride
 207             Addr pf_addr;
 208             if (stride > current_block) {
 209                 // The index (current_block - stride) falls in the range of
 210                 // the previous zone (am_entry_prev), adjust the address
 211                 // accordingly
 212                 Addr blk = states_current_block - stride;
 213                 pf_addr = (am_addr - 1) * hotZoneSize + blk * blkSize;
 214                 setEntryState(*am_entry_prev, blk, AM_PREFETCH);
 215             } else {
 216                 // The index (current_block - stride) falls within
 217                 // am_entry_curr
 218                 Addr blk = current_block - stride;
 219                 pf_addr = am_addr * hotZoneSize + blk * blkSize;
 220                 setEntryState(*am_entry_curr, blk, AM_PREFETCH);
 221             }
 222             addresses.push_back(Queued::AddrPriority(pf_addr, 0));
 223             if (addresses.size() == degree) {
 224                 break;
 225             }
 226         }
 227
 228         // Test accessed negative strides
 229         if (checkCandidate(states, states_current_block, -stride)) {
 230             // candidate found, current_block + stride
 231             Addr pf_addr;
 232             if (current_block + stride >= lines_per_zone) {
 233                 // The index (current_block + stride) falls in the range of
 234                 // the next zone (am_entry_next), adjust the address
 235                 // accordingly
 236                 Addr blk = (states_current_block + stride) % lines_per_zone;
 237                 pf_addr = (am_addr + 1) * hotZoneSize + blk * blkSize;
 238                 setEntryState(*am_entry_next, blk, AM_PREFETCH);
 239             } else {
 240                 // The index (current_block + stride) falls within
 241                 // am_entry_curr
 242                 Addr blk = current_block + stride;
 243                 pf_addr = am_addr * hotZoneSize + blk * blkSize;
 244                 setEntryState(*am_entry_curr, blk, AM_PREFETCH);
 245             }
 246             addresses.push_back(Queued::AddrPriority(pf_addr, 0));
 247             if (addresses.size() == degree) {
 248                 break;
 249             }
 250         }
 251     }
 252 }
 253
 254 AMPM::AMPM(const AMPMPrefetcherParams &p)
 255   : Queued(p), ampm(*p.ampm)
 256 {
 257 }
 258
 259 void
 260 AMPM::calculatePrefetch(const PrefetchInfo &pfi,
 261     std::vector<AddrPriority> &addresses)
 262 {
 263     ampm.calculatePrefetch(pfi, addresses);
 264 }
 265
 266 } // namespace Prefetcher
 267
 268 Prefetcher::AccessMapPatternMatching*
 269 AccessMapPatternMatchingParams::create() const
 270 {
 271     return new Prefetcher::AccessMapPatternMatching(*this);
 272 }
 273
 274 Prefetcher::AMPM*
 275 AMPMPrefetcherParams::create() const
 276 {
 277     return new Prefetcher::AMPM(*this);
 278 }