Patent GB-1313528-A (GB)
Title: Two-level storage system
IPC: G06F13/18
Filed: 1970-12-07
Abstract: 1313528 Data storage INTERNATIONAL BUSINESS MACHINES CORP 7 Dec 1970 [23 Dec. 1969] 57956/70 Heading G4C A two-level storage system comprises a high. speed store 20 and a main store 32 arranged in operation to service storage access requests from a plurality of request sources P, Q, and comprises a plurality of storage request stacks 3, 4, each for storing requests from a different source, and means for servicing concurrently requests from different sources, wherein the high-speed store 20 includes a plurality of storage modules so arranged that more than one request can simultaneously access the high-speed store 20. Tag store 19 contains a multi-bit tag (including the virtual address) for each line (16 words) of data in the high-speed store 20. A directory 45 specifies the virtual address and physical address of each line of data in main store 32. P and Q and R (R being inter-storage transfer, see below) operations can occur concurrently to a large extent. Taking P operations, for example, a P request at 1 has to be repeated if the P request stack 3 is full. Otherwise if the stack is empty or if no request in it is ready for priority determination (due to, e.g., waiting for an interstorage transfer), the request is passed into the stack 3 and to a sequence interlock generator 5 and to P priority and hash 7. Generator 5 appends an interlock vector to the request in the stack 3 specifying the levels (positions) in the two stacks 3, 4 of requests which must be performed before this one (relating to the same location, detected by comparison of virtual addresses, e.g. a store operation followed by a fetch operation for the same location in the programme must be performed in that order). On the other hand, if there is a request in the P stack 3 ready for priority determination, the new request is passed into the stack 3 and the interlock generator 5. The interlock vector is appended as before. Then a ready request from the stack 3 is passed to the P priority and hash 7, this ready request being the oldest such in the stack 3, selected by a shift register holding stack level identifiers in order of age. When a request is received by P priority and hash 7, the virtual address of the required data is hashcoded into the addresses of a primary and an alternate tag in tag store 19 and of the corresponding locations in high speed store 20. A priority resolver 15 performs a priority determination between access attempts from 7, 8, 36 for locations in the same pair of modules of the high speed store 20, the order of (decreasing) priority being R, P, Q. The high-speed store 20 has 8 modules and up to 4 accesses can take place at a time, one access to each of 4 pairs of these modules. A priority resolver 11 performs the same function for the 8-module tag store 19. Assuming the P access attempts are granted access, the two tags addressed in the tag store 19 and the corresponding data from the high speed store 20 are passed to the P decision unit 25 where the desired virtual address is compared to those contained in the primary and alternate tags. If one agrees, the interlock vector is inspected and if this request is interlocked an indication is set in the request stack 3 and the request must contend for priority at 3, 7 again later. However, if the request is not interlocked, a store or fetch operation is performed on the respective data (in the case of a store operation the data is in the request stack waiting), and if the request was for the first word of a line an interstorage transfer operation is then initiated to prefetch the next line from main store 32 into high-speed store 20 unless it is already there, on the assumption that it will probably soon be needed. This prefetch interstorage transfer is produced by setting a request for this next line in the P request stack 3. When the required virtual address is compared (see above) to those in the primary and alternate tags, if neither agrees, R transfer unit 30, using R priority and hash 36, requests an interstorage transfer to move the required line of data from main store 32 to high-speed store 20. The required virtual address is compared with the virtual addresses in the directory 45 to obtain the physical address of the line in the main store 32. The line is transferred to the highspeed store line corresponding to the primary or alternate tag according to a bit of the virtual address and which (if any) of these lines are empty and which (if any) have a "hot" bit set (in the tag). Whenever a high-speed store line is referenced it hot bit is set. Periodically, a virtual address is generated (by a counter) and the hot bit corresponding to this address is reset, through an access request having R priority. Transfer from main store to highspeed store is preceded by updating of the copy (in main store) of the data (if any) to be replaced in high-speed store, if a "changed" bit in the tag for that data indicates that the data has been written into during its presence in high-speed store. After the interstorage transfer is complete, the request which originally was responsible for the transfer is passed from the P stack 3 to the priority area. As a modification, data thus transferred from main store 32 could be supplied directly to the requestor.