stride.cc revision 13425:00abf35b2f7e
111828Sjason@lowepower.com/* 211482Sandreas.sandberg@arm.com * Copyright (c) 2012-2013, 2015 ARM Limited 311482Sandreas.sandberg@arm.com * All rights reserved 411482Sandreas.sandberg@arm.com * 511482Sandreas.sandberg@arm.com * The license below extends only to copyright in the software and shall 611482Sandreas.sandberg@arm.com * not be construed as granting a license to any other intellectual 711482Sandreas.sandberg@arm.com * property including but not limited to intellectual property relating 811482Sandreas.sandberg@arm.com * to a hardware implementation of the functionality of the software 911482Sandreas.sandberg@arm.com * licensed hereunder. You may use the software subject to the license 1011482Sandreas.sandberg@arm.com * terms below provided that you ensure that this notice is replicated 1111482Sandreas.sandberg@arm.com * unmodified and in its entirety in all distributions of the software, 1211482Sandreas.sandberg@arm.com * modified or unmodified, in source code or in binary form. 1311482Sandreas.sandberg@arm.com * 1411482Sandreas.sandberg@arm.com * Copyright (c) 2005 The Regents of The University of Michigan 1511482Sandreas.sandberg@arm.com * All rights reserved. 1611482Sandreas.sandberg@arm.com * 1711482Sandreas.sandberg@arm.com * Redistribution and use in source and binary forms, with or without 1811482Sandreas.sandberg@arm.com * modification, are permitted provided that the following conditions are 1911482Sandreas.sandberg@arm.com * met: redistributions of source code must retain the above copyright 2011482Sandreas.sandberg@arm.com * notice, this list of conditions and the following disclaimer; 2111482Sandreas.sandberg@arm.com * redistributions in binary form must reproduce the above copyright 2211482Sandreas.sandberg@arm.com * notice, this list of conditions and the following disclaimer in the 2311482Sandreas.sandberg@arm.com * documentation and/or other materials provided with the distribution; 2411482Sandreas.sandberg@arm.com * neither the name of the copyright holders nor the names of its 2511482Sandreas.sandberg@arm.com * contributors may be used to endorse or promote products derived from 2611482Sandreas.sandberg@arm.com * this software without specific prior written permission. 2711482Sandreas.sandberg@arm.com * 2811482Sandreas.sandberg@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2911482Sandreas.sandberg@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 3011482Sandreas.sandberg@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 3111482Sandreas.sandberg@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 3211482Sandreas.sandberg@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3311482Sandreas.sandberg@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3411482Sandreas.sandberg@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3511482Sandreas.sandberg@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3611482Sandreas.sandberg@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3711482Sandreas.sandberg@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3811482Sandreas.sandberg@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3911482Sandreas.sandberg@arm.com * 4012575Sgiacomo.travaglini@arm.com * Authors: Ron Dreslinski 4112575Sgiacomo.travaglini@arm.com * Steve Reinhardt 4211482Sandreas.sandberg@arm.com */ 4311482Sandreas.sandberg@arm.com 4411482Sandreas.sandberg@arm.com/** 4511482Sandreas.sandberg@arm.com * @file 4611482Sandreas.sandberg@arm.com * Stride Prefetcher template instantiations. 4711482Sandreas.sandberg@arm.com */ 4811482Sandreas.sandberg@arm.com 4911482Sandreas.sandberg@arm.com#include "mem/cache/prefetch/stride.hh" 5011482Sandreas.sandberg@arm.com 5111482Sandreas.sandberg@arm.com#include <cassert> 5211482Sandreas.sandberg@arm.com 5311482Sandreas.sandberg@arm.com#include "base/intmath.hh" 5411482Sandreas.sandberg@arm.com#include "base/logging.hh" 5511482Sandreas.sandberg@arm.com#include "base/random.hh" 5611482Sandreas.sandberg@arm.com#include "base/trace.hh" 5711482Sandreas.sandberg@arm.com#include "debug/HWPrefetch.hh" 5811482Sandreas.sandberg@arm.com#include "params/StridePrefetcher.hh" 5911482Sandreas.sandberg@arm.com 6011482Sandreas.sandberg@arm.comStridePrefetcher::StridePrefetcher(const StridePrefetcherParams *p) 6111482Sandreas.sandberg@arm.com : QueuedPrefetcher(p), 6211482Sandreas.sandberg@arm.com maxConf(p->max_conf), 6311482Sandreas.sandberg@arm.com threshConf(p->thresh_conf), 6411482Sandreas.sandberg@arm.com minConf(p->min_conf), 6511482Sandreas.sandberg@arm.com startConf(p->start_conf), 6611482Sandreas.sandberg@arm.com pcTableAssoc(p->table_assoc), 6711482Sandreas.sandberg@arm.com pcTableSets(p->table_sets), 6811482Sandreas.sandberg@arm.com useMasterId(p->use_master_id), 6911482Sandreas.sandberg@arm.com degree(p->degree) 7011482Sandreas.sandberg@arm.com{ 7111482Sandreas.sandberg@arm.com assert(isPowerOf2(pcTableSets)); 7211482Sandreas.sandberg@arm.com} 7311482Sandreas.sandberg@arm.com 7411482Sandreas.sandberg@arm.comStridePrefetcher::PCTable* 7511482Sandreas.sandberg@arm.comStridePrefetcher::findTable(int context) 7611482Sandreas.sandberg@arm.com{ 7711482Sandreas.sandberg@arm.com // Check if table for given context exists 7811482Sandreas.sandberg@arm.com auto it = pcTables.find(context); 7911482Sandreas.sandberg@arm.com if (it != pcTables.end()) 8011482Sandreas.sandberg@arm.com return &it->second; 8111482Sandreas.sandberg@arm.com 8211482Sandreas.sandberg@arm.com // If table does not exist yet, create one 8311482Sandreas.sandberg@arm.com return allocateNewContext(context); 8411482Sandreas.sandberg@arm.com} 8511482Sandreas.sandberg@arm.com 8611482Sandreas.sandberg@arm.comStridePrefetcher::PCTable* 8711482Sandreas.sandberg@arm.comStridePrefetcher::allocateNewContext(int context) 8811482Sandreas.sandberg@arm.com{ 8911482Sandreas.sandberg@arm.com // Create new table 9011482Sandreas.sandberg@arm.com auto insertion_result = pcTables.insert(std::make_pair(context, 9111482Sandreas.sandberg@arm.com PCTable(pcTableAssoc, pcTableSets, name()))); 9211482Sandreas.sandberg@arm.com 9311482Sandreas.sandberg@arm.com DPRINTF(HWPrefetch, "Adding context %i with stride entries\n", context); 9411482Sandreas.sandberg@arm.com 9511482Sandreas.sandberg@arm.com // Get iterator to new pc table, and then return a pointer to the new table 9611482Sandreas.sandberg@arm.com return &(insertion_result.first->second); 9711482Sandreas.sandberg@arm.com} 9811482Sandreas.sandberg@arm.com 9911482Sandreas.sandberg@arm.comStridePrefetcher::PCTable::PCTable(int assoc, int sets, const std::string name) 10011482Sandreas.sandberg@arm.com : pcTableAssoc(assoc), pcTableSets(sets), _name(name), entries(pcTableSets) 10111482Sandreas.sandberg@arm.com{ 10211482Sandreas.sandberg@arm.com for (auto& set : entries) { 10311482Sandreas.sandberg@arm.com set.resize(pcTableAssoc); 10411482Sandreas.sandberg@arm.com } 10511482Sandreas.sandberg@arm.com} 10611482Sandreas.sandberg@arm.com 10711482Sandreas.sandberg@arm.comStridePrefetcher::PCTable::~PCTable() 10811482Sandreas.sandberg@arm.com{ 10911482Sandreas.sandberg@arm.com} 11011482Sandreas.sandberg@arm.com 11111482Sandreas.sandberg@arm.comvoid 11211482Sandreas.sandberg@arm.comStridePrefetcher::calculatePrefetch(const PacketPtr &pkt, 11311482Sandreas.sandberg@arm.com std::vector<AddrPriority> &addresses) 11411482Sandreas.sandberg@arm.com{ 11511482Sandreas.sandberg@arm.com if (!pkt->req->hasPC()) { 11611482Sandreas.sandberg@arm.com DPRINTF(HWPrefetch, "Ignoring request with no PC.\n"); 11711482Sandreas.sandberg@arm.com return; 11811482Sandreas.sandberg@arm.com } 11911482Sandreas.sandberg@arm.com 12011482Sandreas.sandberg@arm.com // Get required packet info 12111482Sandreas.sandberg@arm.com Addr pkt_addr = pkt->getAddr(); 12211482Sandreas.sandberg@arm.com Addr pc = pkt->req->getPC(); 12311482Sandreas.sandberg@arm.com bool is_secure = pkt->isSecure(); 12411482Sandreas.sandberg@arm.com MasterID master_id = useMasterId ? pkt->req->masterId() : 0; 12511482Sandreas.sandberg@arm.com 12611482Sandreas.sandberg@arm.com // Get corresponding pc table 12711482Sandreas.sandberg@arm.com PCTable* pcTable = findTable(master_id); 12811482Sandreas.sandberg@arm.com 12911482Sandreas.sandberg@arm.com // Search for entry in the pc table 13011482Sandreas.sandberg@arm.com StrideEntry *entry = pcTable->findEntry(pc, is_secure); 13112575Sgiacomo.travaglini@arm.com 13211482Sandreas.sandberg@arm.com if (entry != nullptr) { 13311482Sandreas.sandberg@arm.com // Hit in table 13411482Sandreas.sandberg@arm.com int new_stride = pkt_addr - entry->lastAddr; 13511482Sandreas.sandberg@arm.com bool stride_match = (new_stride == entry->stride); 13611482Sandreas.sandberg@arm.com 13711482Sandreas.sandberg@arm.com // Adjust confidence for stride entry 13811482Sandreas.sandberg@arm.com if (stride_match && new_stride != 0) { 13911482Sandreas.sandberg@arm.com if (entry->confidence < maxConf) 14011482Sandreas.sandberg@arm.com entry->confidence++; 14111482Sandreas.sandberg@arm.com } else { 14211482Sandreas.sandberg@arm.com if (entry->confidence > minConf) 14311482Sandreas.sandberg@arm.com entry->confidence--; 14411482Sandreas.sandberg@arm.com // If confidence has dropped below the threshold, train new stride 14511482Sandreas.sandberg@arm.com if (entry->confidence < threshConf) 14611482Sandreas.sandberg@arm.com entry->stride = new_stride; 14711482Sandreas.sandberg@arm.com } 14811482Sandreas.sandberg@arm.com 14911482Sandreas.sandberg@arm.com DPRINTF(HWPrefetch, "Hit: PC %x pkt_addr %x (%s) stride %d (%s), " 15011482Sandreas.sandberg@arm.com "conf %d\n", pc, pkt_addr, is_secure ? "s" : "ns", new_stride, 15111482Sandreas.sandberg@arm.com stride_match ? "match" : "change", 15211482Sandreas.sandberg@arm.com entry->confidence); 15311482Sandreas.sandberg@arm.com 15411482Sandreas.sandberg@arm.com entry->lastAddr = pkt_addr; 15511482Sandreas.sandberg@arm.com 15611482Sandreas.sandberg@arm.com // Abort prefetch generation if below confidence threshold 15711482Sandreas.sandberg@arm.com if (entry->confidence < threshConf) 15811482Sandreas.sandberg@arm.com return; 15911482Sandreas.sandberg@arm.com 16011482Sandreas.sandberg@arm.com // Generate up to degree prefetches 16111482Sandreas.sandberg@arm.com for (int d = 1; d <= degree; d++) { 16211482Sandreas.sandberg@arm.com // Round strides up to atleast 1 cacheline 16311482Sandreas.sandberg@arm.com int prefetch_stride = new_stride; 16411482Sandreas.sandberg@arm.com if (abs(new_stride) < blkSize) { 16511482Sandreas.sandberg@arm.com prefetch_stride = (new_stride < 0) ? -blkSize : blkSize; 16611482Sandreas.sandberg@arm.com } 16711482Sandreas.sandberg@arm.com 16811482Sandreas.sandberg@arm.com Addr new_addr = pkt_addr + d * prefetch_stride; 16911482Sandreas.sandberg@arm.com if (samePage(pkt_addr, new_addr)) { 17011482Sandreas.sandberg@arm.com DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr); 17111482Sandreas.sandberg@arm.com addresses.push_back(AddrPriority(new_addr, 0)); 17211482Sandreas.sandberg@arm.com } else { 17311482Sandreas.sandberg@arm.com // Record the number of page crossing prefetches generated 17411482Sandreas.sandberg@arm.com pfSpanPage += degree - d + 1; 17511482Sandreas.sandberg@arm.com DPRINTF(HWPrefetch, "Ignoring page crossing prefetch.\n"); 17611482Sandreas.sandberg@arm.com return; 17711482Sandreas.sandberg@arm.com } 17811482Sandreas.sandberg@arm.com } 17911836SCurtis.Dunham@arm.com } else { 18012575Sgiacomo.travaglini@arm.com // Miss in table 18112575Sgiacomo.travaglini@arm.com DPRINTF(HWPrefetch, "Miss: PC %x pkt_addr %x (%s)\n", pc, pkt_addr, 18211836SCurtis.Dunham@arm.com is_secure ? "s" : "ns"); 18311836SCurtis.Dunham@arm.com 18411482Sandreas.sandberg@arm.com StrideEntry* entry = pcTable->findVictim(pc); 18511482Sandreas.sandberg@arm.com entry->instAddr = pc; 18611482Sandreas.sandberg@arm.com entry->lastAddr = pkt_addr; 18711482Sandreas.sandberg@arm.com entry->isSecure= is_secure; 18811482Sandreas.sandberg@arm.com entry->stride = 0; 18911482Sandreas.sandberg@arm.com entry->confidence = startConf; 19011482Sandreas.sandberg@arm.com } 19111482Sandreas.sandberg@arm.com} 19211482Sandreas.sandberg@arm.com 19311482Sandreas.sandberg@arm.cominline Addr 19411482Sandreas.sandberg@arm.comStridePrefetcher::PCTable::pcHash(Addr pc) const 19511482Sandreas.sandberg@arm.com{ 19611482Sandreas.sandberg@arm.com Addr hash1 = pc >> 1; 19711482Sandreas.sandberg@arm.com Addr hash2 = hash1 >> floorLog2(pcTableSets); 19811482Sandreas.sandberg@arm.com return (hash1 ^ hash2) & (Addr)(pcTableSets - 1); 19911482Sandreas.sandberg@arm.com} 20012575Sgiacomo.travaglini@arm.com 20111482Sandreas.sandberg@arm.cominline StridePrefetcher::StrideEntry* 20212575Sgiacomo.travaglini@arm.comStridePrefetcher::PCTable::findVictim(Addr pc) 20311482Sandreas.sandberg@arm.com{ 20411482Sandreas.sandberg@arm.com // Rand replacement for now 20511482Sandreas.sandberg@arm.com int set = pcHash(pc); 20611482Sandreas.sandberg@arm.com int way = random_mt.random<int>(0, pcTableAssoc - 1); 20711482Sandreas.sandberg@arm.com 20811482Sandreas.sandberg@arm.com DPRINTF(HWPrefetch, "Victimizing lookup table[%d][%d].\n", set, way); 20911482Sandreas.sandberg@arm.com return &entries[set][way]; 21011482Sandreas.sandberg@arm.com} 21111482Sandreas.sandberg@arm.com 21211482Sandreas.sandberg@arm.cominline StridePrefetcher::StrideEntry* 21311482Sandreas.sandberg@arm.comStridePrefetcher::PCTable::findEntry(Addr pc, bool is_secure) 21411482Sandreas.sandberg@arm.com{ 21511482Sandreas.sandberg@arm.com int set = pcHash(pc); 21611482Sandreas.sandberg@arm.com std::vector<StrideEntry>& set_entries = entries[set]; 21711482Sandreas.sandberg@arm.com for (int way = 0; way < pcTableAssoc; way++) { 21811482Sandreas.sandberg@arm.com StrideEntry* entry = &set_entries[way]; 21911482Sandreas.sandberg@arm.com // Search ways for match 22011482Sandreas.sandberg@arm.com if ((entry->instAddr == pc) && (entry->isSecure == is_secure)) { 22111482Sandreas.sandberg@arm.com DPRINTF(HWPrefetch, "Lookup hit table[%d][%d].\n", set, way); 22211482Sandreas.sandberg@arm.com return entry; 22311482Sandreas.sandberg@arm.com } 22411482Sandreas.sandberg@arm.com } 22511482Sandreas.sandberg@arm.com return nullptr; 22611482Sandreas.sandberg@arm.com} 22711482Sandreas.sandberg@arm.com 22811482Sandreas.sandberg@arm.comStridePrefetcher* 22911482Sandreas.sandberg@arm.comStridePrefetcherParams::create() 23011482Sandreas.sandberg@arm.com{ 23111482Sandreas.sandberg@arm.com return new StridePrefetcher(this); 23211482Sandreas.sandberg@arm.com} 23311482Sandreas.sandberg@arm.com