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
| 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"
|
57#include "mem/cache/replacement_policies/base.hh" 58 59struct BRRIPRPParams; 60 61class BRRIPRP : public BaseReplacementPolicy 62{ 63 protected: 64 /** BRRIP-specific implementation of replacement data. */ 65 struct BRRIPReplData : ReplacementData 66 { 67 /** 68 * Re-Reference Interval Prediction Value. 69 * Some values have specific names (according to the paper): 70 * 0 -> near-immediate re-rereference interval 71 * max_RRPV-1 -> long re-rereference interval 72 * max_RRPV -> distant re-rereference interval
| 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
|
73 * A value equal to max_RRPV + 1 indicates an invalid entry.
| |
74 */
| 74 */
|
75 int rrpv;
| 75 SatCounter rrpv;
|
76
| 76
|
| 77 /** Whether the entry is valid. */ 78 bool valid; 79
|
77 /** 78 * Default constructor. Invalidate data. 79 */
| 80 /** 81 * Default constructor. Invalidate data. 82 */
|
80 BRRIPReplData(const int max_RRPV) : rrpv(max_RRPV + 1) {}
| 83 BRRIPReplData(const int num_bits) 84 : rrpv(num_bits), valid(false) 85 { 86 }
|
81 }; 82 83 /**
| 87 }; 88 89 /**
|
84 * Maximum Re-Reference Prediction Value possible. An entry with this 85 * value as the rrpv has the longest possible re-reference interval, 86 * that is, it is likely not to be used in the near future, and is 87 * among the best eviction candidates. 88 * A maxRRPV of 1 implies in a NRU.
| 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.
|
89 */
| 94 */
|
90 const int maxRRPV;
| 95 const unsigned numRRPVBits;
|
91 92 /** 93 * The hit priority (HP) policy replaces entries that do not receive cache 94 * hits over any cache entry that receives a hit, while the frequency 95 * priority (FP) policy replaces infrequently re-referenced entries. 96 */ 97 const bool hitPriority; 98 99 /** 100 * Bimodal throtle parameter. Value in the range [0,100] used to decide 101 * if a new entry is inserted with long or distant re-reference. 102 */ 103 const unsigned btp; 104 105 public: 106 /** Convenience typedef. */ 107 typedef BRRIPRPParams Params; 108 109 /** 110 * Construct and initiliaze this replacement policy. 111 */ 112 BRRIPRP(const Params *p); 113 114 /** 115 * Destructor. 116 */ 117 ~BRRIPRP() {} 118 119 /** 120 * Invalidate replacement data to set it as the next probable victim. 121 * Set RRPV as the the most distant re-reference. 122 * 123 * @param replacement_data Replacement data to be invalidated. 124 */ 125 void invalidate(const std::shared_ptr<ReplacementData>& replacement_data) 126 const override; 127 128 /** 129 * Touch an entry to update its replacement data. 130 * 131 * @param replacement_data Replacement data to be touched. 132 */ 133 void touch(const std::shared_ptr<ReplacementData>& replacement_data) const 134 override; 135 136 /** 137 * Reset replacement data. Used when an entry is inserted. 138 * Set RRPV according to the insertion policy used. 139 * 140 * @param replacement_data Replacement data to be reset. 141 */ 142 void reset(const std::shared_ptr<ReplacementData>& replacement_data) const 143 override; 144 145 /** 146 * Find replacement victim using rrpv. 147 * 148 * @param cands Replacement candidates, selected by indexing policy. 149 * @return Replacement entry to be replaced. 150 */ 151 ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const 152 override; 153 154 /** 155 * Instantiate a replacement data entry. 156 * 157 * @return A shared pointer to the new replacement data. 158 */ 159 std::shared_ptr<ReplacementData> instantiateEntry() override; 160}; 161 162#endif // __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__
| 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__
|