bop.cc revision 13717
113717Sivan.pizarro@metempsy.com/** 213717Sivan.pizarro@metempsy.com * Copyright (c) 2018 Metempsy Technology Consulting 313717Sivan.pizarro@metempsy.com * All rights reserved. 413717Sivan.pizarro@metempsy.com * 513717Sivan.pizarro@metempsy.com * Redistribution and use in source and binary forms, with or without 613717Sivan.pizarro@metempsy.com * modification, are permitted provided that the following conditions are 713717Sivan.pizarro@metempsy.com * met: redistributions of source code must retain the above copyright 813717Sivan.pizarro@metempsy.com * notice, this list of conditions and the following disclaimer; 913717Sivan.pizarro@metempsy.com * redistributions in binary form must reproduce the above copyright 1013717Sivan.pizarro@metempsy.com * notice, this list of conditions and the following disclaimer in the 1113717Sivan.pizarro@metempsy.com * documentation and/or other materials provided with the distribution; 1213717Sivan.pizarro@metempsy.com * neither the name of the copyright holders nor the names of its 1313717Sivan.pizarro@metempsy.com * contributors may be used to endorse or promote products derived from 1413717Sivan.pizarro@metempsy.com * this software without specific prior written permission. 1513717Sivan.pizarro@metempsy.com * 1613717Sivan.pizarro@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713717Sivan.pizarro@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813717Sivan.pizarro@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913717Sivan.pizarro@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013717Sivan.pizarro@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113717Sivan.pizarro@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213717Sivan.pizarro@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313717Sivan.pizarro@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413717Sivan.pizarro@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513717Sivan.pizarro@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613717Sivan.pizarro@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713717Sivan.pizarro@metempsy.com * 2813717Sivan.pizarro@metempsy.com * Authors: Ivan Pizarro 2913717Sivan.pizarro@metempsy.com */ 3013717Sivan.pizarro@metempsy.com 3113717Sivan.pizarro@metempsy.com#include "mem/cache/prefetch/bop.hh" 3213717Sivan.pizarro@metempsy.com 3313717Sivan.pizarro@metempsy.com#include "debug/HWPrefetch.hh" 3413717Sivan.pizarro@metempsy.com#include "params/BOPPrefetcher.hh" 3513717Sivan.pizarro@metempsy.com 3613717Sivan.pizarro@metempsy.comBOPPrefetcher::BOPPrefetcher(const BOPPrefetcherParams *p) 3713717Sivan.pizarro@metempsy.com : QueuedPrefetcher(p), 3813717Sivan.pizarro@metempsy.com scoreMax(p->score_max), roundMax(p->round_max), 3913717Sivan.pizarro@metempsy.com badScore(p->bad_score), rrEntries(p->rr_size), 4013717Sivan.pizarro@metempsy.com tagMask((1 << p->tag_bits) - 1), 4113717Sivan.pizarro@metempsy.com delayQueueEnabled(p->delay_queue_enable), 4213717Sivan.pizarro@metempsy.com delayQueueSize(p->delay_queue_size), 4313717Sivan.pizarro@metempsy.com delayTicks(cyclesToTicks(p->delay_queue_cycles)), 4413717Sivan.pizarro@metempsy.com delayQueueEvent([this]{ delayQueueEventWrapper(); }, name()), 4513717Sivan.pizarro@metempsy.com issuePrefetchRequests(false), bestOffset(1), phaseBestOffset(0), 4613717Sivan.pizarro@metempsy.com bestScore(0), round(0) 4713717Sivan.pizarro@metempsy.com{ 4813717Sivan.pizarro@metempsy.com if (!isPowerOf2(rrEntries)) { 4913717Sivan.pizarro@metempsy.com fatal("%s: number of RR entries is not power of 2\n", name()); 5013717Sivan.pizarro@metempsy.com } 5113717Sivan.pizarro@metempsy.com if (!isPowerOf2(blkSize)) { 5213717Sivan.pizarro@metempsy.com fatal("%s: cache line size is not power of 2\n", name()); 5313717Sivan.pizarro@metempsy.com } 5413717Sivan.pizarro@metempsy.com if (!(p->negative_offsets_enable && (p->offset_list_size % 2 == 0))) { 5513717Sivan.pizarro@metempsy.com fatal("%s: negative offsets enabled with odd offset list size\n", 5613717Sivan.pizarro@metempsy.com name()); 5713717Sivan.pizarro@metempsy.com } 5813717Sivan.pizarro@metempsy.com 5913717Sivan.pizarro@metempsy.com rrLeft.resize(rrEntries); 6013717Sivan.pizarro@metempsy.com rrRight.resize(rrEntries); 6113717Sivan.pizarro@metempsy.com 6213717Sivan.pizarro@metempsy.com // Following the paper implementation, a list with the specified number 6313717Sivan.pizarro@metempsy.com // of offsets which are of the form 2^i * 3^j * 5^k with i,j,k >= 0 6413717Sivan.pizarro@metempsy.com const int factors[] = { 2, 3, 5 }; 6513717Sivan.pizarro@metempsy.com unsigned int i = 0; 6613717Sivan.pizarro@metempsy.com int64_t offset_i = 1; 6713717Sivan.pizarro@metempsy.com 6813717Sivan.pizarro@metempsy.com while (i < p->offset_list_size) 6913717Sivan.pizarro@metempsy.com { 7013717Sivan.pizarro@metempsy.com int64_t offset = offset_i; 7113717Sivan.pizarro@metempsy.com 7213717Sivan.pizarro@metempsy.com for (int n : factors) { 7313717Sivan.pizarro@metempsy.com while ((offset % n) == 0) { 7413717Sivan.pizarro@metempsy.com offset /= n; 7513717Sivan.pizarro@metempsy.com } 7613717Sivan.pizarro@metempsy.com } 7713717Sivan.pizarro@metempsy.com 7813717Sivan.pizarro@metempsy.com if (offset == 1) { 7913717Sivan.pizarro@metempsy.com offsetsList.push_back(OffsetListEntry(offset_i, 0)); 8013717Sivan.pizarro@metempsy.com i++; 8113717Sivan.pizarro@metempsy.com // If we want to use negative offsets, add also the negative value 8213717Sivan.pizarro@metempsy.com // of the offset just calculated 8313717Sivan.pizarro@metempsy.com if (p->negative_offsets_enable) { 8413717Sivan.pizarro@metempsy.com offsetsList.push_back(OffsetListEntry(-offset_i, 0)); 8513717Sivan.pizarro@metempsy.com i++; 8613717Sivan.pizarro@metempsy.com } 8713717Sivan.pizarro@metempsy.com } 8813717Sivan.pizarro@metempsy.com 8913717Sivan.pizarro@metempsy.com offset_i++; 9013717Sivan.pizarro@metempsy.com } 9113717Sivan.pizarro@metempsy.com 9213717Sivan.pizarro@metempsy.com offsetsListIterator = offsetsList.begin(); 9313717Sivan.pizarro@metempsy.com} 9413717Sivan.pizarro@metempsy.com 9513717Sivan.pizarro@metempsy.comvoid 9613717Sivan.pizarro@metempsy.comBOPPrefetcher::delayQueueEventWrapper() 9713717Sivan.pizarro@metempsy.com{ 9813717Sivan.pizarro@metempsy.com while (!delayQueue.empty() && 9913717Sivan.pizarro@metempsy.com delayQueue.front().processTick <= curTick()) 10013717Sivan.pizarro@metempsy.com { 10113717Sivan.pizarro@metempsy.com Addr addr_x = delayQueue.front().baseAddr; 10213717Sivan.pizarro@metempsy.com insertIntoRR(addr_x, RRWay::Left); 10313717Sivan.pizarro@metempsy.com delayQueue.pop_front(); 10413717Sivan.pizarro@metempsy.com } 10513717Sivan.pizarro@metempsy.com 10613717Sivan.pizarro@metempsy.com // Schedule an event for the next element if there is one 10713717Sivan.pizarro@metempsy.com if (!delayQueue.empty()) { 10813717Sivan.pizarro@metempsy.com schedule(delayQueueEvent, delayQueue.front().processTick); 10913717Sivan.pizarro@metempsy.com } 11013717Sivan.pizarro@metempsy.com} 11113717Sivan.pizarro@metempsy.com 11213717Sivan.pizarro@metempsy.comunsigned int 11313717Sivan.pizarro@metempsy.comBOPPrefetcher::hash(Addr addr, unsigned int way) const 11413717Sivan.pizarro@metempsy.com{ 11513717Sivan.pizarro@metempsy.com Addr hash1 = addr >> way; 11613717Sivan.pizarro@metempsy.com Addr hash2 = hash1 >> floorLog2(rrEntries); 11713717Sivan.pizarro@metempsy.com return (hash1 ^ hash2) & (Addr)(rrEntries - 1); 11813717Sivan.pizarro@metempsy.com} 11913717Sivan.pizarro@metempsy.com 12013717Sivan.pizarro@metempsy.comvoid 12113717Sivan.pizarro@metempsy.comBOPPrefetcher::insertIntoRR(Addr addr, unsigned int way) 12213717Sivan.pizarro@metempsy.com{ 12313717Sivan.pizarro@metempsy.com switch (way) { 12413717Sivan.pizarro@metempsy.com case RRWay::Left: 12513717Sivan.pizarro@metempsy.com rrLeft[hash(addr, RRWay::Left)] = addr; 12613717Sivan.pizarro@metempsy.com break; 12713717Sivan.pizarro@metempsy.com case RRWay::Right: 12813717Sivan.pizarro@metempsy.com rrRight[hash(addr, RRWay::Right)] = addr; 12913717Sivan.pizarro@metempsy.com break; 13013717Sivan.pizarro@metempsy.com } 13113717Sivan.pizarro@metempsy.com} 13213717Sivan.pizarro@metempsy.com 13313717Sivan.pizarro@metempsy.comvoid 13413717Sivan.pizarro@metempsy.comBOPPrefetcher::insertIntoDelayQueue(Addr x) 13513717Sivan.pizarro@metempsy.com{ 13613717Sivan.pizarro@metempsy.com if (delayQueue.size() == delayQueueSize) { 13713717Sivan.pizarro@metempsy.com return; 13813717Sivan.pizarro@metempsy.com } 13913717Sivan.pizarro@metempsy.com 14013717Sivan.pizarro@metempsy.com // Add the address to the delay queue and schedule an event to process 14113717Sivan.pizarro@metempsy.com // it after the specified delay cycles 14213717Sivan.pizarro@metempsy.com Tick process_tick = curTick() + delayTicks; 14313717Sivan.pizarro@metempsy.com 14413717Sivan.pizarro@metempsy.com delayQueue.push_back(DelayQueueEntry(x, process_tick)); 14513717Sivan.pizarro@metempsy.com 14613717Sivan.pizarro@metempsy.com if (!delayQueueEvent.scheduled()) { 14713717Sivan.pizarro@metempsy.com schedule(delayQueueEvent, process_tick); 14813717Sivan.pizarro@metempsy.com } 14913717Sivan.pizarro@metempsy.com} 15013717Sivan.pizarro@metempsy.com 15113717Sivan.pizarro@metempsy.comvoid 15213717Sivan.pizarro@metempsy.comBOPPrefetcher::resetScores() 15313717Sivan.pizarro@metempsy.com{ 15413717Sivan.pizarro@metempsy.com for (auto& it : offsetsList) { 15513717Sivan.pizarro@metempsy.com it.second = 0; 15613717Sivan.pizarro@metempsy.com } 15713717Sivan.pizarro@metempsy.com} 15813717Sivan.pizarro@metempsy.com 15913717Sivan.pizarro@metempsy.cominline Addr 16013717Sivan.pizarro@metempsy.comBOPPrefetcher::tag(Addr addr) const 16113717Sivan.pizarro@metempsy.com{ 16213717Sivan.pizarro@metempsy.com return (addr >> blkSize) & tagMask; 16313717Sivan.pizarro@metempsy.com} 16413717Sivan.pizarro@metempsy.com 16513717Sivan.pizarro@metempsy.combool 16613717Sivan.pizarro@metempsy.comBOPPrefetcher::testRR(Addr addr) const 16713717Sivan.pizarro@metempsy.com{ 16813717Sivan.pizarro@metempsy.com for (auto& it : rrLeft) { 16913717Sivan.pizarro@metempsy.com if (it == addr) { 17013717Sivan.pizarro@metempsy.com return true; 17113717Sivan.pizarro@metempsy.com } 17213717Sivan.pizarro@metempsy.com } 17313717Sivan.pizarro@metempsy.com 17413717Sivan.pizarro@metempsy.com for (auto& it : rrRight) { 17513717Sivan.pizarro@metempsy.com if (it == addr) { 17613717Sivan.pizarro@metempsy.com return true; 17713717Sivan.pizarro@metempsy.com } 17813717Sivan.pizarro@metempsy.com } 17913717Sivan.pizarro@metempsy.com 18013717Sivan.pizarro@metempsy.com return false; 18113717Sivan.pizarro@metempsy.com} 18213717Sivan.pizarro@metempsy.com 18313717Sivan.pizarro@metempsy.comvoid 18413717Sivan.pizarro@metempsy.comBOPPrefetcher::bestOffsetLearning(Addr x) 18513717Sivan.pizarro@metempsy.com{ 18613717Sivan.pizarro@metempsy.com Addr offset_addr = (*offsetsListIterator).first; 18713717Sivan.pizarro@metempsy.com Addr lookup_addr = x - offset_addr; 18813717Sivan.pizarro@metempsy.com 18913717Sivan.pizarro@metempsy.com // There was a hit in the RR table, increment the score for this offset 19013717Sivan.pizarro@metempsy.com if (testRR(lookup_addr)) { 19113717Sivan.pizarro@metempsy.com DPRINTF(HWPrefetch, "Address %#lx found in the RR table\n", x); 19213717Sivan.pizarro@metempsy.com (*offsetsListIterator).second++; 19313717Sivan.pizarro@metempsy.com if ((*offsetsListIterator).second > bestScore) { 19413717Sivan.pizarro@metempsy.com bestScore = (*offsetsListIterator).second; 19513717Sivan.pizarro@metempsy.com phaseBestOffset = (*offsetsListIterator).first; 19613717Sivan.pizarro@metempsy.com DPRINTF(HWPrefetch, "New best score is %lu\n", bestScore); 19713717Sivan.pizarro@metempsy.com } 19813717Sivan.pizarro@metempsy.com } 19913717Sivan.pizarro@metempsy.com 20013717Sivan.pizarro@metempsy.com offsetsListIterator++; 20113717Sivan.pizarro@metempsy.com 20213717Sivan.pizarro@metempsy.com // All the offsets in the list were visited meaning that a learning 20313717Sivan.pizarro@metempsy.com // phase finished. Check if 20413717Sivan.pizarro@metempsy.com if (offsetsListIterator == offsetsList.end()) { 20513717Sivan.pizarro@metempsy.com offsetsListIterator = offsetsList.begin(); 20613717Sivan.pizarro@metempsy.com round++; 20713717Sivan.pizarro@metempsy.com 20813717Sivan.pizarro@metempsy.com // Check if the best offset must be updated if: 20913717Sivan.pizarro@metempsy.com // (1) One of the scores equals SCORE_MAX 21013717Sivan.pizarro@metempsy.com // (2) The number of rounds equals ROUND_MAX 21113717Sivan.pizarro@metempsy.com if ((bestScore >= scoreMax) || (round == roundMax)) { 21213717Sivan.pizarro@metempsy.com bestOffset = phaseBestOffset; 21313717Sivan.pizarro@metempsy.com round = 0; 21413717Sivan.pizarro@metempsy.com bestScore = 0; 21513717Sivan.pizarro@metempsy.com phaseBestOffset = 0; 21613717Sivan.pizarro@metempsy.com resetScores(); 21713717Sivan.pizarro@metempsy.com issuePrefetchRequests = true; 21813717Sivan.pizarro@metempsy.com } else if (phaseBestOffset <= badScore) { 21913717Sivan.pizarro@metempsy.com issuePrefetchRequests = false; 22013717Sivan.pizarro@metempsy.com } 22113717Sivan.pizarro@metempsy.com } 22213717Sivan.pizarro@metempsy.com} 22313717Sivan.pizarro@metempsy.com 22413717Sivan.pizarro@metempsy.comvoid 22513717Sivan.pizarro@metempsy.comBOPPrefetcher::calculatePrefetch(const PrefetchInfo &pfi, 22613717Sivan.pizarro@metempsy.com std::vector<AddrPriority> &addresses) 22713717Sivan.pizarro@metempsy.com{ 22813717Sivan.pizarro@metempsy.com Addr addr = pfi.getAddr(); 22913717Sivan.pizarro@metempsy.com Addr tag_x = tag(addr); 23013717Sivan.pizarro@metempsy.com 23113717Sivan.pizarro@metempsy.com if (delayQueueEnabled) { 23213717Sivan.pizarro@metempsy.com insertIntoDelayQueue(tag_x); 23313717Sivan.pizarro@metempsy.com } else { 23413717Sivan.pizarro@metempsy.com insertIntoRR(tag_x, RRWay::Left); 23513717Sivan.pizarro@metempsy.com } 23613717Sivan.pizarro@metempsy.com 23713717Sivan.pizarro@metempsy.com // Go through the nth offset and update the score, the best score and the 23813717Sivan.pizarro@metempsy.com // current best offset if a better one is found 23913717Sivan.pizarro@metempsy.com bestOffsetLearning(tag_x); 24013717Sivan.pizarro@metempsy.com 24113717Sivan.pizarro@metempsy.com // This prefetcher is a degree 1 prefetch, so it will only generate one 24213717Sivan.pizarro@metempsy.com // prefetch at most per access 24313717Sivan.pizarro@metempsy.com if (issuePrefetchRequests) { 24413717Sivan.pizarro@metempsy.com Addr prefetch_addr = addr + (bestOffset << lBlkSize); 24513717Sivan.pizarro@metempsy.com addresses.push_back(AddrPriority(prefetch_addr, 0)); 24613717Sivan.pizarro@metempsy.com DPRINTF(HWPrefetch, "Generated prefetch %#lx\n", prefetch_addr); 24713717Sivan.pizarro@metempsy.com } 24813717Sivan.pizarro@metempsy.com} 24913717Sivan.pizarro@metempsy.com 25013717Sivan.pizarro@metempsy.comvoid 25113717Sivan.pizarro@metempsy.comBOPPrefetcher::notifyFill(const PacketPtr& pkt) 25213717Sivan.pizarro@metempsy.com{ 25313717Sivan.pizarro@metempsy.com // Only insert into the RR right way if it's the pkt is a HWP 25413717Sivan.pizarro@metempsy.com if (!pkt->cmd.isHWPrefetch()) return; 25513717Sivan.pizarro@metempsy.com 25613717Sivan.pizarro@metempsy.com Addr tag_y = tag(pkt->getAddr()); 25713717Sivan.pizarro@metempsy.com 25813717Sivan.pizarro@metempsy.com if (issuePrefetchRequests) { 25913717Sivan.pizarro@metempsy.com insertIntoRR(tag_y - bestOffset, RRWay::Right); 26013717Sivan.pizarro@metempsy.com } 26113717Sivan.pizarro@metempsy.com} 26213717Sivan.pizarro@metempsy.com 26313717Sivan.pizarro@metempsy.comBOPPrefetcher* 26413717Sivan.pizarro@metempsy.comBOPPrefetcherParams::create() 26513717Sivan.pizarro@metempsy.com{ 26613717Sivan.pizarro@metempsy.com return new BOPPrefetcher(this); 26713717Sivan.pizarro@metempsy.com} 268