US3670309A

US3670309A - Storage control system

Info

Publication number: US3670309A
Application number: US887469A
Authority: US
Inventors: Gene M Amdahl; Richard F Arnold; Philip S Dauber; Charles V Freiman; Russell J Robelen; Herbert Schorr; John R Wierzbicki
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1969-12-23
Filing date: 1969-12-23
Publication date: 1972-06-13
Anticipated expiration: 1989-06-13
Also published as: FR2143504A1; GB1313528A; DE2061576A1; FR2143504B1; JPS504530B1

Abstract

Described is a storage control system for a two-level storage system. The system includes a high-speed storage against which requests for data are processed and a slower, larger-capacity main storage. Requests for data are received in terms of logical addresses. Requests can be received concurrently at a plurality of request ports where they are buffered in request stacks. A tag storage serves as an index to the data currently resident in high-speed storage, and a directory storage acts as an index to data currently in main storage. A sequence interlock generator is included which interlocks requests in the plurality of request stacks to insure that requests to the same storage area are performed in proper sequence to insure data integrity. When a request is serviced, the logical address is transformed into a plurality of physical addresses in high-speed storage. The corresponding tags from the tag storage and the corresponding data from the high-speed storage are concurrently fetched. A comparison is made of the tags with the transformed address to determine whether the requested data is in high-speed storage. Since request to the same storage entity in high-speed storage or tag storage can be made concurrently by all request ports, conflict resolvers are included to resolve conflicts arising from simultaneous requests to either of these two storages. High-speed storage is divided into storage modules capable of simultaneous operation such that requests from the plurality of request ports can be serviced concurrently. If comparison of the tags indicate that the requested data is available, the request is serviced. An interstorage transfer mechanism is included such that if the requested data is not available in high-speed storage, then the data is retrieved from main storage and placed into high-speed storage for subsequent processing of the request. Concurrently with interstorage transfer, processing of other requests from the request ports is permissible. In the replacement of data from main storage to high-speed storage, provision is made for also replacing data from high-speed storage to main storage if such be necessary.

Description

United States Patent Amdahl a at.

