brrip_rp.hh revision 12684
12SN/A/** 21762SN/A * Copyright (c) 2018 Inria 32SN/A * All rights reserved. 42SN/A * 52SN/A * Redistribution and use in source and binary forms, with or without 62SN/A * modification, are permitted provided that the following conditions are 72SN/A * met: redistributions of source code must retain the above copyright 82SN/A * notice, this list of conditions and the following disclaimer; 92SN/A * redistributions in binary form must reproduce the above copyright 102SN/A * notice, this list of conditions and the following disclaimer in the 112SN/A * documentation and/or other materials provided with the distribution; 122SN/A * neither the name of the copyright holders nor the names of its 132SN/A * contributors may be used to endorse or promote products derived from 142SN/A * this software without specific prior written permission. 152SN/A * 162SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272665SN/A * 282665SN/A * Authors: Daniel Carvalho 292665SN/A */ 302665SN/A 312665SN/A/** 322SN/A * @file 332SN/A * Declaration of a Re-Reference Interval Prediction replacement policy. 341722SN/A * 355480Snate@binkert.org * Not-Recently Used (NRU) is an approximation of LRU that uses a single bit 362SN/A * to determine if an entry is going to be re-referenced in the near or distant 372SN/A * future. 38146SN/A * 392SN/A * Re-Reference Interval Prediction (RRIP) is an extension of NRU that uses a 402SN/A * re-reference prediction value to determine if entries are going to be re- 412158SN/A * used in the near future or not. 42146SN/A * 431805SN/A * The higher the value of the RRPV, the more distant the entry is from its 44146SN/A * next access. 451717SN/A * 462680SN/A * Bimodal Re-Reference Interval Prediction (BRRIP) is an extension of RRIP 475480Snate@binkert.org * that has a probability of not inserting entries as the LRU. This probability 482521SN/A * is controlled by the bimodal throtle parameter (btp). 4956SN/A * 505478SN/A * From the original paper, this implementation of RRIP is also called 513348SN/A * Static RRIP (SRRIP), as it always inserts entries with the same RRPV. 523348SN/A */ 532521SN/A 545480Snate@binkert.org#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__ 551805SN/A#define __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__ 562SN/A 572SN/A#include "mem/cache/replacement_policies/base.hh" 582107SN/A#include "params/BRRIPRP.hh" 592SN/A 605480Snate@binkert.orgclass BRRIPRP : public BaseReplacementPolicy 615478SN/A{ 624762SN/A protected: 632SN/A /** BRRIP-specific implementation of replacement data. */ 64545SN/A struct BRRIPReplData : ReplacementData 652521SN/A { 662521SN/A /** 672521SN/A * Re-Reference Interval Prediction Value. 682521SN/A * A value equal to max_RRPV + 1 indicates an invalid entry. 692SN/A */ 702SN/A int rrpv; 712SN/A 72926SN/A /** 73926SN/A * Default constructor. Invalidate data. 74926SN/A */ 75926SN/A BRRIPReplData(const int max_RRPV) : rrpv(max_RRPV + 1) {} 76926SN/A }; 77926SN/A 78926SN/A /** 794395SN/A * Maximum Re-Reference Prediction Value possible. An entry with this 801805SN/A * value as the rrpv has the longest possible re-reference interval, 812SN/A * that is, it is likely not to be used in the near future, and is 822SN/A * among the best eviction candidates. 831634SN/A * A maxRRPV of 1 implies in a NRU. 845480Snate@binkert.org */ 851634SN/A const int maxRRPV; 862549SN/A 871806SN/A /** 881634SN/A * The hit priority (HP) policy replaces entries that do not receive cache 891634SN/A * hits over any cache entry that receives a hit, while the frequency 901634SN/A * priority (FP) policy replaces infrequently re-referenced entries. 911634SN/A */ 921634SN/A const bool hitPriority; 932521SN/A 941634SN/A /** 951634SN/A * Bimodal throtle parameter. Value in the range [0,100] used to decide 962512SN/A * if a new entry is inserted with long or distant re-reference. 975480Snate@binkert.org */ 982SN/A const unsigned btp; 992SN/A 1002512SN/A public: 1012512SN/A /** Convenience typedef. */ 1022512SN/A typedef BRRIPRPParams Params; 1032512SN/A 104540SN/A /** 1052641SN/A * Construct and initiliaze this replacement policy. 1062522SN/A */ 1072641SN/A BRRIPRP(const Params *p); 1082512SN/A 1092630SN/A /** 1104986SN/A * Destructor. 1112521SN/A */ 1122641SN/A ~BRRIPRP() {} 113873SN/A 114873SN/A /** 115873SN/A * Invalidate replacement data to set it as the next probable victim. 116873SN/A * Set RRPV as the the most distant re-reference. 117873SN/A * 1182630SN/A * @param replacement_data Replacement data to be invalidated. 119873SN/A */ 120873SN/A void invalidate(const std::shared_ptr<ReplacementData>& replacement_data) 1212630SN/A const override; 122873SN/A 123873SN/A /** 1242630SN/A * Touch an entry to update its replacement data. 125873SN/A * 126873SN/A * @param replacement_data Replacement data to be touched. 1272630SN/A */ 128873SN/A void touch(const std::shared_ptr<ReplacementData>& replacement_data) const 129873SN/A override; 1302512SN/A 1312512SN/A /** 1322512SN/A * Reset replacement data. Used when an entry is inserted. 1334870SN/A * Set RRPV according to the insertion policy used. 134873SN/A * 1355480Snate@binkert.org * @param replacement_data Replacement data to be reset. 1362630SN/A */ 137873SN/A void reset(const std::shared_ptr<ReplacementData>& replacement_data) const 138873SN/A override; 139873SN/A 140873SN/A /** 141873SN/A * Find replacement victim using rrpv. 1425478SN/A * 143873SN/A * @param cands Replacement candidates, selected by indexing policy. 144873SN/A * @return Replacement entry to be replaced. 1452630SN/A */ 146873SN/A ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const 147873SN/A override; 1482630SN/A 149873SN/A /** 150873SN/A * Instantiate a replacement data entry. 1512630SN/A * 152873SN/A * @return A shared pointer to the new replacement data. 153873SN/A */ 1542630SN/A std::shared_ptr<ReplacementData> instantiateEntry() override; 155873SN/A}; 156873SN/A 1572630SN/A#endif // __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__ 158873SN/A