Daniel Carvalho has submitted this change. (
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]>
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/37897
Tested-by: kokoro <[email protected]>
---
M src/mem/cache/replacement_policies/ReplacementPolicies.py
M src/mem/cache/replacement_policies/SConscript
A src/mem/cache/replacement_policies/dueling_rp.cc
A src/mem/cache/replacement_policies/dueling_rp.hh
4 files changed, 290 insertions(+), 0 deletions(-)
Approvals:
Daniel Carvalho: Looks good to me, approved; Looks good to me, approved
kokoro: Regressions pass
diff --git a/src/mem/cache/replacement_policies/ReplacementPolicies.py
b/src/mem/cache/replacement_policies/ReplacementPolicies.py
index 8b308b4..74709f2 100644
--- a/src/mem/cache/replacement_policies/ReplacementPolicies.py
+++ b/src/mem/cache/replacement_policies/ReplacementPolicies.py
@@ -34,6 +34,20 @@
cxx_class = 'replacement_policy::Base'
cxx_header = "mem/cache/replacement_policies/base.hh"
+class DuelingRP(BaseReplacementPolicy):
+ type = 'DuelingRP'
+ cxx_class = 'replacement_policy::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 = 'replacement_policy::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/dueling_rp.cc
b/src/mem/cache/replacement_policies/dueling_rp.cc
new file mode 100644
index 0000000..fc717a3
--- /dev/null
+++ b/src/mem/cache/replacement_policies/dueling_rp.cc
@@ -0,0 +1,164 @@
+/**
+ * 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 replacement_policy
+{
+
+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(const ReplacementCandidates& candidates) const
+{
+ // This function assumes that all candidates are either part of the
same
+ // sampled set, or are not samples.
+ // @todo This should be improved at some point.
+ panic_if(candidates.size() != params().team_size, "We currently only "
+ "support team sizes that match the number of replacement
candidates");
+
+ // 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.
+ 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.
+ // This assumes that A's team is "false", and B's team is "true".
+ bool team_a;
+ if ((is_sample && !team) || (!is_sample && !winner)) {
+ duelingStats.selectedA++;
+ team_a = true;
+ } else {
+ duelingStats.selectedB++;
+ team_a = false;
+ }
+
+ // Create a temporary list of replacement candidates which re-routes
the
+ // replacement data of the selected team
+ std::vector<std::shared_ptr<ReplacementData>> dueling_replacement_data;
+ for (auto& candidate : candidates) {
+ std::shared_ptr<DuelerReplData> dueler_repl_data =
+ std::static_pointer_cast<DuelerReplData>(
+ candidate->replacementData);
+
+ // As of now we assume that all candidates are either part of
+ // the same sampled team, or are not samples.
+ bool candidate_team;
+ panic_if(
+ duelingMonitor.isSample(dueler_repl_data.get(),
candidate_team) &&
+ (team != candidate_team),
+ "Not all sampled candidates belong to the same team");
+
+ // Copy the original entry's data, re-routing its replacement data
+ // to the selected one
+ dueling_replacement_data.push_back(dueler_repl_data);
+ candidate->replacementData = team_a ? dueler_repl_data->replDataA :
+ dueler_repl_data->replDataB;
+ }
+
+ // Use the selected replacement policy to find the victim
+ ReplaceableEntry* victim = team_a ?
replPolicyA->getVictim(candidates) :
+ replPolicyB->getVictim(candidates);
+
+ // Search for entry within the original candidates and clean-up
duplicates
+ for (int i = 0; i < candidates.size(); i++) {
+ candidates[i]->replacementData = dueling_replacement_data[i];
+ }
+
+ return victim;
+}
+
+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(statistics::Group* parent)
+ : statistics::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 replacement_policy
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..23b4378
--- /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/compiler.hh"
+#include "base/statistics.hh"
+#include "mem/cache/replacement_policies/base.hh"
+#include "mem/cache/tags/dueling.hh"
+
+struct DuelingRPParams;
+
+GEM5_DEPRECATED_NAMESPACE(ReplacementPolicy, replacement_policy);
+namespace replacement_policy
+{
+
+/**
+ * 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 statistics::Group
+ {
+ DuelingStats(statistics::Group* parent);
+
+ /** Number of times A was selected on victimization. */
+ statistics::Scalar selectedA;
+
+ /** Number of times B was selected on victimization. */
+ statistics::Scalar selectedB;
+ } duelingStats;
+
+ public:
+ PARAMS(DuelingRP);
+ 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 ReplacementCandidates& candidates)
const
+
override;
+ std::shared_ptr<ReplacementData> instantiateEntry() override;
+};
+
+} // namespace replacement_policy
+
+#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: 8
Gerrit-Owner: Daniel Carvalho <[email protected]>
Gerrit-Reviewer: Bobby R. Bruce <[email protected]>
Gerrit-Reviewer: Daniel Carvalho <[email protected]>
Gerrit-Reviewer: Nikos Nikoleris <[email protected]>
Gerrit-Reviewer: kokoro <[email protected]>
Gerrit-MessageType: merged
_______________________________________________
gem5-dev mailing list -- [email protected]
To unsubscribe send an email to [email protected]
%(web_page_url)slistinfo%(cgiext)s/%(_internal_name)s
