US4774654A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for prefetching subblocks from a low speed memory to a high speed memory of a memory hierarchy depending upon state of replacing bit in the low speed memory
Assignee: International Business Machines Corp
•
Filing: 1984-12-24
•
Granted: 1988-09-27
•
Expires: 2004-12-24
Abstract
Abstract A prefetching mechanism for a memory hierarchy which includes at least two levels of storage, with L1 being a high-speed low-capacity memory, and L2 being a low-speed high-capacity memory, with the units of L2 and L1 being blocks and sub-blocks respectively, with each block containing several sub-blocks in consecutive addresses. Each sub-block is provided an additional bit, called a r-bit, which indicates that the sub-block has been previously stored in L1 when the bit is 1, and has not been previously stored in L1 when the bit is 0. Initially when a block is loaded into L2 each of the r-bits in the sub-block are set to 0. When a sub-block is transferred from L1 to L2, its r-bit is then set to 1 in the L2 block, to indicate its previous storage in L1. When the CPU references a given sub-block which is not present in L1, and has to be fetched from L2 to L1, the remaining sub-blocks in this block having r-bits set to 1 are prefetched to L1. This prefetching of the other sub-blocks having r-bits set to 1 results in a more efficient utilization of the L1 storage capacity and results in a highter hit ratio.
Inventors
- 👤 James H. Pomerene
- 👤 Thomas R. Puzak
- 👤 Rudolph N. Rechtschaffen
- 👤 Kimming So
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 05:40
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0862; G06F12/0893; G06F12/0897; G06F2212/00; G06F2212/60; G06F2212/6024
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
203 words
In a computing system including at least one processor operative with at least two levels of memory hierarchy comprised of a high-speed low capacity first level of memory (L1), and a low-speed high-capacity second level of memory (L2), said L2 memory storing blocks of data having a plurality of sub-blocks, and said L1 memory storing sub-blocks of data, the improvement comprising: each of said sub-blocks stored in said L2 memory having a replacement bit indicative that said sub-block has been previously stored in said L1 memory and is no longer in said L1 memory when said replacement bit is in one state, and had not been previously stored in said L1 memory when said replacement bit is in an opposite state; and means for prefetching from said L2 memory to said L1 memory all sub-blocks in a given block that have their replacement bit in said one state, said sub-blocks being randomly located in said given block following said at least one processor referencing a predetermined sub-block in said L1 memory, said predetermined sub-block being included in said given block, and said sub-block not being present in said L1 memory and has to be fetched from said L2 memory to said L1 memory.
Claim 2
Dependent Claim
203 words
In a computing system including at least one processor operative with at least two levels of memory hierarchy comprised of a high-speed low capacity first level of memory (L1), and a low-speed high-capacity second level of memory (L2), said L2 memory storing blocks of data having a plurality of sub-blocks, and said L1 memory storing sub-blocks of data, the improvement comprising: each of said sub-blocks stored in said L2 memory having a replacement bit indicative that said sub-block has been previously stored in said L1 memory and is no longer in said L1 memory when said replacement bit is in one state, and had not been previously stored in said L1 memory when said replacement bit is in an opposite state; and means for prefetching from said L2 memory to said L1 memory all sub-blocks in a given block that have their replacement bit in said one state, said sub-blocks being randomly located in said given block following said at least one processor referencing a predetermined sub-block in said L1 memory, said predetermined sub-block being included in said given block, and said sub-block not being present in said L1 memory and has to be fetched from said L2 memory to said L1 memory.
Claim 3
Dependent Claim
24 words
The combination claimed in claim 1, wherein said two levels of memory hierarchy comprise a main memory at L1 and a DASD at L2.
Claim 4
Dependent Claim
25 words
The combination claimed in claim 1, wherein said two levels of memory hierarchy comprise a main memory at L1 and a magnetic drum at L2.
Claim 5
Dependent Claim
24 words
The combination claimed in claim 1, wherein said two levels of memory hierarchy comprise a cache at L1 and a main memory at L2.
Claim 6
Dependent Claim
41 words
The combination claimed in claim 1, wherein said at least two levels of memory comprise a three level memory hierarchy with a level 1 cache at L1, a level 2 cache at L2 and a main memory at level 3 (L3).
Claim 7
Independent Claim
238 words
A method of operating a computing system comprised of at least one processor operative with at least two levels of memory hierarchy comprised of a high-speed low-capacity first level of memory (L1), and a low-speed high-capacity second level of memory (L27), said L2 memory storing blocks of data having a plurality of sub-blocks, and said L1 memory storing sub-blocks of data, wherein each sub-block of data includes a replacement bit indicative that the sub-block has been previously stored in L1 and is no longer said L1 memory when the bit is in one state, and had not been previously stored in said L1 memory when in the opposite state, said method comprising the steps of: interrogating said L1 memory by said at least one processor, to access a given sub-block of data, and if said given sub-block is stored therein, accessing same; and interrogating said L2 memory by said at least one processor, to access said given sub-block of data, if said sub-block is not stored in said L1 memory, and if said given sub-block is stored in said L2 memory, transferring same to said L1 memory, and prefetching from said L2 memory to said L1 memory all other sub-blocks, in the same block of data as said given sub-block, that have their replacement bit in said one state indicative of previously having been stored in said L1 memory, said sub-blocks being randomly located in said given block.
Claim 8
Independent Claim
238 words
A method of operating a computing system comprised of at least one processor operative with at least two levels of memory hierarchy comprised of a high-speed low-capacity first level of memory (L1), and a low-speed high-capacity second level of memory (L27), said L2 memory storing blocks of data having a plurality of sub-blocks, and said L1 memory storing sub-blocks of data, wherein each sub-block of data includes a replacement bit indicative that the sub-block has been previously stored in L1 and is no longer said L1 memory when the bit is in one state, and had not been previously stored in said L1 memory when in the opposite state, said method comprising the steps of: interrogating said L1 memory by said at least one processor, to access a given sub-block of data, and if said given sub-block is stored therein, accessing same; and interrogating said L2 memory by said at least one processor, to access said given sub-block of data, if said sub-block is not stored in said L1 memory, and if said given sub-block is stored in said L2 memory, transferring same to said L1 memory, and prefetching from said L2 memory to said L1 memory all other sub-blocks, in the same block of data as said given sub-block, that have their replacement bit in said one state indicative of previously having been stored in said L1 memory, said sub-blocks being randomly located in said given block.
Claim 9
Dependent Claim
24 words
The method claimed in claim 6, wherein said two levels of memory hierarchy comprise a main memory at L1 and a DASD at L2.
Claim 10
Dependent Claim
25 words
The method claimed in claim 6, wherein said two levels of memory hierarchy comprise a main memory at L1 and a magnetic drum at L2.
Claim 11
Dependent Claim
24 words
The method claimed in claim 6, wherein said two levels of memory hierarchy comprise a cache at L1 and a main memory at L2.
Claim 12
Dependent Claim
42 words
The method claimed in claim 6, wherein said at least two levels of memory hierarchy comprise a three level memory hierarchy with a level 1 cache at L1, a level 2 cache at L2 and a main memory at level 3 (L3).
References Cited (Backward Citations)
US3928857A
Cited
US4370710A
Cited
US4437155A
Cited
US4490782A
Cited
US4464712A
Cited
US4533995A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1991-09-27 | 1992-03-28 | 1992-09-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1995-09-27 | 1996-03-28 | 1996-09-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1999-09-27 | 2000-03-28 | 2000-09-27 | $7700.00 | Window Closed / Lapsed |