src/mem/cache/prefetch/spatio_temporal_memory_streaming.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: Javier Bueno
  29  */
  30
  31 #include "mem/cache/prefetch/spatio_temporal_memory_streaming.hh"
  32
  33 #include "debug/HWPrefetch.hh"
  34 #include "mem/cache/prefetch/associative_set_impl.hh"
  35 #include "params/STeMSPrefetcher.hh"
  36
  37 STeMSPrefetcher::STeMSPrefetcher(const STeMSPrefetcherParams *p)
  38   : QueuedPrefetcher(p), spatialRegionSize(p->spatial_region_size),
  39     spatialRegionSizeBits(floorLog2(p->spatial_region_size)),
  40     reconstructionEntries(p->reconstruction_entries),
  41     activeGenerationTable(p->active_generation_table_assoc,
  42                           p->active_generation_table_entries,
  43                           p->active_generation_table_indexing_policy,
  44                           p->active_generation_table_replacement_policy,
  45                           ActiveGenerationTableEntry(
  46                               spatialRegionSize / blkSize)),
  47     patternSequenceTable(p->pattern_sequence_table_assoc,
  48                          p->pattern_sequence_table_entries,
  49                          p->pattern_sequence_table_indexing_policy,
  50                          p->pattern_sequence_table_replacement_policy,
  51                          ActiveGenerationTableEntry(
  52                              spatialRegionSize / blkSize)),
  53     rmob(p->region_miss_order_buffer_entries), rmobHead(0)
  54 {
  55     fatal_if(!isPowerOf2(spatialRegionSize),
  56         "The spatial region size must be a power of 2.");
  57 }
  58
  59 void
  60 STeMSPrefetcher::checkForActiveGenerationsEnd() {
  61     // This prefetcher operates attached to the L1 and it observes all
  62     // accesses, this guarantees that no evictions are missed
  63
  64     // Iterate over all entries, if any recorded cacheline has been evicted,
  65     // the generation finishes, move the entry to the PST
  66     for (auto &agt_entry : activeGenerationTable) {
  67         if (agt_entry.isValid()) {
  68             bool generation_ended = false;
  69             bool sr_is_secure = agt_entry.isSecure();
  70             for (auto &seq_entry : agt_entry.sequence) {
  71                 if (seq_entry.counter > 0) {
  72                     Addr cache_addr =
  73                         agt_entry.paddress + seq_entry.offset * blkSize;
  74                     if (!inCache(cache_addr, sr_is_secure) &&
  75                             !inMissQueue(cache_addr, sr_is_secure)) {
  76                         generation_ended = true;
  77                         break;
  78                     }
  79                 }
  80             }
  81             if (generation_ended) {
  82                 // PST is indexed using the PC (secure bit is unused)
  83                 ActiveGenerationTableEntry *pst_entry =
  84                     patternSequenceTable.findEntry(agt_entry.pc,
  85                                                    false /*unused*/);
  86                 if (pst_entry == nullptr) {
  87                     // Tipically an entry will not exist
  88                     pst_entry = patternSequenceTable.findVictim(agt_entry.pc);
  89                     assert(pst_entry != nullptr);
  90                     patternSequenceTable.insertEntry(agt_entry.pc,
  91                             false /*unused*/, pst_entry);
  92                 } else {
  93                     patternSequenceTable.accessEntry(pst_entry);
  94                 }
  95                 // If the entry existed, this will update the values, if not,
  96                 // this also sets the values of the entry
  97                 pst_entry->update(agt_entry);
  98                 // Free the AGT entry
  99                 agt_entry.setInvalid();
 100             }
 101         }
 102     }
 103 }
 104
 105 void
 106 STeMSPrefetcher::addToRMOB(Addr sr_addr, Addr pst_addr, unsigned int delta)
 107 {
 108     RegionMissOrderBufferEntry &rmob_entry = rmob[rmobHead];
 109     rmobHead = (rmobHead + 1) % rmob.size();
 110
 111     rmob_entry.srAddress = sr_addr;
 112     rmob_entry.pstAddress = pst_addr;
 113     rmob_entry.delta = delta;
 114     rmob_entry.valid = true;
 115 }
 116
 117 void
 118 STeMSPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
 119                                    std::vector<AddrPriority> &addresses)
 120 {
 121     if (!pfi.hasPC()) {
 122         DPRINTF(HWPrefetch, "Ignoring request with no PC.\n");
 123         return;
 124     }
 125
 126     Addr pc = pfi.getPC();
 127     bool is_secure = pfi.isSecure();
 128     // Spatial region address
 129     Addr sr_addr = pfi.getAddr() / spatialRegionSize;
 130     Addr paddr = pfi.getPaddr();
 131
 132     // Offset in cachelines within the spatial region
 133     Addr sr_offset = (pfi.getAddr() % spatialRegionSize) / blkSize;
 134
 135     // Check if any active generation has ended
 136     checkForActiveGenerationsEnd();
 137
 138     ActiveGenerationTableEntry *agt_entry =
 139         activeGenerationTable.findEntry(sr_addr, is_secure);
 140     if (agt_entry != nullptr) {
 141         // found an entry in the AGT, entry is currently being recorded,
 142         // add the offset
 143         activeGenerationTable.accessEntry(agt_entry);
 144         agt_entry->addOffset(sr_offset);
 145         lastTriggerCounter += 1;
 146     } else {
 147         // Not found, this is the first access (Trigger access)
 148
 149         // Add entry to RMOB
 150         Addr pst_addr = (pc << spatialRegionSizeBits) + sr_offset;
 151         addToRMOB(sr_addr, pst_addr, lastTriggerCounter);
 152         // Reset last trigger counter
 153         lastTriggerCounter = 0;
 154
 155         // allocate a new AGT entry
 156         agt_entry = activeGenerationTable.findVictim(sr_addr);
 157         assert(agt_entry != nullptr);
 158         activeGenerationTable.insertEntry(sr_addr, is_secure, agt_entry);
 159         agt_entry->pc = pc;
 160         agt_entry->paddress = paddr;
 161         agt_entry->addOffset(sr_offset);
 162     }
 163     // increase the seq Counter for other entries
 164     for (auto &agt_e : activeGenerationTable) {
 165         if (agt_e.isValid() && agt_entry != &agt_e) {
 166             agt_e.seqCounter += 1;
 167         }
 168     }
 169
 170     // Prefetch generation: if this is a miss, search for the most recent
 171     // entry in the RMOB, and reconstruct the registered access sequence
 172     if (pfi.isCacheMiss()) {
 173         for (unsigned int idx = (rmobHead - 1) % rmob.size();
 174              idx != rmobHead && rmob[idx].valid;
 175              idx = (idx - 1) % rmob.size())
 176         {
 177             if (rmob[idx].srAddress == sr_addr) {
 178                 // reconstruct the access sequence
 179                 reconstructSequence(idx, addresses);
 180                 break;
 181             }
 182         }
 183     }
 184 }
 185
 186 void
 187 STeMSPrefetcher::reconstructSequence(unsigned int rmob_idx,
 188     std::vector<AddrPriority> &addresses)
 189 {
 190     std::vector<Addr> reconstruction(reconstructionEntries, MaxAddr);
 191     unsigned int idx = 0;
 192     // process rmob entries from rmob_idx (most recent with
 193     // address = sr_addr) to the last one (rmobHead)
 194     for (int i = rmob_idx;
 195          i != rmobHead && idx < reconstructionEntries;
 196          i = (i + 1) % rmob.size())
 197     {
 198         reconstruction[idx] = rmob[i].srAddress * spatialRegionSize;
 199         unsigned int next_i = (i + 1) % rmob.size();
 200         idx += rmob[next_i].delta + 1;
 201     }
 202     // Now query the PST with the PC of each RMOB entry
 203     idx = 0;
 204     for (int i = rmob_idx;
 205          i != rmobHead && idx < reconstructionEntries;
 206          i = (i + 1) % rmob.size())
 207     {
 208         ActiveGenerationTableEntry *pst_entry =
 209             patternSequenceTable.findEntry(rmob[i].pstAddress,
 210                                            false /* unused */);
 211         if (pst_entry != nullptr) {
 212             patternSequenceTable.accessEntry(pst_entry);
 213             for (auto &seq_entry : pst_entry->sequence) {
 214                 if (seq_entry.counter > 1) {
 215                     // 2-bit counter: high enough confidence with a
 216                     // value greater than 1
 217                     Addr rec_addr = rmob[i].srAddress * spatialRegionSize +
 218                         seq_entry.offset;
 219                     unsigned ridx = idx + seq_entry.delta;
 220                     // Try to use the corresponding position, if it has been
 221                     // already used, look the surrounding positions
 222                     if (ridx < reconstructionEntries &&
 223                         reconstruction[ridx] == MaxAddr) {
 224                         reconstruction[ridx] = rec_addr;
 225                     } else if ((ridx + 1) < reconstructionEntries &&
 226                         reconstruction[ridx + 1] == MaxAddr) {
 227                         reconstruction[ridx + 1] = rec_addr;
 228                     } else if ((ridx + 2) < reconstructionEntries &&
 229                         reconstruction[ridx + 2] == MaxAddr) {
 230                         reconstruction[ridx + 2] = rec_addr;
 231                     } else if ((ridx > 0) &&
 232                         ((ridx - 1) < reconstructionEntries) &&
 233                         reconstruction[ridx - 1] == MaxAddr) {
 234                         reconstruction[ridx - 1] = rec_addr;
 235                     } else if ((ridx > 1) &&
 236                         ((ridx - 2) < reconstructionEntries) &&
 237                         reconstruction[ridx - 2] == MaxAddr) {
 238                         reconstruction[ridx - 2] = rec_addr;
 239                     }
 240                 }
 241             }
 242         }
 243         unsigned int next_i = (i + 1) % rmob.size();
 244         idx += rmob[next_i].delta + 1;
 245     }
 246     for (Addr pf_addr : reconstruction) {
 247         if (pf_addr != MaxAddr) {
 248             addresses.push_back(AddrPriority(pf_addr, 0));
 249         }
 250     }
 251 }
 252
 253 STeMSPrefetcher *
 254 STeMSPrefetcherParams::create()
 255 {
 256    return new STeMSPrefetcher(this);
 257 }