Storage interface unit

• US 3,967,247 A
• Filed: 11/11/1974
• Issued: 06/29/1976
• Est. Priority Date: 11/11/1974
• Status: Expired due to Term

• Current Assignee: Sperry Rand Corporation
• Original Assignee: Sperry Rand Corporation
• Inventors: Andersen, Vernon K., Goddard, Michael W.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Sachs, Michael C.
• Application Number:
  US05/522,553
• Time in Patent Office: 596 Days
• Field of Search: 340/172.5, 444/1
• US Class Current: 711/136
• CPC Class Codes: G06F 12/0851 Cache with interleaved addressing
• CPC Class Codes: G06F 12/0859 with reload from main memory
• CPC Class Codes: G06F 12/1045 associated with a data cache
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel

Abstract

A storage interface unit adapted to serve as a high speed buffer between plural requestor units and a relatively low speed main memory in a data processing system. The high speed buffer provides temporary storage for a limited number of blocks of data stored in the main memory. When a particular address is requested by a requestor unit, a check is made to determine if that address is resident in the high speed buffer and if so, it is available to the requestor unit for reading or writing. If the desired address is not resident in the high speed buffer, a block in the buffer is selected for replacement. In accordance with the present invention, when a block is to be displaced from the buffer and a new block is requested from the main memory, during the interval that the new block is requested from the main memory, the block to be displaced is checked for modifications. If any word of the old block has been modified since it was obtained originally from main memory the entire block is read into a temporary holding register and is restored in the main memory while the new block is being entered into the buffer storage.

Claims

1. In a digital computing system of the type including a relatively large capacity, high cycle time main memory for storing plural blocks of information, a small capacity, high speed buffer memory for storing subsets of said blocks of information contained in said main memory at addressable locations therein, a plurality of requestor units for addressing information stored in said buffer memory, a tag storage device for storing the addresses of those blocks of information stored in said main memory which are currently contained in said high speed buffer memory as well as age bits indicative of the relative order in which said blocks of information contained in said high speed buffer memory had been addressed by said requestor units, the combination comprising:

a. a plurality of comparator networks having first and second inputs and an output said comparators indicating whether the number represented by the binary digits applied to said first input are greater than, equal to or less than the number represented by the binary digits applied to said second input;

b. means for applying the age bits associated with predetermined blocks of information in said buffer memory individually to said first inputs of said plurality of comparator networks;

c. means for applying the age bits associated with the block of information in said buffer memory currently being addressed by one of said requestor units to said second inputs of all of said comparator networks; and

d. adder means connected to the outputs of said comparator networks for adding 0, clearing or adding 1, to the age bits of the predetermined blocks which were applied to said first inputs of said comparator networks when the number represented by the age bits applied to said first inputs are greater than, equal to or less than the number represented by the age bits applied to said second inputs, respectively whereby, in dependence upon the new age bits of the blocks, a decision may be made as to replacement of a block based on relative usage of the block.

2. In a digital data processing system of the type including a relatively large capacity slow cycle time main memory for storing M sets of N blocks of data, each P-words in length at addressable locations therein;

a plurality of requestor units for providing address representing signals, data representing signals and request control signals, a storage interface unit comprising in combination;

A. a relatively low capacity fast cycle time buffer memory for storing in a first section thereof M sets of n blocks of data, each P-words in length at addressable locations therein, where n <

N and for storing in a second section thereof M tag words, each of said tag words including;

a. n block address fields for specifying which of the N blocks in a given set in said main memory are also resident in a corresponding set in said first section of said buffer memory at any given time; and

b. a modification indicator for indicating when data in said n blocks specified by said n block address field are different from the data stored in the corresponding N blocks in said main memory;

B. priority determining means responsive to said request control signals from said plurality of requestor units for selecting only one of said requestor units at a time to supply said address representing signals to said buffer memory;

c. means responsive to said address representing signals from said one of said requestor units for reading out from said buffer memory a tag word for a desired set;

D. match detecting means responsive to the bit permutations of said tag word in the buffer for said desired set and to said address representing signals from said one of said requestor units for producing a miss control signal when the n blocks in the buffer of said desired set do not include a desired block corresponding to said desired set;

E. control meams responsive to said miss control signal for selecting one of said n blocks in said desired set in said buffer memory for replacement on a block basis by said desired one of said N blocks in said main memory; and

F. means connected to receive said modification indicator and connected to said buffer memory and said main memory for updating main memory by storing said one of said n blocks of the buffer selected for replacement in said main memory at the address specified by said address representing signals from said one of said requestor units only when said modification indicator is of a predetermined binary significance.