Daniel Carvalho has uploaded this change for review. (
https://gem5-review.googlesource.com/11106
Change subject: mem-cache: Create Tree-PLRU replacement policy
......................................................................
mem-cache: Create Tree-PLRU replacement policy
Implementation of a Tree-PLRU replacement policy. It is based on
the assumption that a set associative cache is used.
Change-Id: I74b227e88fd6c93aab5bb2cd0e8730376db28f52
---
M src/mem/cache/replacement_policies/ReplacementPolicies.py
M src/mem/cache/replacement_policies/SConscript
M src/mem/cache/replacement_policies/lru_rp.hh
A src/mem/cache/replacement_policies/tree_plru_rp.cc
A src/mem/cache/replacement_policies/tree_plru_rp.hh
5 files changed, 405 insertions(+), 2 deletions(-)
diff --git a/src/mem/cache/replacement_policies/ReplacementPolicies.py
b/src/mem/cache/replacement_policies/ReplacementPolicies.py
index 5737fa4..0bbf1d1 100644
--- a/src/mem/cache/replacement_policies/ReplacementPolicies.py
+++ b/src/mem/cache/replacement_policies/ReplacementPolicies.py
@@ -90,3 +90,9 @@
class NRURP(BRRIPRP):
btp = 0
max_RRPV = 1
+
+class TreePLRURP(BaseReplacementPolicy):
+ type = 'TreePLRURP'
+ cxx_class = 'TreePLRURP'
+ cxx_header = "mem/cache/replacement_policies/tree_plru_rp.hh"
+ num_leaves = Param.Int(Parent.assoc, "Number of leaves in each tree")
diff --git a/src/mem/cache/replacement_policies/SConscript
b/src/mem/cache/replacement_policies/SConscript
index d6a354a..468cf7d 100644
--- a/src/mem/cache/replacement_policies/SConscript
+++ b/src/mem/cache/replacement_policies/SConscript
@@ -40,3 +40,4 @@
Source('mru_rp.cc')
Source('random_rp.cc')
Source('second_chance_rp.cc')
+Source('tree_plru_rp.cc')
diff --git a/src/mem/cache/replacement_policies/lru_rp.hh
b/src/mem/cache/replacement_policies/lru_rp.hh
index 92aeccc..0905431 100644
--- a/src/mem/cache/replacement_policies/lru_rp.hh
+++ b/src/mem/cache/replacement_policies/lru_rp.hh
@@ -31,8 +31,7 @@
/**
* @file
* 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.
+ * The victim is chosen using the last touch timestamp.
*/
#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_LRU_RP_HH__
diff --git a/src/mem/cache/replacement_policies/tree_plru_rp.cc
b/src/mem/cache/replacement_policies/tree_plru_rp.cc
new file mode 100644
index 0000000..11b8230
--- /dev/null
+++ b/src/mem/cache/replacement_policies/tree_plru_rp.cc
@@ -0,0 +1,234 @@
+/**
+ * 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
+ * Definitions of a Tree-PLRU replacement policy, along with some helper
+ * tree indexing functions.
+ */
+
+#include "mem/cache/replacement_policies/tree_plru_rp.hh"
+
+#include <memory>
+
+#include "base/intmath.hh"
+#include "params/TreePLRURP.hh"
+
+/**
+ * Get the index of the parent of the given indexed subtree.
+ *
+ * @param Index of the queried tree.
+ * @return The index of the parent tree.
+ */
+static uint64_t
+parentIndex(const uint64_t index)
+{
+ return std::floor((index-1)/2);
+}
+
+/**
+ * Get index of the subtree on the left of the given indexed tree.
+ *
+ * @param index The index of the queried tree.
+ * @return The index of the subtree to the left of the queried tree.
+ */
+static uint64_t
+leftSubtreeIndex(const uint64_t index)
+{
+ return 2*index + 1;
+}
+
+/**
+ * Get index of the subtree on the right of the given indexed tree.
+ *
+ * @param index The index of the queried tree.
+ * @return The index of the subtree to the right of the queried tree.
+ */
+static uint64_t
+rightSubtreeIndex(const uint64_t index)
+{
+ return 2*index + 2;
+}
+
+/**
+ * Find out if the subtree at index corresponds to the right or left
subtree
+ * of its parent tree.
+ *
+ * @param index The index of the subtree.
+ * @return True if it is a right subtree, false otherwise.
+ */
+static bool
+isRightSubtree(const uint64_t index)
+{
+ return index%2 == 0;
+}
+
+TreePLRURP::TreePLRUReplData::TreePLRUReplData(
+ uint64_t index, std::shared_ptr<PLRUTree> tree)
+ : index(index), tree(tree)
+{
+}
+
+void
+TreePLRURP::TreePLRUReplData::serialize(CheckpointOut &cp) const
+{
+ SERIALIZE_SCALAR(index);
+ SERIALIZE_CONTAINER(*(tree.get()));
+}
+
+void
+TreePLRURP::TreePLRUReplData::unserialize(CheckpointIn &cp)
+{
+ UNSERIALIZE_SCALAR(index);
+ UNSERIALIZE_CONTAINER(*(tree.get()));
+}
+
+TreePLRURP::TreePLRURP(const Params *p)
+ : BaseReplacementPolicy(p), numLeaves(p->num_leaves), count(0),
+ treeInstance(nullptr)
+{
+ fatal_if(!isPowerOf2(numLeaves),
+ "Number of leaves must be non-zero and a power of 2");
+}
+
+void
+TreePLRURP::invalidate(
+ const std::shared_ptr<ReplacementData>& replacement_data) const
+{
+ // Cast replacement data
+ std::shared_ptr<TreePLRUReplData> treePLRU_replacement_data =
+ std::static_pointer_cast<TreePLRUReplData>(replacement_data);
+ PLRUTree* tree = treePLRU_replacement_data->tree.get();
+
+ // Index of the tree entry we are currently checking
+ // Make this entry the new LRU entry
+ uint64_t tree_index = treePLRU_replacement_data->index;
+
+ // Parse and update tree to make it point to the new LRU
+ do {
+ // Store whether we are coming from a left or right node
+ bool right = isRightSubtree(tree_index);
+
+ // Go to the parent tree node
+ tree_index = parentIndex(tree_index);
+
+ // Update parent node to make it point to the node we just came
from
+ tree->at(tree_index) = right;
+ } while (tree_index != 0);
+}
+
+void
+TreePLRURP::touch(const std::shared_ptr<ReplacementData>& replacement_data)
+const
+{
+ // Cast replacement data
+ std::shared_ptr<TreePLRUReplData> treePLRU_replacement_data =
+ std::static_pointer_cast<TreePLRUReplData>(replacement_data);
+ PLRUTree* tree = treePLRU_replacement_data->tree.get();
+
+ // Index of the tree entry we are currently checking
+ // Make this entry the MRU entry
+ uint64_t tree_index = treePLRU_replacement_data->index;
+
+ // Parse and update tree to make every bit point away from the new MRU
+ do {
+ // Store whether we are coming from a left or right node
+ bool right = isRightSubtree(tree_index);
+
+ // Go to the parent tree node
+ tree_index = parentIndex(tree_index);
+
+ // Update node to not point to the touched leaf
+ tree->at(tree_index) = !right;
+ } while (tree_index != 0);
+}
+
+void
+TreePLRURP::reset(const std::shared_ptr<ReplacementData>& replacement_data)
+const
+{
+ // A reset has the same functionality of a touch
+ touch(replacement_data);
+}
+
+ReplaceableEntry*
+TreePLRURP::getVictim(const ReplacementCandidates& candidates) const
+{
+ // There must be at least one replacement candidate
+ assert(candidates.size() > 0);
+
+ // Get tree
+ PLRUTree* tree = std::static_pointer_cast<TreePLRUReplData>(
+ candidates[0]->replacementData)->tree.get();
+
+ // Index of the tree entry we are currently checking. Start with root.
+ uint64_t tree_index = 0;
+
+ // Parse tree
+ while (tree_index < tree->size() - numLeaves) {
+ // Update node and go to the next tree entry
+ if (tree->at(tree_index)) {
+ tree->at(tree_index) = !tree->at(tree_index);
+ tree_index = rightSubtreeIndex(tree_index);
+ } else {
+ tree->at(tree_index) = !tree->at(tree_index);
+ tree_index = leftSubtreeIndex(tree_index);
+ }
+ }
+
+ // The tree index is currently at the leaf of the victim displaced by
the
+ // number of non-leaf nodes
+ return candidates[tree_index - (numLeaves - 1)];
+}
+
+std::shared_ptr<ReplacementData>
+TreePLRURP::instantiateEntry()
+{
+ // Generate a tree instance every numLeaves created
+ if (count % numLeaves == 0) {
+ treeInstance = new PLRUTree(2*numLeaves-1, false);
+ }
+
+ // Create replacement data using current tree instance
+ TreePLRUReplData* treePLRUReplData = new TreePLRUReplData(
+ count % numLeaves + numLeaves - 1,
+ std::shared_ptr<PLRUTree>(treeInstance));
+
+ // Update instance counter
+ count++;
+
+ return std::shared_ptr<ReplacementData>(treePLRUReplData);
+}
+
+TreePLRURP*
+TreePLRURPParams::create()
+{
+ return new TreePLRURP(this);
+}
diff --git a/src/mem/cache/replacement_policies/tree_plru_rp.hh
b/src/mem/cache/replacement_policies/tree_plru_rp.hh
new file mode 100644
index 0000000..8a31a40
--- /dev/null
+++ b/src/mem/cache/replacement_policies/tree_plru_rp.hh
@@ -0,0 +1,163 @@
+/**
+ * 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 Pseudo-Least Recently Used replacement policy.
+ * The victim is chosen using a tree of bit timestamps. Consecutive calls
to
+ * instantiateEntry() use the same tree up to numLeaves. When numLeaves
+ * replacement datas have been created, a new tree is generated, and the
+ * counter is reset.
+ */
+
+#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__
+#define __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__
+
+#include "mem/cache/replacement_policies/base.hh"
+
+struct TreePLRURPParams;
+
+/**
+ * A binary tree is just an array of bits.
+ */
+typedef std::vector<bool> PLRUTree;
+
+class TreePLRURP : public BaseReplacementPolicy
+{
+ private:
+ /**
+ * Number of leaves that share a single replacement data.
+ */
+ uint64_t numLeaves;
+
+ /**
+ * Count of the number of sharers of a replacement data. It is used
when
+ * instantiating entries to share a replacement data among many
replaceable
+ * entries.
+ */
+ uint64_t count;
+
+ /**
+ * Holds the latest tree instance generated by instantiateEntry().
+ */
+ PLRUTree* treeInstance;
+
+ protected:
+ /**
+ * Tree-PLRU-specific implementation of replacement data. Each
replacement
+ * data shares its tree with other entries.
+ */
+ struct TreePLRUReplData : ReplacementData
+ {
+ /**
+ * Index of this replacement data in the tree.
+ */
+ uint64_t index;
+
+ /**
+ * Shared tree pointer.
+ */
+ std::shared_ptr<PLRUTree> tree;
+
+ /**
+ * Default constructor. Invalidate data.
+ */
+ TreePLRUReplData(uint64_t index, std::shared_ptr<PLRUTree> tree);
+
+ /**
+ * Handle replacement data serialization.
+ */
+ void serialize(CheckpointOut &cp) const override;
+ void unserialize(CheckpointIn &cp) override;
+ };
+
+ public:
+ /** Convenience typedef. */
+ typedef TreePLRURPParams Params;
+
+ /**
+ * Construct and initiliaze this replacement policy.
+ */
+ TreePLRURP(const Params *p);
+
+ /**
+ * Destructor.
+ */
+ ~TreePLRURP() {}
+
+ /**
+ * Invalidate replacement data to set it as the next probable victim.
+ * Makes tree leaf of replacement data the LRU (tree bits point to it).
+ *
+ * @param replacement_data Replacement data to be invalidated.
+ */
+ void invalidate(const std::shared_ptr<ReplacementData>&
replacement_data)
+ const
override;
+
+ /**
+ * Touch an entry to update its replacement data.
+ * Makes tree leaf of replacement data the MRU.
+ *
+ * @param replacement_data Replacement data to be touched.
+ */
+ void touch(const std::shared_ptr<ReplacementData>& replacement_data)
const
+
override;
+
+ /**
+ * Reset replacement data. Used when an entry is inserted. Provides the
+ * same functionality as touch().
+ *
+ * @param replacement_data Replacement data to be reset.
+ */
+ void reset(const std::shared_ptr<ReplacementData>& replacement_data)
const
+
override;
+
+ /**
+ * Find replacement victim using TreePLRU bits. It is assumed that all
+ * candidates share the same replacement data tree.
+ *
+ * @param candidates Replacement candidates, selected by indexing
policy.
+ * @return Replacement entry to be replaced.
+ */
+ ReplaceableEntry* getVictim(const ReplacementCandidates& candidates)
const
+
override;
+
+ /**
+ * Instantiate a replacement data entry. Consecutive calls to this
+ * function use the same tree up to numLeaves. When numLeaves
replacement
+ * data have been created, a new tree is generated, and the counter is
+ * reset.
+ *
+ * @return A shared pointer to the new replacement data.
+ */
+ std::shared_ptr<ReplacementData> instantiateEntry() override;
+};
+
+#endif // __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__
--
To view, visit https://gem5-review.googlesource.com/11106
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: master
Gerrit-Change-Id: I74b227e88fd6c93aab5bb2cd0e8730376db28f52
Gerrit-Change-Number: 11106
Gerrit-PatchSet: 1
Gerrit-Owner: Daniel Carvalho <oda...@yahoo.com.br>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list
gem5-dev@gem5.org
http://m5sim.org/mailman/listinfo/gem5-dev
