Circuit and method to implement a least recently used cache set replacement technique

A circuit for controlling which set of a multi-way set associative cache memory receives data for storage, comprising:

• a memory array for storing at least six bits of information representative of the relative use of the sets within the cache memory;
• a first logic circuit for generating said at least six bits of information and for writing said information to said memory array in a single access cycle;
• and
• a second logic circuit for reading information from said memory array and for producing output signals therefrom, said output signals indicating into which of the sets data is to be written, wherein the number of ways is four, and wherein said second logic circuit includes a plurality of gates responsive to said memory array for producing four output signals, a first output signal indicative of when data is to be written to a first set, a second output signal indicative of when data is to be written to a second set, a third output signal indicative of when data is to be written to a third set, and a fourth output signal indicative of when data is to be written to a fourth set.

A circuit for controlling which set of a multi-way set associative cache memory receives data for storage, comprising:

• memory means for storing at least six bits of information representative of the relative use of the sets within the cache memory;
• first logic circuit means for generating said at least six bits of information and for writing said information to said memory means in a single access cycle;
• and
• second logic circuit means for reading information from said memory means and for producing output signals therefrom, said output signals indicating into which of the sets data is to be written, wherein the number of ways is four, and wherein said first logic circuit means includes a plurality of devices interconnected to generate said six bits of information, and wherein:
• a first bit indicates if a first set is more recently used than a second set,
• a second bit indicates if said first set is more recently used than a third set,
• a third bit indicates if said first set is more recently used than a fourth set,
• a fourth bit indicates if said second set is more recently used than said third set,
• a fifth bit indicates if said second set is more recently used than said fourth set, and
• a sixth bit indicates if said third set is more recently used than said fourth set.

A circuit for controlling which set of a multi-way set associative cache memory receives data for storage, comprising:

• memory means for storing at least six bits of information representative of the relative use of the sets within the cache memory;
• first logic circuit means for generating said at least six bits of information and for writing said information to said memory means in a single access cycle;
• and
• second logic circuit means for reading information from said memory means and for producing output signals therefrom, said output signals indicating into which of the sets data is to be written, wherein the number of ways is four, and wherein said second logic circuit means includes a plurality of gates responsive to said memory means for producing four output signals, a first output signal indicative of when data is to be written to a first set, a second output signal indicative of when data is to be written to a second set, a third output signal indicative of when data is to be written to a third set, and a fourth output signal indicative of when data is to be written to a fourth set.

A cache tag circuit, comprising:

• a memory array partitioned into a four-way set associative cache and for storing at least six bits of information representative of the relative use of said four sets;
• a first logic circuit for generating said at least six bits of information and for writing said information to said memory array in a single access cycle;
• a second logic circuit for reading said at least six bits of information from said memory array and for producing output signals therefrom, said output signals indicating into which of said four sets data is to be written;
• a write circuit, responsive to said output signals, for writing address information to said memory array;
• and
• a read circuit for reading said address information from said memory array, said first logic circuit being responsive to said read circuit, wherein said first logic circuit includes a plurality of devices interconnected to generate said at least six bits of information, and wherein:
• a first bit indicates if a first set is more recently used than a second set,
• a second bit indicates if said first set is more recently used than a third set,
• a third bit indicates if said first set is more recently used than a fourth set,
• a fourth bit indicates if said second set is more recently used than said third set,
• a fifth bit indicates if said second set is more recently used than said fourth set, and
• a sixth bit indicates if said third set is more recently used than said fourth set.

A cache tag circuit, comprising:

• a memory array partitioned into a four-way set associative cache and for storing at least six bits of information representative of the relative use of said four sets;
• a first logic circuit for generating said at least six bits of information and for writing said information to said memory array in a single access cycle;
• a second logic circuit for reading said at least six bits of information from said memory array and for producing output signals therefrom, said output signals indicating into which of said four sets data is to be written;
• a write circuit, responsive to said output signals, for writing address information to said memory array;
• and
• a read circuit for reading said address information from said memory array, said first logic circuit being responsive to said read circuit, wherein said second logic circuit includes a plurality of gates responsive to said memory array for producing four output signals, a first output signal indicative of when data is to be written to a first set, a second output signal indicative of when data is to be written to a second set, a third output signal indicative of when data is to be written to a third set, and a fourth output signal indicative of when data is to be written to a fourth set.

A method of controlling, in a single access cycle, which set of a multi-way set associative cache memory receives data for storage, comprising the steps of:

• generating at least six bits of information representative of the relative use of the sets within the cache memory;
• storing the generated bits of information in a memory array;
• reading the stored information from the memory array;
• and
• producing output signals from the read information, the output signals indicating into which of the sets data is to be written, wherein the number of ways is four, and wherein said step of storing includes the step of writing:
• a first bit when one of a first set and a second set generates a hit,
• a second bit when one of said first set and a third set generates a hit,
• a third bit when one of said first set and a fourth set generates a hit,
• a fourth bit when one of said second set and said third set generates a hit,
• a fifth bit when one of said second set and said fourth set generates a hit, and
• a sixth bit when one of said third set and said fourth set generates a hit.

A method of controlling, in a single access cycle, which set of a multi-way set associative cache memory receives data for storage, comprising the steps of:

• generating at least six bits of information representative of the relative use of the sets within the cache memory;
• storing the generated bits of information in a memory array;
• reading the stored information from the memory array;
• and
• producing output signals from the read information, the output signals indicating into which of the sets data is to be written, wherein the number of ways is four, and wherein said step of producing output signals includes the step of producing four output signals, a first output signal indicative of when data is to be written to a first set, a second output signal indicative of when data is to be written to a second set, a third output signal indicative of when data is to be written to a third set, and a fourth output signal indicative of when data is to be written to a fourth set.