PseudoLRUPolicy.hh revision 6145
1 2#ifndef PSEUDOLRUPOLICY_H 3#define PSEUDOLRUPOLICY_H 4 5#include "AbstractReplacementPolicy.hh" 6 7/** 8 * Implementation of tree-based pseudo-LRU replacement 9 * 10 * Works for any associativity between 1 and 128. 11 * 12 * Also implements associativities that are not a power of 2 by 13 * ignoring paths that lead to a larger index (i.e. truncating the 14 * tree). Note that when this occurs, the algorithm becomes less 15 * fair, as it will favor indicies in the larger (by index) half of 16 * the associative set. This is most unfair when the nearest power of 17 * 2 is one below the associativy, and most fair when it is one above. 18 */ 19 20class PseudoLRUPolicy : public AbstractReplacementPolicy { 21 public: 22 23 PseudoLRUPolicy(Index num_sets, Index assoc); 24 ~PseudoLRUPolicy(); 25 26 void touch(Index set, Index way, Time time); 27 Index getVictim(Index set) const; 28 29 private: 30 unsigned int m_effective_assoc; /** nearest (to ceiling) power of 2 */ 31 unsigned int m_num_levels; /** number of levels in the tree */ 32 uint64* m_trees; /** bit representation of the trees, one for each set */ 33}; 34 35inline 36PseudoLRUPolicy::PseudoLRUPolicy(Index num_sets, Index assoc) 37 : AbstractReplacementPolicy(num_sets, assoc) 38{ 39 int num_tree_nodes; 40 41 // associativity cannot exceed capacity of tree representation 42 assert(num_sets > 0 && assoc > 1 && assoc <= (Index) sizeof(uint64)*4); 43 44 m_trees = NULL; 45 m_num_levels = 0; 46 47 m_effective_assoc = 1; 48 while(m_effective_assoc < assoc){ 49 m_effective_assoc <<= 1; // effective associativity is ceiling power of 2 50 } 51 assoc = m_effective_assoc; 52 while(true){ 53 assoc /= 2; 54 if(!assoc) break; 55 m_num_levels++; 56 } 57 assert(m_num_levels < sizeof(unsigned int)*4); 58 num_tree_nodes = ((int)pow(2, m_num_levels))-1; 59 m_trees = new uint64[m_num_sets]; 60 for(unsigned int i=0; i< m_num_sets; i++){ 61 m_trees[i] = 0; 62 } 63} 64 65inline 66PseudoLRUPolicy::~PseudoLRUPolicy() 67{ 68 if(m_trees != NULL) 69 delete[] m_trees; 70} 71 72inline 73void PseudoLRUPolicy::touch(Index set, Index index, Time time){ 74 assert(index >= 0 && index < m_assoc); 75 assert(set >= 0 && set < m_num_sets); 76 77 int tree_index = 0; 78 int node_val; 79 for(int i=m_num_levels -1; i>=0; i--){ 80 node_val = (index >> i)&1; 81 if(node_val) 82 m_trees[set] |= node_val << tree_index; 83 else 84 m_trees[set] &= ~(1 << tree_index); 85 tree_index = node_val ? (tree_index*2)+2 : (tree_index*2)+1; 86 } 87 m_last_ref_ptr[set][index] = time; 88} 89 90inline 91Index PseudoLRUPolicy::getVictim(Index set) const { 92 // assert(m_assoc != 0); 93 94 Index index = 0; 95 96 int tree_index = 0; 97 int node_val; 98 for(unsigned int i=0;i<m_num_levels;i++){ 99 node_val = (m_trees[set]>>tree_index)&1; 100 index += node_val?0:(m_effective_assoc >> (i+1)); 101 tree_index = node_val? (tree_index*2)+1 : (tree_index*2)+2; 102 } 103 assert(index >= 0 && index < m_effective_assoc); 104 105 /* return either the found index or the max possible index */ 106 /* NOTE: this is not a fair replacement when assoc is not a power of 2 */ 107 return (index > (m_assoc-1)) ? m_assoc-1:index; 108} 109 110#endif // PSEUDOLRUPOLICY_H 111