US 4,458,310 A · Cache memory using a lowest priority replacement circuit

Abstract

A data processing system having a processor, main memory, and a cache memory system which implements the least recently used replacement algorithm in replacing cache memory words with main memory words. The cache memory system is comprised of a cache control circuit and a plurality of cache memories. Each cache memory stores cache memory words having a similar time usage history. The first cache memmory stores cache memory words which are more recently used than the cache memory words in the second cache memory, and the second cache memory stores cache memory words which are more recently used than the cache memory words in the third cache memory. When a main memory word must be transferred to the cache memory, the main memory word is stored in the first memory; and the first cache memory's least recently used cache memory word is stored in the second cache memory. The least recently used cache memory word from the second cache memory is stored in the third cache memory. These operations maintain the proper time usage history of the cache memories.

Claims17

Dependent claims

A data processing system comprising:

a processor means for generating main memory address signals;
a main memory having a plurality of memory locations for storing main memory words;
a cache control means;
first and second cache memories each having a plurality of memory locations for storing main memory addresses and corresponding cache data words in a priority order, and each responsive to main memory address signals which mismatch all of the main memory addresses stored therein to generate and transmit a mismatch signal to said cache control means;
said cache control means responsive to concurrent generation of said mismatch signals by said first and second cache memories to generate and transmit a first control signal to said main memory and said first and second cache memories;
said main memory responsive to said first control signal and said mismatched main memory address signals to access and transmit a main memory word to said first cache memory;
said first cache memory responsive to said first control signal to transmit the lowest priority cache data word and its corresponding stored main memory address to said second cache memory, and to store said transmitted main memory word and said main memory address signals;
and
said second cache memory responsive to said first control signal to store the transmitted lowest priority cache data word and its corresponding main memory address.

6 more elements

In a data processing system having a processor for generating main memory address signals, a main memory for storing main memory words, first and second cache memories for storing main memory addresses and corresponding cache data words and for matching a stored main memory address word with the main memory address signals, and a cache control for controlling said first and second cache memories, a method of accessing said cache memories and said main memory;

comprising the steps of:
storing a set of said cache data words and corresponding main memory address words having a higher priority than another set of said cache data words and corresponding main memory address words in said first cache memory;
storing said other set of said cache data words and corresponding main memory address words in said second cache memory;
detecting main memory address signals which mismatch all of main memory address words stored in said first and second cache memories;
reading from said main memory, the main memory word addressed by the mismatched main memory address signals;
transferring said main memory word to said processor and said first cache memory;
storing said main memory word and said mismatched main memory address signals in said first cache memory;
transmitting the lowest priority cache data word of said first cache memory to said second cache memory;
replacing said lowest priority cache data word of said first cache memory with said main memory data word;
identifying within said first cache memory said main memory data word as the highest priority cache data word and another cache data word as the lowest priority cache data word;
and
storing said transmitted cache data word from said first cache memory in said second cache memory.

9 more elements

In a data processing system having a processor for generating main memory address signals, a main memory for storing main memory words, first and second cache memories for storing main memory addresses and corresponding cache data words and for matching the stored main memory addresses with the main memory address signals, and a cache control for controlling said first and second cache memories, a method of accessing said cache memories and said main memory;

comprising the steps of:
storing a set of said cache data words and corresponding main memory addresses having a higher priority than another set of said cache data words and corresponding main memory addresses in said first cache memory;
storing said other set of said cache data words and corresponding main memory words in said second cache memory;
detecting main memory address signals which match one of the stored main memory addresses in said second cache memory;
transferring the cache data word corresponding to the matched one of said stored main memory addresses from said second cache memory to said processor and said first cache memory;
and
storing said transferred cache data word from said second cache memory in said first cache memory.

4 more elements

Dependencies are inferred from the claim text.

Cache memory using a lowest priority replacement circuit

Life of this patent

Cache memory using a lowest priority replacement circuit

Life of this patent

Abstract

Claims17