LRU pointer updating in a controller for two-way set associative cache

• US 5,724,547 A
• Filed: 06/27/1996
• Issued: 03/03/1998
• Est. Priority Date: 04/25/1991
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Nadir, James, Iyengar, Sundaravarathan Rajagopalan
• Primary Examiner(s): Gossage, Glenn
• Application Number:
  US08/671,446
• Time in Patent Office: 614 Days
• Field of Search: 395/455, 395/456, 395/460, 395/462, 395/463, 395/471, 395/472, 395/473, 395/483, 395/486, 395/487, 365/49, 365/230.03, 365/230.04
• US Class Current: 711/128
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel

Abstract

A cache controller tag random access memory (RAM) is configured into two ways, each way including tag and valid-bit storage for associatively searching a directory for cache data-array addresses. The two ways, a right way and a left way, each store tag addresses. There are two lines selected during a line fill to one of the ways. A least recently used (LRU) pointer selects which way to fill on a line fill cycle. The right way is selected for a line fill in response to right hit signal provided that the LRU pointer points to the right way. The LRU pointer is flipped to point to the left way upon the filling of the right line of the right way. The left way is selected for a line fill in response to a left hit signal provided that the LRU pointer points to the left way. The LRU pointer is flipped to point to the right way upon the filling of the left line of the left way.

Claims

1. A method of selecting a way within a cache directory for storing a received tag address, the received tag address being associated with data to be stored in a cache, associated with the cache directory, the cache directory comprising first and second ways each configured to store a tag address, the method comprising the steps of:

automatically maintaining a pointer for identifying either the first or the second way as storing a tag address associated with data stored within the cache that has been least recently used; and

selecting the first way for storage of the received tag address if the first way is identified by the pointer.

2. The method of claim 1 wherein the step of maintaining the pointer comprises identifying the first way with the pointer when the second way receives a tag address hit during a memory read or write cycle.

3. The method of claim 1 wherein the step of maintaining the pointer comprises identifying the first way with the pointer when a tag address is received within the second way.

4. The method of claim 1 wherein the step of maintaining the pointer comprises maintaining the pointer in a current state if a tag address miss of both the first and second ways occurs.

5. The method of claim 1 wherein the first and second ways are each configured to store a plurality of tag addresses, each tag address of the first way being paired with a tag address of the second way, and wherein the method includes the step of maintaining a pointer for each tag address pairing for identifying either the tag address within the first or second way as being associated with data stored within the cache that has been least recently used.

6. The method of claim 1 wherein the step of maintaining the pointer comprises identifying the first way with the pointer when data, stored within the cache and associated with a tag address stored in the first way, is invalidated.

7. The method of claim 6 wherein the data, stored within the cache and associated with the tag address stored in the first way, is invalidated in a snoop cycle.

8. A method of claim 1, wherein the step of maintaining the pointer comprises the steps of:

detecting the occurrence of a validation action or an invalidation action relating to a first tag address stored in the first way;

configuring the pointer to identify the second way on the occurrence of the validation action; and

configuring the pointer to identify the first way on the occurrence of the invalidation action.

9. The method of claim 8 wherein the validation action comprises a tag address hit on the first tag address stored in the first way during a memory read or write cycle.

10. The method of claim 8 wherein the validation action comprises storing the first tag address in the first way.

11. The method of claim 8 wherein the invalidation action comprises a tag address hit on the first tag stored in the first way during a snoop cycle.

12. The method of claim 8 including the step of maintaining the pointer in a current state on the non-occurrence of either a validation or an invalidation action relating to the first tag address stored in the first way.

13. Apparatus for selecting a way, within a cache directory, for storing a received tag address, the received tag address being associated with data to be stored in a cache associated with the cache directory and the cache directory comprising first and second ways each configured to store a tag address, the apparatus comprising:

means for automatically configuring a pointer for identifying either the first or the second way as storing a tag address associated with data stored within the cache that has been least recently used; and

means for selecting the first way for storage of the received tag address if the first way is identified by the pointer.

14. The apparatus of claim 13 wherein the means for automatically configuring configures the pointer to identifying the first way when the second way receives a tag address hit during a memory read or write cycle.

15. The apparatus of claim 13 wherein means for automatically configuring configures the pointer to identify the first way when a tag address is received within the second way.

16. The apparatus of claim 13 wherein the means for automatically configuring configures the pointer to identify the first way when data, stored within the cache and associated with a tag address stored in the first way, is invalidated.

17. Apparatus for selecting a way, within a cache directory, for storing a received tag address, the received tag address being associated with data to be stored in a cache associated with a cache directory and the cache directory comprising first and second ways each configured to store a tag address, the apparatus comprising:

first logic that automatically sets a pointer to identify either the first or the second way as storing a tag address associated with data that is stored within the cache and that has been least recently used; and

second logic that selects the first way for storage of the received tag address if the first way is identified by the pointer.

18. The apparatus of claim 17 wherein the first logic sets the pointer to identify the first way when the second way receives a tag address hit during a memory read or write cycle.

19. The apparatus of claim 17 wherein the first logic sets the pointer to identify the first way when a tag address is received within the second way.

20. The apparatus of claim 17 wherein the first logic configures the pointer to identify the first way when data, stored within the cache and associated with the tag address stored in the first way, is invalidated.