stride.cc revision 12727:56c23b54bcb1
110447Snilay@cs.wisc.edu/* 210447Snilay@cs.wisc.edu * Copyright (c) 2012-2013, 2015 ARM Limited 310447Snilay@cs.wisc.edu * All rights reserved 410447Snilay@cs.wisc.edu * 510447Snilay@cs.wisc.edu * The license below extends only to copyright in the software and shall 610447Snilay@cs.wisc.edu * not be construed as granting a license to any other intellectual 710447Snilay@cs.wisc.edu * property including but not limited to intellectual property relating 810447Snilay@cs.wisc.edu * to a hardware implementation of the functionality of the software 910447Snilay@cs.wisc.edu * licensed hereunder. You may use the software subject to the license 1010447Snilay@cs.wisc.edu * terms below provided that you ensure that this notice is replicated 1110447Snilay@cs.wisc.edu * unmodified and in its entirety in all distributions of the software, 1210447Snilay@cs.wisc.edu * modified or unmodified, in source code or in binary form. 1310447Snilay@cs.wisc.edu * 1410447Snilay@cs.wisc.edu * Copyright (c) 2005 The Regents of The University of Michigan 1510447Snilay@cs.wisc.edu * All rights reserved. 1610447Snilay@cs.wisc.edu * 1710447Snilay@cs.wisc.edu * Redistribution and use in source and binary forms, with or without 1810447Snilay@cs.wisc.edu * modification, are permitted provided that the following conditions are 1910447Snilay@cs.wisc.edu * met: redistributions of source code must retain the above copyright 2010447Snilay@cs.wisc.edu * notice, this list of conditions and the following disclaimer; 2110447Snilay@cs.wisc.edu * redistributions in binary form must reproduce the above copyright 2210447Snilay@cs.wisc.edu * notice, this list of conditions and the following disclaimer in the 23 * documentation and/or other materials provided with the distribution; 24 * neither the name of the copyright holders nor the names of its 25 * contributors may be used to endorse or promote products derived from 26 * this software without specific prior written permission. 27 * 28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 39 * 40 * Authors: Ron Dreslinski 41 * Steve Reinhardt 42 */ 43 44/** 45 * @file 46 * Stride Prefetcher template instantiations. 47 */ 48 49#include "mem/cache/prefetch/stride.hh" 50 51#include <cassert> 52 53#include "base/intmath.hh" 54#include "base/logging.hh" 55#include "base/random.hh" 56#include "base/trace.hh" 57#include "debug/HWPrefetch.hh" 58#include "params/StridePrefetcher.hh" 59 60StridePrefetcher::StridePrefetcher(const StridePrefetcherParams *p) 61 : QueuedPrefetcher(p), 62 maxConf(p->max_conf), 63 threshConf(p->thresh_conf), 64 minConf(p->min_conf), 65 startConf(p->start_conf), 66 pcTableAssoc(p->table_assoc), 67 pcTableSets(p->table_sets), 68 useMasterId(p->use_master_id), 69 degree(p->degree), 70 pcTable(pcTableAssoc, pcTableSets, name()) 71{ 72 // Don't consult stride prefetcher on instruction accesses 73 onInst = false; 74 75 assert(isPowerOf2(pcTableSets)); 76} 77 78StridePrefetcher::StrideEntry** 79StridePrefetcher::PCTable::allocateNewContext(int context) 80{ 81 auto res = entries.insert(std::make_pair(context, 82 new StrideEntry*[pcTableSets])); 83 auto it = res.first; 84 chatty_assert(res.second, "Allocating an already created context\n"); 85 assert(it->first == context); 86 87 DPRINTF(HWPrefetch, "Adding context %i with stride entries at %p\n", 88 context, it->second); 89 90 StrideEntry** entry = it->second; 91 for (int s = 0; s < pcTableSets; s++) { 92 entry[s] = new StrideEntry[pcTableAssoc]; 93 } 94 return entry; 95} 96 97StridePrefetcher::PCTable::~PCTable() { 98 for (auto entry : entries) { 99 for (int s = 0; s < pcTableSets; s++) { 100 delete[] entry.second[s]; 101 } 102 delete[] entry.second; 103 } 104} 105 106void 107StridePrefetcher::calculatePrefetch(const PacketPtr &pkt, 108 std::vector<AddrPriority> &addresses) 109{ 110 if (!pkt->req->hasPC()) { 111 DPRINTF(HWPrefetch, "Ignoring request with no PC.\n"); 112 return; 113 } 114 115 // Get required packet info 116 Addr pkt_addr = pkt->getAddr(); 117 Addr pc = pkt->req->getPC(); 118 bool is_secure = pkt->isSecure(); 119 MasterID master_id = useMasterId ? pkt->req->masterId() : 0; 120 121 // Lookup pc-based information 122 StrideEntry *entry; 123 124 if (pcTableHit(pc, is_secure, master_id, entry)) { 125 // Hit in table 126 int new_stride = pkt_addr - entry->lastAddr; 127 bool stride_match = (new_stride == entry->stride); 128 129 // Adjust confidence for stride entry 130 if (stride_match && new_stride != 0) { 131 if (entry->confidence < maxConf) 132 entry->confidence++; 133 } else { 134 if (entry->confidence > minConf) 135 entry->confidence--; 136 // If confidence has dropped below the threshold, train new stride 137 if (entry->confidence < threshConf) 138 entry->stride = new_stride; 139 } 140 141 DPRINTF(HWPrefetch, "Hit: PC %x pkt_addr %x (%s) stride %d (%s), " 142 "conf %d\n", pc, pkt_addr, is_secure ? "s" : "ns", new_stride, 143 stride_match ? "match" : "change", 144 entry->confidence); 145 146 entry->lastAddr = pkt_addr; 147 148 // Abort prefetch generation if below confidence threshold 149 if (entry->confidence < threshConf) 150 return; 151 152 // Generate up to degree prefetches 153 for (int d = 1; d <= degree; d++) { 154 // Round strides up to atleast 1 cacheline 155 int prefetch_stride = new_stride; 156 if (abs(new_stride) < blkSize) { 157 prefetch_stride = (new_stride < 0) ? -blkSize : blkSize; 158 } 159 160 Addr new_addr = pkt_addr + d * prefetch_stride; 161 if (samePage(pkt_addr, new_addr)) { 162 DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr); 163 addresses.push_back(AddrPriority(new_addr, 0)); 164 } else { 165 // Record the number of page crossing prefetches generated 166 pfSpanPage += degree - d + 1; 167 DPRINTF(HWPrefetch, "Ignoring page crossing prefetch.\n"); 168 return; 169 } 170 } 171 } else { 172 // Miss in table 173 DPRINTF(HWPrefetch, "Miss: PC %x pkt_addr %x (%s)\n", pc, pkt_addr, 174 is_secure ? "s" : "ns"); 175 176 StrideEntry* entry = pcTableVictim(pc, master_id); 177 entry->instAddr = pc; 178 entry->lastAddr = pkt_addr; 179 entry->isSecure= is_secure; 180 entry->stride = 0; 181 entry->confidence = startConf; 182 } 183} 184 185inline Addr 186StridePrefetcher::pcHash(Addr pc) const 187{ 188 Addr hash1 = pc >> 1; 189 Addr hash2 = hash1 >> floorLog2(pcTableSets); 190 return (hash1 ^ hash2) & (Addr)(pcTableSets - 1); 191} 192 193inline StridePrefetcher::StrideEntry* 194StridePrefetcher::pcTableVictim(Addr pc, int master_id) 195{ 196 // Rand replacement for now 197 int set = pcHash(pc); 198 int way = random_mt.random<int>(0, pcTableAssoc - 1); 199 200 DPRINTF(HWPrefetch, "Victimizing lookup table[%d][%d].\n", set, way); 201 return &pcTable[master_id][set][way]; 202} 203 204inline bool 205StridePrefetcher::pcTableHit(Addr pc, bool is_secure, int master_id, 206 StrideEntry* &entry) 207{ 208 int set = pcHash(pc); 209 StrideEntry* set_entries = pcTable[master_id][set]; 210 for (int way = 0; way < pcTableAssoc; way++) { 211 // Search ways for match 212 if (set_entries[way].instAddr == pc && 213 set_entries[way].isSecure == is_secure) { 214 DPRINTF(HWPrefetch, "Lookup hit table[%d][%d].\n", set, way); 215 entry = &set_entries[way]; 216 return true; 217 } 218 } 219 return false; 220} 221 222StridePrefetcher* 223StridePrefetcherParams::create() 224{ 225 return new StridePrefetcher(this); 226} 227