brrip_rp.hh revision 14211:acfef4916339
1/** 2 * Copyright (c) 2018 Inria 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * Authors: Daniel Carvalho 29 */ 30 31/** 32 * @file 33 * Declaration of a Re-Reference Interval Prediction replacement policy. 34 * 35 * Not-Recently Used (NRU) is an approximation of LRU that uses a single bit 36 * to determine if an entry is going to be re-referenced in the near or distant 37 * future. 38 * 39 * Re-Reference Interval Prediction (RRIP) is an extension of NRU that uses a 40 * re-reference prediction value to determine if entries are going to be re- 41 * used in the near future or not. 42 * 43 * The higher the value of the RRPV, the more distant the entry is from its 44 * next access. 45 * 46 * Bimodal Re-Reference Interval Prediction (BRRIP) is an extension of RRIP 47 * that has a probability of not inserting entries as the LRU. This probability 48 * is controlled by the bimodal throtle parameter (btp). 49 * 50 * From the original paper, this implementation of RRIP is also called 51 * Static RRIP (SRRIP), as it always inserts entries with the same RRPV. 52 */ 53 54#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__ 55#define __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__ 56 57#include "base/sat_counter.hh" 58#include "mem/cache/replacement_policies/base.hh" 59 60struct BRRIPRPParams; 61 62class BRRIPRP : public BaseReplacementPolicy 63{ 64 protected: 65 /** BRRIP-specific implementation of replacement data. */ 66 struct BRRIPReplData : ReplacementData 67 { 68 /** 69 * Re-Reference Interval Prediction Value. 70 * Some values have specific names (according to the paper): 71 * 0 -> near-immediate re-rereference interval 72 * max_RRPV-1 -> long re-rereference interval 73 * max_RRPV -> distant re-rereference interval 74 */ 75 SatCounter rrpv; 76 77 /** Whether the entry is valid. */ 78 bool valid; 79 80 /** 81 * Default constructor. Invalidate data. 82 */ 83 BRRIPReplData(const int num_bits) 84 : rrpv(num_bits), valid(false) 85 { 86 } 87 }; 88 89 /** 90 * Number of RRPV bits. An entry that saturates its RRPV has the longest 91 * possible re-reference interval, that is, it is likely not to be used 92 * in the near future, and is among the best eviction candidates. 93 * A maximum RRPV of 1 implies in a NRU. 94 */ 95 const unsigned numRRPVBits; 96 97 /** 98 * The hit priority (HP) policy replaces entries that do not receive cache 99 * hits over any cache entry that receives a hit, while the frequency 100 * priority (FP) policy replaces infrequently re-referenced entries. 101 */ 102 const bool hitPriority; 103 104 /** 105 * Bimodal throtle parameter. Value in the range [0,100] used to decide 106 * if a new entry is inserted with long or distant re-reference. 107 */ 108 const unsigned btp; 109 110 public: 111 /** Convenience typedef. */ 112 typedef BRRIPRPParams Params; 113 114 /** 115 * Construct and initiliaze this replacement policy. 116 */ 117 BRRIPRP(const Params *p); 118 119 /** 120 * Destructor. 121 */ 122 ~BRRIPRP() {} 123 124 /** 125 * Invalidate replacement data to set it as the next probable victim. 126 * Set RRPV as the the most distant re-reference. 127 * 128 * @param replacement_data Replacement data to be invalidated. 129 */ 130 void invalidate(const std::shared_ptr<ReplacementData>& replacement_data) 131 const override; 132 133 /** 134 * Touch an entry to update its replacement data. 135 * 136 * @param replacement_data Replacement data to be touched. 137 */ 138 void touch(const std::shared_ptr<ReplacementData>& replacement_data) const 139 override; 140 141 /** 142 * Reset replacement data. Used when an entry is inserted. 143 * Set RRPV according to the insertion policy used. 144 * 145 * @param replacement_data Replacement data to be reset. 146 */ 147 void reset(const std::shared_ptr<ReplacementData>& replacement_data) const 148 override; 149 150 /** 151 * Find replacement victim using rrpv. 152 * 153 * @param cands Replacement candidates, selected by indexing policy. 154 * @return Replacement entry to be replaced. 155 */ 156 ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const 157 override; 158 159 /** 160 * Instantiate a replacement data entry. 161 * 162 * @return A shared pointer to the new replacement data. 163 */ 164 std::shared_ptr<ReplacementData> instantiateEntry() override; 165}; 166 167#endif // __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__ 168