summaryrefslogtreecommitdiff
path: root/src/mem
diff options
context:
space:
mode:
authorDaniel R. Carvalho <odanrc@yahoo.com.br>2018-02-19 15:13:11 +0100
committerDaniel Carvalho <odanrc@yahoo.com.br>2018-03-22 14:50:23 +0000
commitd207e9ccee411877fdeac80bb68a27900560f50f (patch)
tree120810cf72c52ed5df29436552e06f1fb11aa5ce /src/mem
parent0473286ab1e9992a906eff380000bf90c82eeccb (diff)
downloadgem5-d207e9ccee411877fdeac80bb68a27900560f50f.tar.xz
mem-cache: Split array indexing and replacement policies.
Replacement policies (LRU, Random) are currently considered as array indexing methods, but have completely different functionalities: - Array indexers determine the possible locations for block allocation. This information is used to generate replacement candidates when conflicts happen. - Replacement policies determine which of the replacement candidates should be evicted to make room for new allocations. For this reason, they were split into different classes. Advantages: - Easier and more straightforward to implement other replacement policies (RRIP, LFU, ARC, ...) - Allow easier future implementation of cache organization schemes As now we can't assure the use of sets, the previous way to create a true LRU is not viable. Now a timestamp_bits parameter controls how many bits are dedicated for the timestamp, and a true LRU can be achieved through an infinite number of bits (although a few bits suffice in practice). Change-Id: I23750db121f1474d17831137e6ff618beb2b3eda Reviewed-on: https://gem5-review.googlesource.com/8501 Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com> Reviewed-by: Jason Lowe-Power <jason@lowepower.com> Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>
Diffstat (limited to 'src/mem')
-rw-r--r--src/mem/cache/Cache.py6
-rw-r--r--src/mem/cache/base.cc2
-rw-r--r--src/mem/cache/blk.hh14
-rw-r--r--src/mem/cache/cache.cc2
-rw-r--r--src/mem/cache/replacement_policies/ReplacementPolicies.py46
-rw-r--r--src/mem/cache/replacement_policies/SConscript37
-rw-r--r--src/mem/cache/replacement_policies/base.cc66
-rw-r--r--src/mem/cache/replacement_policies/base.hh105
-rw-r--r--src/mem/cache/replacement_policies/lru_rp.cc87
-rw-r--r--src/mem/cache/replacement_policies/lru_rp.hh (renamed from src/mem/cache/tags/lru.hh)72
-rw-r--r--src/mem/cache/replacement_policies/random_rp.cc71
-rw-r--r--src/mem/cache/replacement_policies/random_rp.hh (renamed from src/mem/cache/tags/random_repl.hh)55
-rw-r--r--src/mem/cache/tags/SConscript2
-rw-r--r--src/mem/cache/tags/Tags.py13
-rw-r--r--src/mem/cache/tags/base.hh11
-rw-r--r--src/mem/cache/tags/base_set_assoc.cc9
-rw-r--r--src/mem/cache/tags/base_set_assoc.hh60
-rw-r--r--src/mem/cache/tags/fa_lru.cc3
-rw-r--r--src/mem/cache/tags/fa_lru.hh9
-rw-r--r--src/mem/cache/tags/lru.cc120
-rw-r--r--src/mem/cache/tags/random_repl.cc105
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);
-}