LRU cache replacement for a partitioned set associative cache

• US 7,856,633 B1
• Filed: 03/24/2000
• Issued: 12/21/2010
• Est. Priority Date: 03/24/2000
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Lee, Chan W., Krick, Robert, Hinton, Glenn
• Primary Examiner(s): Zhen; Li B
• Assistant Examiner(s): Chew; Brian
• Application Number:
  US09/534,191
• Time in Patent Office: 3,924 Days
• Field of Search: 709/100, 709/102, 709/104, 709/107, 709/108, 711/100, 711/101, 711/117, 711/118, 711/129, 711/136, 718/105
• US Class Current: 718/105
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 9/3017 Runtime instruction translation, e.g. macros
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/3808 for instruction reuse, e.g. trace cache, branch target cache
• CPC Class Codes: G06F 9/382 Pipelined decoding, e.g. using predecoding
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3856 Reordering of instructions, e.g. using queues or age tags
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]

Abstract

A method of partitioning a memory resource, associated with a multi-threaded processor, includes defining the memory resource to include first and second portions that are dedicated to the first and second threads respectively. A third portion of the memory resource is then designated as being shared between the first and second threads. Upon receipt of an information item, (e.g., a microinstruction associated with the first thread and to be stored in the memory resource), a history of Least Recently Used (LRU) portions is examined to identify a location in either the first or the third portion, but not the second portion, as being a least recently used portion. The second portion is excluded from this examination on account of being dedicated to the second thread. The information item is then stored within a location, within either the first or the third portion, identified as having been least recently used.

Claims

1. A method including:

dedicating a first portion comprising one or more ways of an N way set associative cache exclusively to a first thread;

dedicating a second portion comprising one or more ways of the cache exclusively to a second thread;

dynamically sharing a third portion comprising one or more ways of the cache between the first and second threads; and

performing victim selection in the cache by,

examining a Least Recently Used (LRU) history for a selected set to identify a least recently used way within the cache as a candidate way to store an information item associated with the first thread;

determining whether the candidate way is within the first or the third portion of the cache;

if the candidate way is within the first or the third portion of the cache, then storing the information associated with the first thread in the candidate way; and

if the candidate way is within the second portion of the cache, then identifying a further way within the cache as being the candidate way, wherein the further way is not the candidate way previously identified.

2. The method of claim 1 wherein the dynamic sharing of the third portion of the cache is performed according to resource demands of the respective first and second threads.

3. The method of claim 1 wherein the examining includes examining the LRU history to identify M least recently used ways within the cache, wherein M>

1, and wherein the determining is performed for the M candidate ways, and wherein the further way is another of the M candidate ways.

4. The method of claim 1 wherein the identifying of the further way as being the candidate way comprises identifying a second-least recently used way within the cache.

5. The method of claim 1 wherein the examining includes examining entries within the LRU history for the selected set, each entry corresponding to a respective one of the ways, wherein the entries are ordered in a sequence determined by least recent usage of the respective ways.

6. The method of claim 1 wherein the cache is a trace cache memory, and wherein the information item associated with the first thread comprises a microinstruction of the first thread.

7. An N way set associative cache comprising:

a first portion comprising one or more ways dedicated to utilization by a first thread executing within a multi-threaded processor;

a second portion comprising one or more ways dedicated to utilization by a second thread executing within the multi-threaded processor;

a third portion comprising one or more ways shared by the first and second threads; and

selection logic to examine a Least Recently Used (LRU) history for a selected set to identify a least recently used way within the cache as a candidate way within which to store an information item associated with the first thread, to store the information associated the first thread in the candidate way if the candidate way is within the first or third portions of the cache, but if the candidate way is within the second portion of the cache, then to identify a further way within the cache as being the candidate way, wherein the further way is not the candidate way previously identified.

8. The cache of claim 7 wherein the third portion of the cache is shared according to resource demands of the first and second threads.

9. The cache of claim 7 wherein the selection logic is to examine for the selected set the LRU history to identify M least recently used ways within the cache, and wherein M>

1.

10. The cache of claim 7 wherein the selection logic identifies as the further way a second-least recently used way within the cache.

11. The cache of claim 7 wherein the selection logic examines entries within the LRU history for the selected set to identify the least recently used way, wherein the entries are ordered in a sequence determined by least recent usage of the ways to which they correspond.

12. The cache of claim 7 wherein the cache is a trace cache memory, and wherein the information item associated with the first thread comprises a microinstruction of the first thread.

13. A method including:

configuring an N way set associative cache, associated with a multi-threaded processor, to include first and second portions comprising one or more ways dedicated to the first and second threads respectively and a third portion comprising one or more ways shared between the first and second threads;

