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 * Declaration of a Pseudo-Least Recently Used replacement policy. 3413221Sodanrc@yahoo.com.br * The victim is chosen using a tree of bit timestamps. 3513221Sodanrc@yahoo.com.br * 3613221Sodanrc@yahoo.com.br * A tree contains consists of leafs that represent the direction to take when 3713221Sodanrc@yahoo.com.br * searching for the LRU entry. 3813221Sodanrc@yahoo.com.br * 3913221Sodanrc@yahoo.com.br * Let's assume each tree contains 8 replacement data entries. For example, if 4013221Sodanrc@yahoo.com.br * these entries are named from A to H, and the tree's bits are: 4113221Sodanrc@yahoo.com.br * ____1____ 4213221Sodanrc@yahoo.com.br * __0__ __1__ 4313221Sodanrc@yahoo.com.br * _0_ _1_ _1_ _0_ 4413221Sodanrc@yahoo.com.br * A B C D E F G H 4513221Sodanrc@yahoo.com.br * 4613221Sodanrc@yahoo.com.br * Then the current PLRU entry is given by the sequence: 4713221Sodanrc@yahoo.com.br * 1 (get right child) -> 1 (get right child) -> 0 (get left child) -> G 4813221Sodanrc@yahoo.com.br * 4913221Sodanrc@yahoo.com.br * When an entry is touched the bits of the parent nodes are iteratively 5013221Sodanrc@yahoo.com.br * updated to point away from it. Therefore, if entry B is touched, its parent, 5113221Sodanrc@yahoo.com.br * grandparents, etc would be updated, and we'd end up with the following tree: 5213221Sodanrc@yahoo.com.br * ____1____ 5313221Sodanrc@yahoo.com.br * __1__ __1__ 5413221Sodanrc@yahoo.com.br * _0_ _1_ _1_ _0_ 5513221Sodanrc@yahoo.com.br * A B C D E F G H 5613221Sodanrc@yahoo.com.br * 5713221Sodanrc@yahoo.com.br * Explanation: The parent of B must point away from it, that is, to the left 5813221Sodanrc@yahoo.com.br * child, but it is already doing so, so it is left unmodified (0). Then the 5913221Sodanrc@yahoo.com.br * grandparent must point to the right subtree, as B belongs to its left 6013221Sodanrc@yahoo.com.br * subtree (0 becomes 1). Lastly, the root must point away from the 6113221Sodanrc@yahoo.com.br * grandparent, so it is left unmodified (0). 6213221Sodanrc@yahoo.com.br * 6313221Sodanrc@yahoo.com.br * For invalidations the process is similar to touches, but instead of pointing 6413221Sodanrc@yahoo.com.br * away, the bits point toward the entry. 6513221Sodanrc@yahoo.com.br * 6613221Sodanrc@yahoo.com.br * Consecutive calls to instantiateEntry() use the same tree up to numLeaves. 6713221Sodanrc@yahoo.com.br * When numLeaves replacement datas have been created, a new tree is generated, 6813221Sodanrc@yahoo.com.br * and the counter is reset. 6913221Sodanrc@yahoo.com.br */ 7013221Sodanrc@yahoo.com.br 7113221Sodanrc@yahoo.com.br#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__ 7213221Sodanrc@yahoo.com.br#define __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__ 7313221Sodanrc@yahoo.com.br 7413236Sodanrc@yahoo.com.br#include <cstdint> 7513236Sodanrc@yahoo.com.br#include <memory> 7613236Sodanrc@yahoo.com.br#include <vector> 7713236Sodanrc@yahoo.com.br 7813221Sodanrc@yahoo.com.br#include "mem/cache/replacement_policies/base.hh" 7913221Sodanrc@yahoo.com.br 8013221Sodanrc@yahoo.com.brstruct TreePLRURPParams; 8113221Sodanrc@yahoo.com.br 8213221Sodanrc@yahoo.com.brclass TreePLRURP : public BaseReplacementPolicy 8313221Sodanrc@yahoo.com.br{ 8413221Sodanrc@yahoo.com.br private: 8513221Sodanrc@yahoo.com.br /** 8613221Sodanrc@yahoo.com.br * Instead of implementing the tree itself with pointers, it is implemented 8713221Sodanrc@yahoo.com.br * as an array of bits. The index of the node defines its position in the 8813221Sodanrc@yahoo.com.br * tree, and its parent. Index 0 represents the root, 1 is its left node, 8913221Sodanrc@yahoo.com.br * and 2 is its right node. Then, in a BFS fashion this is expanded to the 9013221Sodanrc@yahoo.com.br * following nodes (3 and 4 are respectively 1's left and right nodes, and 9113221Sodanrc@yahoo.com.br * 5 and 6 are 2's left and right nodes, and so on). 9213221Sodanrc@yahoo.com.br * 9313221Sodanrc@yahoo.com.br * i.e., the following trees are equivalent in this representation: 9413221Sodanrc@yahoo.com.br * ____1____ 9513221Sodanrc@yahoo.com.br * __0__ __1__ 9613221Sodanrc@yahoo.com.br * _0_ _1_ _1_ _0_ 9713221Sodanrc@yahoo.com.br * A B C D E F G H 9813221Sodanrc@yahoo.com.br * 9913221Sodanrc@yahoo.com.br * 1 0 1 0 1 1 0 10013221Sodanrc@yahoo.com.br * 10113221Sodanrc@yahoo.com.br * Notice that the replacement data entries are not represented in the tree 10213221Sodanrc@yahoo.com.br * to avoid unnecessary storage costs. 10313221Sodanrc@yahoo.com.br */ 10413221Sodanrc@yahoo.com.br typedef std::vector<bool> PLRUTree; 10513221Sodanrc@yahoo.com.br 10613221Sodanrc@yahoo.com.br /** 10713221Sodanrc@yahoo.com.br * Number of leaves that share a single replacement data. 10813221Sodanrc@yahoo.com.br */ 10913221Sodanrc@yahoo.com.br const uint64_t numLeaves; 11013221Sodanrc@yahoo.com.br 11113221Sodanrc@yahoo.com.br /** 11213221Sodanrc@yahoo.com.br * Count of the number of sharers of a replacement data. It is used when 11313221Sodanrc@yahoo.com.br * instantiating entries to share a replacement data among many replaceable 11413221Sodanrc@yahoo.com.br * entries. 11513221Sodanrc@yahoo.com.br */ 11613221Sodanrc@yahoo.com.br uint64_t count; 11713221Sodanrc@yahoo.com.br 11813221Sodanrc@yahoo.com.br /** 11913221Sodanrc@yahoo.com.br * Holds the latest temporary tree instance created by instantiateEntry(). 12013221Sodanrc@yahoo.com.br */ 12113221Sodanrc@yahoo.com.br PLRUTree* treeInstance; 12213221Sodanrc@yahoo.com.br 12313221Sodanrc@yahoo.com.br protected: 12413221Sodanrc@yahoo.com.br /** 12513221Sodanrc@yahoo.com.br * Tree-PLRU-specific implementation of replacement data. Each replacement 12613221Sodanrc@yahoo.com.br * data shares its tree with other entries. 12713221Sodanrc@yahoo.com.br */ 12813221Sodanrc@yahoo.com.br struct TreePLRUReplData : ReplacementData 12913221Sodanrc@yahoo.com.br { 13013221Sodanrc@yahoo.com.br /** 13113221Sodanrc@yahoo.com.br * Theoretical index of this replacement data in the tree. In practice, 13213221Sodanrc@yahoo.com.br * the corresponding node does not exist, as the tree stores only the 13313221Sodanrc@yahoo.com.br * nodes that are not leaves. 13413221Sodanrc@yahoo.com.br */ 13513221Sodanrc@yahoo.com.br const uint64_t index; 13613221Sodanrc@yahoo.com.br 13713221Sodanrc@yahoo.com.br /** 13813221Sodanrc@yahoo.com.br * Shared tree pointer. A tree is shared between numLeaves nodes, so 13913221Sodanrc@yahoo.com.br * that accesses to a replacement data entry updates the PLRU bits of 14013221Sodanrc@yahoo.com.br * all other replacement data entries in its set. 14113221Sodanrc@yahoo.com.br */ 14213221Sodanrc@yahoo.com.br std::shared_ptr<PLRUTree> tree; 14313221Sodanrc@yahoo.com.br 14413221Sodanrc@yahoo.com.br /** 14513221Sodanrc@yahoo.com.br * Default constructor. Invalidate data. 14613221Sodanrc@yahoo.com.br * 14713221Sodanrc@yahoo.com.br * @param index Index of the corresponding entry in the tree. 14813221Sodanrc@yahoo.com.br * @param tree The shared tree pointer. 14913221Sodanrc@yahoo.com.br */ 15013221Sodanrc@yahoo.com.br TreePLRUReplData(const uint64_t index, std::shared_ptr<PLRUTree> tree); 15113221Sodanrc@yahoo.com.br }; 15213221Sodanrc@yahoo.com.br 15313221Sodanrc@yahoo.com.br public: 15413221Sodanrc@yahoo.com.br /** Convenience typedef. */ 15513221Sodanrc@yahoo.com.br typedef TreePLRURPParams Params; 15613221Sodanrc@yahoo.com.br 15713221Sodanrc@yahoo.com.br /** 15813221Sodanrc@yahoo.com.br * Construct and initiliaze this replacement policy. 15913221Sodanrc@yahoo.com.br */ 16013221Sodanrc@yahoo.com.br TreePLRURP(const Params *p); 16113221Sodanrc@yahoo.com.br 16213221Sodanrc@yahoo.com.br /** 16313221Sodanrc@yahoo.com.br * Destructor. 16413221Sodanrc@yahoo.com.br */ 16513221Sodanrc@yahoo.com.br ~TreePLRURP() {} 16613221Sodanrc@yahoo.com.br 16713221Sodanrc@yahoo.com.br /** 16813221Sodanrc@yahoo.com.br * Invalidate replacement data to set it as the next probable victim. 16913221Sodanrc@yahoo.com.br * Makes tree leaf of replacement data the LRU (tree bits point to it). 17013221Sodanrc@yahoo.com.br * 17113221Sodanrc@yahoo.com.br * @param replacement_data Replacement data to be invalidated. 17213221Sodanrc@yahoo.com.br */ 17313221Sodanrc@yahoo.com.br void invalidate(const std::shared_ptr<ReplacementData>& replacement_data) 17413221Sodanrc@yahoo.com.br const override; 17513221Sodanrc@yahoo.com.br 17613221Sodanrc@yahoo.com.br /** 17713221Sodanrc@yahoo.com.br * Touch an entry to update its replacement data. 17813221Sodanrc@yahoo.com.br * Makes tree leaf of replacement data the MRU. 17913221Sodanrc@yahoo.com.br * 18013221Sodanrc@yahoo.com.br * @param replacement_data Replacement data to be touched. 18113221Sodanrc@yahoo.com.br */ 18213221Sodanrc@yahoo.com.br void touch(const std::shared_ptr<ReplacementData>& replacement_data) const 18313221Sodanrc@yahoo.com.br override; 18413221Sodanrc@yahoo.com.br 18513221Sodanrc@yahoo.com.br /** 18613221Sodanrc@yahoo.com.br * Reset replacement data. Used when an entry is inserted. Provides the 18713221Sodanrc@yahoo.com.br * same functionality as touch(). 18813221Sodanrc@yahoo.com.br * 18913221Sodanrc@yahoo.com.br * @param replacement_data Replacement data to be reset. 19013221Sodanrc@yahoo.com.br */ 19113221Sodanrc@yahoo.com.br void reset(const std::shared_ptr<ReplacementData>& replacement_data) const 19213221Sodanrc@yahoo.com.br override; 19313221Sodanrc@yahoo.com.br 19413221Sodanrc@yahoo.com.br /** 19513221Sodanrc@yahoo.com.br * Find replacement victim using TreePLRU bits. It is assumed that all 19613221Sodanrc@yahoo.com.br * candidates share the same replacement data tree. 19713221Sodanrc@yahoo.com.br * 19813221Sodanrc@yahoo.com.br * @param candidates Replacement candidates, selected by indexing policy. 19913221Sodanrc@yahoo.com.br * @return Replacement entry to be replaced. 20013221Sodanrc@yahoo.com.br */ 20113221Sodanrc@yahoo.com.br ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const 20213221Sodanrc@yahoo.com.br override; 20313221Sodanrc@yahoo.com.br 20413221Sodanrc@yahoo.com.br /** 20513221Sodanrc@yahoo.com.br * Instantiate a replacement data entry. Consecutive calls to this 20613221Sodanrc@yahoo.com.br * function use the same tree up to numLeaves. When numLeaves replacement 20713221Sodanrc@yahoo.com.br * data have been created, a new tree is generated, and the counter is 20813221Sodanrc@yahoo.com.br * reset. 20913221Sodanrc@yahoo.com.br * Therefore, it is essential that entries that share the same replacement 21013221Sodanrc@yahoo.com.br * data call this function consecutively. 21113221Sodanrc@yahoo.com.br * 21213221Sodanrc@yahoo.com.br * @return A shared pointer to the new replacement data. 21313221Sodanrc@yahoo.com.br */ 21413221Sodanrc@yahoo.com.br std::shared_ptr<ReplacementData> instantiateEntry() override; 21513221Sodanrc@yahoo.com.br}; 21613221Sodanrc@yahoo.com.br 21713221Sodanrc@yahoo.com.br#endif // __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__ 218