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
Reviewed-on: https://gem5-review.googlesource.com/c/11106
Reviewed-by: Jason Lowe-Power <jason@lowepower.com>
Maintainer: Jason Lowe-Power <jason@lowepower.com>

5 files changed, 439 insertions, 2 deletions

diff --git a/src/mem/cache/replacement_policies/ReplacementPolicies.py b/src/mem/cache/replacement_policies/ReplacementPolicies.py
index 5737fa450..0bbf1d16b 100644
--- a/src/mem/cache/replacement_policies/ReplacementPolicies.py
+++ b/src/mem/cache/replacement_policies/ReplacementPolicies.py
@@ -90,3 +90,9 @@ class RRIPRP(BRRIPRP):
 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 d6a354a87..468cf7df4 100644
--- a/src/mem/cache/replacement_policies/SConscript
+++ b/src/mem/cache/replacement_policies/SConscript
@@ -40,3 +40,4 @@ Source('lru_rp.cc')
 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 1b8a396b6..b9094eb41 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 000000000..f5e07b2c3
--- /dev/null
+++ b/src/mem/cache/replacement_policies/tree_plru_rp.cc
@@ -0,0 +1,218 @@
+/**
+ * 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, which map an index to the tree 2D-array.
+ */
+
+#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(
+    const uint64_t index, std::shared_ptr<PLRUTree> tree)
+    : index(index), tree(tree)
+{
+}
+
+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
+        const 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
+        const 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
+    const 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()) {
+        // Go to the next tree entry
+        if (tree->at(tree_index)) {
+            tree_index = rightSubtreeIndex(tree_index);
+        } else {
+            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(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 000000000..1e81061a3
--- /dev/null
+++ b/src/mem/cache/replacement_policies/tree_plru_rp.hh
@@ -0,0 +1,213 @@
+/**
+ * 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.
+ *
+ * A tree contains consists of leafs that represent the direction to take when
+ * searching for the LRU entry.
+ *
+ * Let's assume each tree contains 8 replacement data entries. For example, if
+ * these entries are named from A to H, and the tree's bits are:
+ *    ____1____
+ *  __0__   __1__
+ * _0_ _1_ _1_ _0_
+ * A B C D E F G H
+ *
+ * Then the current PLRU entry is given by the sequence:
+ *     1 (get right child) -> 1 (get right child) -> 0 (get left child) -> G
+ *
+ * When an entry is touched the bits of the parent nodes are iteratively
+ * updated to point away from it. Therefore, if entry B is touched, its parent,
+ * grandparents, etc would be updated, and we'd end up with the following tree:
+ *    ____1____
+ *  __1__   __1__
+ * _0_ _1_ _1_ _0_
+ * A B C D E F G H
+ *
+ * Explanation: The parent of B must point away from it, that is, to the left
+ * child, but it is already doing so, so it is left unmodified (0). Then the
+ * grandparent must point to the right subtree, as B belongs to its left
+ * subtree (0 becomes 1). Lastly, the root must point away from the
+ * grandparent, so it is left unmodified (0).
+ *
+ * For invalidations the process is similar to touches, but instead of pointing
+ * away, the bits point toward the entry.
+ *
+ * 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;
+
+class TreePLRURP : public BaseReplacementPolicy
+{
+  private:
+    /**
+     * Instead of implementing the tree itself with pointers, it is implemented
+     * as an array of bits. The index of the node defines its position in the
+     * tree, and its parent. Index 0 represents the root, 1 is its left node,
+     * and 2 is its right node. Then, in a BFS fashion this is expanded to the
+     * following nodes (3 and 4 are respectively 1's left and right nodes, and
+     * 5 and 6 are 2's left and right nodes, and so on).
+     *
+     * i.e., the following trees are equivalent in this representation:
+     *    ____1____
+     *  __0__   __1__
+     * _0_ _1_ _1_ _0_
+     * A B C D E F G H
+     *
+     * 1 0 1 0 1 1 0
+     *
+     * Notice that the replacement data entries are not represented in the tree
+     * to avoid unnecessary storage costs.
+     */
+    typedef std::vector<bool> PLRUTree;
+
+    /**
+     * Number of leaves that share a single replacement data.
+     */
+    const 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 temporary tree instance created by instantiateEntry().
+     */
+    PLRUTree* treeInstance;
+
+  protected:
+    /**
+     * Tree-PLRU-specific implementation of replacement data. Each replacement
+     * data shares its tree with other entries.
+     */
+    struct TreePLRUReplData : ReplacementData
+    {
+        /**
+         * Theoretical index of this replacement data in the tree. In practice,
+         * the corresponding node does not exist, as the tree stores only the
+         * nodes that are not leaves.
+         */
+        const uint64_t index;
+
+        /**
+         * Shared tree pointer. A tree is shared between numLeaves nodes, so
+         * that accesses to a replacement data entry updates the PLRU bits of
+         * all other replacement data entries in its set.
+         */
+        std::shared_ptr<PLRUTree> tree;
+
+        /**
+         * Default constructor. Invalidate data.
+         *
+         * @param index Index of the corresponding entry in the tree.
+         * @param tree The shared tree pointer.
+         */
+        TreePLRUReplData(const uint64_t index, std::shared_ptr<PLRUTree> tree);
+    };
+
+  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.
+     * Therefore, it is essential that entries that share the same replacement
+     * data call this function consecutively.
+     *
+     * @return A shared pointer to the new replacement data.
+     */
+    std::shared_ptr<ReplacementData> instantiateEntry() override;
+};
+
+#endif // __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__