Patent ID: 7917700

Claim:
A method for replacing a cache line comprising the steps of: identifying a requirement for replacement in a congruence class; calculating a first pseudo least recently used (PLRU) cache line for replacement in the congruence class; calculating an alternate pseudo least recently used (PLRU) cache line for replacement in the congruence class; checking for said calculated first PLRU cache line being in a victim cache coherency state; said victim cache coherency state being used to manage a cache line currently in use by a read claim engine or a snoop engine; selecting said calculated alternate PLRU cache line for replacement responsive to identifying said calculated first PLRU cache line being in the victim cache coherency state; providing a binary tree representing a current pseudo least recently used (PLRU) cache line and each of a plurality of ways of associativity for the shared cache including 8 ways of associativity for the shared cache represented by way 0, way 1, way 2, way 3, way 4, way 5, way 6, way 7; and wherein the current PLRU cache line is represented by 7 bits including B 0 , B 1 , B 2 , B 3 , B 4 , B 5 , B 6 ; providing selection pseudo-code including ALT_PLRU <= way_0 when ((LRU/=way_0) and (B0=‘0’) and (B1=‘0’)) else way_1 when ((LRU/=way_1) and (B0=‘1’) and (B1=‘0’)) else way_2 when ((LRU/=way_2) and (B2=‘0’) and (B1=‘1’)) else way_3 when ((LRU/=way_3) and (B2=‘1’) and (B1=‘1’)) else way_4 when ((LRU/=way_4) and (B4=‘0’) and (B5=‘0’)) else way_5 when ((LRU/=way_5) and (B4=‘1’) and (B5=‘0’)) else way_6 when ((LRU/=way_6) and (B6=‘0’) and (B5=‘1’)) else way_7 when ((LRU/=way_7) and (B6=‘1’) and (B5=‘1’)). where each of said respective 8 ways 0-7 of associativity for the shared cache is represented by way_n, and the respective terms (LRU/=way_n) defines a multiplexer decision pipe receiving respective current PLRU cache line bits B 0 , B 1 , B 2 , B 3 , B 4 , B 5 , B 6 providing the alternate PLRU output represented by ALT_PLRU.