From 160bcba0d6729d37caf65e97a99e2ebdcf71f6a8 Mon Sep 17 00:00:00 2001 From: "Daniel R. Carvalho" Date: Tue, 5 Jun 2018 13:59:42 +0200 Subject: [PATCH] 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 Maintainer: Jason Lowe-Power --- .../ReplacementPolicies.py | 6 + src/mem/cache/replacement_policies/SConscript | 1 + src/mem/cache/replacement_policies/lru_rp.hh | 3 +- .../replacement_policies/tree_plru_rp.cc | 218 ++++++++++++++++++ .../replacement_policies/tree_plru_rp.hh | 213 +++++++++++++++++ 5 files changed, 439 insertions(+), 2 deletions(-) create mode 100644 src/mem/cache/replacement_policies/tree_plru_rp.cc create mode 100644 src/mem/cache/replacement_policies/tree_plru_rp.hh 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 + +#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 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& replacement_data) const +{ + // Cast replacement data + std::shared_ptr treePLRU_replacement_data = + std::static_pointer_cast(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& replacement_data) +const +{ + // Cast replacement data + std::shared_ptr treePLRU_replacement_data = + std::static_pointer_cast(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& 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( + 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 +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(treeInstance)); + + // Update instance counter + count++; + + return std::shared_ptr(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 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 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 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& 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& 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& 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 instantiateEntry() override; +}; + +#endif // __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__ -- 2.30.2