Daniel Carvalho has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/37897 )
Change subject: mem-cache: Implement a dueling Replacement Policy
......................................................................
mem-cache: Implement a dueling Replacement Policy
Implement a template dueling replacement policy which monitors
two replacement policies to decide and select the one that
provides the least amount of misses.
Change-Id: I6a6e96a9388cce8f8c8cd7b9c1dbe9f0554ccc64
Signed-off-by: Daniel R. Carvalho <[email protected]>
---
M src/mem/cache/replacement_policies/ReplacementPolicies.py
M src/mem/cache/replacement_policies/SConscript
M src/mem/cache/replacement_policies/base.hh
A src/mem/cache/replacement_policies/dueling_rp.cc
A src/mem/cache/replacement_policies/dueling_rp.hh
5 files changed, 273 insertions(+), 1 deletion(-)
diff --git a/src/mem/cache/replacement_policies/ReplacementPolicies.py
b/src/mem/cache/replacement_policies/ReplacementPolicies.py
index 06a4909..14ce51e 100644
--- a/src/mem/cache/replacement_policies/ReplacementPolicies.py
+++ b/src/mem/cache/replacement_policies/ReplacementPolicies.py
@@ -34,6 +34,20 @@
cxx_class = 'ReplacementPolicy::Base'
cxx_header = "mem/cache/replacement_policies/base.hh"
+class DuelingRP(BaseReplacementPolicy):
+ type = 'DuelingRP'
+ cxx_class = 'ReplacementPolicy::Dueling'
+ cxx_header = "mem/cache/replacement_policies/dueling_rp.hh"
+
+ constituency_size = Param.Unsigned(
+ "The size of a region containing one sample")
+ team_size = Param.Unsigned(
+ "Number of entries in a sampling set that belong to a team")
+ replacement_policy_a = Param.BaseReplacementPolicy(
+ "Sub-replacement policy A")
+ replacement_policy_b = Param.BaseReplacementPolicy(
+ "Sub-replacement policy B")
+
class FIFORP(BaseReplacementPolicy):
type = 'FIFORP'
cxx_class = 'ReplacementPolicy::FIFO'
diff --git a/src/mem/cache/replacement_policies/SConscript
b/src/mem/cache/replacement_policies/SConscript
index 2537d22..29152a0 100644
--- a/src/mem/cache/replacement_policies/SConscript
+++ b/src/mem/cache/replacement_policies/SConscript
@@ -32,6 +32,7 @@
Source('bip_rp.cc')
Source('brrip_rp.cc')
+Source('dueling_rp.cc')
Source('fifo_rp.cc')
Source('lfu_rp.cc')
Source('lru_rp.cc')
diff --git a/src/mem/cache/replacement_policies/base.hh
b/src/mem/cache/replacement_policies/base.hh
index 61bf6e8..d5673ec 100644
--- a/src/mem/cache/replacement_policies/base.hh
+++ b/src/mem/cache/replacement_policies/base.hh
@@ -39,12 +39,16 @@
namespace ReplacementPolicy {
+class Dueling;
+
/**
* A common base class of cache replacement policy objects.
*/
class Base : public SimObject
{
protected:
+ friend Dueling;
+
/**
* Replacement candidates as chosen by the indexing policy. Although
* the entry contains its replacemnt data, when using dynamic sampling
@@ -126,7 +130,7 @@
* @param candidates Replacement candidates, selected by indexing
policy.
* @return Replacement entry to be replaced.
*/
- ReplaceableEntry*
+ virtual ReplaceableEntry*
getVictim(const std::vector<ReplaceableEntry*>& candidates) const
{
ReplacementCandidates replacement_candidates;
diff --git a/src/mem/cache/replacement_policies/dueling_rp.cc
b/src/mem/cache/replacement_policies/dueling_rp.cc
new file mode 100644
index 0000000..59c8990
--- /dev/null
+++ b/src/mem/cache/replacement_policies/dueling_rp.cc
@@ -0,0 +1,142 @@
+/**
+ * Copyright (c) 2019, 2020 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.
+ */
+
+#include "mem/cache/replacement_policies/dueling_rp.hh"
+
+#include "base/logging.hh"
+#include "params/DuelingRP.hh"
+
+namespace ReplacementPolicy {
+
+Dueling::Dueling(const Params &p)
+ : Base(p), replPolicyA(p.replacement_policy_a),
+ replPolicyB(p.replacement_policy_b),
+ duelingMonitor(p.constituency_size, p.team_size),
+ duelingStats(this)
+{
+ fatal_if((replPolicyA == nullptr) || (replPolicyB == nullptr),
+ "All replacement policies must be instantiated");
+}
+
+void
+Dueling::invalidate(
+ const std::shared_ptr<ReplacementData>& replacement_data) const
+{
+ std::shared_ptr<DuelerReplData> casted_replacement_data =
+ std::static_pointer_cast<DuelerReplData>(replacement_data);
+ replPolicyA->invalidate(casted_replacement_data->replDataA);
+ replPolicyB->invalidate(casted_replacement_data->replDataB);
+}
+
+void
+Dueling::touch(const std::shared_ptr<ReplacementData>& replacement_data)
const
+{
+ std::shared_ptr<DuelerReplData> casted_replacement_data =
+ std::static_pointer_cast<DuelerReplData>(replacement_data);
+ replPolicyA->touch(casted_replacement_data->replDataA);
+ replPolicyB->touch(casted_replacement_data->replDataB);
+}
+
+void
+Dueling::reset(const std::shared_ptr<ReplacementData>& replacement_data)
const
+{
+ std::shared_ptr<DuelerReplData> casted_replacement_data =
+ std::static_pointer_cast<DuelerReplData>(replacement_data);
+ replPolicyA->reset(casted_replacement_data->replDataA);
+ replPolicyB->reset(casted_replacement_data->replDataB);
+
+ // A miss in a set is a sample to the duel. A call to this function
+ // implies in the replacement of an entry, which was either caused by
+ // a miss, an external invalidation, or the initialization of the table
+ // entry (when warming up)
+
duelingMonitor.sample(static_cast<Dueler*>(casted_replacement_data.get()));
+}
+
+ReplaceableEntry*
+Dueling::getVictim(ReplacementCandidates& candidates) const
+{
+ panic("This function should not be called");
+ return nullptr;
+}
+
+ReplaceableEntry*
+Dueling::getVictim(const std::vector<ReplaceableEntry*>& candidates) const
+{
+ // The team with the most misses loses
+ bool winner = !duelingMonitor.getWinner();
+
+ // If the entry is a sample, it can only be used with a certain policy.
+ // This assumes that all candidates are either part of the same sampled
+ // set, or are not samples.
+ bool team;
+ bool is_sample = duelingMonitor.isSample(static_cast<Dueler*>(
+ std::static_pointer_cast<DuelerReplData>(
+ candidates[0]->replacementData).get()), team);
+
+ // All replacement candidates must be set appropriately, so that the
+ // proper replacement data is used. A replacement policy X must be used
+ // if the candidates are its samples - in which case they must always
+ // use X - or if it is not a sample, and X is currently the best RP
+ if ((is_sample && team) || (!is_sample && winner)) {
+ duelingStats.selectedA++;
+ ReplacementCandidates candidates_a;
+ for (auto& candidate : candidates) {
+ auto repl_data = std::static_pointer_cast<DuelerReplData>(
+ candidate->replacementData)->replDataA;
+ candidates_a.push_back(ReplacementCandidate(repl_data,
candidate));
+ }
+ return replPolicyA->getVictim(candidates_a);
+ } else {
+ duelingStats.selectedB++;
+ ReplacementCandidates candidates_b;
+ for (auto& candidate : candidates) {
+ auto repl_data = std::static_pointer_cast<DuelerReplData>(
+ candidate->replacementData)->replDataB;
+ candidates_b.push_back(ReplacementCandidate(repl_data,
candidate));
+ }
+ return replPolicyB->getVictim(candidates_b);
+ }
+}
+
+std::shared_ptr<ReplacementData>
+Dueling::instantiateEntry()
+{
+ DuelerReplData* replacement_data = new DuelerReplData(
+ replPolicyA->instantiateEntry(), replPolicyB->instantiateEntry());
+ duelingMonitor.initEntry(static_cast<Dueler*>(replacement_data));
+ return std::shared_ptr<DuelerReplData>(replacement_data);
+}
+
+Dueling::DuelingStats::DuelingStats(Stats::Group* parent)
+ : Stats::Group(parent),
+ ADD_STAT(selectedA, "Number of times A was selected to victimize"),
+ ADD_STAT(selectedB, "Number of times B was selected to victimize")
+{
+}
+
+} // namespace ReplacementPolicy
diff --git a/src/mem/cache/replacement_policies/dueling_rp.hh
b/src/mem/cache/replacement_policies/dueling_rp.hh
new file mode 100644
index 0000000..55627bf
--- /dev/null
+++ b/src/mem/cache/replacement_policies/dueling_rp.hh
@@ -0,0 +1,111 @@
+/**
+ * Copyright (c) 2019, 2020 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.
+ */
+
+#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_DUELING_RP_HH__
+#define __MEM_CACHE_REPLACEMENT_POLICIES_DUELING_RP_HH__
+
+#include <memory>
+
+#include "base/dueling.hh"
+#include "base/statistics.hh"
+#include "mem/cache/replacement_policies/base.hh"
+
+struct DuelingRPParams;
+
+namespace ReplacementPolicy {
+
+/**
+ * This replacement policy duels two replacement policies to find out which
+ * one provides the best results. A policy is said to have the best results
+ * when it has a lower number of misses.
+ */
+class Dueling : public Base
+{
+ protected:
+ /**
+ * Dueler-specific implementation of replacement data. Contains all
+ * sub-replacement policies' replacement data.
+ */
+ struct DuelerReplData : ReplacementData, Dueler
+ {
+ std::shared_ptr<ReplacementData> replDataA;
+ std::shared_ptr<ReplacementData> replDataB;
+
+ /** Default constructor. Initialize sub-replacement data. */
+ DuelerReplData(const std::shared_ptr<ReplacementData>& repl_data_a,
+ const std::shared_ptr<ReplacementData>& repl_data_b)
+ : ReplacementData(), Dueler(), replDataA(repl_data_a),
+ replDataB(repl_data_b)
+ {
+ }
+ };
+
+ /** Sub-replacement policy used in this multiple container. */
+ Base* const replPolicyA;
+ /** Sub-replacement policy used in this multiple container. */
+ Base* const replPolicyB;
+
+ /**
+ * A dueling monitor that decides which is the best sub-policy based on
+ * their number of misses.
+ */
+ mutable DuelingMonitor duelingMonitor;
+
+ mutable struct DuelingStats : public Stats::Group
+ {
+ DuelingStats(Stats::Group* parent);
+
+ /** Number of times A was selected on victimization. */
+ Stats::Scalar selectedA;
+
+ /** Number of times B was selected on victimization. */
+ Stats::Scalar selectedB;
+ } duelingStats;
+
+ ReplaceableEntry* getVictim(ReplacementCandidates& candidates) const
+ override;
+
+ public:
+ typedef DuelingRPParams Params;
+ Dueling(const Params &p);
+ ~Dueling() = default;
+
+ void invalidate(const std::shared_ptr<ReplacementData>&
replacement_data)
+ const
override;
+ void touch(const std::shared_ptr<ReplacementData>& replacement_data)
const
+
override;
+ void reset(const std::shared_ptr<ReplacementData>& replacement_data)
const
+
override;
+ ReplaceableEntry* getVictim(
+ const std::vector<ReplaceableEntry*>& candidates) const override;
+ std::shared_ptr<ReplacementData> instantiateEntry() override;
+};
+
+} // namespace ReplacementPolicy
+
+#endif // __MEM_CACHE_REPLACEMENT_POLICIES_DUELING_RP_HH__
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/37897
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: develop
Gerrit-Change-Id: I6a6e96a9388cce8f8c8cd7b9c1dbe9f0554ccc64
Gerrit-Change-Number: 37897
Gerrit-PatchSet: 1
Gerrit-Owner: Daniel Carvalho <[email protected]>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list -- [email protected]
To unsubscribe send an email to [email protected]
%(web_page_url)slistinfo%(cgiext)s/%(_internal_name)s
