PseudoLRUPolicy.hh revision 10301
17008SN/A/* 27008SN/A * Copyright (c) 2007 Mark D. Hill and David A. Wood 37008SN/A * All rights reserved. 47008SN/A * 57008SN/A * Redistribution and use in source and binary forms, with or without 67008SN/A * modification, are permitted provided that the following conditions are 77008SN/A * met: redistributions of source code must retain the above copyright 87008SN/A * notice, this list of conditions and the following disclaimer; 97008SN/A * redistributions in binary form must reproduce the above copyright 107008SN/A * notice, this list of conditions and the following disclaimer in the 117008SN/A * documentation and/or other materials provided with the distribution; 127008SN/A * neither the name of the copyright holders nor the names of its 137008SN/A * contributors may be used to endorse or promote products derived from 147008SN/A * this software without specific prior written permission. 157008SN/A * 167008SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 177008SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 187008SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 197008SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 207008SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 217008SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 227008SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 237008SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 247008SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 257008SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 267008SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 277008SN/A */ 286145SN/A 297039SN/A#ifndef __MEM_RUBY_SYSTEM_PSEUDOLRUPOLICY_HH__ 307039SN/A#define __MEM_RUBY_SYSTEM_PSEUDOLRUPOLICY_HH__ 316145SN/A 3210301Snilay@cs.wisc.edu#include "mem/ruby/structures/AbstractReplacementPolicy.hh" 336145SN/A 346145SN/A/** 356145SN/A * Implementation of tree-based pseudo-LRU replacement 366145SN/A * 376145SN/A * Works for any associativity between 1 and 128. 386145SN/A * 396145SN/A * Also implements associativities that are not a power of 2 by 406145SN/A * ignoring paths that lead to a larger index (i.e. truncating the 416145SN/A * tree). Note that when this occurs, the algorithm becomes less 426145SN/A * fair, as it will favor indicies in the larger (by index) half of 436145SN/A * the associative set. This is most unfair when the nearest power of 446145SN/A * 2 is one below the associativy, and most fair when it is one above. 456145SN/A */ 466145SN/A 477039SN/Aclass PseudoLRUPolicy : public AbstractReplacementPolicy 487039SN/A{ 497039SN/A public: 507039SN/A PseudoLRUPolicy(Index num_sets, Index assoc); 517039SN/A ~PseudoLRUPolicy(); 526145SN/A 539505SN/A void touch(Index set, Index way, Tick time); 547039SN/A Index getVictim(Index set) const; 556145SN/A 567039SN/A private: 577039SN/A unsigned int m_effective_assoc; /** nearest (to ceiling) power of 2 */ 587039SN/A unsigned int m_num_levels; /** number of levels in the tree */ 597039SN/A uint64* m_trees; /** bit representation of the 607039SN/A * trees, one for each set */ 616145SN/A}; 626145SN/A 636145SN/Ainline 646145SN/APseudoLRUPolicy::PseudoLRUPolicy(Index num_sets, Index assoc) 657039SN/A : AbstractReplacementPolicy(num_sets, assoc) 666145SN/A{ 677039SN/A // associativity cannot exceed capacity of tree representation 687039SN/A assert(num_sets > 0 && assoc > 1 && assoc <= (Index) sizeof(uint64)*4); 696145SN/A 707039SN/A m_trees = NULL; 717039SN/A m_num_levels = 0; 726145SN/A 737039SN/A m_effective_assoc = 1; 747039SN/A while (m_effective_assoc < assoc) { 757039SN/A // effective associativity is ceiling power of 2 767039SN/A m_effective_assoc <<= 1; 777039SN/A } 787039SN/A assoc = m_effective_assoc; 797039SN/A while (true) { 807039SN/A assoc /= 2; 817039SN/A if(!assoc) break; 827039SN/A m_num_levels++; 837039SN/A } 847039SN/A assert(m_num_levels < sizeof(unsigned int)*4); 857039SN/A m_trees = new uint64[m_num_sets]; 867039SN/A for (unsigned i = 0; i < m_num_sets; i++) { 877039SN/A m_trees[i] = 0; 887039SN/A } 896145SN/A} 906145SN/A 916145SN/Ainline 926145SN/APseudoLRUPolicy::~PseudoLRUPolicy() 936145SN/A{ 947039SN/A if (m_trees != NULL) 957039SN/A delete[] m_trees; 966145SN/A} 976145SN/A 987039SN/Ainline void 999505SN/APseudoLRUPolicy::touch(Index set, Index index, Tick time) 1007039SN/A{ 1017039SN/A assert(index >= 0 && index < m_assoc); 1027039SN/A assert(set >= 0 && set < m_num_sets); 1036145SN/A 1047039SN/A int tree_index = 0; 1057039SN/A int node_val; 1067039SN/A for (int i = m_num_levels - 1; i >= 0; i--) { 1077039SN/A node_val = (index >> i)&1; 1087039SN/A if (node_val) 1097039SN/A m_trees[set] |= node_val << tree_index; 1107039SN/A else 1117039SN/A m_trees[set] &= ~(1 << tree_index); 1127039SN/A tree_index = node_val ? (tree_index*2)+2 : (tree_index*2)+1; 1137039SN/A } 1147039SN/A m_last_ref_ptr[set][index] = time; 1156145SN/A} 1166145SN/A 1177039SN/Ainline Index 1187039SN/APseudoLRUPolicy::getVictim(Index set) const 1197039SN/A{ 1207039SN/A // assert(m_assoc != 0); 1217039SN/A Index index = 0; 1226145SN/A 1237039SN/A int tree_index = 0; 1247039SN/A int node_val; 1257039SN/A for (unsigned i = 0; i < m_num_levels; i++){ 1267039SN/A node_val = (m_trees[set] >> tree_index) & 1; 1277039SN/A index += node_val ? 0 : (m_effective_assoc >> (i + 1)); 1287039SN/A tree_index = node_val ? (tree_index * 2) + 1 : (tree_index * 2) + 2; 1297039SN/A } 1307039SN/A assert(index >= 0 && index < m_effective_assoc); 1316145SN/A 1327039SN/A /* return either the found index or the max possible index */ 1337039SN/A /* NOTE: this is not a fair replacement when assoc is not a power of 2 */ 1347039SN/A return (index > (m_assoc - 1)) ? m_assoc - 1 : index; 1356145SN/A} 1366145SN/A 1377039SN/A#endif // __MEM_RUBY_SYSTEM_PSEUDOLRUPOLICY_HH__ 138