Publication

Abstract : High associativity with replacement policy as LRU is annbsp;optimal solution for cache design when miss rate has to benbsp;reduced. But when associativity increases, implementing LRUnbsp;policy becomes complex. As many advance and demandingnbsp;technologies like multimedia, multithreading, database and lownbsp;power devices running on high performance processors in serversnbsp;and work stations use higher associativity to enrich performance,nbsp;there is a need for designing highly efficient LRU hardwarenbsp;implementations. This paper gives analyses variousnbsp;implementations of the LRU policy for a cache with highnbsp;associativity. The implementation problems are explored,nbsp;objectives of the design are identified and variousnbsp;implementations namely Square Matrix, Skewed Matrix,nbsp;Counter, Link-list, Phase and Systolic Array methods arenbsp;compared with each other on the basis of objective outlined. Thesenbsp;implementations are synthesized to determine the constraints andnbsp;the effect of increase in associativity on the performance. Whennbsp;the associativity is smaller, reduction of associated logic isnbsp;important and at higher associativity conservation of space isnbsp;more important. At higher associativity Linked List, Systolicnbsp;Array and Skewed Matrix are the designs found suitable fornbsp;implementations