tree_plru_rp.cc revision 13236
113221Sodanrc@yahoo.com.br/** 213221Sodanrc@yahoo.com.br * Copyright (c) 2018 Inria 313221Sodanrc@yahoo.com.br * All rights reserved. 413221Sodanrc@yahoo.com.br * 513221Sodanrc@yahoo.com.br * Redistribution and use in source and binary forms, with or without 613221Sodanrc@yahoo.com.br * modification, are permitted provided that the following conditions are 713221Sodanrc@yahoo.com.br * met: redistributions of source code must retain the above copyright 813221Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer; 913221Sodanrc@yahoo.com.br * redistributions in binary form must reproduce the above copyright 1013221Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer in the 1113221Sodanrc@yahoo.com.br * documentation and/or other materials provided with the distribution; 1213221Sodanrc@yahoo.com.br * neither the name of the copyright holders nor the names of its 1313221Sodanrc@yahoo.com.br * contributors may be used to endorse or promote products derived from 1413221Sodanrc@yahoo.com.br * this software without specific prior written permission. 1513221Sodanrc@yahoo.com.br * 1613221Sodanrc@yahoo.com.br * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713221Sodanrc@yahoo.com.br * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813221Sodanrc@yahoo.com.br * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913221Sodanrc@yahoo.com.br * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013221Sodanrc@yahoo.com.br * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113221Sodanrc@yahoo.com.br * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213221Sodanrc@yahoo.com.br * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313221Sodanrc@yahoo.com.br * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413221Sodanrc@yahoo.com.br * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513221Sodanrc@yahoo.com.br * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613221Sodanrc@yahoo.com.br * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713221Sodanrc@yahoo.com.br * 2813221Sodanrc@yahoo.com.br * Authors: Daniel Carvalho 2913221Sodanrc@yahoo.com.br */ 3013221Sodanrc@yahoo.com.br 3113221Sodanrc@yahoo.com.br/** 3213221Sodanrc@yahoo.com.br * @file 3313221Sodanrc@yahoo.com.br * Definitions of a Tree-PLRU replacement policy, along with some helper 3413221Sodanrc@yahoo.com.br * tree indexing functions, which map an index to the tree 2D-array. 3513221Sodanrc@yahoo.com.br */ 3613221Sodanrc@yahoo.com.br 3713221Sodanrc@yahoo.com.br#include "mem/cache/replacement_policies/tree_plru_rp.hh" 3813221Sodanrc@yahoo.com.br 3913236Sodanrc@yahoo.com.br#include <cmath> 4013221Sodanrc@yahoo.com.br 4113221Sodanrc@yahoo.com.br#include "base/intmath.hh" 4213236Sodanrc@yahoo.com.br#include "base/logging.hh" 4313221Sodanrc@yahoo.com.br#include "params/TreePLRURP.hh" 4413221Sodanrc@yahoo.com.br 4513221Sodanrc@yahoo.com.br/** 4613221Sodanrc@yahoo.com.br * Get the index of the parent of the given indexed subtree. 4713221Sodanrc@yahoo.com.br * 4813221Sodanrc@yahoo.com.br * @param Index of the queried tree. 4913221Sodanrc@yahoo.com.br * @return The index of the parent tree. 5013221Sodanrc@yahoo.com.br */ 5113221Sodanrc@yahoo.com.brstatic uint64_t 5213221Sodanrc@yahoo.com.brparentIndex(const uint64_t index) 5313221Sodanrc@yahoo.com.br{ 5413221Sodanrc@yahoo.com.br return std::floor((index-1)/2); 5513221Sodanrc@yahoo.com.br} 5613221Sodanrc@yahoo.com.br 5713221Sodanrc@yahoo.com.br/** 5813221Sodanrc@yahoo.com.br * Get index of the subtree on the left of the given indexed tree. 5913221Sodanrc@yahoo.com.br * 6013221Sodanrc@yahoo.com.br * @param index The index of the queried tree. 6113221Sodanrc@yahoo.com.br * @return The index of the subtree to the left of the queried tree. 6213221Sodanrc@yahoo.com.br */ 6313221Sodanrc@yahoo.com.brstatic uint64_t 6413221Sodanrc@yahoo.com.brleftSubtreeIndex(const uint64_t index) 6513221Sodanrc@yahoo.com.br{ 6613221Sodanrc@yahoo.com.br return 2*index + 1; 6713221Sodanrc@yahoo.com.br} 6813221Sodanrc@yahoo.com.br 6913221Sodanrc@yahoo.com.br/** 7013221Sodanrc@yahoo.com.br * Get index of the subtree on the right of the given indexed tree. 7113221Sodanrc@yahoo.com.br * 7213221Sodanrc@yahoo.com.br * @param index The index of the queried tree. 7313221Sodanrc@yahoo.com.br * @return The index of the subtree to the right of the queried tree. 7413221Sodanrc@yahoo.com.br */ 7513221Sodanrc@yahoo.com.brstatic uint64_t 7613221Sodanrc@yahoo.com.brrightSubtreeIndex(const uint64_t index) 7713221Sodanrc@yahoo.com.br{ 7813221Sodanrc@yahoo.com.br return 2*index + 2; 7913221Sodanrc@yahoo.com.br} 8013221Sodanrc@yahoo.com.br 8113221Sodanrc@yahoo.com.br/** 8213221Sodanrc@yahoo.com.br * Find out if the subtree at index corresponds to the right or left subtree 8313221Sodanrc@yahoo.com.br * of its parent tree. 8413221Sodanrc@yahoo.com.br * 8513221Sodanrc@yahoo.com.br * @param index The index of the subtree. 8613221Sodanrc@yahoo.com.br * @return True if it is a right subtree, false otherwise. 8713221Sodanrc@yahoo.com.br */ 8813221Sodanrc@yahoo.com.brstatic bool 8913221Sodanrc@yahoo.com.brisRightSubtree(const uint64_t index) 9013221Sodanrc@yahoo.com.br{ 9113221Sodanrc@yahoo.com.br return index%2 == 0; 9213221Sodanrc@yahoo.com.br} 9313221Sodanrc@yahoo.com.br 9413221Sodanrc@yahoo.com.brTreePLRURP::TreePLRUReplData::TreePLRUReplData( 9513221Sodanrc@yahoo.com.br const uint64_t index, std::shared_ptr<PLRUTree> tree) 9613221Sodanrc@yahoo.com.br : index(index), tree(tree) 9713221Sodanrc@yahoo.com.br{ 9813221Sodanrc@yahoo.com.br} 9913221Sodanrc@yahoo.com.br 10013221Sodanrc@yahoo.com.brTreePLRURP::TreePLRURP(const Params *p) 10113221Sodanrc@yahoo.com.br : BaseReplacementPolicy(p), numLeaves(p->num_leaves), count(0), 10213221Sodanrc@yahoo.com.br treeInstance(nullptr) 10313221Sodanrc@yahoo.com.br{ 10413221Sodanrc@yahoo.com.br fatal_if(!isPowerOf2(numLeaves), 10513221Sodanrc@yahoo.com.br "Number of leaves must be non-zero and a power of 2"); 10613221Sodanrc@yahoo.com.br} 10713221Sodanrc@yahoo.com.br 10813221Sodanrc@yahoo.com.brvoid 10913221Sodanrc@yahoo.com.brTreePLRURP::invalidate( 11013221Sodanrc@yahoo.com.br const std::shared_ptr<ReplacementData>& replacement_data) const 11113221Sodanrc@yahoo.com.br{ 11213221Sodanrc@yahoo.com.br // Cast replacement data 11313221Sodanrc@yahoo.com.br std::shared_ptr<TreePLRUReplData> treePLRU_replacement_data = 11413221Sodanrc@yahoo.com.br std::static_pointer_cast<TreePLRUReplData>(replacement_data); 11513221Sodanrc@yahoo.com.br PLRUTree* tree = treePLRU_replacement_data->tree.get(); 11613221Sodanrc@yahoo.com.br 11713221Sodanrc@yahoo.com.br // Index of the tree entry we are currently checking 11813221Sodanrc@yahoo.com.br // Make this entry the new LRU entry 11913221Sodanrc@yahoo.com.br uint64_t tree_index = treePLRU_replacement_data->index; 12013221Sodanrc@yahoo.com.br 12113221Sodanrc@yahoo.com.br // Parse and update tree to make it point to the new LRU 12213221Sodanrc@yahoo.com.br do { 12313221Sodanrc@yahoo.com.br // Store whether we are coming from a left or right node 12413221Sodanrc@yahoo.com.br const bool right = isRightSubtree(tree_index); 12513221Sodanrc@yahoo.com.br 12613221Sodanrc@yahoo.com.br // Go to the parent tree node 12713221Sodanrc@yahoo.com.br tree_index = parentIndex(tree_index); 12813221Sodanrc@yahoo.com.br 12913221Sodanrc@yahoo.com.br // Update parent node to make it point to the node we just came from 13013221Sodanrc@yahoo.com.br tree->at(tree_index) = right; 13113221Sodanrc@yahoo.com.br } while (tree_index != 0); 13213221Sodanrc@yahoo.com.br} 13313221Sodanrc@yahoo.com.br 13413221Sodanrc@yahoo.com.brvoid 13513221Sodanrc@yahoo.com.brTreePLRURP::touch(const std::shared_ptr<ReplacementData>& replacement_data) 13613221Sodanrc@yahoo.com.brconst 13713221Sodanrc@yahoo.com.br{ 13813221Sodanrc@yahoo.com.br // Cast replacement data 13913221Sodanrc@yahoo.com.br std::shared_ptr<TreePLRUReplData> treePLRU_replacement_data = 14013221Sodanrc@yahoo.com.br std::static_pointer_cast<TreePLRUReplData>(replacement_data); 14113221Sodanrc@yahoo.com.br PLRUTree* tree = treePLRU_replacement_data->tree.get(); 14213221Sodanrc@yahoo.com.br 14313221Sodanrc@yahoo.com.br // Index of the tree entry we are currently checking 14413221Sodanrc@yahoo.com.br // Make this entry the MRU entry 14513221Sodanrc@yahoo.com.br uint64_t tree_index = treePLRU_replacement_data->index; 14613221Sodanrc@yahoo.com.br 14713221Sodanrc@yahoo.com.br // Parse and update tree to make every bit point away from the new MRU 14813221Sodanrc@yahoo.com.br do { 14913221Sodanrc@yahoo.com.br // Store whether we are coming from a left or right node 15013221Sodanrc@yahoo.com.br const bool right = isRightSubtree(tree_index); 15113221Sodanrc@yahoo.com.br 15213221Sodanrc@yahoo.com.br // Go to the parent tree node 15313221Sodanrc@yahoo.com.br tree_index = parentIndex(tree_index); 15413221Sodanrc@yahoo.com.br 15513221Sodanrc@yahoo.com.br // Update node to not point to the touched leaf 15613221Sodanrc@yahoo.com.br tree->at(tree_index) = !right; 15713221Sodanrc@yahoo.com.br } while (tree_index != 0); 15813221Sodanrc@yahoo.com.br} 15913221Sodanrc@yahoo.com.br 16013221Sodanrc@yahoo.com.brvoid 16113221Sodanrc@yahoo.com.brTreePLRURP::reset(const std::shared_ptr<ReplacementData>& replacement_data) 16213221Sodanrc@yahoo.com.brconst 16313221Sodanrc@yahoo.com.br{ 16413221Sodanrc@yahoo.com.br // A reset has the same functionality of a touch 16513221Sodanrc@yahoo.com.br touch(replacement_data); 16613221Sodanrc@yahoo.com.br} 16713221Sodanrc@yahoo.com.br 16813221Sodanrc@yahoo.com.brReplaceableEntry* 16913221Sodanrc@yahoo.com.brTreePLRURP::getVictim(const ReplacementCandidates& candidates) const 17013221Sodanrc@yahoo.com.br{ 17113221Sodanrc@yahoo.com.br // There must be at least one replacement candidate 17213221Sodanrc@yahoo.com.br assert(candidates.size() > 0); 17313221Sodanrc@yahoo.com.br 17413221Sodanrc@yahoo.com.br // Get tree 17513221Sodanrc@yahoo.com.br const PLRUTree* tree = std::static_pointer_cast<TreePLRUReplData>( 17613221Sodanrc@yahoo.com.br candidates[0]->replacementData)->tree.get(); 17713221Sodanrc@yahoo.com.br 17813221Sodanrc@yahoo.com.br // Index of the tree entry we are currently checking. Start with root. 17913221Sodanrc@yahoo.com.br uint64_t tree_index = 0; 18013221Sodanrc@yahoo.com.br 18113221Sodanrc@yahoo.com.br // Parse tree 18213221Sodanrc@yahoo.com.br while (tree_index < tree->size()) { 18313221Sodanrc@yahoo.com.br // Go to the next tree entry 18413221Sodanrc@yahoo.com.br if (tree->at(tree_index)) { 18513221Sodanrc@yahoo.com.br tree_index = rightSubtreeIndex(tree_index); 18613221Sodanrc@yahoo.com.br } else { 18713221Sodanrc@yahoo.com.br tree_index = leftSubtreeIndex(tree_index); 18813221Sodanrc@yahoo.com.br } 18913221Sodanrc@yahoo.com.br } 19013221Sodanrc@yahoo.com.br 19113221Sodanrc@yahoo.com.br // The tree index is currently at the leaf of the victim displaced by the 19213221Sodanrc@yahoo.com.br // number of non-leaf nodes 19313221Sodanrc@yahoo.com.br return candidates[tree_index - (numLeaves - 1)]; 19413221Sodanrc@yahoo.com.br} 19513221Sodanrc@yahoo.com.br 19613221Sodanrc@yahoo.com.brstd::shared_ptr<ReplacementData> 19713221Sodanrc@yahoo.com.brTreePLRURP::instantiateEntry() 19813221Sodanrc@yahoo.com.br{ 19913221Sodanrc@yahoo.com.br // Generate a tree instance every numLeaves created 20013221Sodanrc@yahoo.com.br if (count % numLeaves == 0) { 20113221Sodanrc@yahoo.com.br treeInstance = new PLRUTree(numLeaves - 1, false); 20213221Sodanrc@yahoo.com.br } 20313221Sodanrc@yahoo.com.br 20413221Sodanrc@yahoo.com.br // Create replacement data using current tree instance 20513221Sodanrc@yahoo.com.br TreePLRUReplData* treePLRUReplData = new TreePLRUReplData( 20613221Sodanrc@yahoo.com.br (count % numLeaves) + numLeaves - 1, 20713221Sodanrc@yahoo.com.br std::shared_ptr<PLRUTree>(treeInstance)); 20813221Sodanrc@yahoo.com.br 20913221Sodanrc@yahoo.com.br // Update instance counter 21013221Sodanrc@yahoo.com.br count++; 21113221Sodanrc@yahoo.com.br 21213221Sodanrc@yahoo.com.br return std::shared_ptr<ReplacementData>(treePLRUReplData); 21313221Sodanrc@yahoo.com.br} 21413221Sodanrc@yahoo.com.br 21513221Sodanrc@yahoo.com.brTreePLRURP* 21613221Sodanrc@yahoo.com.brTreePLRURPParams::create() 21713221Sodanrc@yahoo.com.br{ 21813221Sodanrc@yahoo.com.br return new TreePLRURP(this); 21913221Sodanrc@yahoo.com.br} 220