PseudoLRUPolicy.hh revision 6145
15083Sgblack@eecs.umich.edu 25083Sgblack@eecs.umich.edu#ifndef PSEUDOLRUPOLICY_H 35083Sgblack@eecs.umich.edu#define PSEUDOLRUPOLICY_H 45083Sgblack@eecs.umich.edu 55083Sgblack@eecs.umich.edu#include "AbstractReplacementPolicy.hh" 65083Sgblack@eecs.umich.edu 75083Sgblack@eecs.umich.edu/** 85083Sgblack@eecs.umich.edu * Implementation of tree-based pseudo-LRU replacement 95083Sgblack@eecs.umich.edu * 105083Sgblack@eecs.umich.edu * Works for any associativity between 1 and 128. 115083Sgblack@eecs.umich.edu * 125083Sgblack@eecs.umich.edu * Also implements associativities that are not a power of 2 by 135083Sgblack@eecs.umich.edu * ignoring paths that lead to a larger index (i.e. truncating the 145083Sgblack@eecs.umich.edu * tree). Note that when this occurs, the algorithm becomes less 155083Sgblack@eecs.umich.edu * fair, as it will favor indicies in the larger (by index) half of 165083Sgblack@eecs.umich.edu * the associative set. This is most unfair when the nearest power of 175083Sgblack@eecs.umich.edu * 2 is one below the associativy, and most fair when it is one above. 185083Sgblack@eecs.umich.edu */ 195083Sgblack@eecs.umich.edu 205083Sgblack@eecs.umich.educlass PseudoLRUPolicy : public AbstractReplacementPolicy { 215083Sgblack@eecs.umich.edu public: 225083Sgblack@eecs.umich.edu 235083Sgblack@eecs.umich.edu PseudoLRUPolicy(Index num_sets, Index assoc); 245083Sgblack@eecs.umich.edu ~PseudoLRUPolicy(); 255083Sgblack@eecs.umich.edu 265083Sgblack@eecs.umich.edu void touch(Index set, Index way, Time time); 275083Sgblack@eecs.umich.edu Index getVictim(Index set) const; 285083Sgblack@eecs.umich.edu 295083Sgblack@eecs.umich.edu private: 305083Sgblack@eecs.umich.edu unsigned int m_effective_assoc; /** nearest (to ceiling) power of 2 */ 315083Sgblack@eecs.umich.edu unsigned int m_num_levels; /** number of levels in the tree */ 325083Sgblack@eecs.umich.edu uint64* m_trees; /** bit representation of the trees, one for each set */ 335083Sgblack@eecs.umich.edu}; 345083Sgblack@eecs.umich.edu 355083Sgblack@eecs.umich.eduinline 365083Sgblack@eecs.umich.eduPseudoLRUPolicy::PseudoLRUPolicy(Index num_sets, Index assoc) 375083Sgblack@eecs.umich.edu : AbstractReplacementPolicy(num_sets, assoc) 385083Sgblack@eecs.umich.edu{ 395083Sgblack@eecs.umich.edu int num_tree_nodes; 405083Sgblack@eecs.umich.edu 415083Sgblack@eecs.umich.edu // associativity cannot exceed capacity of tree representation 425083Sgblack@eecs.umich.edu assert(num_sets > 0 && assoc > 1 && assoc <= (Index) sizeof(uint64)*4); 435083Sgblack@eecs.umich.edu 445083Sgblack@eecs.umich.edu m_trees = NULL; 455083Sgblack@eecs.umich.edu m_num_levels = 0; 465083Sgblack@eecs.umich.edu 475083Sgblack@eecs.umich.edu m_effective_assoc = 1; 485083Sgblack@eecs.umich.edu while(m_effective_assoc < assoc){ 495083Sgblack@eecs.umich.edu m_effective_assoc <<= 1; // effective associativity is ceiling power of 2 505083Sgblack@eecs.umich.edu } 515083Sgblack@eecs.umich.edu assoc = m_effective_assoc; 525083Sgblack@eecs.umich.edu while(true){ 535083Sgblack@eecs.umich.edu assoc /= 2; 545083Sgblack@eecs.umich.edu if(!assoc) break; 555083Sgblack@eecs.umich.edu m_num_levels++; 565083Sgblack@eecs.umich.edu } 575083Sgblack@eecs.umich.edu assert(m_num_levels < sizeof(unsigned int)*4); 585083Sgblack@eecs.umich.edu num_tree_nodes = ((int)pow(2, m_num_levels))-1; 595083Sgblack@eecs.umich.edu m_trees = new uint64[m_num_sets]; 605083Sgblack@eecs.umich.edu for(unsigned int i=0; i< m_num_sets; i++){ 615083Sgblack@eecs.umich.edu m_trees[i] = 0; 625083Sgblack@eecs.umich.edu } 635083Sgblack@eecs.umich.edu} 645083Sgblack@eecs.umich.edu 655083Sgblack@eecs.umich.eduinline 665083Sgblack@eecs.umich.eduPseudoLRUPolicy::~PseudoLRUPolicy() 675083Sgblack@eecs.umich.edu{ 685083Sgblack@eecs.umich.edu if(m_trees != NULL) 695083Sgblack@eecs.umich.edu delete[] m_trees; 705083Sgblack@eecs.umich.edu} 715083Sgblack@eecs.umich.edu 725083Sgblack@eecs.umich.eduinline 735083Sgblack@eecs.umich.eduvoid PseudoLRUPolicy::touch(Index set, Index index, Time time){ 745083Sgblack@eecs.umich.edu assert(index >= 0 && index < m_assoc); 755083Sgblack@eecs.umich.edu assert(set >= 0 && set < m_num_sets); 765083Sgblack@eecs.umich.edu 775083Sgblack@eecs.umich.edu int tree_index = 0; 785083Sgblack@eecs.umich.edu int node_val; 795083Sgblack@eecs.umich.edu for(int i=m_num_levels -1; i>=0; i--){ 805083Sgblack@eecs.umich.edu node_val = (index >> i)&1; 815083Sgblack@eecs.umich.edu if(node_val) 825083Sgblack@eecs.umich.edu m_trees[set] |= node_val << tree_index; 835083Sgblack@eecs.umich.edu else 845083Sgblack@eecs.umich.edu m_trees[set] &= ~(1 << tree_index); 855083Sgblack@eecs.umich.edu tree_index = node_val ? (tree_index*2)+2 : (tree_index*2)+1; 865083Sgblack@eecs.umich.edu } 875083Sgblack@eecs.umich.edu m_last_ref_ptr[set][index] = time; 885083Sgblack@eecs.umich.edu} 895083Sgblack@eecs.umich.edu 905083Sgblack@eecs.umich.eduinline 915083Sgblack@eecs.umich.eduIndex PseudoLRUPolicy::getVictim(Index set) const { 925083Sgblack@eecs.umich.edu // assert(m_assoc != 0); 935083Sgblack@eecs.umich.edu 945083Sgblack@eecs.umich.edu Index index = 0; 955083Sgblack@eecs.umich.edu 965083Sgblack@eecs.umich.edu int tree_index = 0; 975083Sgblack@eecs.umich.edu int node_val; 985083Sgblack@eecs.umich.edu for(unsigned int i=0;i<m_num_levels;i++){ 995083Sgblack@eecs.umich.edu node_val = (m_trees[set]>>tree_index)&1; 1005083Sgblack@eecs.umich.edu index += node_val?0:(m_effective_assoc >> (i+1)); 1015083Sgblack@eecs.umich.edu tree_index = node_val? (tree_index*2)+1 : (tree_index*2)+2; 1025083Sgblack@eecs.umich.edu } 1035083Sgblack@eecs.umich.edu assert(index >= 0 && index < m_effective_assoc); 1045083Sgblack@eecs.umich.edu 1055083Sgblack@eecs.umich.edu /* return either the found index or the max possible index */ 1065083Sgblack@eecs.umich.edu /* NOTE: this is not a fair replacement when assoc is not a power of 2 */ 1075083Sgblack@eecs.umich.edu return (index > (m_assoc-1)) ? m_assoc-1:index; 1085083Sgblack@eecs.umich.edu} 1095083Sgblack@eecs.umich.edu 1105083Sgblack@eecs.umich.edu#endif // PSEUDOLRUPOLICY_H 1115083Sgblack@eecs.umich.edu