US3670309A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Storage control system
Assignee: International Business Machines Corp
•
Filing: 1969-12-23
•
Granted: 1972-06-13
•
Expires: 1989-12-23
Abstract
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.
Inventors
- 👤 Gene M Amdahl
- 👤 Richard F Arnold
- 👤 Philip S Dauber
- 👤 Charles V Freiman
- 👤 Russell J Robelen
- 👤 Herbert Schorr
- 👤 John R Wierzbicki
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-22 17:21
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0844; G06F12/0855; G06F12/0857; G06F13/00; G06F13/14; G06F13/16; G06F13/18
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
251 words
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.
Claim 2
Dependent Claim
251 words
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.
Claim 3
Dependent Claim
48 words
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.
Claim 4
Dependent Claim
39 words
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.
Claim 5
Dependent Claim
56 words
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.
Claim 6
Dependent Claim
39 words
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.
Claim 7
Dependent Claim
23 words
The combination of claim 5 wherein said first means includes a tag storage for storing tags identifying data resident in said high-speed storage.
Claim 8
Dependent Claim
50 words
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.
Claim 9
Dependent Claim
35 words
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.
Claim 10
Dependent Claim
84 words
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.
Claim 11
Dependent Claim
39 words
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.
Claim 12
Dependent Claim
80 words
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.
Claim 13
Dependent Claim
55 words
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.
Claim 14
Dependent Claim
80 words
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.
Claim 15
Dependent Claim
26 words
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.
Claim 16
Dependent Claim
40 words
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.
Claim 17
Dependent Claim
45 words
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.
Claim 18
Dependent Claim
47 words
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.
Claim 19
Dependent Claim
51 words
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.
Claim 20
Dependent Claim
49 words
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.
Claim 21
Dependent Claim
32 words
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.
Claim 22
Dependent Claim
34 words
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.
Claim 23
Dependent Claim
24 words
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.
Claim 24
Dependent Claim
36 words
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.
Claim 25
Dependent Claim
30 words
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.
Claim 26
Dependent Claim
55 words
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.
Claim 27
Independent Claim
132 words
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.
Claim 28
Independent Claim
132 words
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.
Claim 29
Dependent Claim
85 words
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.
Claim 30
Independent Claim
177 words
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.
Claim 31
Independent Claim
177 words
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.
Claim 32
Independent Claim
186 words
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.
Claim 33
Independent Claim
186 words
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.
References Cited (Backward Citations)
US3218611A
Cited
US3368207A
Cited
US3398405A
Cited
US3469239A
Cited
US3473159A
Cited
US3461433A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1975-06-13 | 1975-12-13 | 1976-06-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1979-06-13 | 1979-12-13 | 1980-06-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1983-06-13 | 1983-12-13 | 1984-06-13 | $7700.00 | Window Closed / Lapsed |