src/mem/cache/replacement_policies/tree_plru_rp.cc

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