diff options
Diffstat (limited to 'src/mem/cache/replacement_policies')
18 files changed, 598 insertions, 279 deletions
diff --git a/src/mem/cache/replacement_policies/ReplacementPolicies.py b/src/mem/cache/replacement_policies/ReplacementPolicies.py index f2cee35d1..381f386ed 100644 --- a/src/mem/cache/replacement_policies/ReplacementPolicies.py +++ b/src/mem/cache/replacement_policies/ReplacementPolicies.py @@ -73,7 +73,7 @@ class BRRIPRP(BaseReplacementPolicy): type = 'BRRIPRP' cxx_class = 'BRRIPRP' cxx_header = "mem/cache/replacement_policies/brrip_rp.hh" - max_RRPV = Param.Unsigned(3, "Maximum RRPV possible") + max_RRPV = Param.Int(3, "Maximum RRPV possible") hit_priority = Param.Bool(False, "Prioritize evicting blocks that havent had a hit recently") btp = Param.Percent(3, diff --git a/src/mem/cache/replacement_policies/SConscript b/src/mem/cache/replacement_policies/SConscript index 8036ac7cb..74022feda 100644 --- a/src/mem/cache/replacement_policies/SConscript +++ b/src/mem/cache/replacement_policies/SConscript @@ -32,7 +32,6 @@ Import('*') SimObject('ReplacementPolicies.py') -Source('base.cc') Source('bip_rp.cc') Source('brrip_rp.cc') Source('fifo_rp.cc') diff --git a/src/mem/cache/replacement_policies/base.cc b/src/mem/cache/replacement_policies/base.cc deleted file mode 100644 index c422a75d8..000000000 --- a/src/mem/cache/replacement_policies/base.cc +++ /dev/null @@ -1,66 +0,0 @@ -/** - * Copyright (c) 2018 Inria - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer; - * redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution; - * neither the name of the copyright holders nor the names of its - * contributors may be used to endorse or promote products derived from - * this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * - * Authors: Daniel Carvalho - */ - -/** - * @file - * Declaration of a common base class for cache replacement policy objects. - * In general replacement policies try to use invalid entries as victims, - * and if no such blocks exist the replacement policy is applied. - */ - -#include "mem/cache/replacement_policies/base.hh" - -BaseReplacementPolicy::BaseReplacementPolicy(const Params *p) - : SimObject(p) -{ -} - -void -BaseReplacementPolicy::touch(CacheBlk *blk) -{ - // Inform block has been touched - blk->isTouched = true; - - // Update frequency counter - blk->refCount++; -} - -void -BaseReplacementPolicy::reset(CacheBlk *blk) -{ - // Inform block has been touched - blk->isTouched = true; - - // Set insertion tick - blk->tickInserted = curTick(); - - // Reset frequency counter - blk->refCount = 0; -} diff --git a/src/mem/cache/replacement_policies/base.hh b/src/mem/cache/replacement_policies/base.hh index 383f3f01a..0ce86d091 100644 --- a/src/mem/cache/replacement_policies/base.hh +++ b/src/mem/cache/replacement_policies/base.hh @@ -31,26 +31,37 @@ #ifndef __MEM_CACHE_REPLACEMENT_POLICIES_BASE_HH__ #define __MEM_CACHE_REPLACEMENT_POLICIES_BASE_HH__ -#include "mem/cache/base.hh" -#include "mem/cache/blk.hh" +#include <memory> + #include "params/BaseReplacementPolicy.hh" #include "sim/sim_object.hh" /** + * The replacement data needed by the replacement policy. + * Each replacement policy should have its own replacement data. + */ +struct ReplacementData {}; + +/** + * A replaceable entry is used by any table-like structure that needs to + * implement replacement functionality. It provides the replacement data + * pointer instantiated and needed by the replacement policy used. + * @sa Replacement Policies + */ +class ReplaceableEntry +{ + public: + /** + * Replacement data associated to this entry. + * It is instantiated by the replacement policy. + */ + std::shared_ptr<ReplacementData> replacementData; +}; + +/** * Replacement candidates as chosen by the indexing policy. - * - * The base functions touch() and reset() must be called by all subclasses - * that override them. - * - * @todo - * Currently the replacement candidates are simply the cache blocks - * derived from the possible placement locations of an address, as - * defined by the getPossibleLocations() from BaseTags. In a future - * patch it should be an inheritable class to allow the replacement - * policies to be used with any table-like structure that needs to - * replace its entries. */ -typedef std::vector<CacheBlk*> ReplacementCandidates; +typedef std::vector<ReplaceableEntry*> ReplacementCandidates; /** * A common base class of cache replacement policy objects. @@ -66,7 +77,7 @@ class BaseReplacementPolicy : public SimObject /** * Construct and initiliaze this replacement policy. */ - BaseReplacementPolicy(const Params *p); + BaseReplacementPolicy(const Params *p) : SimObject(p) {} /** * Destructor. @@ -74,32 +85,44 @@ class BaseReplacementPolicy : public SimObject virtual ~BaseReplacementPolicy() {} /** - * Touch a block to update its replacement data. - * Updates number of references. + * Invalidate replacement data to set it as the next probable victim. * - * This base function must be called by all subclasses that override it. - * - * @param blk Cache block to be touched. + * @param replacement_data Replacement data to be invalidated. */ - virtual void touch(CacheBlk *blk); + virtual void invalidate(const std::shared_ptr<ReplacementData>& + replacement_data) const = 0; /** - * Reset replacement data for a block. Used when a block is inserted. - * Sets the insertion tick, and update number of references. + * Update replacement data. * - * This base function must be called by all subclasses that override it. + * @param replacement_data Replacement data to be touched. + */ + virtual void touch(const std::shared_ptr<ReplacementData>& + replacement_data) const = 0; + + /** + * Reset replacement data. Used when it's holder is inserted/validated. * - * @param blk Cache block to be reset. + * @param replacement_data Replacement data to be reset. */ - virtual void reset(CacheBlk *blk); + virtual void reset(const std::shared_ptr<ReplacementData>& + replacement_data) const = 0; /** * Find replacement victim among candidates. * * @param candidates Replacement candidates, selected by indexing policy. - * @return Cache block to be replaced. + * @return Replacement entry to be replaced. + */ + virtual ReplaceableEntry* getVictim( + const ReplacementCandidates& candidates) const = 0; + + /** + * Instantiate a replacement data entry. + * + * @return A shared pointer to the new replacement data. */ - virtual CacheBlk* getVictim(const ReplacementCandidates& candidates) = 0; + virtual std::shared_ptr<ReplacementData> instantiateEntry() = 0; }; #endif // __MEM_CACHE_REPLACEMENT_POLICIES_BASE_HH__ diff --git a/src/mem/cache/replacement_policies/bip_rp.cc b/src/mem/cache/replacement_policies/bip_rp.cc index 215711bb9..4a3a516f4 100644 --- a/src/mem/cache/replacement_policies/bip_rp.cc +++ b/src/mem/cache/replacement_policies/bip_rp.cc @@ -30,8 +30,9 @@ #include "mem/cache/replacement_policies/bip_rp.hh" +#include <memory> + #include "base/random.hh" -#include "debug/CacheRepl.hh" BIPRP::BIPRP(const Params *p) : LRURP(p), btp(p->btp) @@ -39,16 +40,17 @@ BIPRP::BIPRP(const Params *p) } void -BIPRP::reset(CacheBlk *blk) +BIPRP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const { - BaseReplacementPolicy::reset(blk); + std::shared_ptr<LRUReplData> casted_replacement_data = + std::static_pointer_cast<LRUReplData>(replacement_data); - // Blocks are inserted as MRU if lower than btp, LRU otherwise + // Entries are inserted as MRU if lower than btp, LRU otherwise if (random_mt.random<unsigned>(1, 100) <= btp) { - blk->lastTouchTick = curTick(); + casted_replacement_data->lastTouchTick = curTick(); } else { // Make their timestamps as old as possible, so that they become LRU - blk->lastTouchTick = 0; + casted_replacement_data->lastTouchTick = 1; } } diff --git a/src/mem/cache/replacement_policies/bip_rp.hh b/src/mem/cache/replacement_policies/bip_rp.hh index f6e2a9c64..ac4db02e0 100644 --- a/src/mem/cache/replacement_policies/bip_rp.hh +++ b/src/mem/cache/replacement_policies/bip_rp.hh @@ -31,7 +31,7 @@ /** * @file * Declaration of a Bimodal Interval Prediction replacement policy. - * Has a probability of when placing new blocks, placing them as MRU. + * Has a probability of when placing new entries, placing them as MRU. * * Although both LRU and LIP can be seen as specific cases of BIP * where the bimodal throtle parameter are 1 and 0, respectively, we @@ -41,8 +41,8 @@ * In the original paper they use btp = 1/32 ~= 3%. */ -#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_LIP_RP_HH__ -#define __MEM_CACHE_REPLACEMENT_POLICIES_LIP_RP_HH__ +#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_BIP_RP_HH__ +#define __MEM_CACHE_REPLACEMENT_POLICIES_BIP_RP_HH__ #include "mem/cache/replacement_policies/lru_rp.hh" #include "params/BIPRP.hh" @@ -52,7 +52,7 @@ class BIPRP : public LRURP protected: /** * Bimodal throtle parameter. Value in the range [0,100] used to decide - * if a new block is inserted at the MRU or LRU position. + * if a new entry is inserted at the MRU or LRU position. */ const unsigned btp; @@ -71,14 +71,14 @@ class BIPRP : public LRURP ~BIPRP() {} /** - * Reset replacement data for a block. Used when a block is inserted. - * Sets the insertion tick, and update correspondent replacement data. - * Uses the bimodal throtle parameter to decide whether the new block + * Reset replacement data for an entry. Used when an entry is inserted. + * Uses the bimodal throtle parameter to decide whether the new entry * should be inserted as MRU, or LRU. * - * @param blk Cache block to be reset. + * @param replacement_data Replacement data to be reset. */ - void reset(CacheBlk *blk) override; + void reset(const std::shared_ptr<ReplacementData>& replacement_data) const + override; }; -#endif // __MEM_CACHE_REPLACEMENT_POLICIES_LIP_RP_HH__ +#endif // __MEM_CACHE_REPLACEMENT_POLICIES_BIP_RP_HH__ diff --git a/src/mem/cache/replacement_policies/brrip_rp.cc b/src/mem/cache/replacement_policies/brrip_rp.cc index 9185638d7..846b4fb9c 100644 --- a/src/mem/cache/replacement_policies/brrip_rp.cc +++ b/src/mem/cache/replacement_policies/brrip_rp.cc @@ -30,88 +30,110 @@ #include "mem/cache/replacement_policies/brrip_rp.hh" +#include <memory> + +#include "base/logging.hh" // For fatal_if #include "base/random.hh" -#include "debug/CacheRepl.hh" BRRIPRP::BRRIPRP(const Params *p) : BaseReplacementPolicy(p), maxRRPV(p->max_RRPV), hitPriority(p->hit_priority), btp(p->btp) { - if (maxRRPV == 0){ - fatal("max_RRPV should be greater than zero.\n"); - } + fatal_if(maxRRPV <= 0, "max_RRPV should be greater than zero.\n"); +} + +void +BRRIPRP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data) +const +{ + std::shared_ptr<BRRIPReplData> casted_replacement_data = + std::static_pointer_cast<BRRIPReplData>(replacement_data); + + // Set RRPV to an invalid distance + casted_replacement_data->rrpv = maxRRPV + 1; } void -BRRIPRP::touch(CacheBlk *blk) +BRRIPRP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const { - BaseReplacementPolicy::touch(blk); + std::shared_ptr<BRRIPReplData> casted_replacement_data = + std::static_pointer_cast<BRRIPReplData>(replacement_data); // Update RRPV if not 0 yet - // Every hit in HP mode makes the block the last to be evicted, while - // in FP mode a hit makes the block less likely to be evicted + // Every hit in HP mode makes the entry the last to be evicted, while + // in FP mode a hit makes the entry less likely to be evicted if (hitPriority) { - blk->rrpv = 0; - } else if (blk->rrpv > 0) { - blk->rrpv--; + casted_replacement_data->rrpv = 0; + } else if (casted_replacement_data->rrpv > 0) { + casted_replacement_data->rrpv--; } } void -BRRIPRP::reset(CacheBlk *blk) +BRRIPRP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const { - BaseReplacementPolicy::reset(blk); + std::shared_ptr<BRRIPReplData> casted_replacement_data = + std::static_pointer_cast<BRRIPReplData>(replacement_data); // Reset RRPV - // Blocks are inserted as "long re-reference" if lower than btp, + // Replacement data is inserted as "long re-reference" if lower than btp, // "distant re-reference" otherwise if (random_mt.random<unsigned>(1, 100) <= btp) { - blk->rrpv = maxRRPV-1; + casted_replacement_data->rrpv = maxRRPV-1; } else { - blk->rrpv = maxRRPV; + casted_replacement_data->rrpv = maxRRPV; } } -CacheBlk* -BRRIPRP::getVictim(const ReplacementCandidates& candidates) +ReplaceableEntry* +BRRIPRP::getVictim(const ReplacementCandidates& candidates) const { // There must be at least one replacement candidate assert(candidates.size() > 0); - // Use visitor to search for the victim - CacheBlk* blk = candidates[0]; + // Use first candidate as dummy victim + ReplaceableEntry* victim = candidates[0]; + + // Store victim->rrpv in a variable to improve code readability + int victim_RRPV = std::static_pointer_cast<BRRIPReplData>( + victim->replacementData)->rrpv; + + // Visit all candidates to find victim for (const auto& candidate : candidates) { - // Stop iteration if found an invalid block - if (!candidate->isValid()) { - blk = candidate; - blk->rrpv = maxRRPV; - break; - // Update victim block if necessary - } else if (candidate->rrpv > blk->rrpv) { - blk = candidate; + // Get candidate's rrpv + int candidate_RRPV = std::static_pointer_cast<BRRIPReplData>( + candidate->replacementData)->rrpv; + + // Stop searching for victims if an invalid entry is found + if (candidate_RRPV == maxRRPV + 1) { + return candidate; + // Update victim entry if necessary + } else if (candidate_RRPV > victim_RRPV) { + victim = candidate; + victim_RRPV = candidate_RRPV; } } - // Make sure we don't have an invalid rrpv - assert(blk->rrpv <= maxRRPV); - - // Get difference of block's RRPV to the highest possible RRPV in - // order to update the RRPV of all the other blocks accordingly - unsigned diff = maxRRPV - blk->rrpv; + // Get difference of victim's RRPV to the highest possible RRPV in + // order to update the RRPV of all the other entries accordingly + int diff = maxRRPV - victim_RRPV; // No need to update RRPV if there is no difference if (diff > 0){ // Update RRPV of all candidates for (const auto& candidate : candidates) { - // Update the block's RPPV with the new value - candidate->rrpv += diff; + std::static_pointer_cast<BRRIPReplData>( + candidate->replacementData)->rrpv += diff; } } - DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n", - blk->set, blk->way); + return victim; +} - return blk; +std::shared_ptr<ReplacementData> +BRRIPRP::instantiateEntry() +{ + return std::shared_ptr<ReplacementData>(new BRRIPReplData(maxRRPV)); } BRRIPRP* diff --git a/src/mem/cache/replacement_policies/brrip_rp.hh b/src/mem/cache/replacement_policies/brrip_rp.hh index 489b81ec0..e442d85ce 100644 --- a/src/mem/cache/replacement_policies/brrip_rp.hh +++ b/src/mem/cache/replacement_policies/brrip_rp.hh @@ -33,22 +33,22 @@ * Declaration of a Re-Reference Interval Prediction replacement policy. * * Not-Recently Used (NRU) is an approximation of LRU that uses a single bit - * to determine if a block is going to be re-referenced in the near or distant + * to determine if an entry is going to be re-referenced in the near or distant * future. * * Re-Reference Interval Prediction (RRIP) is an extension of NRU that uses a - * re-reference prediction value to determine if blocks are going to be re- + * re-reference prediction value to determine if entries are going to be re- * used in the near future or not. * - * The higher the value of the RRPV, the more distant the block is from - * its next access. + * The higher the value of the RRPV, the more distant the entry is from its + * next access. * * Bimodal Re-Reference Interval Prediction (BRRIP) is an extension of RRIP - * that has a probability of not inserting blocks as the LRU. This probability + * that has a probability of not inserting entries as the LRU. This probability * is controlled by the bimodal throtle parameter (btp). * * From the original paper, this implementation of RRIP is also called - * Static RRIP (SRRIP), as it always inserts blocks with the same RRPV. + * Static RRIP (SRRIP), as it always inserts entries with the same RRPV. */ #ifndef __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__ @@ -60,25 +60,40 @@ class BRRIPRP : public BaseReplacementPolicy { protected: + /** BRRIP-specific implementation of replacement data. */ + struct BRRIPReplData : ReplacementData + { + /** + * Re-Reference Interval Prediction Value. + * A value equal to max_RRPV + 1 indicates an invalid entry. + */ + int rrpv; + + /** + * Default constructor. Invalidate data. + */ + BRRIPReplData(const int max_RRPV) : rrpv(max_RRPV + 1) {} + }; + /** - * Maximum Re-Reference Prediction Value possible. A block with this + * Maximum Re-Reference Prediction Value possible. An entry with this * value as the rrpv has the longest possible re-reference interval, * that is, it is likely not to be used in the near future, and is * among the best eviction candidates. * A maxRRPV of 1 implies in a NRU. */ - const unsigned maxRRPV; + const int maxRRPV; /** - * The hit priority (HP) policy replaces blocks that do not receive cache - * hits over any cache block that receives a hit, while the frequency - * priority (FP) policy replaces infrequently re-referenced blocks. + * The hit priority (HP) policy replaces entries that do not receive cache + * hits over any cache entry that receives a hit, while the frequency + * priority (FP) policy replaces infrequently re-referenced entries. */ const bool hitPriority; /** * Bimodal throtle parameter. Value in the range [0,100] used to decide - * if a new block is inserted with long or distant re-reference. + * if a new entry is inserted with long or distant re-reference. */ const unsigned btp; @@ -97,28 +112,46 @@ class BRRIPRP : public BaseReplacementPolicy ~BRRIPRP() {} /** - * Touch a block to update its replacement data. + * Invalidate replacement data to set it as the next probable victim. + * Set RRPV as the the most distant re-reference. + * + * @param replacement_data Replacement data to be invalidated. + */ + void invalidate(const std::shared_ptr<ReplacementData>& replacement_data) + const override; + + /** + * Touch an entry to update its replacement data. * - * @param blk Cache block to be touched. + * @param replacement_data Replacement data to be touched. */ - void touch(CacheBlk *blk) override; + void touch(const std::shared_ptr<ReplacementData>& replacement_data) const + override; /** - * Reset replacement data for a block. Used when a block is inserted. - * Sets the insertion tick, and update correspondent replacement data. + * Reset replacement data. Used when an entry is inserted. * Set RRPV according to the insertion policy used. * - * @param blk Cache block to be reset. + * @param replacement_data Replacement data to be reset. */ - void reset(CacheBlk *blk) override; + void reset(const std::shared_ptr<ReplacementData>& replacement_data) const + override; /** * Find replacement victim using rrpv. * * @param cands Replacement candidates, selected by indexing policy. - * @return Cache block to be replaced. + * @return Replacement entry to be replaced. + */ + ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const + override; + + /** + * Instantiate a replacement data entry. + * + * @return A shared pointer to the new replacement data. */ - CacheBlk* getVictim(const ReplacementCandidates& candidates) override; + std::shared_ptr<ReplacementData> instantiateEntry() override; }; #endif // __MEM_CACHE_REPLACEMENT_POLICIES_BRRIP_RP_HH__ diff --git a/src/mem/cache/replacement_policies/fifo_rp.cc b/src/mem/cache/replacement_policies/fifo_rp.cc index fd320be83..731945a0a 100644 --- a/src/mem/cache/replacement_policies/fifo_rp.cc +++ b/src/mem/cache/replacement_policies/fifo_rp.cc @@ -30,36 +30,61 @@ #include "mem/cache/replacement_policies/fifo_rp.hh" -#include "debug/CacheRepl.hh" +#include <memory> FIFORP::FIFORP(const Params *p) : BaseReplacementPolicy(p) { } -CacheBlk* -FIFORP::getVictim(const ReplacementCandidates& candidates) +void +FIFORP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data) +const +{ + // Reset insertion tick + std::static_pointer_cast<FIFOReplData>( + replacement_data)->tickInserted = Tick(0); +} + +void +FIFORP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const +{ + // A touch does not modify the insertion tick +} + +void +FIFORP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const +{ + // Set insertion tick + std::static_pointer_cast<FIFOReplData>( + replacement_data)->tickInserted = curTick(); +} + +ReplaceableEntry* +FIFORP::getVictim(const ReplacementCandidates& candidates) const { // There must be at least one replacement candidate assert(candidates.size() > 0); // Visit all candidates to find victim - CacheBlk* blk = candidates[0]; + ReplaceableEntry* victim = candidates[0]; for (const auto& candidate : candidates) { - // Stop iteration if found an invalid block - if (!candidate->isValid()) { - blk = candidate; - break; - // Update victim block if necessary - } else if (candidate->tickInserted < blk->tickInserted) { - blk = candidate; + // Update victim entry if necessary + if (std::static_pointer_cast<FIFOReplData>( + candidate->replacementData)->tickInserted < + std::static_pointer_cast<FIFOReplData>( + victim->replacementData)->tickInserted) { + victim = candidate; } } - DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n", - blk->set, blk->way); + return victim; +} - return blk; +std::shared_ptr<ReplacementData> +FIFORP::instantiateEntry() +{ + return std::shared_ptr<ReplacementData>(new FIFOReplData()); } FIFORP* diff --git a/src/mem/cache/replacement_policies/fifo_rp.hh b/src/mem/cache/replacement_policies/fifo_rp.hh index 16493711c..a686b449b 100644 --- a/src/mem/cache/replacement_policies/fifo_rp.hh +++ b/src/mem/cache/replacement_policies/fifo_rp.hh @@ -31,7 +31,7 @@ /** * @file * Declaration of a First In First Out replacement policy. - * The victim is chosen using the timestamp. The oldest block is always chosen + * The victim is chosen using the timestamp. The oldest entry is always chosen * to be evicted, regardless of the amount of times it has been touched. */ @@ -43,6 +43,18 @@ class FIFORP : public BaseReplacementPolicy { + /** FIFO-specific implementation of replacement data. */ + struct FIFOReplData : ReplacementData + { + /** Tick on which the entry was inserted. */ + Tick tickInserted; + + /** + * Default constructor. Invalidate data. + */ + FIFOReplData() : tickInserted(0) {} + }; + public: /** Convenience typedef. */ typedef FIFORPParams Params; @@ -58,12 +70,47 @@ class FIFORP : public BaseReplacementPolicy ~FIFORP() {} /** + * Invalidate replacement data to set it as the next probable victim. + * Reset insertion tick to 0. + * + * @param replacement_data Replacement data to be invalidated. + */ + void invalidate(const std::shared_ptr<ReplacementData>& replacement_data) + const override; + + /** + * Touch an entry to update its replacement data. + * Does not modify the replacement data. + * + * @param replacement_data Replacement data to be touched. + */ + void touch(const std::shared_ptr<ReplacementData>& replacement_data) const + override; + + /** + * Reset replacement data. Used when an entry is inserted. + * Sets its insertion tick. + * + * @param replacement_data Replacement data to be reset. + */ + void reset(const std::shared_ptr<ReplacementData>& replacement_data) const + override; + + /** * Find replacement victim using insertion timestamps. * * @param cands Replacement candidates, selected by indexing policy. - * @return Cache block to be replaced. + * @return Replacement entry to be replaced. + */ + ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const + override; + + /** + * Instantiate a replacement data entry. + * + * @return A shared pointer to the new replacement data. */ - CacheBlk* getVictim(const ReplacementCandidates& cands) override; + std::shared_ptr<ReplacementData> instantiateEntry() override; }; #endif // __MEM_CACHE_REPLACEMENT_POLICIES_FIFO_RP_HH__ diff --git a/src/mem/cache/replacement_policies/lfu_rp.cc b/src/mem/cache/replacement_policies/lfu_rp.cc index 90a5ee227..ffa653e87 100644 --- a/src/mem/cache/replacement_policies/lfu_rp.cc +++ b/src/mem/cache/replacement_policies/lfu_rp.cc @@ -30,36 +30,60 @@ #include "mem/cache/replacement_policies/lfu_rp.hh" -#include "debug/CacheRepl.hh" +#include <memory> LFURP::LFURP(const Params *p) : BaseReplacementPolicy(p) { } -CacheBlk* -LFURP::getVictim(const ReplacementCandidates& candidates) +void +LFURP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data) +const +{ + // Reset reference count + std::static_pointer_cast<LFUReplData>(replacement_data)->refCount = 0; +} + +void +LFURP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const +{ + // Update reference count + std::static_pointer_cast<LFUReplData>(replacement_data)->refCount++; +} + +void +LFURP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const +{ + // Reset reference count + std::static_pointer_cast<LFUReplData>(replacement_data)->refCount = 1; +} + +ReplaceableEntry* +LFURP::getVictim(const ReplacementCandidates& candidates) const { // There must be at least one replacement candidate assert(candidates.size() > 0); // Visit all candidates to find victim - CacheBlk* blk = candidates[0]; + ReplaceableEntry* victim = candidates[0]; for (const auto& candidate : candidates) { - // Stop iteration if found an invalid block - if (!candidate->isValid()) { - blk = candidate; - break; - // Update victim block if necessary - } else if (candidate->refCount < blk->refCount) { - blk = candidate; + // Update victim entry if necessary + if (std::static_pointer_cast<LFUReplData>( + candidate->replacementData)->refCount < + std::static_pointer_cast<LFUReplData>( + victim->replacementData)->refCount) { + victim = candidate; } } - DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n", - blk->set, blk->way); + return victim; +} - return blk; +std::shared_ptr<ReplacementData> +LFURP::instantiateEntry() +{ + return std::shared_ptr<ReplacementData>(new LFUReplData()); } LFURP* diff --git a/src/mem/cache/replacement_policies/lfu_rp.hh b/src/mem/cache/replacement_policies/lfu_rp.hh index affc849a2..8709e35d4 100644 --- a/src/mem/cache/replacement_policies/lfu_rp.hh +++ b/src/mem/cache/replacement_policies/lfu_rp.hh @@ -32,7 +32,7 @@ * @file * Declaration of a Least Frequently Used replacement policy. * The victim is chosen using the reference frequency. The least referenced - * block is always chosen to be evicted, regardless of the amount of times + * entry is always chosen to be evicted, regardless of the amount of times * it has been touched, or how long has passed since its last touch. */ @@ -44,6 +44,19 @@ class LFURP : public BaseReplacementPolicy { + protected: + /** LFU-specific implementation of replacement data. */ + struct LFUReplData : ReplacementData + { + /** Number of references to this entry since it was reset. */ + unsigned refCount; + + /** + * Default constructor. Invalidate data. + */ + LFUReplData() : refCount(0) {} + }; + public: /** Convenience typedef. */ typedef LFURPParams Params; @@ -59,12 +72,47 @@ class LFURP : public BaseReplacementPolicy ~LFURP() {} /** + * Invalidate replacement data to set it as the next probable victim. + * Clear the number of references. + * + * @param replacement_data Replacement data to be invalidated. + */ + void invalidate(const std::shared_ptr<ReplacementData>& replacement_data) + const override; + + /** + * Touch an entry to update its replacement data. + * Increase number of references. + * + * @param replacement_data Replacement data to be touched. + */ + void touch(const std::shared_ptr<ReplacementData>& replacement_data) const + override; + + /** + * Reset replacement data. Used when an entry is inserted. + * Reset number of references. + * + * @param replacement_data Replacement data to be reset. + */ + void reset(const std::shared_ptr<ReplacementData>& replacement_data) const + override; + + /** * Find replacement victim using reference frequency. * * @param cands Replacement candidates, selected by indexing policy. - * @return Cache block to be replaced. + * @return Replacement entry to be replaced. + */ + ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const + override; + + /** + * Instantiate a replacement data entry. + * + * @return A shared pointer to the new replacement data. */ - CacheBlk* getVictim(const ReplacementCandidates& candidates) override; + std::shared_ptr<ReplacementData> instantiateEntry() override; }; #endif // __MEM_CACHE_REPLACEMENT_POLICIES_LFU_RP_HH__ diff --git a/src/mem/cache/replacement_policies/lru_rp.cc b/src/mem/cache/replacement_policies/lru_rp.cc index b2fa20b6f..99e35db19 100644 --- a/src/mem/cache/replacement_policies/lru_rp.cc +++ b/src/mem/cache/replacement_policies/lru_rp.cc @@ -30,7 +30,7 @@ #include "mem/cache/replacement_policies/lru_rp.hh" -#include "debug/CacheRepl.hh" +#include <memory> LRURP::LRURP(const Params *p) : BaseReplacementPolicy(p) @@ -38,46 +38,55 @@ LRURP::LRURP(const Params *p) } void -LRURP::touch(CacheBlk *blk) +LRURP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data) +const { - BaseReplacementPolicy::touch(blk); + // Reset last touch timestamp + std::static_pointer_cast<LRUReplData>( + replacement_data)->lastTouchTick = Tick(0); +} +void +LRURP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const +{ // Update last touch timestamp - blk->lastTouchTick = curTick(); + std::static_pointer_cast<LRUReplData>( + replacement_data)->lastTouchTick = curTick(); } void -LRURP::reset(CacheBlk *blk) +LRURP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const { - BaseReplacementPolicy::reset(blk); - // Set last touch timestamp - blk->lastTouchTick = blk->tickInserted; + std::static_pointer_cast<LRUReplData>( + replacement_data)->lastTouchTick = curTick(); } -CacheBlk* -LRURP::getVictim(const ReplacementCandidates& candidates) +ReplaceableEntry* +LRURP::getVictim(const ReplacementCandidates& candidates) const { // There must be at least one replacement candidate assert(candidates.size() > 0); // Visit all candidates to find victim - CacheBlk* blk = candidates[0]; + ReplaceableEntry* victim = candidates[0]; for (const auto& candidate : candidates) { - // Stop iteration if found an invalid block - if (!candidate->isValid()) { - blk = candidate; - break; - // Update victim block if necessary - } else if (candidate->lastTouchTick < blk->lastTouchTick) { - blk = candidate; + // Update victim entry if necessary + if (std::static_pointer_cast<LRUReplData>( + candidate->replacementData)->lastTouchTick < + std::static_pointer_cast<LRUReplData>( + victim->replacementData)->lastTouchTick) { + victim = candidate; } } - DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n", - blk->set, blk->way); + return victim; +} - return blk; +std::shared_ptr<ReplacementData> +LRURP::instantiateEntry() +{ + return std::shared_ptr<ReplacementData>(new LRUReplData()); } LRURP* diff --git a/src/mem/cache/replacement_policies/lru_rp.hh b/src/mem/cache/replacement_policies/lru_rp.hh index 2dd7e86f0..e8e708f1c 100644 --- a/src/mem/cache/replacement_policies/lru_rp.hh +++ b/src/mem/cache/replacement_policies/lru_rp.hh @@ -43,6 +43,19 @@ class LRURP : public BaseReplacementPolicy { + protected: + /** LRU-specific implementation of replacement data. */ + struct LRUReplData : ReplacementData + { + /** Tick on which the entry was last touched. */ + Tick lastTouchTick; + + /** + * Default constructor. Invalidate data. + */ + LRUReplData() : lastTouchTick(0) {} + }; + public: /** Convenience typedef. */ typedef LRURPParams Params; @@ -58,27 +71,47 @@ class LRURP : public BaseReplacementPolicy ~LRURP() {} /** - * Touch a block to update its last touch tick. + * Invalidate replacement data to set it as the next probable victim. + * Sets its last touch tick as the starting tick. * - * @param blk Cache block to be touched. + * @param replacement_data Replacement data to be invalidated. */ - void touch(CacheBlk *blk) override; + void invalidate(const std::shared_ptr<ReplacementData>& replacement_data) + const override; /** - * Reset replacement data for a block. Used when a block is inserted. + * Touch an entry to update its replacement data. * Sets its last touch tick as the current tick. * - * @param blk Cache block to be reset. + * @param replacement_data Replacement data to be touched. */ - void reset(CacheBlk *blk) override; + void touch(const std::shared_ptr<ReplacementData>& replacement_data) const + override; + + /** + * Reset replacement data. Used when an entry is inserted. + * Sets its last touch tick as the current tick. + * + * @param replacement_data Replacement data to be reset. + */ + void reset(const std::shared_ptr<ReplacementData>& replacement_data) const + override; /** * Find replacement victim using LRU timestamps. * * @param candidates Replacement candidates, selected by indexing policy. - * @return Cache block to be replaced. + * @return Replacement entry to be replaced. + */ + ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const + override; + + /** + * Instantiate a replacement data entry. + * + * @return A shared pointer to the new replacement data. */ - CacheBlk* getVictim(const ReplacementCandidates& candidates) override; + std::shared_ptr<ReplacementData> instantiateEntry() override; }; #endif // __MEM_CACHE_REPLACEMENT_POLICIES_LRU_RP_HH__ diff --git a/src/mem/cache/replacement_policies/mru_rp.cc b/src/mem/cache/replacement_policies/mru_rp.cc index f4cf014ae..ff84fc368 100644 --- a/src/mem/cache/replacement_policies/mru_rp.cc +++ b/src/mem/cache/replacement_policies/mru_rp.cc @@ -30,7 +30,7 @@ #include "mem/cache/replacement_policies/mru_rp.hh" -#include "debug/CacheRepl.hh" +#include <memory> MRURP::MRURP(const Params *p) : BaseReplacementPolicy(p) @@ -38,46 +38,55 @@ MRURP::MRURP(const Params *p) } void -MRURP::touch(CacheBlk *blk) +MRURP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data) +const { - BaseReplacementPolicy::touch(blk); + // Reset last touch timestamp + std::static_pointer_cast<MRUReplData>( + replacement_data)->lastTouchTick = Tick(0); +} +void +MRURP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const +{ // Update last touch timestamp - blk->lastTouchTick = curTick(); + std::static_pointer_cast<MRUReplData>( + replacement_data)->lastTouchTick = curTick(); } void -MRURP::reset(CacheBlk *blk) +MRURP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const { - BaseReplacementPolicy::reset(blk); - // Set last touch timestamp - blk->lastTouchTick = blk->tickInserted; + std::static_pointer_cast<MRUReplData>( + replacement_data)->lastTouchTick = curTick(); } -CacheBlk* -MRURP::getVictim(const ReplacementCandidates& candidates) +ReplaceableEntry* +MRURP::getVictim(const ReplacementCandidates& candidates) const { // There must be at least one replacement candidate assert(candidates.size() > 0); // Visit all candidates to find victim - CacheBlk* blk = candidates[0]; + ReplaceableEntry* victim = candidates[0]; for (const auto& candidate : candidates) { - // Stop iteration if found an invalid block - if (!candidate->isValid()) { - blk = candidate; - break; - // Update victim block if necessary - } else if (candidate->lastTouchTick > blk->lastTouchTick) { - blk = candidate; + // Update victim entry if necessary + if (std::static_pointer_cast<MRUReplData>( + candidate->replacementData)->lastTouchTick > + std::static_pointer_cast<MRUReplData>( + victim->replacementData)->lastTouchTick) { + victim = candidate; } } - DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n", - blk->set, blk->way); + return victim; +} - return blk; +std::shared_ptr<ReplacementData> +MRURP::instantiateEntry() +{ + return std::shared_ptr<ReplacementData>(new MRUReplData()); } MRURP* diff --git a/src/mem/cache/replacement_policies/mru_rp.hh b/src/mem/cache/replacement_policies/mru_rp.hh index fd9a29dff..11cc272a4 100644 --- a/src/mem/cache/replacement_policies/mru_rp.hh +++ b/src/mem/cache/replacement_policies/mru_rp.hh @@ -31,7 +31,7 @@ /** * @file * Declaration of a Most Recently Used replacement policy. - * The victim is chosen using the timestamp. The block that was accessed the + * The victim is chosen using the timestamp. The entry that was accessed the * last is the one chosen to be replaced. */ @@ -43,6 +43,19 @@ class MRURP : public BaseReplacementPolicy { + protected: + /** MRU-specific implementation of replacement data. */ + struct MRUReplData : ReplacementData + { + /** Tick on which the entry was last touched. */ + Tick lastTouchTick; + + /** + * Default constructor. Invalidate data. + */ + MRUReplData() : lastTouchTick(0) {} + }; + public: /** Convenience typedef. */ typedef MRURPParams Params; @@ -58,26 +71,47 @@ class MRURP : public BaseReplacementPolicy ~MRURP() {} /** - * Touch a block to update its last touch tick. + * Invalidate replacement data to set it as the next probable victim. + * Sets its last touch tick as the starting tick. + * + * @param replacement_data Replacement data to be invalidated. + */ + void invalidate(const std::shared_ptr<ReplacementData>& replacement_data) + const override; + + /** + * Touch an entry to update its replacement data. + * Sets its last touch tick as the current tick. * - * @param blk Cache block to be touched. + * @param replacement_data Replacement data to be touched. */ - void touch(CacheBlk *blk) override; + void touch(const std::shared_ptr<ReplacementData>& replacement_data) const + override; /** - * Reset replacement data for a block. Used when a block is inserted. + * Reset replacement data. Used when an entry is inserted. * Sets its last touch tick as the current tick. * - * @param blk Cache block to be reset. + * @param replacement_data Replacement data to be reset. */ - void reset(CacheBlk *blk) override; + void reset(const std::shared_ptr<ReplacementData>& replacement_data) const + override; /** * Find replacement victim using access timestamps. + * * @param cands Replacement candidates, selected by indexing policy. - * @return Cache block to be replaced. + * @return Replacement entry to be replaced. + */ + ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const + override; + + /** + * Instantiate a replacement data entry. + * + * @return A shared pointer to the new replacement data. */ - CacheBlk* getVictim(const ReplacementCandidates& candidates) override; + std::shared_ptr<ReplacementData> instantiateEntry() override; }; #endif // __MEM_CACHE_REPLACEMENT_POLICIES_MRU_RP_HH__ diff --git a/src/mem/cache/replacement_policies/random_rp.cc b/src/mem/cache/replacement_policies/random_rp.cc index 1c54bdac6..24e64fc90 100644 --- a/src/mem/cache/replacement_policies/random_rp.cc +++ b/src/mem/cache/replacement_policies/random_rp.cc @@ -31,37 +31,62 @@ #include "mem/cache/replacement_policies/random_rp.hh" #include "base/random.hh" -#include "debug/CacheRepl.hh" +#include "mem/cache/blk.hh" RandomRP::RandomRP(const Params *p) : BaseReplacementPolicy(p) { } -CacheBlk* -RandomRP::getVictim(const ReplacementCandidates& candidates) +void +RandomRP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data) +const +{ + // Unprioritize replacement data victimization + std::static_pointer_cast<RandomReplData>( + replacement_data)->valid = false; +} + +void +RandomRP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const +{ +} + +void +RandomRP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const +{ + // Unprioritize replacement data victimization + std::static_pointer_cast<RandomReplData>( + replacement_data)->valid = true; +} + +ReplaceableEntry* +RandomRP::getVictim(const ReplacementCandidates& candidates) const { // There must be at least one replacement candidate assert(candidates.size() > 0); // Choose one candidate at random - CacheBlk* blk = candidates[random_mt.random<unsigned>(0, + ReplaceableEntry* victim = candidates[random_mt.random<unsigned>(0, candidates.size() - 1)]; - // Visit all candidates to find an invalid entry + // Visit all candidates to search for an invalid entry. If one is found, + // its eviction is prioritized for (const auto& candidate : candidates) { - // Give priority to victimise invalid entries - if (!candidate->isValid()){ - blk = candidate; + if (!std::static_pointer_cast<RandomReplData>( + candidate->replacementData)->valid) { + victim = candidate; break; } } - // If no invalid blocks were found, choose one of the candidates randomly - DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n", - blk->set, blk->way); + return victim; +} - return blk; +std::shared_ptr<ReplacementData> +RandomRP::instantiateEntry() +{ + return std::shared_ptr<ReplacementData>(new ReplacementData()); } RandomRP* diff --git a/src/mem/cache/replacement_policies/random_rp.hh b/src/mem/cache/replacement_policies/random_rp.hh index 338b26ff2..5514961b6 100644 --- a/src/mem/cache/replacement_policies/random_rp.hh +++ b/src/mem/cache/replacement_policies/random_rp.hh @@ -42,6 +42,22 @@ class RandomRP : public BaseReplacementPolicy { + protected: + /** MRU-specific implementation of replacement data. */ + struct RandomReplData : ReplacementData + { + /** + * Flag informing if the replacement data is valid or not. + * Invalid entries are prioritized to be evicted. + */ + bool valid; + + /** + * Default constructor. Invalidate data. + */ + RandomReplData() : valid(false) {} + }; + public: /** Convenience typedef. */ typedef RandomRPParams Params; @@ -57,11 +73,47 @@ class RandomRP : public BaseReplacementPolicy ~RandomRP() {} /** + * Invalidate replacement data to set it as the next probable victim. + * Prioritize replacement data for victimization. + * + * @param replacement_data Replacement data to be invalidated. + */ + void invalidate(const std::shared_ptr<ReplacementData>& replacement_data) + const override; + + /** + * Touch an entry to update its replacement data. + * Does not do anything. + * + * @param replacement_data Replacement data to be touched. + */ + void touch(const std::shared_ptr<ReplacementData>& replacement_data) const + override; + + /** + * Reset replacement data. Used when an entry is inserted. + * Unprioritize replacement data for victimization. + * + * @param replacement_data Replacement data to be reset. + */ + void reset(const std::shared_ptr<ReplacementData>& replacement_data) const + override; + + /** * Find replacement victim at random. + * * @param candidates Replacement candidates, selected by indexing policy. - * @return Cache block to be replaced. + * @return Replacement entry to be replaced. + */ + ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const + override; + + /** + * Instantiate a replacement data entry. + * + * @return A shared pointer to the new replacement data. */ - CacheBlk* getVictim(const ReplacementCandidates& candidates) override; + std::shared_ptr<ReplacementData> instantiateEntry() override; }; #endif // __MEM_CACHE_REPLACEMENT_POLICIES_RANDOM_RP_HH__ |