STORAGE CONTROL SYSTEM Inventors: Gene M. And-ll, Sir-stage; Riel-d 1''. Arnold, Pslo Alto, both ofCalifi; up 8. Dsuher, Oasining; (II-ks V. l hirrsn,

Plessantville, both of N.Y.; Rr-efl J. Itobelen, Palo Alto,Cs.|if.;l-lsrhertSeher-r, Hriar Cliff, N.Y.', John R. WI,

Primary Examiner-Gareth D. Shaw Attorney-Hanifin 8: Jancin and Peter R. Lead [57] ABSTRACT Described is s storage control system for s two-levei storage system. The system includes a high-speed storage against [151 3,670,309 [451 June 13, 1972 widchrequensfordstssneprooenedsndsslowenlarprcapocitymalnstorage. Requestsfordstsarereoeived In terms oflogicsiaddresses. Requestscanbereoeivedooncurrently st apluralityot'requestportswheretheynrebufleredinrequest stacks. Atagstorageservesssan indextothedatacurrendy residentinhigh-speedstorsge, andadirectorystorsgesetsss an index to data currently in main storage. A sequence interlock generator is included which interlocks requests in the plurslityofrequenrtseka toiruurethstrequeetstothe lame storweareaareperkmnedin propersequenoetoinsuredats integrity. Whenarequestiaservieedthelogiealeddressis tramfonnedintoapluralityofphysicaladdressesinhilhlpeedstorsge'llreoonespondlngtspfromthetlgstorqe andtheeorrespondingdstafiomthehigh-speedltorsgeare concurrently fetched. A comparison is made ofthe tag with the malformed adthess to determine whether the requested dataisinhigh-speedstoragesineerequesttothessrne r y r v a a s made ooncurrendy by all request ports, conflict resolver: are included to resolve conflicts arising from simultaneous requests to either ot'these two storages. High-speed storage is divided into storage modules capable of simultaneous operationauchthatrequestsfromthe plurality otrequestportscan be serviced concurrently. If eomparison of the tags indicate that therequesteddataisavailable, therequestlsserviced. An interstorage transfer mechanhm is included such that ifthe requested data is not available in high-speed storage. then the datsisretrievedfi-ommainstoragesndplaced into high-speed storage for subsequent processing of the request. Concurrently with interstorage transfer, processing of other requests from the request ports is permiuible. In the replacement of data fiorn main storage to high-speed storage, provision is made for also replacing data from high-speed storage to main storage ilsuch beneeesary.

PATEN'IEDJRRI: m2 3.670.309

SHEER 01 RF 179 PREO GRFO FIG. 1 N \2 J; JL

P sEouERcE REQUEST mTERLocR REQUEST STACK GENERATOR sTAcR I {j 12/ l 36 P o R mom" 1 a PRIORITY momn R HASH R HASH & HASH :9 H85 TS -31 PRIORITY \15 PRIORITY \H RESOLVER REsoLvER l -18 & P 26 0 DEClSION DECISION n tlzr 28 I 23 24 R ,30 35) 4h. TRANSFER HIGH mun m DIRECTORY 5mm STORAGE INVENTORS.

I c R ARI'J" F mw l J PHILIP sfoAuRER 22 CHARLES v FREIHAN l RUSSELL J ROBELEN 21 HERBERT SCHORR JOHN R. mERzmcm I I 33 Pain lea! P OUT OOUT PATENTEnJuA 1 3 m2 sum 02 nr 179 START FIG. IA

1A FIG. 1B

EEEFF 16 3A P REQUEST STACK El?" cm Income GATE mcoumc P REQUEST 5C REQUEST TO P SA/ T0 P REQUEST REQUEST 51m 51m ,s.1.c. AAo Ann s.1.c. P PRIORITY AREA GENERATE nnenwcx FOR mconmc REQUEST GENERATE IATEPLocA 5B AND coATEuo FOR Pmomn concunaznm.

GATE Au AVAILABLE REQUEST m P PRIORITY AREA REQUEST CONTENDS TB FOR PRIORITY HASH v.A.

PATENTEDJIIII 13 m2 SHEET 03 OF 179 TAO CONFLICTS RESD?LVED GATE TAGS AND DATA TO P DECISION UIIIT IIIITIATE IIITERSTORAGE TRANSFER SOB ABORT FIG.1C

SOD

REOUEST DATED FROI REOIIEST STACK TO PRIORITY AREA OPERATE OII DESIRED \IA.

PREFETCH ANTICIPATED OATA IF APPLICABLE EIIO miminm 13 1912 3.6 70.309

$11EE1 1170f 179 FIG. 2D

0 H88 0 TAG ELL 4011 CELL 4013 (1-16.27) 1F1G.28)

Q DEC1S1ON 4015 (FIG. 51)

R TRANSFER PATENTEU 13 a HSS csu. new) 4026 NEH 08 OF 179 amp 3060 3' R TAG CELL (FIG. 50)

H06 H04 H52 PATENTEUJUIUIQTZ 3.670.309

sum

15 or 179 FIG. 5

P REQUEST STACK AND REGISTER CONTROL P GATE CONTROL FIG. 5A FIG. 58 FIG. 5C FIG. 5D FIG. 5Q FIG. 5R

FIG. 5E FIG. 5F FIG. 56 FIG. 5H FIG. 5s FIG. 5T HG, Fm,

FIG. 51 FIG. 5J FIG. 5K FIG. 5L FIG. 5W FIG. 5X

FIG.5M FIG. 5N FIG. 52 FIG. 5P

FIG. 7AA

A 0 REQUEST STACK AND REGISTER CONTROL 0 GATE CONTROL FIG. 7A FIG.7B FIG. 7C FIG.TD FIG. 70 FIG. 7R

FIG.7E FIG. 7F FIG. 7G FIG-TH FIG. 73 FIG.7T F|G F|G FIG. "I FIG. 7J FIG. 7K FIG.7L FIG-7W FIG. 7X

FIG. 7M FIG. 7N FIG. 72 FIG. 7P

PATENTEDJun 13 m2 SHEET 1711f 179 Son 0 0 M0 M0 PO vm mm um I 0 Hm x1 HQ" 6 4062 28 5 uuunn m 4 3 E mm 0:

Claims

1. In a data processing system having a plurality of sources of requests for accessing data in a storage system, wherein said sources concurrently issue serial requests, the combination comprising: storage means comprising a main storage having a multiplicity of addressable locations for storing data, and a high-speed storage faster in operation than said main storage and having a multiplicity of addressable locations for storing data which locations are fewer in number than the number of locations in said main storage, said high-speed storage being operable to simultaneously access plural locations in response therefor; a plurality of input ports adapted to be connected to said data processing system for receiving requests from said respective sources; buffer means connected to said input ports and being operative to receive requests and store such requests until the completion of the accessing requested thereby; data transfer means for transferring data between said storage means and said sources of requests; and control means connected to said storage means and said buffer means for concurrently accessing said storage means in response to concurrent plural requests in said buffer means, said control means comprising first means for determining if any data being accessed is resident in said high-speed storage and providing positive and negative determinations thereof; second means responsive to a positive determination by said first means for accessing data resident in said high-speed storage; and third means responsive to a negative determination by said first means for transferring requested data from said main storage into said high-speed storage.

2. The combination of claim 1 wherein: said buffer means includes a plurality of request stacks, each request stack being connected to receive requests from a different one of said ports, each request stack including a plurality of registers for storing requests until the accessing requested thereby is completed.

3. The combination of claim 2 wherein said control means includes sequence interlocking means connected to said input ports and said buffer means for interlocking incoming requests with requests in said request stacks into a sequence that maintains data integrity.

4. The combination of claim 3 wherein each request is compared to prior requests in said request stacks and a store request for access to a given location is interlocked witH all prior requests in said stacks for access to such location and a fetch request is interlocked with any prior store request accessing the same location.

5. The combination of claim 1 wherein each request includes a virtual address of the data being accessed thereby, and said system includes addressing means for translating each virtual address into at least one physical address in said high-speed storage.

6. The combination of claim 5 wherein said first means includes a tag storage for storing tags identifying data resident in said high-speed storage.

7. The combination of claim 6 wherein said tag storage includes a multiplicity of addressable locations corresponding to the number of locations in said high-speed storage, and said addressing means is further operative to translate each virtual address in a request into at least one physical address in said tag storage.

8. The combination of claim 7 wherein said third means is connected to said tag storage and is operative to write therein tags identifying the data being transferred from said main storage into said high-speed storage.

9. The combination of claim 8 wherein each tag includes the virtual address of the data identified thereby, said first means being operative to access said tag storage concurrently with accessing of said high-speed storage, to read out the tag at the physical address being accessed, said first means including comparison means for comparing the virtual address in the tag so accessed with the virtual address of the data being accessed and providing said positive determination when said virtual addresses so compared are the same.

10. The combination of claim 9 wherein said addressing means is operative to translate each virtual address into plural physical addresses in each of said tag storage and said high-speed storage, whereby all locations of such addresses are concurrently accessed.

11. The combination of claim 10 wherein: said buffer means includes a plurality of request stacks each connected to receive requests from a different one of said ports, each stack including registers for storing plural requests until the accessing requested thereby is completed; and said control means includes fourth means connected to said request stacks and being operative to grant priority to, only one request at a time, in each request stack, to access said tag storage and said high-speed storage.

12. The combination of claim 11 wherein: said control means includes resolution means operably connected to detect conflicts between concurrent requests to which priority has been granted by said fourth means and to grant priority to one of said conflicting requests according to a predetermined priority associated with said input ports which received the conflicting requests.

13. The combination of claim 12 wherein: each request stack register includes interstorage transfer control bits settable when said third means is operated to transfer data from said main storage, and said control means is further operative to service other requests while such data is being fetched from said main storage, said fourth means being operative to grant priority to the associated request when said data arrives from said main storage and is ready to be stored in said high-speed storage.

14. The combination of claim 13 wherein said resolution means grants highest priority to a conflicting request associated with the transfer of data from said main storage.

15. The combination of claim 13 wherein: each register includes a wait bit settable by said third means to place the associated request in a wait state during the transfer of requested data from said main storage to said high-speed storage.

16. The combination of claim 12 wherein said conflicting requests arise out of concurrent requests to access the same physical address in said high-speed storage, and said resolution means include comparator means responsive to said concurrent requests for comparing addressEs therein to detect said conflicting requests.

17. The combination of claim 12 wherein said request stacks further include a plurality of priority history means, for storing an indication of the successful attempted accesses of a request for tags and data in said plurality of physical addresses in said tag storage and said high-speed storage.

18. The combination of claim 17 wherein said control means includes fifth means for allowing a request to continually contend for access to tags or data if said priority history indication indicates a request has not been successful in obtaining access to both tags and data in said plurality of physical addresses.

19. The combination of claim 10 wherein said third means includes means for selecting one of said plurality of high-speed storage physical addresses associated with the virtual address of the data being accessed, as a target physical address in said high-speed storage for receiving data transferred from said main storage.

20. The combination of claim 19 wherein said control means includes means providing an indication if the data in said target physical address has been changed since first entering said target physical address.

21. The combination of claim 20 further including means responsive to said indication for transferring the changed data in said target physical address into Main Storage before transferring requested data into said target physical address.

22. The combination of claim 21 wherein control means includes apparatus for periodically placing each high-speed storage physical address in a replacement target candidacy state.

23. The combination of claim 10 wherein: each data identified by a virtual address is a data word, and each said physical address location contains a line of data, each line including a plurality of data words.

24. The combination of claim 23 wherein said control means includes means responsive to accessing a predetermined word in a line, for prefetching from said main storage another line of data.

25. The combination of claim 5 wherein data is stored randomly in said main storage and said system includes a directory storage for storing information as to where data is stored in said main storage, said third means being operative to access said directory during the transfer of data into and out of said main storage.

26. The method of servicing a request for data entity storage in a desired location in a digital computer storage system wherein said storage system includes a high-speed storage against which requests are processed, a main storage containing system information, a plurality of input ports, a request stack for each input port, priority contingent means, accessing means for said tag storage and said high-speed storage, and decision means, including the following steps: temporarily storing requests in said request stacks as they are received from said plurality of requestors; allowing a plurality of requests, one from each request stack, to contend for priority to access a plurality of tags from said tag storage; determining that said desired data location is currently resident in said high-speed storage; storing said data entity into said desired location.

27. The method of claim 26 wherein said storing step includes the steps of: setting a marker in said requests in said request stacks indicating that said desired location is resident in high-speed storage; allowing said requests as marked to contend for priority to access at least one said desired location in said high-speed store and at least one address in said tag storage; storing the data into said high-speed location; storing an indication in said tag storage that said high-speed storage location has been changed.

28. The method of fetching a data entity in a system including a plurality of input ports from a plurality of requestors, a plurality of request stacks, a plurality of priority and resolution means, a system main storage, a high-speed storage, a tag storage, a plurality of decision means, and an interstorage transfer mechanism for transferring data between said high-speed storage and said main storage, including the steps of: selecting a request from each said plurality of request stacks; allowing said requests to contend for priority to access said high-speed storage and said tag storage; accessing said last-named storages; determining that said desired data is not resident in said high-speed storage for at least one of said plurality of requests; allowing said at least one request to contend for priority to the interstorage transfer unit; selecting a request to use the interstorage transfer unit; transferring data between main and high-speed storage while continuing to service other system requests; informing said selected request when said interstorage transfer is complete; and concurrently fetching said desired data for said selected request.

29. The method of storing data in a digital computer which includes a plurality of input ports from a plurality of requestors, a plurality of request stacks, a plurality of priority and resolution means, a system main storage, a high-speed storage, a tag storage, a plurality of decision means, and an interstorage transfer mechanism for transferring data between said high-speed storage and said main storage, including the steps of: selecting a request from each of said plurality of request stacks; allowing said requests to contend for priority to access said high-speed said tag storages; determining that said desired data entities are not resident in said high-speed storage for at least one of said requests; allowing said at least one of said requests to contend for priority to said interstorage transfer unit; selecting a request to use said interstorage transfer unit; transferring data between main storage and high-speed storage while continuing to service other system requests; informing said selected request when said interstorage transfer unit is complete; allowing said selected requests to store its data; and updating the tag of said stored data to indicate its changed condition.