src/mem/cache/prefetch/delta_correlating_prediction_tables.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  * Authors: Javier Bueno
  29  */
  30
  31 #include "mem/cache/prefetch/delta_correlating_prediction_tables.hh"
  32
  33 #include "debug/HWPrefetch.hh"
  34 #include "mem/cache/prefetch/associative_set_impl.hh"
  35 #include "params/DCPTPrefetcher.hh"
  36 #include "params/DeltaCorrelatingPredictionTables.hh"
  37
  38 DeltaCorrelatingPredictionTables::DeltaCorrelatingPredictionTables(
  39    DeltaCorrelatingPredictionTablesParams *p) : SimObject(p),
  40    deltaBits(p->delta_bits), deltaMaskBits(p->delta_mask_bits),
  41    table(p->table_assoc, p->table_entries, p->table_indexing_policy,
  42          p->table_replacement_policy, DCPTEntry(p->deltas_per_entry))
  43 {
  44 }
  45
  46 void
  47 DeltaCorrelatingPredictionTables::DCPTEntry::reset()
  48 {
  49     for (auto &delta : deltas) {
  50         delta = 0;
  51     }
  52     lastAddress = 0;
  53     deltaPointer = 0;
  54 }
  55
  56 void
  57 DeltaCorrelatingPredictionTables::DCPTEntry::addAddress(Addr address,
  58     unsigned int delta_bits)
  59 {
  60     if ((address - lastAddress) != 0) {
  61         Addr delta = address - lastAddress;
  62         // Account for the sign bit
  63         Addr max_positive_delta = (1 << (delta_bits-1)) - 1;
  64         if (address > lastAddress) {
  65             // check positive delta overflow
  66             if (delta > max_positive_delta) {
  67                 delta = 0;
  68             }
  69         } else {
  70             // check negative delta overflow
  71             if (lastAddress - address > (max_positive_delta + 1)) {
  72                 delta = 0;
  73             }
  74         }
  75         deltas[deltaPointer] = delta;
  76         deltaPointer = (deltaPointer + 1) % deltas.size();
  77         lastAddress = address;
  78     }
  79 }
  80
  81 void
  82 DeltaCorrelatingPredictionTables::DCPTEntry::getCandidates(
  83     std::vector<QueuedPrefetcher::AddrPriority> &pfs, unsigned int mask) const
  84 {
  85     // most recent index
  86     unsigned int last = (deltaPointer - 1) % deltas.size();
  87     // second most recent index
  88     unsigned int last_prev = (deltaPointer - 2) % deltas.size();
  89     int delta_0 = deltas[last_prev];
  90     int delta_1 = deltas[last];
  91
  92     // a delta 0 means that it overflowed, we can not match it
  93     if (delta_0 == 0 || delta_1 == 0) {
  94         return;
  95     }
  96
  97     // Try to find the two most recent deltas in a previous position on the
  98     // delta circular array, if found, start issuing prefetches using the
  99     // remaining deltas (adding each delta to the last Addr to generate the
 100     // prefetched address.
 101
 102     // oldest index
 103     int idx_0 = deltaPointer + 1;
 104     // second oldest index
 105     int idx_1 = deltaPointer + 2;
 106     for (int i = 0; i < deltas.size() - 2; i += 1) {
 107         int this_delta_0 = deltas[(idx_0 + i) % deltas.size()];
 108         int this_delta_1 = deltas[(idx_1 + i) % deltas.size()];
 109         if ((this_delta_0 >> mask) == (delta_0 >> mask) &&
 110             (this_delta_1 >> mask) == (delta_1 >> mask)) {
 111             Addr addr = lastAddress;
 112             // Pattern found, issue prefetches with the remaining deltas after
 113             // this pair
 114             i += 2; // skip the matching pair
 115             do {
 116                 int pf_delta = deltas[(idx_0 + i) % deltas.size()];
 117                 addr += pf_delta;
 118                 pfs.push_back(QueuedPrefetcher::AddrPriority(addr, 0));
 119                 i += 1;
 120             } while (i < deltas.size() - 2);
 121         }
 122     }
 123 }
 124
 125 void
 126 DeltaCorrelatingPredictionTables::calculatePrefetch(
 127     const BasePrefetcher::PrefetchInfo &pfi,
 128     std::vector<QueuedPrefetcher::AddrPriority> &addresses)
 129 {
 130     if (!pfi.hasPC()) {
 131         DPRINTF(HWPrefetch, "Ignoring request with no PC.\n");
 132         return;
 133     }
 134     Addr address = pfi.getAddr();
 135     Addr pc = pfi.getPC();
 136     // Look up table entry, is_secure is unused in findEntry because we
 137     // index using the pc
 138     DCPTEntry *entry = table.findEntry(pc, false /* unused */);
 139     if (entry != nullptr) {
 140         entry->addAddress(address, deltaBits);
 141         //Delta correlating
 142         entry->getCandidates(addresses, deltaMaskBits);
 143     } else {
 144         entry = table.findVictim(pc);
 145
 146         table.insertEntry(pc, false /* unused */, entry);
 147
 148         entry->lastAddress = address;
 149     }
 150 }
 151
 152 DeltaCorrelatingPredictionTables *
 153 DeltaCorrelatingPredictionTablesParams::create()
 154 {
 155    return new DeltaCorrelatingPredictionTables(this);
 156 }
 157
 158 DCPTPrefetcher::DCPTPrefetcher(const DCPTPrefetcherParams *p)
 159   : QueuedPrefetcher(p), dcpt(*p->dcpt)
 160 {
 161 }
 162
 163 void
 164 DCPTPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
 165     std::vector<AddrPriority> &addresses)
 166 {
 167     dcpt.calculatePrefetch(pfi, addresses);
 168 }
 169
 170 DCPTPrefetcher*
 171 DCPTPrefetcherParams::create()
 172 {
 173     return new DCPTPrefetcher(this);
 174 }