tree_plru_rp.hh revision 13221:48bce2835200
1/** 2 * Copyright (c) 2018 Inria 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * Authors: Daniel Carvalho 29 */ 30 31/** 32 * @file 33 * Declaration of a Pseudo-Least Recently Used replacement policy. 34 * The victim is chosen using a tree of bit timestamps. 35 * 36 * A tree contains consists of leafs that represent the direction to take when 37 * searching for the LRU entry. 38 * 39 * Let's assume each tree contains 8 replacement data entries. For example, if 40 * these entries are named from A to H, and the tree's bits are: 41 * ____1____ 42 * __0__ __1__ 43 * _0_ _1_ _1_ _0_ 44 * A B C D E F G H 45 * 46 * Then the current PLRU entry is given by the sequence: 47 * 1 (get right child) -> 1 (get right child) -> 0 (get left child) -> G 48 * 49 * When an entry is touched the bits of the parent nodes are iteratively 50 * updated to point away from it. Therefore, if entry B is touched, its parent, 51 * grandparents, etc would be updated, and we'd end up with the following tree: 52 * ____1____ 53 * __1__ __1__ 54 * _0_ _1_ _1_ _0_ 55 * A B C D E F G H 56 * 57 * Explanation: The parent of B must point away from it, that is, to the left 58 * child, but it is already doing so, so it is left unmodified (0). Then the 59 * grandparent must point to the right subtree, as B belongs to its left 60 * subtree (0 becomes 1). Lastly, the root must point away from the 61 * grandparent, so it is left unmodified (0). 62 * 63 * For invalidations the process is similar to touches, but instead of pointing 64 * away, the bits point toward the entry. 65 * 66 * Consecutive calls to instantiateEntry() use the same tree up to numLeaves. 67 * When numLeaves replacement datas have been created, a new tree is generated, 68 * and the counter is reset. 69 */ 70 71#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__ 72#define __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__ 73 74#include "mem/cache/replacement_policies/base.hh" 75 76struct TreePLRURPParams; 77 78class TreePLRURP : public BaseReplacementPolicy 79{ 80 private: 81 /** 82 * Instead of implementing the tree itself with pointers, it is implemented 83 * as an array of bits. The index of the node defines its position in the 84 * tree, and its parent. Index 0 represents the root, 1 is its left node, 85 * and 2 is its right node. Then, in a BFS fashion this is expanded to the 86 * following nodes (3 and 4 are respectively 1's left and right nodes, and 87 * 5 and 6 are 2's left and right nodes, and so on). 88 * 89 * i.e., the following trees are equivalent in this representation: 90 * ____1____ 91 * __0__ __1__ 92 * _0_ _1_ _1_ _0_ 93 * A B C D E F G H 94 * 95 * 1 0 1 0 1 1 0 96 * 97 * Notice that the replacement data entries are not represented in the tree 98 * to avoid unnecessary storage costs. 99 */ 100 typedef std::vector<bool> PLRUTree; 101 102 /** 103 * Number of leaves that share a single replacement data. 104 */ 105 const uint64_t numLeaves; 106 107 /** 108 * Count of the number of sharers of a replacement data. It is used when 109 * instantiating entries to share a replacement data among many replaceable 110 * entries. 111 */ 112 uint64_t count; 113 114 /** 115 * Holds the latest temporary tree instance created by instantiateEntry(). 116 */ 117 PLRUTree* treeInstance; 118 119 protected: 120 /** 121 * Tree-PLRU-specific implementation of replacement data. Each replacement 122 * data shares its tree with other entries. 123 */ 124 struct TreePLRUReplData : ReplacementData 125 { 126 /** 127 * Theoretical index of this replacement data in the tree. In practice, 128 * the corresponding node does not exist, as the tree stores only the 129 * nodes that are not leaves. 130 */ 131 const uint64_t index; 132 133 /** 134 * Shared tree pointer. A tree is shared between numLeaves nodes, so 135 * that accesses to a replacement data entry updates the PLRU bits of 136 * all other replacement data entries in its set. 137 */ 138 std::shared_ptr<PLRUTree> tree; 139 140 /** 141 * Default constructor. Invalidate data. 142 * 143 * @param index Index of the corresponding entry in the tree. 144 * @param tree The shared tree pointer. 145 */ 146 TreePLRUReplData(const uint64_t index, std::shared_ptr<PLRUTree> tree); 147 }; 148 149 public: 150 /** Convenience typedef. */ 151 typedef TreePLRURPParams Params; 152 153 /** 154 * Construct and initiliaze this replacement policy. 155 */ 156 TreePLRURP(const Params *p); 157 158 /** 159 * Destructor. 160 */ 161 ~TreePLRURP() {} 162 163 /** 164 * Invalidate replacement data to set it as the next probable victim. 165 * Makes tree leaf of replacement data the LRU (tree bits point to it). 166 * 167 * @param replacement_data Replacement data to be invalidated. 168 */ 169 void invalidate(const std::shared_ptr<ReplacementData>& replacement_data) 170 const override; 171 172 /** 173 * Touch an entry to update its replacement data. 174 * Makes tree leaf of replacement data the MRU. 175 * 176 * @param replacement_data Replacement data to be touched. 177 */ 178 void touch(const std::shared_ptr<ReplacementData>& replacement_data) const 179 override; 180 181 /** 182 * Reset replacement data. Used when an entry is inserted. Provides the 183 * same functionality as touch(). 184 * 185 * @param replacement_data Replacement data to be reset. 186 */ 187 void reset(const std::shared_ptr<ReplacementData>& replacement_data) const 188 override; 189 190 /** 191 * Find replacement victim using TreePLRU bits. It is assumed that all 192 * candidates share the same replacement data tree. 193 * 194 * @param candidates Replacement candidates, selected by indexing policy. 195 * @return Replacement entry to be replaced. 196 */ 197 ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const 198 override; 199 200 /** 201 * Instantiate a replacement data entry. Consecutive calls to this 202 * function use the same tree up to numLeaves. When numLeaves replacement 203 * data have been created, a new tree is generated, and the counter is 204 * reset. 205 * Therefore, it is essential that entries that share the same replacement 206 * data call this function consecutively. 207 * 208 * @return A shared pointer to the new replacement data. 209 */ 210 std::shared_ptr<ReplacementData> instantiateEntry() override; 211}; 212 213#endif // __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__ 214