src/mem/cache/prefetch/stride.cc

   1 /*
   2  * Copyright (c) 2018 Inria
   3  * Copyright (c) 2012-2013, 2015 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) 2005 The Regents of The University of Michigan
  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  * Authors: Ron Dreslinski
  42  *          Steve Reinhardt
  43  *          Daniel Carvalho
  44  */
  45
  46 /**
  47  * @file
  48  * Stride Prefetcher template instantiations.
  49  */
  50
  51 #include "mem/cache/prefetch/stride.hh"
  52
  53 #include <cassert>
  54
  55 #include "base/intmath.hh"
  56 #include "base/logging.hh"
  57 #include "base/random.hh"
  58 #include "base/trace.hh"
  59 #include "debug/HWPrefetch.hh"
  60 #include "mem/cache/replacement_policies/base.hh"
  61 #include "params/StridePrefetcher.hh"
  62
  63 StridePrefetcher::StrideEntry::StrideEntry()
  64 {
  65     invalidate();
  66 }
  67
  68 void
  69 StridePrefetcher::StrideEntry::invalidate()
  70 {
  71     instAddr = 0;
  72     lastAddr = 0;
  73     isSecure = false;
  74     stride = 0;
  75     confidence = 0;
  76 }
  77
  78 StridePrefetcher::StridePrefetcher(const StridePrefetcherParams *p)
  79     : QueuedPrefetcher(p),
  80       maxConf(p->max_conf),
  81       threshConf(p->thresh_conf),
  82       minConf(p->min_conf),
  83       startConf(p->start_conf),
  84       pcTableAssoc(p->table_assoc),
  85       pcTableSets(p->table_sets),
  86       useMasterId(p->use_master_id),
  87       degree(p->degree),
  88       replacementPolicy(p->replacement_policy)
  89 {
  90     assert(isPowerOf2(pcTableSets));
  91 }
  92
  93 StridePrefetcher::PCTable*
  94 StridePrefetcher::findTable(int context)
  95 {
  96     // Check if table for given context exists
  97     auto it = pcTables.find(context);
  98     if (it != pcTables.end())
  99         return &it->second;
 100
 101     // If table does not exist yet, create one
 102     return allocateNewContext(context);
 103 }
 104
 105 StridePrefetcher::PCTable*
 106 StridePrefetcher::allocateNewContext(int context)
 107 {
 108     // Create new table
 109     auto insertion_result = pcTables.insert(std::make_pair(context,
 110         PCTable(pcTableAssoc, pcTableSets, name(), replacementPolicy)));
 111
 112     DPRINTF(HWPrefetch, "Adding context %i with stride entries\n", context);
 113
 114     // Get iterator to new pc table, and then return a pointer to the new table
 115     return &(insertion_result.first->second);
 116 }
 117
 118 StridePrefetcher::PCTable::PCTable(int assoc, int sets, const std::string name,
 119                                    BaseReplacementPolicy* replacementPolicy)
 120     : pcTableSets(sets), _name(name), entries(pcTableSets),
 121       replacementPolicy(replacementPolicy)
 122 {
 123     for (int set = 0; set < sets; set++) {
 124         entries[set].resize(assoc);
 125         for (int way = 0; way < assoc; way++) {
 126             // Inform the entry its position
 127             entries[set][way].setPosition(set, way);
 128
 129             // Initialize replacement policy data
 130             entries[set][way].replacementData =
 131                 replacementPolicy->instantiateEntry();
 132         }
 133     }
 134 }
 135
 136 StridePrefetcher::PCTable::~PCTable()
 137 {
 138 }
 139
 140 void
 141 StridePrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
 142                                     std::vector<AddrPriority> &addresses)
 143 {
 144     if (!pfi.hasPC()) {
 145         DPRINTF(HWPrefetch, "Ignoring request with no PC.\n");
 146         return;
 147     }
 148
 149     // Get required packet info
 150     Addr pf_addr = pfi.getAddr();
 151     Addr pc = pfi.getPC();
 152     bool is_secure = pfi.isSecure();
 153     MasterID master_id = useMasterId ? pfi.getMasterId() : 0;
 154
 155     // Get corresponding pc table
 156     PCTable* pcTable = findTable(master_id);
 157
 158     // Search for entry in the pc table
 159     StrideEntry *entry = pcTable->findEntry(pc, is_secure);
 160
 161     if (entry != nullptr) {
 162         // Hit in table
 163         int new_stride = pf_addr - entry->lastAddr;
 164         bool stride_match = (new_stride == entry->stride);
 165
 166         // Adjust confidence for stride entry
 167         if (stride_match && new_stride != 0) {
 168             if (entry->confidence < maxConf)
 169                 entry->confidence++;
 170         } else {
 171             if (entry->confidence > minConf)
 172                 entry->confidence--;
 173             // If confidence has dropped below the threshold, train new stride
 174             if (entry->confidence < threshConf)
 175                 entry->stride = new_stride;
 176         }
 177
 178         DPRINTF(HWPrefetch, "Hit: PC %x pkt_addr %x (%s) stride %d (%s), "
 179                 "conf %d\n", pc, pf_addr, is_secure ? "s" : "ns",
 180                 new_stride, stride_match ? "match" : "change",
 181                 entry->confidence);
 182
 183         entry->lastAddr = pf_addr;
 184
 185         // Abort prefetch generation if below confidence threshold
 186         if (entry->confidence < threshConf)
 187             return;
 188
 189         // Generate up to degree prefetches
 190         for (int d = 1; d <= degree; d++) {
 191             // Round strides up to atleast 1 cacheline
 192             int prefetch_stride = new_stride;
 193             if (abs(new_stride) < blkSize) {
 194                 prefetch_stride = (new_stride < 0) ? -blkSize : blkSize;
 195             }
 196
 197             Addr new_addr = pf_addr + d * prefetch_stride;
 198             addresses.push_back(AddrPriority(new_addr, 0));
 199         }
 200     } else {
 201         // Miss in table
 202         DPRINTF(HWPrefetch, "Miss: PC %x pkt_addr %x (%s)\n", pc, pf_addr,
 203                 is_secure ? "s" : "ns");
 204
 205         StrideEntry* entry = pcTable->findVictim(pc);
 206
 207         // Invalidate victim
 208         entry->invalidate();
 209         replacementPolicy->invalidate(entry->replacementData);
 210
 211         // Insert new entry's data
 212         entry->instAddr = pc;
 213         entry->lastAddr = pf_addr;
 214         entry->isSecure = is_secure;
 215         entry->confidence = startConf;
 216         replacementPolicy->reset(entry->replacementData);
 217     }
 218 }
 219
 220 inline Addr
 221 StridePrefetcher::PCTable::pcHash(Addr pc) const
 222 {
 223     Addr hash1 = pc >> 1;
 224     Addr hash2 = hash1 >> floorLog2(pcTableSets);
 225     return (hash1 ^ hash2) & (Addr)(pcTableSets - 1);
 226 }
 227
 228 inline StridePrefetcher::StrideEntry*
 229 StridePrefetcher::PCTable::findVictim(Addr pc)
 230 {
 231     // Rand replacement for now
 232     int set = pcHash(pc);
 233
 234     // Get possible entries to be victimized
 235     std::vector<ReplaceableEntry*> possible_entries;
 236     for (auto& entry : entries[set]) {
 237         possible_entries.push_back(&entry);
 238     }
 239
 240     // Choose victim based on replacement policy
 241     StrideEntry* victim = static_cast<StrideEntry*>(
 242         replacementPolicy->getVictim(possible_entries));
 243
 244     DPRINTF(HWPrefetch, "Victimizing lookup table[%d][%d].\n",
 245             victim->getSet(), victim->getWay());
 246
 247     return victim;
 248 }
 249
 250 inline StridePrefetcher::StrideEntry*
 251 StridePrefetcher::PCTable::findEntry(Addr pc, bool is_secure)
 252 {
 253     int set = pcHash(pc);
 254     for (auto& entry : entries[set]) {
 255         // Search ways for match
 256         if ((entry.instAddr == pc) && (entry.isSecure == is_secure)) {
 257             DPRINTF(HWPrefetch, "Lookup hit table[%d][%d].\n", entry.getSet(),
 258                     entry.getWay());
 259             replacementPolicy->touch(entry.replacementData);
 260             return &entry;
 261         }
 262     }
 263     return nullptr;
 264 }
 265
 266 StridePrefetcher*
 267 StridePrefetcherParams::create()
 268 {
 269     return new StridePrefetcher(this);
 270 }