Daniel Carvalho has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/38118 )
Change subject: mem-cache: Add Signature-Based Hit Predictor replacement
policy
......................................................................
mem-cache: Add Signature-Based Hit Predictor replacement policy
Add the SHiP Replacement Policy, as described in "SHiP: Signature-
based Hit Predictor for High Performance Caching", by Wu et al.
Instruction Sequence signatures have not been implemented.
Change-Id: I44f00d26eab4c96c9c5bc29740862a87356d30d1
Signed-off-by: Daniel R. Carvalho <oda...@yahoo.com.br>
---
M src/mem/cache/replacement_policies/ReplacementPolicies.py
M src/mem/cache/replacement_policies/SConscript
A src/mem/cache/replacement_policies/ship_rp.cc
A src/mem/cache/replacement_policies/ship_rp.hh
4 files changed, 382 insertions(+), 0 deletions(-)
diff --git a/src/mem/cache/replacement_policies/ReplacementPolicies.py
b/src/mem/cache/replacement_policies/ReplacementPolicies.py
index 22b85b0..61378ab 100644
--- a/src/mem/cache/replacement_policies/ReplacementPolicies.py
+++ b/src/mem/cache/replacement_policies/ReplacementPolicies.py
@@ -108,6 +108,31 @@
btp = 100
num_bits = 1
+class SHiPRP(BRRIPRP):
+ type = 'SHiPRP'
+ abstract = True
+ cxx_class = 'ReplacementPolicy::SHiP'
+ cxx_header = "mem/cache/replacement_policies/ship_rp.hh"
+
+ shct_size = Param.Unsigned(16384, "Number of SHCT entries")
+ # By default any value greater than 0 is enough to change insertion
policy
+ insertion_threshold = Param.Percent(1,
+ "Percentage at which an entry changes insertion policy")
+ # Always make hits mark entries as last to be evicted
+ hit_priority = True
+ # Let the predictor decide when to change insertion policy
+ btp = 0
+
+class SHiPMemRP(SHiPRP):
+ type = 'SHiPMemRP'
+ cxx_class = 'ReplacementPolicy::SHiPMem'
+ cxx_header = "mem/cache/replacement_policies/ship_rp.hh"
+
+class SHiPPCRP(SHiPRP):
+ type = 'SHiPPCRP'
+ cxx_class = 'ReplacementPolicy::SHiPPC'
+ cxx_header = "mem/cache/replacement_policies/ship_rp.hh"
+
class TreePLRURP(BaseReplacementPolicy):
type = 'TreePLRURP'
cxx_class = 'ReplacementPolicy::TreePLRU'
diff --git a/src/mem/cache/replacement_policies/SConscript
b/src/mem/cache/replacement_policies/SConscript
index 29152a0..6370052 100644
--- a/src/mem/cache/replacement_policies/SConscript
+++ b/src/mem/cache/replacement_policies/SConscript
@@ -39,5 +39,6 @@
Source('mru_rp.cc')
Source('random_rp.cc')
Source('second_chance_rp.cc')
+Source('ship_rp.cc')
Source('tree_plru_rp.cc')
Source('weighted_lru_rp.cc')
diff --git a/src/mem/cache/replacement_policies/ship_rp.cc
b/src/mem/cache/replacement_policies/ship_rp.cc
new file mode 100644
index 0000000..eefec43
--- /dev/null
+++ b/src/mem/cache/replacement_policies/ship_rp.cc
@@ -0,0 +1,171 @@
+/**
+ * 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/ship_rp.hh"
+
+#include "base/logging.hh"
+#include "params/SHiPMemRP.hh"
+#include "params/SHiPPCRP.hh"
+#include "params/SHiPRP.hh"
+
+namespace ReplacementPolicy {
+
+SHiP::SHiPReplData::SHiPReplData(int num_bits)
+ : BRRIPReplData(num_bits), signature(0), outcome(false)
+{
+}
+
+SHiP::SignatureType
+SHiP::SHiPReplData::getSignature() const
+{
+ return signature;
+}
+
+void
+SHiP::SHiPReplData::setSignature(SignatureType new_signature)
+{
+ signature = new_signature;
+ outcome = false;
+}
+
+void
+SHiP::SHiPReplData::setReReferenced()
+{
+ outcome = true;
+}
+
+bool
+SHiP::SHiPReplData::wasReReferenced() const
+{
+ return outcome;
+}
+
+SHiP::SHiP(const Params &p)
+ : BRRIP(p), insertionThreshold(p.insertion_threshold / 100.0),
+ SHCT(p.shct_size, SatCounter(numRRPVBits))
+{
+}
+
+void
+SHiP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
+{
+ std::shared_ptr<SHiPReplData> casted_replacement_data =
+ std::static_pointer_cast<SHiPReplData>(replacement_data);
+
+ // The predictor is detrained when an entry that has not been re-
+ // referenced since insertion is invalidated
+ if (casted_replacement_data->wasReReferenced()) {
+ SHCT[casted_replacement_data->getSignature()]--;
+ }
+
+ BRRIP::invalidate(replacement_data);
+}
+
+void
+SHiP::touch(const std::shared_ptr<ReplacementData>& replacement_data,
+ const PacketPtr pkt)
+{
+ std::shared_ptr<SHiPReplData> casted_replacement_data =
+ std::static_pointer_cast<SHiPReplData>(replacement_data);
+
+ // When a hit happens the SHCT entry indexed by the signature is
+ // incremented
+ SHCT[getSignature(pkt)]++;
+ casted_replacement_data->setReReferenced();
+
+ // This was a hit; update replacement data accordingly
+ BRRIP::touch(replacement_data);
+}
+
+void
+SHiP::touch(const std::shared_ptr<ReplacementData>& replacement_data)
+ const
+{
+ panic("Cant train predictor without access information.");
+}
+
+void
+SHiP::reset(const std::shared_ptr<ReplacementData>& replacement_data,
+ const PacketPtr pkt)
+{
+ std::shared_ptr<SHiPReplData> casted_replacement_data =
+ std::static_pointer_cast<SHiPReplData>(replacement_data);
+
+ // Get signature
+ const SignatureType signature = getSignature(pkt);
+
+ // Store signature
+ casted_replacement_data->setSignature(signature);
+
+ // If SHCT for signature is set, predict intermediate re-reference.
+ // Predict distant re-reference otherwise
+ BRRIP::reset(replacement_data);
+ if (SHCT[signature].calcSaturation() >= insertionThreshold) {
+ casted_replacement_data->rrpv--;
+ }
+}
+
+void
+SHiP::reset(const std::shared_ptr<ReplacementData>& replacement_data)
+ const
+{
+ panic("Cant train predictor without access information.");
+}
+
+std::shared_ptr<ReplacementData>
+SHiP::instantiateEntry()
+{
+ return std::shared_ptr<ReplacementData>(new SHiPReplData(numRRPVBits));
+}
+
+SHiPMem::SHiPMem(const SHiPMemRPParams &p) : SHiP(p) {}
+
+SHiP::SignatureType
+SHiPMem::getSignature(const PacketPtr pkt) const
+{
+ return static_cast<SignatureType>(pkt->getAddr() % SHCT.size());
+}
+
+SHiPPC::SHiPPC(const SHiPPCRPParams &p) : SHiP(p) {}
+
+SHiP::SignatureType
+SHiPPC::getSignature(const PacketPtr pkt) const
+{
+ SignatureType signature;
+
+ if (pkt->req->hasPC()) {
+ signature = static_cast<SignatureType>(pkt->req->getPC());
+ } else {
+ signature = NO_PC_SIGNATURE;
+ }
+
+ return signature % SHCT.size();
+}
+
+} // namespace ReplacementPolicy
+
diff --git a/src/mem/cache/replacement_policies/ship_rp.hh
b/src/mem/cache/replacement_policies/ship_rp.hh
new file mode 100644
index 0000000..6280cf9
--- /dev/null
+++ b/src/mem/cache/replacement_policies/ship_rp.hh
@@ -0,0 +1,185 @@
+/**
+ * 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.
+ */
+
+/**
+ * @file
+ * Declaration of a the SHiP Replacement Policy, as described in "SHiP:
+ * Signature-based Hit Predictor for High Performance Caching", by
+ * Wu et al.
+ */
+
+#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_SHIP_RP_HH__
+#define __MEM_CACHE_REPLACEMENT_POLICIES_SHIP_RP_HH__
+
+#include <vector>
+
+#include "base/sat_counter.hh"
+#include "mem/cache/replacement_policies/brrip_rp.hh"
+#include "mem/packet.hh"
+
+struct SHiPRPParams;
+struct SHiPMemRPParams;
+struct SHiPPCRPParams;
+
+namespace ReplacementPolicy {
+
+class SHiP : public BRRIP
+{
+ protected:
+ typedef std::size_t SignatureType;
+
+ /** SHiP-specific implementation of replacement data. */
+ class SHiPReplData : public BRRIPReplData
+ {
+ private:
+ /** Signature that caused the insertion of this entry. */
+ SignatureType signature;
+
+ /** Outcome of insertion; set to one if entry is re-referenced. */
+ bool outcome;
+
+ public:
+ SHiPReplData(int num_bits);
+
+ /** Get entry's signature. */
+ SignatureType getSignature() const;
+
+ /**
+ * Set this entry's signature and reset outcome.
+ *
+ * @param signature New signature value/
+ */
+ void setSignature(SignatureType signature);
+
+ /** Set that this entry has been re-referenced. */
+ void setReReferenced();
+
+ /**
+ * Get whether entry has been re-referenced since insertion.
+ *
+ * @return True if entry has been re-referenced since insertion.
+ */
+ bool wasReReferenced() const;
+ };
+
+ /**
+ * Saturation percentage at which an entry starts being inserted as
+ * intermediate re-reference.
+ */
+ const double insertionThreshold;
+
+ /**
+ * Signature History Counter Table; learns the re-reference behavior
+ * of a signature. A zero entry provides a strong indication that
+ * future lines brought by that signature will not receive any hits.
+ */
+ std::vector<SatCounter8> SHCT;
+
+ /**
+ * Extract signature from packet.
+ *
+ * @param pkt The packet to extract a signature from.
+ * @return The signature extracted.
+ */
+ virtual SignatureType getSignature(const PacketPtr pkt) const = 0;
+
+ public:
+ typedef SHiPRPParams Params;
+ SHiP(const Params &p);
+ ~SHiP() = default;
+
+ /**
+ * Invalidate replacement data to set it as the next probable victim.
+ * Updates predictor and invalidate data.
+ *
+ * @param replacement_data Replacement data to be invalidated.
+ */
+ void invalidate(const std::shared_ptr<ReplacementData>&
replacement_data)
+
override;
+
+ /**
+ * Touch an entry to update its replacement data.
+ * Updates predictor and assigns RRPV values of Table 3.
+ *
+ * @param replacement_data Replacement data to be touched.
+ * @param pkt Packet that generated this hit.
+ */
+ void touch(const std::shared_ptr<ReplacementData>& replacement_data,
+ const PacketPtr pkt) override;
+ void touch(const std::shared_ptr<ReplacementData>& replacement_data)
const
+ override;
+
+ /**
+ * Reset replacement data. Used when an entry is inserted.
+ * Updates predictor and assigns RRPV values of Table 3.
+ *
+ * @param replacement_data Replacement data to be reset.
+ * @param pkt Packet that generated this miss.
+ */
+ void reset(const std::shared_ptr<ReplacementData>& replacement_data,
+ const PacketPtr pkt) override;
+ void reset(const std::shared_ptr<ReplacementData>& replacement_data)
const
+ override;
+
+ /**
+ * Instantiate a replacement data entry.
+ *
+ * @return A shared pointer to the new replacement data.
+ */
+ std::shared_ptr<ReplacementData> instantiateEntry() override;
+};
+
+/** SHiP that Uses memory addresses as signatures. */
+class SHiPMem : public SHiP
+{
+ protected:
+ SignatureType getSignature(const PacketPtr pkt) const override;
+
+ public:
+ SHiPMem(const SHiPMemRPParams &p);
+ ~SHiPMem() = default;
+};
+
+/** SHiP that Uses PCs as signatures. */
+class SHiPPC : public SHiP
+{
+ private:
+ /** Signature to be used when no PC is provided in an access. */
+ const SignatureType NO_PC_SIGNATURE = 0;
+
+ protected:
+ SignatureType getSignature(const PacketPtr pkt) const override;
+
+ public:
+ SHiPPC(const SHiPPCRPParams &p);
+ ~SHiPPC() = default;
+};
+
+} // namespace ReplacementPolicy
+
+#endif // __MEM_CACHE_REPLACEMENT_POLICIES_SHIP_RP_HH__
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/38118
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: I44f00d26eab4c96c9c5bc29740862a87356d30d1
Gerrit-Change-Number: 38118
Gerrit-PatchSet: 1
Gerrit-Owner: Daniel Carvalho <oda...@yahoo.com.br>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list -- gem5-dev@gem5.org
To unsubscribe send an email to gem5-dev-le...@gem5.org
%(web_page_url)slistinfo%(cgiext)s/%(_internal_name)s