for an information item associated with the first thread, examining for a selected set a history of least recently used ways until one is found that is within one of the first and third portions; and

storing the information item within the found way.

14. The method of claim 13 wherein the sharing of the third portion of the cache is performed according to resource demands of the respective first and second threads.

15. The method of claim 13, wherein the examining is performed on M ways of the history of least recently used ways, and where M>

1.

16. The method of claim 13 wherein the examination of the history of least recently used ways includes examining entries within the history, each entry corresponding to a respective one of the ways, wherein the entries are ordered in a sequence determined by least recent usage of the respective ways.

17. The method of claim 13 wherein the cache is a trace cache memory, and wherein the information item associated with the first thread comprises a microinstruction of the first thread.

18. A computer storage storing a sequence of instructions that, when executed within a processor, causes the processor to perform the steps of:

dedicating a first portion comprising one or more ways of an N way set associative cache exclusively to a first thread;

dedicating a second portion comprising one or more ways of the cache exclusively to a second thread;

dynamically sharing a third portion comprising one or more ways of the cache between the first and second threads; and

performing victim selection in the cache by,

examining a Least Recently Used (LRU) history for a selected set to identify a least recently used way within the cache as a candidate way to store an information item associated with the first thread;

determining whether the candidate way is within the first or the third portion of the cache;

if the candidate way is within the first or the third portion of the cache, then storing the information associated with the first thread in the candidate way; and

if the candidate way is within the second portion of the cache, then identifying a further way within the cache as being the candidate way, wherein the further way is not the candidate way previously identified.

19. The computer storage of claim 18 wherein the dynamic sharing of the third portion of the cache is performed according to resource demands of the respective first and second threads.

20. The computer storage of claim 18 wherein the examining includes examining the LRU history to identify M least recently used ways within the cache, wherein M>

1, and wherein the determining is performed for the M candidate ways, and wherein the further way is another of the M candidate ways.

21. The computer storage of claim 18 wherein the identifying of the further way as being the candidate way comprises identifying a second-least recently used way within the cache.

22. The computer storage of claim 18 wherein the examining includes examining entries within the LRU history for the selected set, each entry corresponding to a respective one of the ways, wherein the entries are ordered in a sequence determined by least recent usage of the respective ways.

23. The computer storage of claim 18 wherein the cache is a trace cache memory, and wherein the information item associated with the first thread comprises a microinstruction of the first thread.

24. A method comprising:

detecting misses in an N way set associative cache of a processor;

performing victim selection responsive to each of the misses in a manner that partitions the capacity of the cache to make a first and second portion each comprising one or more ways available for replacement respectively only by each of a first and second instruction threads while at the same time that defines a shared portion comprising one or more ways available to both the first and second instruction threads, wherein the performing victim selection responsive to each of the misses includes examining entries of a least recently used history until an available one of said ways within a selected set is found.

25. The method of claim 24, further comprising:

performing fine multithreading of the first and second threads in the processor.

26. The method of claim 24, wherein the examining includes examining M of the entries corresponding to the M least recently used of the ways, and wherein M>

1.

27. The method of claim 24 wherein the shared portion of the cache is shared according to resource demands of the respective first and second threads.

28. The method of claim 24 wherein each of the entries corresponds to a respective one of the ways, and wherein the entries are ordered in a sequence determined by least recent usage of the respective ways.

29. The method of claim 24 wherein the cache is a trace cache memory to store microinstructions of the first and second instruction threads.

30. An apparatus comprising:

a processor including,

an N way set associative cache having a storage capacity, and

victim selection logic including logic to partition the storage capacity of the cache having a dedicated portion comprising one or more ways for each of a first and second instruction threads while at the same time having a shared portion comprising one or more ways accessible by both the first and second threads, wherein the victim selection logic responsive to each of the misses in the cache to examine entries of a least recently used history for a selected set of the cache until one of said ways is found that is available to the instruction thread causing that cache miss.

31. The apparatus of claim 30, wherein the cache is a trace cache and the processor is capable of fine simultaneous multithreading.

32. The apparatus of claim 30, wherein the cache is a trace cache, wherein the trace cache is to store microinstructions of the first and second threads.

33. The apparatus of claim 30 wherein the entries are ordered in a sequence determined by least recent usage of the ways to which they correspond.

34. The apparatus of claim 30 wherein the victim selection logic responsive to each of the misses in the cache to examine M entries corresponding to M least recently used ways within the cache, and wherein M>

1.

35. The apparatus of claim 30 wherein the shared portion of the cache is shared according to resource demands of the respective first and second threads.