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

• US 5,530,833 A
• Filed: 06/06/1995
• Issued: 06/25/1996
• Est. Priority Date: 04/25/1991
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Iyengar, Sundaravarathan R., Nadir, James
• Primary Examiner(s): Gossage, Glenn
• Application Number:
  US08/486,132
• Time in Patent Office: 385 Days
• Field of Search: 395/463, 395/487, 395/456, 395/455, 395/460, 395/462, 395/471, 395/472, 395/473, 395/483, 395/486, 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. An apparatus for selecting which way to fill during a line fill cycle in a cache directory that is divided into two ways, a right way and a left way, each way storing tag addresses and in which there are two lines selected during a line fill to one of said ways, said apparatus including a least recently used pointer in each line of a data array, said least recently used pointer when set to a first state pointing to said left way and when set to a second state pointing to said right way, said apparatus comprising:

a bus connected to said right way of said directory and to said left way of said directory, for transmitting a bus address including a tag;

a first logic (28) connected to said bus that generates a right hit signal upon a first condition that a match exists between said tag and one of said tag addresses stored in said right way;

a second logic (26) connected to said bus that generates a left hit signal upon a second condition that a match exists between said tag and one of said tag addresses stored in said left way; and

,

an interface control logic (30), connected to said first logic (28), said second logic (26) and said least recently used pointer, that selects said right way for a line fill in response to said right hit signal and selects said left way for a line fill in response to said left hit signal and upon a third condition that neither said right hit signal nor said left hit signal occurs, that selects said left way for a line fill provided that said least recently used pointer is set to said first state and that selects said right way for a line fill in response to said right hit signal provided that said least recently used pointer is set to said second state, said interface control logic (30) setting said least recently used pointer to said second state upon a filling of a line of said left way and setting said least recently used pointer to said first state upon a filling of a line of said right way.

2. A method of selecting, utilizing a least recently used pointer, which way to fill during a line fill cycle in a cache directory that is divided into two ways, a right way and a left way, each way storing tag addresses and in which there are two lines selected during a line fill to one of said ways, said method comprising steps of:

A. comparing a tag with said tag addresses stored in said right and left ways of said directory;

B. generating a right hit signal upon a condition that a match exists between said tag and one of said tag addresses stored in said right way;

C. generating a left hit signal upon a condition that a match exists between said tag and one of said tag addresses stored in said left way;

D. selecting said right way for a line fill in response to said right hit signal;

E. selecting said left way for a line fill in response to said left hit signal;

F. selecting said right way for a line fill upon a condition that neither a right hit signal nor a left hit signal occurs and said least recently used pointer points to said right way;

G. selecting said left way for a line fill upon a condition that neither a right hit signal nor a left hit signal occurs and said least recently used pointer points to said left way;

H. setting said least recently used pointer to point to said left way upon a filling of a line of said right way; and

,

I. setting said least recently used pointer to point to said right way upon a filling of a line of said left way.

3. An apparatus for selecting which way to fill during a line fill cycle in a cache directory that is divided into two ways, a right way and a left way, each way storing tag addresses and in which there are two lines selected during a line fill to one of said ways, said apparatus including a least recently used pointer in each line of a data array, said least recently used pointer when set to a first state pointing to said left way and when set to a second state pointing to said right way, said apparatus comprising:

a bus connected to said right way of said directory, for transmitting a bus address including a tag;

first logic means (28) connected to said bus for generating a right hit signal upon a first condition that a match exists between said tag and one of said tag addresses stored in said right way;

second logic means (26) connected to said bus for generating a left hit signal upon a second condition that a match exists between said tag and one of said tag addresses stored in said left way; and

,

an interface control logic means (30), connected to said first logic means (28), said second logic means (26) and said least recently used pointer, for selecting said right way for a line fill in response to said right hit signal and for selecting said left way for a line fill in response to said left hit signal and, upon a third condition that neither said right hit signal nor said left hit signal occurs, for selecting said left way for a line fill provided that said least recently used pointer is set to said first state and for selecting said right way for a line fill in response to said right hit signal provided that said least recently used pointer is set to said second state, said interface control logic means (30) setting said least recently used pointer to said second state upon a filling of a line of said left way and setting said least recently used pointer to said first state upon a filling of a line of said right way.