diff options
Diffstat (limited to 'src/mem/cache/replacement_policies/tree_plru_rp.hh')
| -rw-r--r-- | src/mem/cache/replacement_policies/tree_plru_rp.hh | 213 |
1 files changed, 213 insertions, 0 deletions
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__ |