tree_plru_rp.cc 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 * Definitions of a Tree-PLRU replacement policy, along with some helper 34 * tree indexing functions, which map an index to the tree 2D-array. 35 */ 36 37#include "mem/cache/replacement_policies/tree_plru_rp.hh" 38 39#include <memory> 40 41#include "base/intmath.hh" 42#include "params/TreePLRURP.hh" 43 44/** 45 * Get the index of the parent of the given indexed subtree. 46 * 47 * @param Index of the queried tree. 48 * @return The index of the parent tree. 49 */ 50static uint64_t 51parentIndex(const uint64_t index) 52{ 53 return std::floor((index-1)/2); 54} 55 56/** 57 * Get index of the subtree on the left of the given indexed tree. 58 * 59 * @param index The index of the queried tree. 60 * @return The index of the subtree to the left of the queried tree. 61 */ 62static uint64_t 63leftSubtreeIndex(const uint64_t index) 64{ 65 return 2*index + 1; 66} 67 68/** 69 * Get index of the subtree on the right of the given indexed tree. 70 * 71 * @param index The index of the queried tree. 72 * @return The index of the subtree to the right of the queried tree. 73 */ 74static uint64_t 75rightSubtreeIndex(const uint64_t index) 76{ 77 return 2*index + 2; 78} 79 80/** 81 * Find out if the subtree at index corresponds to the right or left subtree 82 * of its parent tree. 83 * 84 * @param index The index of the subtree. 85 * @return True if it is a right subtree, false otherwise. 86 */ 87static bool 88isRightSubtree(const uint64_t index) 89{ 90 return index%2 == 0; 91} 92 93TreePLRURP::TreePLRUReplData::TreePLRUReplData( 94 const uint64_t index, std::shared_ptr<PLRUTree> tree) 95 : index(index), tree(tree) 96{ 97} 98 99TreePLRURP::TreePLRURP(const Params *p) 100 : BaseReplacementPolicy(p), numLeaves(p->num_leaves), count(0), 101 treeInstance(nullptr) 102{ 103 fatal_if(!isPowerOf2(numLeaves), 104 "Number of leaves must be non-zero and a power of 2"); 105} 106 107void 108TreePLRURP::invalidate( 109 const std::shared_ptr<ReplacementData>& replacement_data) const 110{ 111 // Cast replacement data 112 std::shared_ptr<TreePLRUReplData> treePLRU_replacement_data = 113 std::static_pointer_cast<TreePLRUReplData>(replacement_data); 114 PLRUTree* tree = treePLRU_replacement_data->tree.get(); 115 116 // Index of the tree entry we are currently checking 117 // Make this entry the new LRU entry 118 uint64_t tree_index = treePLRU_replacement_data->index; 119 120 // Parse and update tree to make it point to the new LRU 121 do { 122 // Store whether we are coming from a left or right node 123 const bool right = isRightSubtree(tree_index); 124 125 // Go to the parent tree node 126 tree_index = parentIndex(tree_index); 127 128 // Update parent node to make it point to the node we just came from 129 tree->at(tree_index) = right; 130 } while (tree_index != 0); 131} 132 133void 134TreePLRURP::touch(const std::shared_ptr<ReplacementData>& replacement_data) 135const 136{ 137 // Cast replacement data 138 std::shared_ptr<TreePLRUReplData> treePLRU_replacement_data = 139 std::static_pointer_cast<TreePLRUReplData>(replacement_data); 140 PLRUTree* tree = treePLRU_replacement_data->tree.get(); 141 142 // Index of the tree entry we are currently checking 143 // Make this entry the MRU entry 144 uint64_t tree_index = treePLRU_replacement_data->index; 145 146 // Parse and update tree to make every bit point away from the new MRU 147 do { 148 // Store whether we are coming from a left or right node 149 const bool right = isRightSubtree(tree_index); 150 151 // Go to the parent tree node 152 tree_index = parentIndex(tree_index); 153 154 // Update node to not point to the touched leaf 155 tree->at(tree_index) = !right; 156 } while (tree_index != 0); 157} 158 159void 160TreePLRURP::reset(const std::shared_ptr<ReplacementData>& replacement_data) 161const 162{ 163 // A reset has the same functionality of a touch 164 touch(replacement_data); 165} 166 167ReplaceableEntry* 168TreePLRURP::getVictim(const ReplacementCandidates& candidates) const 169{ 170 // There must be at least one replacement candidate 171 assert(candidates.size() > 0); 172 173 // Get tree 174 const PLRUTree* tree = std::static_pointer_cast<TreePLRUReplData>( 175 candidates[0]->replacementData)->tree.get(); 176 177 // Index of the tree entry we are currently checking. Start with root. 178 uint64_t tree_index = 0; 179 180 // Parse tree 181 while (tree_index < tree->size()) { 182 // Go to the next tree entry 183 if (tree->at(tree_index)) { 184 tree_index = rightSubtreeIndex(tree_index); 185 } else { 186 tree_index = leftSubtreeIndex(tree_index); 187 } 188 } 189 190 // The tree index is currently at the leaf of the victim displaced by the 191 // number of non-leaf nodes 192 return candidates[tree_index - (numLeaves - 1)]; 193} 194 195std::shared_ptr<ReplacementData> 196TreePLRURP::instantiateEntry() 197{ 198 // Generate a tree instance every numLeaves created 199 if (count % numLeaves == 0) { 200 treeInstance = new PLRUTree(numLeaves - 1, false); 201 } 202 203 // Create replacement data using current tree instance 204 TreePLRUReplData* treePLRUReplData = new TreePLRUReplData( 205 (count % numLeaves) + numLeaves - 1, 206 std::shared_ptr<PLRUTree>(treeInstance)); 207 208 // Update instance counter 209 count++; 210 211 return std::shared_ptr<ReplacementData>(treePLRUReplData); 212} 213 214TreePLRURP* 215TreePLRURPParams::create() 216{ 217 return new TreePLRURP(this); 218} 219