src/mem/cache/prefetch/pif.cc

   1 /**
   2  * Copyright (c) 2019 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: Ivan Pizarro
  29  */
  30
  31 #include "mem/cache/prefetch/pif.hh"
  32
  33 #include <utility>
  34
  35 #include "debug/HWPrefetch.hh"
  36 #include "mem/cache/prefetch/associative_set_impl.hh"
  37 #include "params/PIFPrefetcher.hh"
  38
  39 PIFPrefetcher::PIFPrefetcher(const PIFPrefetcherParams *p)
  40     : QueuedPrefetcher(p),
  41       precSize(p->prec_spatial_region_bits),
  42       succSize(p->succ_spatial_region_bits),
  43       maxCompactorEntries(p->compactor_entries),
  44       maxStreamAddressBufferEntries(p->stream_address_buffer_entries),
  45       historyBuffer(p->history_buffer_size),
  46       historyBufferTail(0),
  47       index(p->index_assoc, p->index_entries, p->index_indexing_policy,
  48             p->index_replacement_policy),
  49       streamAddressBuffer(), listenersPC()
  50 {
  51 }
  52
  53 PIFPrefetcher::CompactorEntry::CompactorEntry(Addr addr,
  54     unsigned int prec_size, unsigned int succ_size)
  55 {
  56     trigger = addr;
  57     prec.resize(prec_size, false);
  58     succ.resize(succ_size, false);
  59 }
  60
  61 Addr
  62 PIFPrefetcher::CompactorEntry::distanceFromTrigger(Addr target,
  63         unsigned int log_blk_size) const
  64 {
  65     const Addr target_blk = target >> log_blk_size;
  66     const Addr trigger_blk = trigger >> log_blk_size;
  67
  68     return target_blk > trigger_blk ?
  69               target_blk - trigger_blk : trigger_blk - target_blk;
  70 }
  71
  72 bool
  73 PIFPrefetcher::CompactorEntry::inSameSpatialRegion(Addr pc,
  74         unsigned int log_blk_size, bool update)
  75 {
  76     Addr blk_distance = distanceFromTrigger(pc, log_blk_size);
  77
  78     bool hit = (pc > trigger) ?
  79         (succ.size() >= blk_distance) : (prec.size() >= blk_distance);
  80     if (hit && update) {
  81         if (pc > trigger) {
  82             succ[blk_distance - 1] = true;
  83         } else if (pc < trigger) {
  84             prec[blk_distance - 1] = true;
  85         }
  86     }
  87     return hit;
  88 }
  89
  90 bool
  91 PIFPrefetcher::CompactorEntry::hasAddress(Addr target,
  92                                           unsigned int log_blk_size) const
  93 {
  94     Addr blk_distance = distanceFromTrigger(target, log_blk_size);
  95     bool hit = false;
  96     if (target > trigger) {
  97         hit = blk_distance <= succ.size() && succ[blk_distance - 1];
  98     } else if (target < trigger) {
  99         hit = blk_distance <= prec.size() && succ[blk_distance - 1];
 100     } else {
 101         hit = true;
 102     }
 103     return hit;
 104 }
 105
 106 void
 107 PIFPrefetcher::CompactorEntry::getPredictedAddresses(unsigned int log_blk_size,
 108     std::vector<AddrPriority> &addresses) const
 109 {
 110     // Calculate the addresses of the instruction blocks that are encoded
 111     // by the bit vector and issue prefetch requests for these addresses.
 112     // Predictions are made by traversing the bit vector from left to right
 113     // as this typically predicts the accesses in the order they will be
 114     // issued in the core.
 115     const Addr trigger_blk = trigger >> log_blk_size;
 116     for (int i = prec.size()-1; i >= 0; i--) {
 117         // Address from the preceding blocks to issue a prefetch
 118         if (prec[i]) {
 119             const Addr prec_addr = (trigger_blk - (i+1)) << log_blk_size;
 120             addresses.push_back(AddrPriority(prec_addr, 0));
 121         }
 122     }
 123     for (int i = 0; i < succ.size(); i++) {
 124         // Address from the succeding blocks to issue a prefetch
 125         if (succ[i]) {
 126             const Addr succ_addr = (trigger_blk + (i+1)) << log_blk_size;
 127             addresses.push_back(AddrPriority(succ_addr, 0));
 128         }
 129     }
 130 }
 131
 132 void
 133 PIFPrefetcher::notifyRetiredInst(const Addr pc)
 134 {
 135     // First access to the prefetcher
 136     if (temporalCompactor.size() == 0) {
 137         spatialCompactor = CompactorEntry(pc, precSize, succSize);
 138     } else {
 139         // If the PC of the instruction retired is in the same spatial region
 140         // than the last trigger address, update the bit vectors based on the
 141         // distance between them
 142         if (spatialCompactor.inSameSpatialRegion(pc, lBlkSize, true)) {
 143         // If the PC of the instruction retired is outside the latest spatial
 144         // region, check if it matches in any of the regions in the temporal
 145         // compactor and update it to the MRU position
 146         } else {
 147             bool is_in_temporal_compactor = false;
 148
 149             // Check if the PC is in the temporal compactor
 150             for (auto it = temporalCompactor.begin();
 151                     it != temporalCompactor.end(); it++)
 152             {
 153                 if (it->inSameSpatialRegion(pc, lBlkSize, false)) {
 154                     spatialCompactor = (*it);
 155                     temporalCompactor.erase(it);
 156                     is_in_temporal_compactor = true;
 157                     break;
 158                 }
 159             }
 160
 161             if (temporalCompactor.size() == maxCompactorEntries) {
 162                 temporalCompactor.pop_front(); // Discard the LRU entry
 163             }
 164
 165             temporalCompactor.push_back(spatialCompactor);
 166
 167             // If the compactor entry is neither the spatial or can't be
 168             // found in the temporal compactor, reset the spatial compactor
 169             // updating the trigger address and resetting the vector bits
 170             if (!is_in_temporal_compactor) {
 171                 // Insert the spatial entry into the history buffer and update
 172                 // the 'index' table to point to the new entry
 173                 historyBuffer[historyBufferTail] = spatialCompactor;
 174
 175                 IndexEntry *idx_entry =
 176                     index.findEntry(spatialCompactor.trigger, false);
 177                 if (idx_entry != nullptr) {
 178                     index.accessEntry(idx_entry);
 179                 } else {
 180                     idx_entry = index.findVictim(spatialCompactor.trigger);
 181                     assert(idx_entry != nullptr);
 182                     index.insertEntry(spatialCompactor.trigger, false,
 183                                       idx_entry);
 184                 }
 185                 idx_entry->historyIndex = historyBufferTail;
 186
 187                 historyBufferTail++;
 188                 if (historyBufferTail == historyBuffer.size()) {
 189                     historyBufferTail = 0;
 190                 }
 191
 192                 // Reset the spatial compactor fields with the new address
 193                 spatialCompactor = CompactorEntry(pc, precSize, succSize);
 194             }
 195         }
 196     }
 197 }
 198
 199 void
 200 PIFPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
 201     std::vector<AddrPriority> &addresses)
 202 {
 203     const Addr addr = pfi.getAddr();
 204
 205     // First check if the access has been prefetched, this is done by
 206     // comparing the access against the active Stream Address Buffers
 207     for (auto &sabEntry : streamAddressBuffer) {
 208         if (sabEntry->hasAddress(addr, lBlkSize)) {
 209             // Advance to the next entry (first check if we have reached the
 210             // end of the history buffer)
 211             if (sabEntry == &(historyBuffer[historyBuffer.size() - 1])) {
 212                 sabEntry = &(historyBuffer[0]);
 213             } else {
 214                 sabEntry++;
 215             }
 216             sabEntry->getPredictedAddresses(lBlkSize, addresses);
 217             // We are done
 218             return;
 219         }
 220     }
 221
 222     // Check if a valid entry in the 'index' table is found and allocate a new
 223     // active prediction stream
 224     IndexEntry *idx_entry = index.findEntry(addr, /* unused */ false);
 225
 226     if (idx_entry != nullptr) {
 227         index.accessEntry(idx_entry);
 228         // Trigger address from the 'index' table and index to the history
 229         // buffer
 230         const unsigned int hb_entry = idx_entry->historyIndex;
 231         CompactorEntry *entry = &historyBuffer[hb_entry];
 232
 233         // Track the block in the Stream Address Buffer
 234         if (streamAddressBuffer.size() == maxStreamAddressBufferEntries) {
 235             streamAddressBuffer.pop_front();
 236         }
 237         streamAddressBuffer.push_back(entry);
 238
 239         entry->getPredictedAddresses(lBlkSize, addresses);
 240     }
 241 }
 242
 243 void
 244 PIFPrefetcher::PrefetchListenerPC::notify(const Addr& pc)
 245 {
 246     parent.notifyRetiredInst(pc);
 247 }
 248
 249 void
 250 PIFPrefetcher::addEventProbeRetiredInsts(SimObject *obj, const char *name)
 251 {
 252     ProbeManager *pm(obj->getProbeManager());
 253     listenersPC.push_back(new PrefetchListenerPC(*this, pm, name));
 254 }
 255
 256 PIFPrefetcher*
 257 PIFPrefetcherParams::create()
 258 {
 259     return new PIFPrefetcher(this);
 260 }