Cache Line Replacement Selection using a Logical Multi-Way Tree with Access Order States Maintained at Each Node
Original Publication Date: 2004-Aug-18
Included in the Prior Art Database: 2004-Aug-18
An improved method for cache line replacement selection in a set-associative cache is disclosed. In this method, a line is selected for replacement within a set in an N-way set associative cache using a logical multi-way tree, where the leaf nodes of the tree represent lines in a set, and where if the branching factor of a given node in the logical tree at a given level is k, then the state of the node is represented by one of k! (k factorial) logical states representing an access order of the nodes below the given node in the logical tree.