US 4,322,795 AGranted

Cache memory utilizing selective clearing and least recently used updating

AssigneeHoneywell Information Systems Inc.

InventorsRonald E. Lange, Richard J. Fisher

Life of this patent

Estimating the term…

Loading patent…

Abstract

An apparatus is disclosed herein for providing faster memory access for a CPU by utilizing a least recently used scheme for selecting a storage location in which to store data retrieved from main memory upon a cache miss. A duplicate directory arrangement is also disclosed for selective clearing of the cache in multiprocessor systems where data in a cache becomes obsolete by virtue of a change made to the corresponding data in main memory by another processor. The advantage of higher overall speed for CPU operations is achieved because of the higher hit ratio provided by the disclosed arrangement. In the preferred embodiment, the cache utilizes: a cache store for storing data; primary and duplicate directories for identifying the data stored in the cache; a full/empty array to mark the status of the storage locations; a least recently used array to indicate where incoming data should be stored; and a control means to orchestrate all these elements.

Claims10

Dependent claims

A cache memory apparatus for a central processing unit (CPU) in a data processing system having a main memory, said CPU requesting data words stored in said main memory when required for execution of a program, comprising:

(a.) storage means for storing and accessing a plurality of data words used by said CPU, said data words stored in a plurality of sections, each section being divided into a plurality of blocks, each block storing a data word;
(b.) directory apparatus having a plurality of levels, each level corresponding to a section of said storage means, and each level divided into a plurality of columns where each column corresponds to one block of said storage means, said directory apparatus including means for storing addresses identifying data words in main memory which are stored in said storage means, said directory apparatus including means for comparing said stored addresses to addresses of data words requested by said CPU, said directory apparatus further including means for generating match information when said requested data word is present in said first means thereby indicating on which level said data was found;
and
(c.) control apparatus including means for causing said requested data word to be supplied from said first means to said CPU when a match occurs, said control apparatus including means for causing said requested data word to be retrieved from said main memory, said control apparatus further including means for supplying said requested data word to said CPU, and storing said requested data word in said storage means, said control apparatus including means for directing that an address indexing said retrieved data word be stored in a least recently used (LRU) level of said directory apparatus, said control apparatus also including means for generating and storing update data on a new most recently used level when a match occurs, said control apparatus generating and storing means manipulating data bits identifying least recent usage of two predetermined levels.

1 more element

A cache memory apparatus for providing higher speed access to information used by a first central processing unit (CPU) than is provided by the main memory of the multiprocessor data processing system of which the first CPU is a part, comprising:

(a) a cache store means arranged in a plurality of sections each section comprised of a plurality of rows of individually addressable blocks each block having a plurality of individual addressable storage units for storing data words needed by said CPU for its operations;
(b) a primary directory arranged into a plurality of individually addressable columns, each column corresponding to a block of said cache store means, and each column arranged into a plurality of levels of tag address storage locations each level corresponding to a particular block in a row of blocks in said cache store means, each said levels for storing a tag address indicating what data words reside in the corresponding block of said cache store means and including a comparator for comparing the tag addresses of the data words stored in said cache store to the tag address of the data requested by said CPU and for generating match signals indicating in which section of said cache store, if any, said data may be found;
(c) full empty storage means for storing a plurality of individually addressable full/empty status bits each bit corresponding to a particular level of a particular column of said primary directory each of said indicator for indicating whether its corresponding level is full or empty;
(d) a selective clearing means having an address input for receiving a change notification address indicating which addresses in said main memory have been changed by another CPU in the system, and having an output for supplying a changed address signal indicating which data in said cache store has been changed in said main memory, said changed address signal to designate which of said full/empty status bits should be cleared to empty;
(e) a least recently used indicator (LRU) means including an LRU memory array comprised of a plurality of individually addressable LRU bits each said bit associated with one level of one column of said primary directory the number of said LRU bits being sufficient to encode the order of use of the levels in the associated columns of said primary directory such that the level which has been least recently used can be decoded from said LRU bits, and having an output for providing said least recently used data, and having an input for updating said LRU bits when the order of use has changed and said least recently used indicator means including a field programmable logic array comprised of a plurality of programmable AND-OR terms with inputs coupled to said LRU memory array, said full/empty status bits and to said match signals from said comparator, and with outputs coupled to said LRU memory array and to said primary directory and cache store, said field programmable logic array programmed to update said LRU bits upon a cache bit or miss and to direct the tag address of the retrieved data into either an empty level or the least most recently used level of said primary directory and the retrieved data into the corresponding section of cache store upon a cache miss;
(f) means for storing the address of information being requested by said CPU;
(g) means for comparing this address to the tag information stored in said primary directory to determine if the requested data is in said cache store;
(h) means for switching said data to said CPU if present in said cache store, and, if the data is not in said cache store, for causing said field programmable logic array to determine the least recently used level of the addressed column in said primary directory;
(i) means for causing the tag address of the requested data to be written into the level of said primary directory as directed by said field programmable logic array;
(j) means for causing the data retrieved from said main memory to be stored in the location in said cache store corresponding to the level of said primary directory just changed;
(k) means for receiving said changed address signal;
and
(l) means for generating from it a clear signal to clear the correct full/empty status indicator.

10 more elements

