Victim cache line selection

1. A method of evicting a victim cache line from a set-associative cache memory including a plurality of ways, said method comprising:

recording, in a data structure of the cache memory, an eviction history of an immediately previous N ways from which cache lines have been evicted, wherein N is an integer greater than 1, wherein recording the eviction history includes recording the ordering of evictions from an immediately previous N ways from which cache lines have been evicted, and wherein the ordering specifies ways belonging to different congruence classes among a group of multiple congruence classes including the selected congruence class;

in response to receipt of a memory access request specifying a target address, selecting a selected congruence class among a plurality of congruence classes in the cache memory based on the target address, wherein each of the plurality of congruence classes includes a plurality of members each belonging to a respective one of the plurality of ways;

removing, as a candidate for selection, multiple members of the selected congruence class based on the eviction history recorded in the data structure;

selecting a selected member from among remaining members of the selected congruence class that remain as candidates after the removing; and

evicting a victim cache line cached in the selected member of the selected congruence class.

2. The method of claim 1 , wherein a total number of the plurality of ways is not an integer power of two.

3. The method of claim 1 , wherein:

the method further comprises the cache memory determining whether the selected congruence class includes any invalid members;

the cache memory chooses the victim cache line utilizing the step of removing and the step of selecting in response to the determining that the selected congruence class contains no invalid members; and

the cache memory chooses the selected member randomly from among invalid members in response to determining that the selected congruence class includes multiple invalid members.

4. The method of claim 1 , wherein:

the method further comprises recording relative replacement priorities of the plurality of members of the selected congruence class in a replacement data structure; and

the selecting includes selecting the selected member based on the relative replacement priorities recorded in the replacement data structure.

5. The method of claim 4 , wherein the relative replacement priorities prioritize a least recently used member for replacement.

6. A set-associative cache memory comprising:

a cache array including a plurality of congruence classes, wherein each of the plurality of congruence classes includes a plurality of members each belonging to a respective one of a plurality of ways;

a cache directory of contents of the cache array;

a history data structure that records an eviction history of an immediately previous N ways from which cache lines have been evicted, wherein N is an integer greater than 1, wherein the eviction history records an ordering of evictions from an immediately previous N ways from which cache lines have been evicted, and wherein the ordering specifies ways belonging to different congruence classes among a group of multiple congruence classes including the selected congruence class;

replacement logic configured to perform:

in response to receipt of a memory access request specifying a target address, selecting a selected congruence class among the plurality of congruence classes based on the target address,

removing, as a candidate for selection, multiple members of the selected congruence class based on the history recorded in the history data structure;

selecting a selected member from among remaining members of the selected congruence class that remain as candidates after the removing; and

evicting a victim cache line cached in the selected member of the selected congruence class.

7. The cache memory of claim 6 , wherein a total number of the plurality of ways is not an integer power of two.

8. The cache memory of claim 6 , wherein:

the replacement logic is further configured to perform:

determining whether the selected congruence class includes any invalid members;

choosing the victim cache line by the removing and the selecting in response to the determining that the selected congruence class contains no invalid members; and

choosing the selected member randomly from among invalid members in response to determining that the selected congruence class includes multiple invalid members.

9. The cache memory of claim 6 , and further comprising:

a replacement data structure that records relative replacement priorities of the plurality of members of the selected congruence class, wherein the replacement logic performs the selecting based on the relative replacement priorities recorded in the replacement data structure.

10. The cache memory of claim 9 , wherein the relative replacement priorities prioritize a least recently used member for replacement.

11. A data processing system, comprising:

a processor core; and

a set-associative cache memory coupled to the processor core, said set-associative cache memory including:

a cache array including a plurality of congruence classes, wherein each of the plurality of congruence classes includes a plurality of members each belonging to a respective one of a plurality of ways, wherein N is an integer greater than 1;

a cache directory of contents of the cache array;

a history data structure that records an eviction history of an immediately previous N ways from which cache lines have been evicted, wherein the eviction history records an ordering of evictions from an immediately previous N ways from which cache lines have been evicted, and wherein the ordering specifies ways belonging to different congruence classes among a group of multiple congruence classes including the selected congruence class;

replacement logic configured to perform:

in response to receipt of a memory access request specifying a target address, selecting a selected congruence class among the plurality of congruence classes based on the target address,

removing, as a candidate for selection, multiple member of the selected congruence class based on the history recorded in the history data structure;

selecting a selected member from among remaining members of the selected congruence class that remain as candidates after the removing; and

evicting a victim cache line cached in the selected member of the selected congruence class.

12. The data processing system of claim 11 , wherein a total number of the plurality of ways is not an integer power of two.

13. The data processing system of claim 11 , wherein:

the replacement logic is further configured to perform:

determining whether the selected congruence class includes any invalid members;

choosing the victim cache line by the removing and the selecting in response to the determining that the selected congruence class contains no invalid members; and

choosing the selected member randomly from among invalid members in response to determining that the selected congruence class includes multiple invalid members.

14. The data processing system of claim 11 , and further comprising:

a replacement data structure that records relative replacement priorities of the plurality of members of the selected congruence class, wherein the replacement logic performs the selecting based on the relative replacement priorities recorded in the replacement data structure.

15. The data processing system of claim 14 , wherein the relative replacement priorities prioritize a least recently used member for replacement.