bop.hh 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/** 3213717Sivan.pizarro@metempsy.com * Implementation of the 'A Best-Offset Prefetcher' 3313717Sivan.pizarro@metempsy.com * Reference: 3413717Sivan.pizarro@metempsy.com * Michaud, P. (2015, June). A best-offset prefetcher. 3513717Sivan.pizarro@metempsy.com * In 2nd Data Prefetching Championship. 3613717Sivan.pizarro@metempsy.com */ 3713717Sivan.pizarro@metempsy.com 3813717Sivan.pizarro@metempsy.com#ifndef __MEM_CACHE_PREFETCH_BOP_HH__ 3913717Sivan.pizarro@metempsy.com#define __MEM_CACHE_PREFETCH_BOP_HH__ 4013717Sivan.pizarro@metempsy.com 4113717Sivan.pizarro@metempsy.com#include <queue> 4213717Sivan.pizarro@metempsy.com 4313717Sivan.pizarro@metempsy.com#include "mem/cache/prefetch/queued.hh" 4413717Sivan.pizarro@metempsy.com#include "mem/packet.hh" 4513717Sivan.pizarro@metempsy.com 4613717Sivan.pizarro@metempsy.comstruct BOPPrefetcherParams; 4713717Sivan.pizarro@metempsy.com 4813717Sivan.pizarro@metempsy.comclass BOPPrefetcher : public QueuedPrefetcher 4913717Sivan.pizarro@metempsy.com{ 5013717Sivan.pizarro@metempsy.com private: 5113717Sivan.pizarro@metempsy.com 5213717Sivan.pizarro@metempsy.com enum RRWay { 5313717Sivan.pizarro@metempsy.com Left, 5413717Sivan.pizarro@metempsy.com Right 5513717Sivan.pizarro@metempsy.com }; 5613717Sivan.pizarro@metempsy.com 5713717Sivan.pizarro@metempsy.com /** Learning phase parameters */ 5813717Sivan.pizarro@metempsy.com const unsigned int scoreMax; 5913717Sivan.pizarro@metempsy.com const unsigned int roundMax; 6013717Sivan.pizarro@metempsy.com const unsigned int badScore; 6113717Sivan.pizarro@metempsy.com /** Recent requests table parameteres */ 6213717Sivan.pizarro@metempsy.com const unsigned int rrEntries; 6313717Sivan.pizarro@metempsy.com const unsigned int tagMask; 6413717Sivan.pizarro@metempsy.com /** Delay queue parameters */ 6513717Sivan.pizarro@metempsy.com const bool delayQueueEnabled; 6613717Sivan.pizarro@metempsy.com const unsigned int delayQueueSize; 6713717Sivan.pizarro@metempsy.com const unsigned int delayTicks; 6813717Sivan.pizarro@metempsy.com 6913717Sivan.pizarro@metempsy.com std::vector<Addr> rrLeft; 7013717Sivan.pizarro@metempsy.com std::vector<Addr> rrRight; 7113717Sivan.pizarro@metempsy.com 7213717Sivan.pizarro@metempsy.com /** Structure to save the offset and the score */ 7313717Sivan.pizarro@metempsy.com typedef std::pair<int16_t, uint8_t> OffsetListEntry; 7413717Sivan.pizarro@metempsy.com std::vector<OffsetListEntry> offsetsList; 7513717Sivan.pizarro@metempsy.com 7613717Sivan.pizarro@metempsy.com /** In a first implementation of the BO prefetcher, both banks of the 7713717Sivan.pizarro@metempsy.com * RR were written simultaneously when a prefetched line is inserted 7813717Sivan.pizarro@metempsy.com * into the cache. Adding the delay queue tries to avoid always 7913717Sivan.pizarro@metempsy.com * striving for timeless prefetches, which has been found to not 8013717Sivan.pizarro@metempsy.com * always being optimal. 8113717Sivan.pizarro@metempsy.com */ 8213717Sivan.pizarro@metempsy.com struct DelayQueueEntry 8313717Sivan.pizarro@metempsy.com { 8413717Sivan.pizarro@metempsy.com Addr baseAddr; 8513717Sivan.pizarro@metempsy.com Tick processTick; 8613717Sivan.pizarro@metempsy.com 8713717Sivan.pizarro@metempsy.com DelayQueueEntry(Addr x, Tick t) : baseAddr(x), processTick(t) 8813717Sivan.pizarro@metempsy.com {} 8913717Sivan.pizarro@metempsy.com }; 9013717Sivan.pizarro@metempsy.com 9113717Sivan.pizarro@metempsy.com std::deque<DelayQueueEntry> delayQueue; 9213717Sivan.pizarro@metempsy.com 9313717Sivan.pizarro@metempsy.com /** Event to handle the delay queue processing */ 9413717Sivan.pizarro@metempsy.com void delayQueueEventWrapper(); 9513717Sivan.pizarro@metempsy.com EventFunctionWrapper delayQueueEvent; 9613717Sivan.pizarro@metempsy.com 9713717Sivan.pizarro@metempsy.com /** Hardware prefetcher enabled */ 9813717Sivan.pizarro@metempsy.com bool issuePrefetchRequests; 9913717Sivan.pizarro@metempsy.com /** Current best offset to issue prefetches */ 10013717Sivan.pizarro@metempsy.com Addr bestOffset; 10113717Sivan.pizarro@metempsy.com /** Current best offset found in the learning phase */ 10213717Sivan.pizarro@metempsy.com Addr phaseBestOffset; 10313717Sivan.pizarro@metempsy.com /** Current test offset index */ 10413717Sivan.pizarro@metempsy.com std::vector<OffsetListEntry>::iterator offsetsListIterator; 10513717Sivan.pizarro@metempsy.com /** Max score found so far */ 10613717Sivan.pizarro@metempsy.com unsigned int bestScore; 10713717Sivan.pizarro@metempsy.com /** Current round */ 10813717Sivan.pizarro@metempsy.com unsigned int round; 10913717Sivan.pizarro@metempsy.com 11013717Sivan.pizarro@metempsy.com /** Generate a hash for the specified address to index the RR table 11113717Sivan.pizarro@metempsy.com * @param addr: address to hash 11213717Sivan.pizarro@metempsy.com * @param way: RR table to which is addressed (left/right) 11313717Sivan.pizarro@metempsy.com */ 11413717Sivan.pizarro@metempsy.com unsigned int hash(Addr addr, unsigned int way) const; 11513717Sivan.pizarro@metempsy.com 11613717Sivan.pizarro@metempsy.com /** Insert the specified address into the RR table 11713717Sivan.pizarro@metempsy.com * @param addr: address to insert 11813717Sivan.pizarro@metempsy.com * @param way: RR table to which the address will be inserted 11913717Sivan.pizarro@metempsy.com */ 12013717Sivan.pizarro@metempsy.com void insertIntoRR(Addr addr, unsigned int way); 12113717Sivan.pizarro@metempsy.com 12213717Sivan.pizarro@metempsy.com /** Insert the specified address into the delay queue. This will 12313717Sivan.pizarro@metempsy.com * trigger an event after the delay cycles pass 12413717Sivan.pizarro@metempsy.com * @param addr: address to insert into the delay queue 12513717Sivan.pizarro@metempsy.com */ 12613717Sivan.pizarro@metempsy.com void insertIntoDelayQueue(Addr addr); 12713717Sivan.pizarro@metempsy.com 12813717Sivan.pizarro@metempsy.com /** Reset all the scores from the offset list */ 12913717Sivan.pizarro@metempsy.com void resetScores(); 13013717Sivan.pizarro@metempsy.com 13113717Sivan.pizarro@metempsy.com /** Generate the tag for the specified address based on the tag bits 13213717Sivan.pizarro@metempsy.com * and the block size 13313717Sivan.pizarro@metempsy.com * @param addr: address to get the tag from 13413717Sivan.pizarro@metempsy.com */ 13513717Sivan.pizarro@metempsy.com Addr tag(Addr addr) const; 13613717Sivan.pizarro@metempsy.com 13713717Sivan.pizarro@metempsy.com /** Test if @X-O is hitting in the RR table to update the 13813717Sivan.pizarro@metempsy.com offset score */ 13913717Sivan.pizarro@metempsy.com bool testRR(Addr) const; 14013717Sivan.pizarro@metempsy.com 14113717Sivan.pizarro@metempsy.com /** Learning phase of the BOP. Update the intermediate values of the 14213717Sivan.pizarro@metempsy.com round and update the best offset if found */ 14313717Sivan.pizarro@metempsy.com void bestOffsetLearning(Addr); 14413717Sivan.pizarro@metempsy.com 14513717Sivan.pizarro@metempsy.com /** Update the RR right table after a prefetch fill */ 14613717Sivan.pizarro@metempsy.com void notifyFill(const PacketPtr& pkt) override; 14713717Sivan.pizarro@metempsy.com 14813717Sivan.pizarro@metempsy.com public: 14913717Sivan.pizarro@metempsy.com 15013717Sivan.pizarro@metempsy.com BOPPrefetcher(const BOPPrefetcherParams *p); 15113717Sivan.pizarro@metempsy.com ~BOPPrefetcher() {} 15213717Sivan.pizarro@metempsy.com 15313717Sivan.pizarro@metempsy.com void calculatePrefetch(const PrefetchInfo &pfi, 15413717Sivan.pizarro@metempsy.com std::vector<AddrPriority> &addresses); 15513717Sivan.pizarro@metempsy.com}; 15613717Sivan.pizarro@metempsy.com 15713717Sivan.pizarro@metempsy.com#endif /* __MEM_CACHE_PREFETCH_BOP_HH__ */ 158