A cache memory apparatus for each CPU in a multiprocessor data processing system having a main memory comprising:

(a) a cache address latch means for receiving and holding the absolute address of the data requested by said CPU, said cache address latch means comprised of first, second and third portions, said portions for coupling portions of said absolute address to other parts of said cache memory apparatus;
(b) a cache store means for storing and accessing a plurality of pieces of information used by said CPU, said information stored in a high speed random access memory divided into a plurality of individually addressable sections, each section having a data input and output and divided into a plurality of blocks, and each block divided into a plurality of individually addressable words, said cache store means having an address input coupled to said second and third portions of said cache address latch for receiving a cache store read/write address signal for designating which block and which word of said block in which to store data coming into said data input and which word of which block to present at said data output, and having a section strobe input;
(c) a first switching means having a data output coupled to a data input of said cache store means and having a plurality of data inputs coupled to said CPU and said main memory, and having a control input, said first switching means for switching data from said CPU into said cache store means during CPU store operations and for switching data retrieved from main memory into said cache store means after a cache miss has occurred;
(d) a second switching means having a plurality of data inputs coupled to said data outputs from said sections of said cache store means, a data output and a control input, said second switching means for selecting under the control of a block select signal presented at said control input one of the data outputs from said sections of said cache store means and switching it through to said data output of said second switching means;
(e) a primary directory means having a plurality of levels each associated with and corresponding to one of said sections of said cache store means, each said level coupled to a data input which is in turn coupled to said first portion of said cache address latch and each said level divided into a plurality of individually addressable tag address storage cells with a row of said cells in each level comprising a column each said cell corresponding to one of said blocks of said cache store means and each adapted to store a plurality of tag address bits comprising tag words from said absolute address of the data stored in the corresponding block of said cache store means, each said level having an output for presentation of the tag address bits stored in a selected one of said tag cells, said primary directory means also having a directory read/write address input coupled to said second portion of said cache address latch for receiving a plurality of block address bits comprising part of said absolute address for designating which column of said tag cells to present at said level outputs, and said primary directory means having a level strobe input for receiving a signal designating which of said tag cells in a column addressed by said block address signal in which to store incoming tag words, said primary directory means for storing said tag words in said tag cells indicating what data is stored in said cache store means and where it is stored and for retrieving a selected column of said tag words and presenting them at said level outputs for comparison;
(f) a comparison means for comparing the tag address of the data requested by said CPU to the tag addresses stored in said primary directory means and for generating a match signal if a match is found, and for generating LRU (least recently used) update data, said comparison means having a plurality of inputs coupled to said level outputs for receiving said tag words and having a data desired tag word input coupled to said first portion of said cache address latch means for receiving a data desired tag word to compare against said tag words from said primary directory means and having outputs for said match signals;
(g) an LRU latch means having an LRU address input coupled to said second portion of said cache address latch means for receiving and holding the portion of said absolute address constituting said block address bit and presenting same at an output;
(h) an LRU array means for storing data encoded to indicate the least recently used level of said primary directory means, said array comprised of a plurality of rows of a plurality of storage bits, each row associated with and corresponding to one of said columns of said primary directory means and each row comprised of a sufficient number of storage bits to enable encoding of data sufficient to determine the order in time of last usage of each level in the associated column where each bit represents the status as between two of said levels and there are the same number of bits as there are combinations of the number of levels there are in said primary directory means taken two at a time, said LRU array having an address input coupled to said output of said LRU latch means for receiving the address bits designating which column in said primary directory means is being examined by said comparison means so that the storage bits of the corresponding row may be presented at an LRU level output, and having an LRU update input for receiving LRU update data to update said storage bits in the selected row when there is a match with a particular level or there is a cache miss and an empty level or the least recently used level is used to store the tag word for the data retrieved from said main memory after said miss, said updating to change said row of storage bits to indicate the matched or newly stored level is now most recently used;
(i) a control means including a field programmable logic array for controlling the elements of said cache memory apparatus and having an input coupled to said match signal output for receiving said match signal said signal indicating which, if any, of said levels of the addressed column match the address of the data requested, and having a block select output coupled to said control input of said second switching means for causing same to switch a selected one of the outputs of said levels to the output of said second switching means when said match signal occurs, and said control means having a level strobe output coupled to said level strobe input of said primary directory means and said section strobe input of said cache store means for causing said tag address bits of said absolute address in said cache address latch to be strobed into the tag cell of the least recently used level of said primary directory means when a miss occurs and for causing data being written into said cache store means either during a CPU store operation or upon retrieval from said main memory to be stored in a selected one of said sections corresponding to the level of said primary directory means in which said tag address bits corresponding to the data are stored, and having an output coupled to said first switching means for controlling whether data from said CPU or said main memory is switched into said cache store means, and said control means having a strobe address register input for receiving a signal from said CPU indicating the CPU is requesting data and has prepared the absolute address of said data, and having a miss output for signalling other elements in said data processing system that the requested data has not been found in said cache store means and to retrieve the data from said main memory, and said control means having an LRU level input for receiving data from said LRU array means for decoding into information on which level of said primary directory mans has been least recently used so that said level strobe signal can be prepared utilizing this information.

6 more elements

Dependencies are inferred from the claim text.