PseudoLRUPolicy.hh revision 7039
1/* 2 * Copyright (c) 2007 Mark D. Hill and David A. Wood 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 29#ifndef __MEM_RUBY_SYSTEM_PSEUDOLRUPOLICY_HH__ 30#define __MEM_RUBY_SYSTEM_PSEUDOLRUPOLICY_HH__ 31 32#include "mem/ruby/system/AbstractReplacementPolicy.hh" 33 34/** 35 * Implementation of tree-based pseudo-LRU replacement 36 * 37 * Works for any associativity between 1 and 128. 38 * 39 * Also implements associativities that are not a power of 2 by 40 * ignoring paths that lead to a larger index (i.e. truncating the 41 * tree). Note that when this occurs, the algorithm becomes less 42 * fair, as it will favor indicies in the larger (by index) half of 43 * the associative set. This is most unfair when the nearest power of 44 * 2 is one below the associativy, and most fair when it is one above. 45 */ 46 47class PseudoLRUPolicy : public AbstractReplacementPolicy 48{ 49 public: 50 PseudoLRUPolicy(Index num_sets, Index assoc); 51 ~PseudoLRUPolicy(); 52 53 void touch(Index set, Index way, Time time); 54 Index getVictim(Index set) const; 55 56 private: 57 unsigned int m_effective_assoc; /** nearest (to ceiling) power of 2 */ 58 unsigned int m_num_levels; /** number of levels in the tree */ 59 uint64* m_trees; /** bit representation of the 60 * trees, one for each set */ 61}; 62 63inline 64PseudoLRUPolicy::PseudoLRUPolicy(Index num_sets, Index assoc) 65 : AbstractReplacementPolicy(num_sets, assoc) 66{ 67 int num_tree_nodes; 68 69 // associativity cannot exceed capacity of tree representation 70 assert(num_sets > 0 && assoc > 1 && assoc <= (Index) sizeof(uint64)*4); 71 72 m_trees = NULL; 73 m_num_levels = 0; 74 75 m_effective_assoc = 1; 76 while (m_effective_assoc < assoc) { 77 // effective associativity is ceiling power of 2 78 m_effective_assoc <<= 1; 79 } 80 assoc = m_effective_assoc; 81 while (true) { 82 assoc /= 2; 83 if(!assoc) break; 84 m_num_levels++; 85 } 86 assert(m_num_levels < sizeof(unsigned int)*4); 87 num_tree_nodes = (1 << m_num_levels) - 1; 88 m_trees = new uint64[m_num_sets]; 89 for (unsigned i = 0; i < m_num_sets; i++) { 90 m_trees[i] = 0; 91 } 92} 93 94inline 95PseudoLRUPolicy::~PseudoLRUPolicy() 96{ 97 if (m_trees != NULL) 98 delete[] m_trees; 99} 100 101inline void 102PseudoLRUPolicy::touch(Index set, Index index, Time time) 103{ 104 assert(index >= 0 && index < m_assoc); 105 assert(set >= 0 && set < m_num_sets); 106 107 int tree_index = 0; 108 int node_val; 109 for (int i = m_num_levels - 1; i >= 0; i--) { 110 node_val = (index >> i)&1; 111 if (node_val) 112 m_trees[set] |= node_val << tree_index; 113 else 114 m_trees[set] &= ~(1 << tree_index); 115 tree_index = node_val ? (tree_index*2)+2 : (tree_index*2)+1; 116 } 117 m_last_ref_ptr[set][index] = time; 118} 119 120inline Index 121PseudoLRUPolicy::getVictim(Index set) const 122{ 123 // assert(m_assoc != 0); 124 Index index = 0; 125 126 int tree_index = 0; 127 int node_val; 128 for (unsigned i = 0; i < m_num_levels; i++){ 129 node_val = (m_trees[set] >> tree_index) & 1; 130 index += node_val ? 0 : (m_effective_assoc >> (i + 1)); 131 tree_index = node_val ? (tree_index * 2) + 1 : (tree_index * 2) + 2; 132 } 133 assert(index >= 0 && index < m_effective_assoc); 134 135 /* return either the found index or the max possible index */ 136 /* NOTE: this is not a fair replacement when assoc is not a power of 2 */ 137 return (index > (m_assoc - 1)) ? m_assoc - 1 : index; 138} 139 140#endif // __MEM_RUBY_SYSTEM_PSEUDOLRUPOLICY_HH__ 141