diff options
Diffstat (limited to 'src/mem')
21 files changed, 549 insertions, 346 deletions
diff --git a/src/mem/cache/Cache.py b/src/mem/cache/Cache.py index bac6c73e1..faee0925b 100644 --- a/src/mem/cache/Cache.py +++ b/src/mem/cache/Cache.py @@ -43,6 +43,7 @@ from m5.params import * from m5.proxy import * from MemObject import MemObject from Prefetcher import BasePrefetcher +from ReplacementPolicies import * from Tags import * class BaseCache(MemObject): @@ -74,7 +75,10 @@ class BaseCache(MemObject): prefetch_on_access = Param.Bool(False, "Notify the hardware prefetcher on every access (not just misses)") - tags = Param.BaseTags(LRU(), "Tag store (replacement policy)") + tags = Param.BaseTags(BaseSetAssoc(), "Tag store") + replacement_policy = Param.BaseReplacementPolicy(LRURP(), + "Replacement policy") + sequential_access = Param.Bool(False, "Whether to access tags and data sequentially") diff --git a/src/mem/cache/base.cc b/src/mem/cache/base.cc index 6f2532371..2c7d9fb68 100644 --- a/src/mem/cache/base.cc +++ b/src/mem/cache/base.cc @@ -52,8 +52,6 @@ #include "mem/cache/cache.hh" #include "mem/cache/mshr.hh" #include "mem/cache/tags/fa_lru.hh" -#include "mem/cache/tags/lru.hh" -#include "mem/cache/tags/random_repl.hh" #include "sim/full_system.hh" using namespace std; diff --git a/src/mem/cache/blk.hh b/src/mem/cache/blk.hh index 7dd0a92ae..a1e45028b 100644 --- a/src/mem/cache/blk.hh +++ b/src/mem/cache/blk.hh @@ -99,7 +99,7 @@ class CacheBlk /** The current status of this block. @sa CacheBlockStatusBits */ State status; - /** Which curTick() will this block be accessable */ + /** Which curTick() will this block be accessible */ Tick whenReady; /** @@ -108,7 +108,10 @@ class CacheBlk */ int set, way; - /** whether this block has been touched */ + /** + * Whether this block has been touched since simulation started. + * Used to calculate number of used tags. + */ bool isTouched; /** Number of references to this block since it was brought in. */ @@ -117,8 +120,15 @@ class CacheBlk /** holds the source requestor ID for this block. */ int srcMasterId; + /** Tick on which the block was inserted in the cache. */ Tick tickInserted; + /** + * Replacement policy data. As of now it is only an update timestamp. + * Tick on which the block was last touched. + */ + Tick lastTouchTick; + protected: /** * Represents that the indicated thread context has a "lock" on diff --git a/src/mem/cache/cache.cc b/src/mem/cache/cache.cc index 9ee935961..cbc0ed90a 100644 --- a/src/mem/cache/cache.cc +++ b/src/mem/cache/cache.cc @@ -1816,6 +1816,7 @@ Cache::invalidateVisitor(CacheBlk &blk) CacheBlk* Cache::allocateBlock(Addr addr, bool is_secure, PacketList &writebacks) { + // Find replacement victim CacheBlk *blk = tags->findVictim(addr); // It is valid to return nullptr if there is no victim @@ -2802,6 +2803,7 @@ Cache* CacheParams::create() { assert(tags); + assert(replacement_policy); return new Cache(this); } diff --git a/src/mem/cache/replacement_policies/ReplacementPolicies.py b/src/mem/cache/replacement_policies/ReplacementPolicies.py new file mode 100644 index 000000000..64743819b --- /dev/null +++ b/src/mem/cache/replacement_policies/ReplacementPolicies.py @@ -0,0 +1,46 @@ +# 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 + +from m5.params import * +from m5.proxy import * +from m5.SimObject import SimObject + +class BaseReplacementPolicy(SimObject): + type = 'BaseReplacementPolicy' + abstract = True + cxx_header = "mem/cache/replacement_policies/base.hh" + +class LRURP(BaseReplacementPolicy): + type = 'LRURP' + cxx_class = 'LRURP' + cxx_header = "mem/cache/replacement_policies/lru_rp.hh" + +class RandomRP(BaseReplacementPolicy): + type = 'RandomRP' + cxx_class = 'RandomRP' + cxx_header = "mem/cache/replacement_policies/random_rp.hh" diff --git a/src/mem/cache/replacement_policies/SConscript b/src/mem/cache/replacement_policies/SConscript new file mode 100644 index 000000000..c3c89923f --- /dev/null +++ b/src/mem/cache/replacement_policies/SConscript @@ -0,0 +1,37 @@ +# -*- mode:python -*- + +# 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 + +Import('*') + +SimObject('ReplacementPolicies.py') + +Source('base.cc') +Source('lru_rp.cc') +Source('random_rp.cc') diff --git a/src/mem/cache/replacement_policies/base.cc b/src/mem/cache/replacement_policies/base.cc new file mode 100644 index 000000000..c422a75d8 --- /dev/null +++ b/src/mem/cache/replacement_policies/base.cc @@ -0,0 +1,66 @@ +/** + * 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 new file mode 100644 index 000000000..383f3f01a --- /dev/null +++ b/src/mem/cache/replacement_policies/base.hh @@ -0,0 +1,105 @@ +/** + * 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 + */ + +#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 "params/BaseReplacementPolicy.hh" +#include "sim/sim_object.hh" + +/** + * 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; + +/** + * A common base class of cache replacement policy objects. + */ +class BaseReplacementPolicy : public SimObject +{ + public: + /** + * Convenience typedef. + */ + typedef BaseReplacementPolicyParams Params; + + /** + * Construct and initiliaze this replacement policy. + */ + BaseReplacementPolicy(const Params *p); + + /** + * Destructor. + */ + virtual ~BaseReplacementPolicy() {} + + /** + * Touch a block to update its replacement data. + * Updates number of references. + * + * This base function must be called by all subclasses that override it. + * + * @param blk Cache block to be touched. + */ + virtual void touch(CacheBlk *blk); + + /** + * Reset replacement data for a block. Used when a block is inserted. + * Sets the insertion tick, and update number of references. + * + * This base function must be called by all subclasses that override it. + * + * @param blk Cache block to be reset. + */ + virtual void reset(CacheBlk *blk); + + /** + * Find replacement victim among candidates. + * + * @param candidates Replacement candidates, selected by indexing policy. + * @return Cache block to be replaced. + */ + virtual CacheBlk* getVictim(const ReplacementCandidates& candidates) = 0; +}; + +#endif // __MEM_CACHE_REPLACEMENT_POLICIES_BASE_HH__ diff --git a/src/mem/cache/replacement_policies/lru_rp.cc b/src/mem/cache/replacement_policies/lru_rp.cc new file mode 100644 index 000000000..b2fa20b6f --- /dev/null +++ b/src/mem/cache/replacement_policies/lru_rp.cc @@ -0,0 +1,87 @@ +/** + * 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 + */ + +#include "mem/cache/replacement_policies/lru_rp.hh" + +#include "debug/CacheRepl.hh" + +LRURP::LRURP(const Params *p) + : BaseReplacementPolicy(p) +{ +} + +void +LRURP::touch(CacheBlk *blk) +{ + BaseReplacementPolicy::touch(blk); + + // Update last touch timestamp + blk->lastTouchTick = curTick(); +} + +void +LRURP::reset(CacheBlk *blk) +{ + BaseReplacementPolicy::reset(blk); + + // Set last touch timestamp + blk->lastTouchTick = blk->tickInserted; +} + +CacheBlk* +LRURP::getVictim(const ReplacementCandidates& candidates) +{ + // There must be at least one replacement candidate + assert(candidates.size() > 0); + + // Visit all candidates to find victim + CacheBlk* blk = 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; + } + } + + DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n", + blk->set, blk->way); + + return blk; +} + +LRURP* +LRURPParams::create() +{ + return new LRURP(this); +} diff --git a/src/mem/cache/tags/lru.hh b/src/mem/cache/replacement_policies/lru_rp.hh index 1fbe4eb6d..3e5efe61f 100644 --- a/src/mem/cache/tags/lru.hh +++ b/src/mem/cache/replacement_policies/lru_rp.hh @@ -1,17 +1,5 @@ -/* - * Copyright (c) 2012-2013 ARM Limited - * All rights reserved. - * - * The license below extends only to copyright in the software and shall - * not be construed as granting a license to any other intellectual - * property including but not limited to intellectual property relating - * to a hardware implementation of the functionality of the software - * licensed hereunder. You may use the software subject to the license - * terms below provided that you ensure that this notice is replicated - * unmodified and in its entirety in all distributions of the software, - * modified or unmodified, in source code or in binary form. - * - * Copyright (c) 2003-2005,2014 The Regents of The University of Michigan +/** + * Copyright (c) 2018 Inria * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -37,42 +25,60 @@ * (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: Erik Hallnor + * Authors: Daniel Carvalho */ /** * @file - * Declaration of a LRU tag store. - * The LRU tags guarantee that the true least-recently-used way in - * a set will always be evicted. + * Declaration of a Least Recently Used replacement policy. + * The victim is chosen using the timestamp. The timestamp may be true or + * pseudo, depending on the quantity of bits allocated for that. */ -#ifndef __MEM_CACHE_TAGS_LRU_HH__ -#define __MEM_CACHE_TAGS_LRU_HH__ +#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_LRU_RP_HH__ +#define __MEM_CACHE_REPLACEMENT_POLICIES_LRU_RP_HH__ -#include "mem/cache/tags/base_set_assoc.hh" -#include "params/LRU.hh" +#include "mem/cache/replacement_policies/base.hh" +#include "params/LRURP.hh" -class LRU : public BaseSetAssoc +class LRURP : public BaseReplacementPolicy { public: /** Convenience typedef. */ - typedef LRUParams Params; + typedef LRURPParams Params; + + /** + * Construct and initiliaze this replacement policy. + */ + LRURP(const Params *p); + + /** + * Destructor. + */ + ~LRURP() {} /** - * Construct and initialize this tag store. + * Touch a block to update its last touch tick. + * + * @param blk Cache block to be touched. */ - LRU(const Params *p); + void touch(CacheBlk *blk); /** - * Destructor + * Reset replacement data for a block. Used when a block is inserted. + * Sets its last touch tick as the current tick. + * + * @param blk Cache block to be reset. */ - ~LRU() {} + void reset(CacheBlk *blk); - CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat) override; - CacheBlk* findVictim(Addr addr) override; - void insertBlock(PacketPtr pkt, BlkType *blk) override; - void invalidate(CacheBlk *blk) override; + /** + * Find replacement victim using LRU timestamps. + * + * @param candidates Replacement candidates, selected by indexing policy. + * @return Cache block to be replaced. + */ + CacheBlk* getVictim(const ReplacementCandidates& candidates) override; }; -#endif // __MEM_CACHE_TAGS_LRU_HH__ +#endif // __MEM_CACHE_REPLACEMENT_POLICIES_LRU_RP_HH__ diff --git a/src/mem/cache/replacement_policies/random_rp.cc b/src/mem/cache/replacement_policies/random_rp.cc new file mode 100644 index 000000000..1c54bdac6 --- /dev/null +++ b/src/mem/cache/replacement_policies/random_rp.cc @@ -0,0 +1,71 @@ +/** + * 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 + */ + +#include "mem/cache/replacement_policies/random_rp.hh" + +#include "base/random.hh" +#include "debug/CacheRepl.hh" + +RandomRP::RandomRP(const Params *p) + : BaseReplacementPolicy(p) +{ +} + +CacheBlk* +RandomRP::getVictim(const ReplacementCandidates& candidates) +{ + // 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, + candidates.size() - 1)]; + + // Visit all candidates to find an invalid entry + for (const auto& candidate : candidates) { + // Give priority to victimise invalid entries + if (!candidate->isValid()){ + blk = 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 blk; +} + +RandomRP* +RandomRPParams::create() +{ + return new RandomRP(this); +} diff --git a/src/mem/cache/tags/random_repl.hh b/src/mem/cache/replacement_policies/random_rp.hh index 71b2f5ce6..338b26ff2 100644 --- a/src/mem/cache/tags/random_repl.hh +++ b/src/mem/cache/replacement_policies/random_rp.hh @@ -1,17 +1,5 @@ -/* - * Copyright (c) 2017 ARM Limited - * All rights reserved. - * - * The license below extends only to copyright in the software and shall - * not be construed as granting a license to any other intellectual - * property including but not limited to intellectual property relating - * to a hardware implementation of the functionality of the software - * licensed hereunder. You may use the software subject to the license - * terms below provided that you ensure that this notice is replicated - * unmodified and in its entirety in all distributions of the software, - * modified or unmodified, in source code or in binary form. - * - * Copyright (c) 2014 The Regents of The University of Michigan +/** + * Copyright (c) 2018 Inria * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -37,42 +25,43 @@ * (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: Anthony Gutierrez + * Authors: Daniel Carvalho */ /** * @file - * Declaration of a random replacement tag store. - * The RandomRepl tags first try to evict an invalid - * block. If no invalid blocks are found, a candidate - * for eviction is found at random. + * Declaration of a random replacement policy. + * The victim is chosen at random, if there are no invalid entries. */ -#ifndef __MEM_CACHE_TAGS_RANDOM_REPL_HH__ -#define __MEM_CACHE_TAGS_RANDOM_REPL_HH__ +#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_RANDOM_RP_HH__ +#define __MEM_CACHE_REPLACEMENT_POLICIES_RANDOM_RP_HH__ -#include "mem/cache/tags/base_set_assoc.hh" -#include "params/RandomRepl.hh" +#include "mem/cache/replacement_policies/base.hh" +#include "params/RandomRP.hh" -class RandomRepl : public BaseSetAssoc +class RandomRP : public BaseReplacementPolicy { public: /** Convenience typedef. */ - typedef RandomReplParams Params; + typedef RandomRPParams Params; /** - * Construct and initiliaze this tag store. + * Construct and initiliaze this replacement policy. */ - RandomRepl(const Params *p); + RandomRP(const Params *p); /** - * Destructor + * Destructor. */ - ~RandomRepl() {} + ~RandomRP() {} - CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat); - CacheBlk* findVictim(Addr addr); - void insertBlock(PacketPtr pkt, BlkType *blk); + /** + * Find replacement victim at random. + * @param candidates Replacement candidates, selected by indexing policy. + * @return Cache block to be replaced. + */ + CacheBlk* getVictim(const ReplacementCandidates& candidates) override; }; -#endif // __MEM_CACHE_TAGS_RANDOM_REPL_HH__ +#endif // __MEM_CACHE_REPLACEMENT_POLICIES_RANDOM_RP_HH__ diff --git a/src/mem/cache/tags/SConscript b/src/mem/cache/tags/SConscript index 1412286a7..9758b566e 100644 --- a/src/mem/cache/tags/SConscript +++ b/src/mem/cache/tags/SConscript @@ -34,6 +34,4 @@ SimObject('Tags.py') Source('base.cc') Source('base_set_assoc.cc') -Source('lru.cc') -Source('random_repl.cc') Source('fa_lru.cc') diff --git a/src/mem/cache/tags/Tags.py b/src/mem/cache/tags/Tags.py index b19010f52..ff4eff44e 100644 --- a/src/mem/cache/tags/Tags.py +++ b/src/mem/cache/tags/Tags.py @@ -66,19 +66,12 @@ class BaseTags(ClockedObject): class BaseSetAssoc(BaseTags): type = 'BaseSetAssoc' - abstract = True cxx_header = "mem/cache/tags/base_set_assoc.hh" assoc = Param.Int(Parent.assoc, "associativity") -class LRU(BaseSetAssoc): - type = 'LRU' - cxx_class = 'LRU' - cxx_header = "mem/cache/tags/lru.hh" - -class RandomRepl(BaseSetAssoc): - type = 'RandomRepl' - cxx_class = 'RandomRepl' - cxx_header = "mem/cache/tags/random_repl.hh" + # Get replacement policy from the parent (cache) + replacement_policy = Param.BaseReplacementPolicy( + Parent.replacement_policy, "Replacement policy") class FALRU(BaseTags): type = 'FALRU' diff --git a/src/mem/cache/tags/base.hh b/src/mem/cache/tags/base.hh index 9e7242c1b..74fc7e0d0 100644 --- a/src/mem/cache/tags/base.hh +++ b/src/mem/cache/tags/base.hh @@ -54,6 +54,7 @@ #include "base/callback.hh" #include "base/statistics.hh" #include "mem/cache/blk.hh" +#include "mem/cache/replacement_policies/base.hh" #include "params/BaseTags.hh" #include "sim/clocked_object.hh" @@ -249,6 +250,14 @@ class BaseTags : public ClockedObject occupancies[blk->srcMasterId]--; } + /** + * Find replacement victim based on address. + * + * @param addr Address to find a victim for. + * @return Cache block to be replaced. + */ + virtual CacheBlk* findVictim(Addr addr) = 0; + virtual CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat) = 0; virtual Addr extractTag(Addr addr) const = 0; @@ -263,8 +272,6 @@ class BaseTags : public ClockedObject */ virtual Addr regenerateBlkAddr(const CacheBlk* blk) const = 0; - virtual CacheBlk* findVictim(Addr addr) = 0; - virtual int extractSet(Addr addr) const = 0; virtual void forEachBlk(CacheBlkVisitor &visitor) = 0; diff --git a/src/mem/cache/tags/base_set_assoc.cc b/src/mem/cache/tags/base_set_assoc.cc index 61764fe91..2475e6fc0 100644 --- a/src/mem/cache/tags/base_set_assoc.cc +++ b/src/mem/cache/tags/base_set_assoc.cc @@ -60,7 +60,8 @@ BaseSetAssoc::BaseSetAssoc(const Params *p) dataBlks(new uint8_t[p->size]), // Allocate data storage in one big chunk numSets(p->size / (p->block_size * p->assoc)), sequentialAccess(p->sequential_access), - sets(p->size / (p->block_size * p->assoc)) + sets(p->size / (p->block_size * p->assoc)), + replacementPolicy(p->replacement_policy) { // Check parameters if (blkSize < 4 || !isPowerOf2(blkSize)) { @@ -184,3 +185,9 @@ BaseSetAssoc::computeStats() } } } + +BaseSetAssoc * +BaseSetAssocParams::create() +{ + return new BaseSetAssoc(this); +} diff --git a/src/mem/cache/tags/base_set_assoc.hh b/src/mem/cache/tags/base_set_assoc.hh index 1fd739110..f7b386a92 100644 --- a/src/mem/cache/tags/base_set_assoc.hh +++ b/src/mem/cache/tags/base_set_assoc.hh @@ -64,14 +64,9 @@ * A BaseSetAssoc cache tag store. * @sa \ref gem5MemorySystem "gem5 Memory System" * - * The BaseSetAssoc tags provide a base, as well as the functionality - * common to any set associative tags. Any derived class must implement - * the methods related to the specifics of the actual replacment policy. - * These are: - * - * BlkType* accessBlock(); - * BlkType* findVictim(); - * void insertBlock(); + * The BaseSetAssoc placement policy divides the cache into s sets of w + * cache lines (ways). A cache line is mapped onto a set, and can be placed + * into any of the ways of this set. */ class BaseSetAssoc : public BaseTags { @@ -109,7 +104,10 @@ class BaseSetAssoc : public BaseTags /** Mask out all bits that aren't part of the set index. */ unsigned setMask; -public: + /** Replacement policy */ + BaseReplacementPolicy *replacementPolicy; + + public: /** Convenience typedef. */ typedef BaseSetAssocParams Params; @@ -169,7 +167,9 @@ public: lat = cache->ticksToCycles(blk->whenReady - curTick()) + accessLatency; } - blk->refCount += 1; + + // Update replacement data of accessed block + replacementPolicy->touch(blk); } else { // If a cache miss lat = lookupLatency; @@ -189,25 +189,29 @@ public: CacheBlk* findBlock(Addr addr, bool is_secure) const override; /** - * Find an invalid block to evict for the address provided. - * If there are no invalid blocks, this will return the block - * in the least-recently-used position. - * @param addr The addr to a find a replacement candidate for. - * @return The candidate block. + * Find replacement victim based on address. + * + * @param addr Address to find a victim for. + * @return Cache block to be replaced. */ CacheBlk* findVictim(Addr addr) override { - BlkType *blk = nullptr; - int set = extractSet(addr); - - // prefer to evict an invalid block - for (int i = 0; i < allocAssoc; ++i) { - blk = sets[set].blks[i]; - if (!blk->isValid()) - break; - } + // Choose replacement victim from replacement candidates + return replacementPolicy->getVictim(getPossibleLocations(addr)); + } - return blk; + /** + * Find all possible block locations for insertion and replacement of + * an address. Should be called immediately before ReplacementPolicy's + * findVictim() not to break cache resizing. + * Returns blocks in all ways belonging to the set of the address. + * + * @param addr The addr to a find possible locations for. + * @return The possible locations. + */ + const std::vector<CacheBlk*> getPossibleLocations(Addr addr) + { + return sets[extractSet(addr)].blks; } /** @@ -242,9 +246,8 @@ public: } // Previous block, if existed, has been removed, and now we have - // to insert the new one and mark it as touched + // to insert the new one tagsInUse++; - blk->isTouched = true; // Set tag for new block. Caller is responsible for setting status. blk->tag = extractTag(addr); @@ -254,11 +257,12 @@ public: occupancies[master_id]++; blk->srcMasterId = master_id; blk->task_id = task_id; - blk->tickInserted = curTick(); // We only need to write into one tag and one data block. tagAccesses += 1; dataAccesses += 1; + + replacementPolicy->reset(blk); } /** diff --git a/src/mem/cache/tags/fa_lru.cc b/src/mem/cache/tags/fa_lru.cc index d40398975..a38d0bf34 100644 --- a/src/mem/cache/tags/fa_lru.cc +++ b/src/mem/cache/tags/fa_lru.cc @@ -98,7 +98,6 @@ FALRU::FALRU(const Params *p) } blks[i].prev = &(blks[i-1]); blks[i].next = &(blks[i+1]); - blks[i].isTouched = false; blks[i].set = 0; blks[i].way = i; } @@ -255,13 +254,13 @@ FALRU::findVictim(Addr addr) replacements[0]++; } else { tagsInUse++; - blk->isTouched = true; if (!warmedUp && tagsInUse.value() >= warmupBound) { warmedUp = true; warmupCycle = curTick(); } } //assert(check()); + return blk; } diff --git a/src/mem/cache/tags/fa_lru.hh b/src/mem/cache/tags/fa_lru.hh index 559f56e28..7f3f99ae0 100644 --- a/src/mem/cache/tags/fa_lru.hh +++ b/src/mem/cache/tags/fa_lru.hh @@ -67,8 +67,6 @@ public: FALRUBlk *prev; /** The next block in LRU order. */ FALRUBlk *next; - /** Has this block been touched? */ - bool isTouched; /** * A bit mask of the sizes of cache that this block is resident in. @@ -204,9 +202,10 @@ public: CacheBlk* findBlock(Addr addr, bool is_secure) const override; /** - * Find a replacement block for the address provided. - * @param pkt The request to a find a replacement candidate for. - * @return The block to place the replacement in. + * Find replacement victim based on address. + * + * @param addr Address to find a victim for. + * @return Cache block to be replaced. */ CacheBlk* findVictim(Addr addr) override; diff --git a/src/mem/cache/tags/lru.cc b/src/mem/cache/tags/lru.cc deleted file mode 100644 index 4302a8de6..000000000 --- a/src/mem/cache/tags/lru.cc +++ /dev/null @@ -1,120 +0,0 @@ -/* - * Copyright (c) 2012-2013 ARM Limited - * All rights reserved. - * - * The license below extends only to copyright in the software and shall - * not be construed as granting a license to any other intellectual - * property including but not limited to intellectual property relating - * to a hardware implementation of the functionality of the software - * licensed hereunder. You may use the software subject to the license - * terms below provided that you ensure that this notice is replicated - * unmodified and in its entirety in all distributions of the software, - * modified or unmodified, in source code or in binary form. - * - * Copyright (c) 2003-2005,2014 The Regents of The University of Michigan - * 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: Erik Hallnor - */ - -/** - * @file - * Definitions of a LRU tag store. - */ - -#include "mem/cache/tags/lru.hh" - -#include "debug/CacheRepl.hh" -#include "mem/cache/base.hh" - -LRU::LRU(const Params *p) - : BaseSetAssoc(p) -{ -} - -CacheBlk* -LRU::accessBlock(Addr addr, bool is_secure, Cycles &lat) -{ - CacheBlk *blk = BaseSetAssoc::accessBlock(addr, is_secure, lat); - - if (blk != nullptr) { - // move this block to head of the MRU list - sets[blk->set].moveToHead(blk); - DPRINTF(CacheRepl, "set %x: moving blk %x (%s) to MRU\n", - blk->set, regenerateBlkAddr(blk), - is_secure ? "s" : "ns"); - } - - return blk; -} - -CacheBlk* -LRU::findVictim(Addr addr) -{ - int set = extractSet(addr); - // grab a replacement candidate - BlkType *blk = nullptr; - for (int i = assoc - 1; i >= 0; i--) { - BlkType *b = sets[set].blks[i]; - if (b->way < allocAssoc) { - blk = b; - break; - } - } - assert(!blk || blk->way < allocAssoc); - - if (blk && blk->isValid()) { - DPRINTF(CacheRepl, "set %x: selecting blk %x for replacement\n", - set, regenerateBlkAddr(blk)); - } - - return blk; -} - -void -LRU::insertBlock(PacketPtr pkt, BlkType *blk) -{ - BaseSetAssoc::insertBlock(pkt, blk); - - int set = extractSet(pkt->getAddr()); - sets[set].moveToHead(blk); -} - -void -LRU::invalidate(CacheBlk *blk) -{ - BaseSetAssoc::invalidate(blk); - - // should be evicted before valid blocks - int set = blk->set; - sets[set].moveToTail(blk); -} - -LRU* -LRUParams::create() -{ - return new LRU(this); -} diff --git a/src/mem/cache/tags/random_repl.cc b/src/mem/cache/tags/random_repl.cc deleted file mode 100644 index aa5f6fcb9..000000000 --- a/src/mem/cache/tags/random_repl.cc +++ /dev/null @@ -1,105 +0,0 @@ -/* - * Copyright (c) 2017 ARM Limited - * All rights reserved. - * - * The license below extends only to copyright in the software and shall - * not be construed as granting a license to any other intellectual - * property including but not limited to intellectual property relating - * to a hardware implementation of the functionality of the software - * licensed hereunder. You may use the software subject to the license - * terms below provided that you ensure that this notice is replicated - * unmodified and in its entirety in all distributions of the software, - * modified or unmodified, in source code or in binary form. - * - * Copyright (c) 2014 The Regents of The University of Michigan - * Copyright (c) 2016 ARM Limited - * 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: Anthony Gutierrez - */ - -/** - * @file - * Definitions of a random replacement tag store. - */ - -#include "mem/cache/tags/random_repl.hh" - -#include "base/random.hh" -#include "debug/CacheRepl.hh" -#include "mem/cache/base.hh" - -RandomRepl::RandomRepl(const Params *p) - : BaseSetAssoc(p) - -{ -} - -CacheBlk* -RandomRepl::accessBlock(Addr addr, bool is_secure, Cycles &lat) -{ - return BaseSetAssoc::accessBlock(addr, is_secure, lat); -} - -CacheBlk* -RandomRepl::findVictim(Addr addr) -{ - CacheBlk *blk = BaseSetAssoc::findVictim(addr); - unsigned set = extractSet(addr); - - // if all blocks are valid, pick a replacement at random - if (blk && blk->isValid()) { - // find a random index within the bounds of the set - int idx = random_mt.random<int>(0, assoc - 1); - blk = sets[set].blks[idx]; - // Enforce allocation limit - while (blk->way >= allocAssoc) { - idx = (idx + 1) % assoc; - blk = sets[set].blks[idx]; - } - - assert(idx < assoc); - assert(idx >= 0); - assert(blk->way < allocAssoc); - - DPRINTF(CacheRepl, "set %x: selecting blk %x for replacement\n", - blk->set, regenerateBlkAddr(blk)); - } - - return blk; -} - -void -RandomRepl::insertBlock(PacketPtr pkt, BlkType *blk) -{ - BaseSetAssoc::insertBlock(pkt, blk); -} - -RandomRepl* -RandomReplParams::create() -{ - return new RandomRepl(this); -} |