112626Sodanrc@yahoo.com.br/** 212626Sodanrc@yahoo.com.br * Copyright (c) 2018 Inria 312626Sodanrc@yahoo.com.br * All rights reserved. 412626Sodanrc@yahoo.com.br * 512626Sodanrc@yahoo.com.br * Redistribution and use in source and binary forms, with or without 612626Sodanrc@yahoo.com.br * modification, are permitted provided that the following conditions are 712626Sodanrc@yahoo.com.br * met: redistributions of source code must retain the above copyright 812626Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer; 912626Sodanrc@yahoo.com.br * redistributions in binary form must reproduce the above copyright 1012626Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer in the 1112626Sodanrc@yahoo.com.br * documentation and/or other materials provided with the distribution; 1212626Sodanrc@yahoo.com.br * neither the name of the copyright holders nor the names of its 1312626Sodanrc@yahoo.com.br * contributors may be used to endorse or promote products derived from 1412626Sodanrc@yahoo.com.br * this software without specific prior written permission. 1512626Sodanrc@yahoo.com.br * 1612626Sodanrc@yahoo.com.br * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1712626Sodanrc@yahoo.com.br * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1812626Sodanrc@yahoo.com.br * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1912626Sodanrc@yahoo.com.br * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2012626Sodanrc@yahoo.com.br * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2112626Sodanrc@yahoo.com.br * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2212626Sodanrc@yahoo.com.br * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2312626Sodanrc@yahoo.com.br * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2412626Sodanrc@yahoo.com.br * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2512626Sodanrc@yahoo.com.br * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2612626Sodanrc@yahoo.com.br * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2712626Sodanrc@yahoo.com.br * 2812626Sodanrc@yahoo.com.br * Authors: Daniel Carvalho 2912626Sodanrc@yahoo.com.br */ 3012626Sodanrc@yahoo.com.br 3112626Sodanrc@yahoo.com.br/** 3212626Sodanrc@yahoo.com.br * @file 3312626Sodanrc@yahoo.com.br * Declaration of a Re-Reference Interval Prediction replacement policy. 3412626Sodanrc@yahoo.com.br * 3512626Sodanrc@yahoo.com.br * Not-Recently Used (NRU) is an approximation of LRU that uses a single bit 3612684Sodanrc@yahoo.com.br * to determine if an entry is going to be re-referenced in the near or distant 3712626Sodanrc@yahoo.com.br * future. 3812626Sodanrc@yahoo.com.br * 3912626Sodanrc@yahoo.com.br * Re-Reference Interval Prediction (RRIP) is an extension of NRU that uses a 4012684Sodanrc@yahoo.com.br * re-reference prediction value to determine if entries are going to be re- 4112626Sodanrc@yahoo.com.br * used in the near future or not. 4212626Sodanrc@yahoo.com.br * 4312684Sodanrc@yahoo.com.br * The higher the value of the RRPV, the more distant the entry is from its 4412684Sodanrc@yahoo.com.br * next access. 4512626Sodanrc@yahoo.com.br * 4612626Sodanrc@yahoo.com.br * Bimodal Re-Reference Interval Prediction (BRRIP) is an extension of RRIP 4712684Sodanrc@yahoo.com.br * that has a probability of not inserting entries as the LRU. This probability 4812626Sodanrc@yahoo.com.br * is controlled by the bimodal throtle parameter (btp). 4912626Sodanrc@yahoo.com.br * 5012626Sodanrc@yahoo.com.br * From the original paper, this implementation of RRIP is also called 5112684Sodanrc@yahoo.com.br * Static RRIP (SRRIP), as it always inserts entries with the same RRPV. 5212626Sodanrc@yahoo.com.br */ 5312626Sodanrc@yahoo.com.br 5412626Sodanrc@yahoo.com.br#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__ 5512626Sodanrc@yahoo.com.br#define __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__ 5612626Sodanrc@yahoo.com.br 5714211Sodanrc@yahoo.com.br#include "base/sat_counter.hh" 5812626Sodanrc@yahoo.com.br#include "mem/cache/replacement_policies/base.hh" 5912727Snikos.nikoleris@arm.com 6012727Snikos.nikoleris@arm.comstruct BRRIPRPParams; 6112626Sodanrc@yahoo.com.br 6212626Sodanrc@yahoo.com.brclass BRRIPRP : public BaseReplacementPolicy 6312626Sodanrc@yahoo.com.br{ 6412626Sodanrc@yahoo.com.br protected: 6512684Sodanrc@yahoo.com.br /** BRRIP-specific implementation of replacement data. */ 6612684Sodanrc@yahoo.com.br struct BRRIPReplData : ReplacementData 6712684Sodanrc@yahoo.com.br { 6812684Sodanrc@yahoo.com.br /** 6912684Sodanrc@yahoo.com.br * Re-Reference Interval Prediction Value. 7013849Sanis.peysieux@inria.fr * Some values have specific names (according to the paper): 7113849Sanis.peysieux@inria.fr * 0 -> near-immediate re-rereference interval 7213849Sanis.peysieux@inria.fr * max_RRPV-1 -> long re-rereference interval 7313849Sanis.peysieux@inria.fr * max_RRPV -> distant re-rereference interval 7412684Sodanrc@yahoo.com.br */ 7514211Sodanrc@yahoo.com.br SatCounter rrpv; 7614211Sodanrc@yahoo.com.br 7714211Sodanrc@yahoo.com.br /** Whether the entry is valid. */ 7814211Sodanrc@yahoo.com.br bool valid; 7912684Sodanrc@yahoo.com.br 8012684Sodanrc@yahoo.com.br /** 8112684Sodanrc@yahoo.com.br * Default constructor. Invalidate data. 8212684Sodanrc@yahoo.com.br */ 8314211Sodanrc@yahoo.com.br BRRIPReplData(const int num_bits) 8414211Sodanrc@yahoo.com.br : rrpv(num_bits), valid(false) 8514211Sodanrc@yahoo.com.br { 8614211Sodanrc@yahoo.com.br } 8712684Sodanrc@yahoo.com.br }; 8812684Sodanrc@yahoo.com.br 8912626Sodanrc@yahoo.com.br /** 9014211Sodanrc@yahoo.com.br * Number of RRPV bits. An entry that saturates its RRPV has the longest 9114211Sodanrc@yahoo.com.br * possible re-reference interval, that is, it is likely not to be used 9214211Sodanrc@yahoo.com.br * in the near future, and is among the best eviction candidates. 9314211Sodanrc@yahoo.com.br * A maximum RRPV of 1 implies in a NRU. 9412626Sodanrc@yahoo.com.br */ 9514211Sodanrc@yahoo.com.br const unsigned numRRPVBits; 9612626Sodanrc@yahoo.com.br 9712626Sodanrc@yahoo.com.br /** 9812684Sodanrc@yahoo.com.br * The hit priority (HP) policy replaces entries that do not receive cache 9912684Sodanrc@yahoo.com.br * hits over any cache entry that receives a hit, while the frequency 10012684Sodanrc@yahoo.com.br * priority (FP) policy replaces infrequently re-referenced entries. 10112626Sodanrc@yahoo.com.br */ 10212626Sodanrc@yahoo.com.br const bool hitPriority; 10312626Sodanrc@yahoo.com.br 10412626Sodanrc@yahoo.com.br /** 10512626Sodanrc@yahoo.com.br * Bimodal throtle parameter. Value in the range [0,100] used to decide 10612684Sodanrc@yahoo.com.br * if a new entry is inserted with long or distant re-reference. 10712626Sodanrc@yahoo.com.br */ 10812626Sodanrc@yahoo.com.br const unsigned btp; 10912626Sodanrc@yahoo.com.br 11012626Sodanrc@yahoo.com.br public: 11112626Sodanrc@yahoo.com.br /** Convenience typedef. */ 11212626Sodanrc@yahoo.com.br typedef BRRIPRPParams Params; 11312626Sodanrc@yahoo.com.br 11412626Sodanrc@yahoo.com.br /** 11512626Sodanrc@yahoo.com.br * Construct and initiliaze this replacement policy. 11612626Sodanrc@yahoo.com.br */ 11712626Sodanrc@yahoo.com.br BRRIPRP(const Params *p); 11812626Sodanrc@yahoo.com.br 11912626Sodanrc@yahoo.com.br /** 12012626Sodanrc@yahoo.com.br * Destructor. 12112626Sodanrc@yahoo.com.br */ 12212626Sodanrc@yahoo.com.br ~BRRIPRP() {} 12312626Sodanrc@yahoo.com.br 12412626Sodanrc@yahoo.com.br /** 12512684Sodanrc@yahoo.com.br * Invalidate replacement data to set it as the next probable victim. 12612684Sodanrc@yahoo.com.br * Set RRPV as the the most distant re-reference. 12712626Sodanrc@yahoo.com.br * 12812684Sodanrc@yahoo.com.br * @param replacement_data Replacement data to be invalidated. 12912626Sodanrc@yahoo.com.br */ 13012684Sodanrc@yahoo.com.br void invalidate(const std::shared_ptr<ReplacementData>& replacement_data) 13112684Sodanrc@yahoo.com.br const override; 13212626Sodanrc@yahoo.com.br 13312626Sodanrc@yahoo.com.br /** 13412684Sodanrc@yahoo.com.br * Touch an entry to update its replacement data. 13512684Sodanrc@yahoo.com.br * 13612684Sodanrc@yahoo.com.br * @param replacement_data Replacement data to be touched. 13712684Sodanrc@yahoo.com.br */ 13812684Sodanrc@yahoo.com.br void touch(const std::shared_ptr<ReplacementData>& replacement_data) const 13912684Sodanrc@yahoo.com.br override; 14012684Sodanrc@yahoo.com.br 14112684Sodanrc@yahoo.com.br /** 14212684Sodanrc@yahoo.com.br * Reset replacement data. Used when an entry is inserted. 14312626Sodanrc@yahoo.com.br * Set RRPV according to the insertion policy used. 14412626Sodanrc@yahoo.com.br * 14512684Sodanrc@yahoo.com.br * @param replacement_data Replacement data to be reset. 14612626Sodanrc@yahoo.com.br */ 14712684Sodanrc@yahoo.com.br void reset(const std::shared_ptr<ReplacementData>& replacement_data) const 14812684Sodanrc@yahoo.com.br override; 14912626Sodanrc@yahoo.com.br 15012626Sodanrc@yahoo.com.br /** 15112626Sodanrc@yahoo.com.br * Find replacement victim using rrpv. 15212626Sodanrc@yahoo.com.br * 15312626Sodanrc@yahoo.com.br * @param cands Replacement candidates, selected by indexing policy. 15412684Sodanrc@yahoo.com.br * @return Replacement entry to be replaced. 15512626Sodanrc@yahoo.com.br */ 15612684Sodanrc@yahoo.com.br ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const 15712684Sodanrc@yahoo.com.br override; 15812684Sodanrc@yahoo.com.br 15912684Sodanrc@yahoo.com.br /** 16012684Sodanrc@yahoo.com.br * Instantiate a replacement data entry. 16112684Sodanrc@yahoo.com.br * 16212684Sodanrc@yahoo.com.br * @return A shared pointer to the new replacement data. 16312684Sodanrc@yahoo.com.br */ 16412684Sodanrc@yahoo.com.br std::shared_ptr<ReplacementData> instantiateEntry() override; 16512626Sodanrc@yahoo.com.br}; 16612626Sodanrc@yahoo.com.br 16712626Sodanrc@yahoo.com.br#endif // __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__ 168