brrip_rp.hh revision 12727:56c23b54bcb1
113531Sjairo.balart@metempsy.com/** 214227Sgiacomo.travaglini@arm.com * Copyright (c) 2018 Inria 314227Sgiacomo.travaglini@arm.com * All rights reserved. 414227Sgiacomo.travaglini@arm.com * 514227Sgiacomo.travaglini@arm.com * Redistribution and use in source and binary forms, with or without 614227Sgiacomo.travaglini@arm.com * modification, are permitted provided that the following conditions are 714227Sgiacomo.travaglini@arm.com * met: redistributions of source code must retain the above copyright 814227Sgiacomo.travaglini@arm.com * notice, this list of conditions and the following disclaimer; 914227Sgiacomo.travaglini@arm.com * redistributions in binary form must reproduce the above copyright 1014227Sgiacomo.travaglini@arm.com * notice, this list of conditions and the following disclaimer in the 1114227Sgiacomo.travaglini@arm.com * documentation and/or other materials provided with the distribution; 1214227Sgiacomo.travaglini@arm.com * neither the name of the copyright holders nor the names of its 1314227Sgiacomo.travaglini@arm.com * contributors may be used to endorse or promote products derived from 1413531Sjairo.balart@metempsy.com * this software without specific prior written permission. 1513531Sjairo.balart@metempsy.com * 1613531Sjairo.balart@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713531Sjairo.balart@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813531Sjairo.balart@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913531Sjairo.balart@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013531Sjairo.balart@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113531Sjairo.balart@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213531Sjairo.balart@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313531Sjairo.balart@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413531Sjairo.balart@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513531Sjairo.balart@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613531Sjairo.balart@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713531Sjairo.balart@metempsy.com * 2813531Sjairo.balart@metempsy.com * Authors: Daniel Carvalho 2913531Sjairo.balart@metempsy.com */ 3013531Sjairo.balart@metempsy.com 3113531Sjairo.balart@metempsy.com/** 3213531Sjairo.balart@metempsy.com * @file 3313531Sjairo.balart@metempsy.com * Declaration of a Re-Reference Interval Prediction replacement policy. 3413531Sjairo.balart@metempsy.com * 3513531Sjairo.balart@metempsy.com * Not-Recently Used (NRU) is an approximation of LRU that uses a single bit 3613531Sjairo.balart@metempsy.com * to determine if an entry is going to be re-referenced in the near or distant 3713531Sjairo.balart@metempsy.com * future. 3813531Sjairo.balart@metempsy.com * 3913531Sjairo.balart@metempsy.com * Re-Reference Interval Prediction (RRIP) is an extension of NRU that uses a 4013531Sjairo.balart@metempsy.com * re-reference prediction value to determine if entries are going to be re- 4113531Sjairo.balart@metempsy.com * used in the near future or not. 4213531Sjairo.balart@metempsy.com * 4313531Sjairo.balart@metempsy.com * The higher the value of the RRPV, the more distant the entry is from its 4413531Sjairo.balart@metempsy.com * next access. 4513531Sjairo.balart@metempsy.com * 4613531Sjairo.balart@metempsy.com * Bimodal Re-Reference Interval Prediction (BRRIP) is an extension of RRIP 4713531Sjairo.balart@metempsy.com * that has a probability of not inserting entries as the LRU. This probability 4813531Sjairo.balart@metempsy.com * is controlled by the bimodal throtle parameter (btp). 4913531Sjairo.balart@metempsy.com * 5013531Sjairo.balart@metempsy.com * From the original paper, this implementation of RRIP is also called 5113926Sgiacomo.travaglini@arm.com * Static RRIP (SRRIP), as it always inserts entries with the same RRPV. 5213926Sgiacomo.travaglini@arm.com */ 5313926Sgiacomo.travaglini@arm.com 5413531Sjairo.balart@metempsy.com#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__ 5513531Sjairo.balart@metempsy.com#define __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__ 5613531Sjairo.balart@metempsy.com 5713531Sjairo.balart@metempsy.com#include "mem/cache/replacement_policies/base.hh" 5813531Sjairo.balart@metempsy.com 5913531Sjairo.balart@metempsy.comstruct BRRIPRPParams; 6013531Sjairo.balart@metempsy.com 6113531Sjairo.balart@metempsy.comclass BRRIPRP : public BaseReplacementPolicy 6213531Sjairo.balart@metempsy.com{ 6313531Sjairo.balart@metempsy.com protected: 6413531Sjairo.balart@metempsy.com /** BRRIP-specific implementation of replacement data. */ 6513531Sjairo.balart@metempsy.com struct BRRIPReplData : ReplacementData 6613531Sjairo.balart@metempsy.com { 6713531Sjairo.balart@metempsy.com /** 6813531Sjairo.balart@metempsy.com * Re-Reference Interval Prediction Value. 6913531Sjairo.balart@metempsy.com * A value equal to max_RRPV + 1 indicates an invalid entry. 7013531Sjairo.balart@metempsy.com */ 7113531Sjairo.balart@metempsy.com int rrpv; 7213531Sjairo.balart@metempsy.com 7313531Sjairo.balart@metempsy.com /** 7413531Sjairo.balart@metempsy.com * Default constructor. Invalidate data. 7513531Sjairo.balart@metempsy.com */ 7613531Sjairo.balart@metempsy.com BRRIPReplData(const int max_RRPV) : rrpv(max_RRPV + 1) {} 7713531Sjairo.balart@metempsy.com }; 7813531Sjairo.balart@metempsy.com 7913531Sjairo.balart@metempsy.com /** 8013531Sjairo.balart@metempsy.com * Maximum Re-Reference Prediction Value possible. An entry with this 8113531Sjairo.balart@metempsy.com * value as the rrpv has the longest possible re-reference interval, 8213826Sgiacomo.travaglini@arm.com * that is, it is likely not to be used in the near future, and is 8313826Sgiacomo.travaglini@arm.com * among the best eviction candidates. 8413826Sgiacomo.travaglini@arm.com * A maxRRPV of 1 implies in a NRU. 8513826Sgiacomo.travaglini@arm.com */ 8613826Sgiacomo.travaglini@arm.com const int maxRRPV; 8713826Sgiacomo.travaglini@arm.com 8813531Sjairo.balart@metempsy.com /** 8913760Sjairo.balart@metempsy.com * The hit priority (HP) policy replaces entries that do not receive cache 9013531Sjairo.balart@metempsy.com * hits over any cache entry that receives a hit, while the frequency 9113531Sjairo.balart@metempsy.com * priority (FP) policy replaces infrequently re-referenced entries. 9213531Sjairo.balart@metempsy.com */ 9313531Sjairo.balart@metempsy.com const bool hitPriority; 9413531Sjairo.balart@metempsy.com 9513531Sjairo.balart@metempsy.com /** 9613531Sjairo.balart@metempsy.com * Bimodal throtle parameter. Value in the range [0,100] used to decide 9713531Sjairo.balart@metempsy.com * if a new entry is inserted with long or distant re-reference. 9813531Sjairo.balart@metempsy.com */ 9913531Sjairo.balart@metempsy.com const unsigned btp; 10013531Sjairo.balart@metempsy.com 10113531Sjairo.balart@metempsy.com public: 10213531Sjairo.balart@metempsy.com /** Convenience typedef. */ 10313760Sjairo.balart@metempsy.com typedef BRRIPRPParams Params; 10413531Sjairo.balart@metempsy.com 10513531Sjairo.balart@metempsy.com /** 10613531Sjairo.balart@metempsy.com * Construct and initiliaze this replacement policy. 10713531Sjairo.balart@metempsy.com */ 10813531Sjairo.balart@metempsy.com BRRIPRP(const Params *p); 10913531Sjairo.balart@metempsy.com 11013531Sjairo.balart@metempsy.com /** 11113531Sjairo.balart@metempsy.com * Destructor. 11213531Sjairo.balart@metempsy.com */ 11313531Sjairo.balart@metempsy.com ~BRRIPRP() {} 11413531Sjairo.balart@metempsy.com 11513531Sjairo.balart@metempsy.com /** 11613580Sgabeblack@google.com * Invalidate replacement data to set it as the next probable victim. 11713531Sjairo.balart@metempsy.com * Set RRPV as the the most distant re-reference. 11813531Sjairo.balart@metempsy.com * 11913580Sgabeblack@google.com * @param replacement_data Replacement data to be invalidated. 12013531Sjairo.balart@metempsy.com */ 12113531Sjairo.balart@metempsy.com void invalidate(const std::shared_ptr<ReplacementData>& replacement_data) 12213531Sjairo.balart@metempsy.com const override; 12313531Sjairo.balart@metempsy.com 12413760Sjairo.balart@metempsy.com /** 12513531Sjairo.balart@metempsy.com * Touch an entry to update its replacement data. 12613531Sjairo.balart@metempsy.com * 12713531Sjairo.balart@metempsy.com * @param replacement_data Replacement data to be touched. 12813531Sjairo.balart@metempsy.com */ 12913531Sjairo.balart@metempsy.com void touch(const std::shared_ptr<ReplacementData>& replacement_data) const 13013531Sjairo.balart@metempsy.com override; 13114246Sgiacomo.travaglini@arm.com 13213531Sjairo.balart@metempsy.com /** 13313531Sjairo.balart@metempsy.com * Reset replacement data. Used when an entry is inserted. 13413531Sjairo.balart@metempsy.com * Set RRPV according to the insertion policy used. 13513531Sjairo.balart@metempsy.com * 13613531Sjairo.balart@metempsy.com * @param replacement_data Replacement data to be reset. 13713531Sjairo.balart@metempsy.com */ 13813531Sjairo.balart@metempsy.com void reset(const std::shared_ptr<ReplacementData>& replacement_data) const 13913531Sjairo.balart@metempsy.com override; 14013531Sjairo.balart@metempsy.com 14113531Sjairo.balart@metempsy.com /** 14213531Sjairo.balart@metempsy.com * Find replacement victim using rrpv. 14313531Sjairo.balart@metempsy.com * 14413531Sjairo.balart@metempsy.com * @param cands Replacement candidates, selected by indexing policy. 14513531Sjairo.balart@metempsy.com * @return Replacement entry to be replaced. 14613531Sjairo.balart@metempsy.com */ 14713760Sjairo.balart@metempsy.com ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const 14813531Sjairo.balart@metempsy.com override; 14913531Sjairo.balart@metempsy.com 15013531Sjairo.balart@metempsy.com /** 15113531Sjairo.balart@metempsy.com * Instantiate a replacement data entry. 15213531Sjairo.balart@metempsy.com * 15313531Sjairo.balart@metempsy.com * @return A shared pointer to the new replacement data. 15413531Sjairo.balart@metempsy.com */ 15513531Sjairo.balart@metempsy.com std::shared_ptr<ReplacementData> instantiateEntry() override; 15613531Sjairo.balart@metempsy.com}; 15713531Sjairo.balart@metempsy.com 15813531Sjairo.balart@metempsy.com#endif // __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__ 15913531Sjairo.balart@metempsy.com