US5778436A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Predictive caching system and method based on memory access which previously followed a cache miss
Assignee: Duke University
•
Filing: 1997-11-25
•
Granted: 1998-07-07
•
Expires: 2017-11-25
Abstract
Abstract Predictive cache memory systems and methods are responsive to cache misses to prefetch a data block from main memory based upon the data block which last followed the memory address which caused the cache miss. In response to an access request to main memory for a first main memory data block, which is caused by a primary cache miss, a second main memory data block is identified which was accessed following a previous access request to the main memory for the first main memory data block. Once identified, the second memory data block is stored in a predictive cache if the second main memory data block is not already stored in the predictive cache. Thus, if the next main memory request is for the second main memory block, as was earlier predicted, the second main memory block is already in the predictive cache and may be accessed rapidly. The identification of data blocks for prefetching may be provided by a prediction table which stores therein identifications of a plurality of succeeding main memory data blocks, each of which was accessed following an access request to a corresponding one of a plurality of preceding main memory data blocks. The Prediction Table is updated if predictions are incorrect. The predictive cache may be implemented using on-chip SRAM cache which is integrated with a DRAM array so that transfers between the DRAM array and the predictive cache may occur at high speed using an internal buffer.
Inventors
- 👤 Gershon Kedem
- 👤 Thomas Alexander
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 22:21
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0862
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
160 words
A predictive cache memory subsystem for a data processing system including a main memory, said predictive cache memory subsystem comprising: cache memory means for storing therein data blocks from said main memory; identifying means, responsive to an access request to said main memory for a first main memory data block which results from a cache miss, such that said first main memory data block is not present in said cache memory means, for identifying a second main memory data block which was accessed following an immediately preceding access request to said main memory for said first main memory data block, said identifying means being nonresponsive to a cache hit wherein said first main memory data block is present in said cache memory means; and storing means, responsive to said identifying means, for storing said second main memory data block in said cache memory means if said second main memory data block is not already stored in said cache memory means.
Claim 2
Dependent Claim
160 words
A predictive cache memory subsystem for a data processing system including a main memory, said predictive cache memory subsystem comprising: cache memory means for storing therein data blocks from said main memory; identifying means, responsive to an access request to said main memory for a first main memory data block which results from a cache miss, such that said first main memory data block is not present in said cache memory means, for identifying a second main memory data block which was accessed following an immediately preceding access request to said main memory for said first main memory data block, said identifying means being nonresponsive to a cache hit wherein said first main memory data block is present in said cache memory means; and storing means, responsive to said identifying means, for storing said second main memory data block in said cache memory means if said second main memory data block is not already stored in said cache memory means.
Claim 3
Dependent Claim
63 words
A predictive cache memory subsystem according to claim 1 further comprising: updating means, responsive to an access request to said main memory for a third main memory data block following said access request to said main memory for said first main memory data block, for replacing identification of the second main memory data block with identification of the third main memory data block.
Claim 4
Dependent Claim
91 words
A predictive cache memory subsystem according to claim 1 wherein said identifying means comprises: a prediction table, for storing therein identifications of a plurality of succeeding main memory data blocks, each of which was accessed following an access request to a corresponding one of a plurality of preceding main memory data blocks; and means, responsive to an access request to said first main memory data block, for indexing into said prediction table using the address of said first memory block, to thereby obtain identification of said second main memory data block.
Claim 5
Dependent Claim
83 words
A predictive cache memory subsystem according to claim 3 wherein said storing means comprises: means, responsive to said prediction table containing identification of said second main memory data block, for determining if the second main memory data block is stored in said cache memory means; and means, responsive to the second data block not being stored in said cache memory means, for obtaining said second data block from said main memory, and for storing the second data block in said cache memory means.
Claim 6
Dependent Claim
44 words
A predictive cache memory subsystem according to claim 1 wherein said second main memory data block comprises a plurality of second main memory data blocks which were accessed following said previous access request to said main memory for said first main memory data block.
Claim 7
Dependent Claim
52 words
A predictive cache memory subsystem according to claim 1 wherein said identifying means identifies a second main memory block which was accessed following a previous access request to said main memory for a combination of said first main memory block and at least one additional main memory block, using a HASH function.
Claim 8
Dependent Claim
85 words
A predictive cache memory subsystem according to claim 1: wherein said cache memory means comprises a first cache memory and a second cache memory; wherein said identifying means is responsive to an access request to said main memory of a first main memory data block which results from a first cache memory miss, such that said first cache memory does not contain said first main memory data block; and wherein said storing means stores said second main memory data block in said second cache memory.
Claim 9
Dependent Claim
45 words
A predictive cache memory subsystem according to claim 7 wherein said first cache memory is integrated into a first integrated circuit along with a microprocessor, and wherein said second cache memory is integrated into a plurality of second integrated circuits along with said main memory.
Claim 10
Dependent Claim
27 words
A predictive cache memory subsystem according to claim 8 wherein said plurality of second integrated circuits comprise a plurality of DRAM integrated circuits, including on-chip SRAM buffer.
Claim 11
Dependent Claim
287 words
A predictive cache memory subsystem for a data processing system including a primary cache and a main memory, said predictive cache memory subsystem comprising: a predictive cache, for storing therein data blocks from main memory which are not in said primary cache, and which are predicted to be used by said data processing system; a prediction table which stores therein identifications of a plurality of succeeding main memory data blocks, each of which was accessed following an access request to a corresponding one of a plurality of preceding main memory data blocks; a prefetch controller which is responsive to a first access request by said primary cache to a first main memory data block which results from a cache memory miss, such that said first main memory data block is not in said primary cache, to index into said prediction table to obtain the stored identification of a second main memory block which was accessed following an immediately preceding access request to said first main memory data block, and to fetch the second main memory block from said main memory into said predictive cache if said second main memory block is not already in said predictive cache, said prefetch controller being nonresponsive to a primary cache hit wherein said first main memory data block is present in said primary cache; and an update controller which is responsive to a second access request by said primary cache to main memory following said first access request, for replacing the stored identification of said second main memory block in said prediction table, with an identification of the memory block which is accessed during said second access request, if said second access request does not access said second main memory block.
Claim 12
Dependent Claim
287 words
A predictive cache memory subsystem for a data processing system including a primary cache and a main memory, said predictive cache memory subsystem comprising: a predictive cache, for storing therein data blocks from main memory which are not in said primary cache, and which are predicted to be used by said data processing system; a prediction table which stores therein identifications of a plurality of succeeding main memory data blocks, each of which was accessed following an access request to a corresponding one of a plurality of preceding main memory data blocks; a prefetch controller which is responsive to a first access request by said primary cache to a first main memory data block which results from a cache memory miss, such that said first main memory data block is not in said primary cache, to index into said prediction table to obtain the stored identification of a second main memory block which was accessed following an immediately preceding access request to said first main memory data block, and to fetch the second main memory block from said main memory into said predictive cache if said second main memory block is not already in said predictive cache, said prefetch controller being nonresponsive to a primary cache hit wherein said first main memory data block is present in said primary cache; and an update controller which is responsive to a second access request by said primary cache to main memory following said first access request, for replacing the stored identification of said second main memory block in said prediction table, with an identification of the memory block which is accessed during said second access request, if said second access request does not access said second main memory block.
Claim 13
Dependent Claim
69 words
A predictive cache memory subsystem according to claim 10 wherein said prediction table further comprises: a prediction table cache which stores therein identifications of a portion of said plurality of succeeding main memory blocks from said prediction table, such that said prefetch controller and said update controller access said prediction table cache if said stored identification of said second main memory block is stored in said prediction table cache.
Claim 14
Dependent Claim
51 words
A predictive cache memory subsystem according to claim 10 wherein said prefetch controller indexes into said prediction table to obtain the stored identification of a plurality of second main memory data blocks which were accessed following said previous access request to said main memory for said first main memory data block.
Claim 15
Dependent Claim
59 words
A predictive cache memory subsystem according to claim 10 wherein said prefetch controller indexes into said prediction table to obtain the stored identification of a second main memory block which was accessed following a previous access request to said main memory, using a HASH function of said first main memory block and at least one additional main memory block.
Claim 16
Dependent Claim
43 words
A predictive cache memory subsystem according to claim 10 wherein said primary cache is integrated into a first integrated circuit along with a microprocessor, and wherein said predictive cache is integrated into a plurality of second integrated circuits along with said main memory.
Claim 17
Dependent Claim
27 words
A predictive cache memory subsystem according to claim 14 wherein said plurality of second integrated circuits comprise a plurality of DRAM integrated circuits, including on-chip SRAM buffer.
Claim 18
Dependent Claim
144 words
A predictive cache memory method for a data processing system including main memory and cache memory for storing therein data blocks from said main memory, said predictive cache memory method comprising the steps of: identifying a second main memory data block which was accessed following an immediately preceding access request to said main memory for a first main memory data block, in response to an access request to said main memory for said first main memory data block which results from a cache miss such that said first main memory data block is not present in said cache memory, while ignoring a cache hit wherein said first main memory data block is present in said cache memory; and storing said second main memory data block in said cache memory if said second main memory data block is not already stored in said cache memory.
Claim 19
Dependent Claim
144 words
A predictive cache memory method for a data processing system including main memory and cache memory for storing therein data blocks from said main memory, said predictive cache memory method comprising the steps of: identifying a second main memory data block which was accessed following an immediately preceding access request to said main memory for a first main memory data block, in response to an access request to said main memory for said first main memory data block which results from a cache miss such that said first main memory data block is not present in said cache memory, while ignoring a cache hit wherein said first main memory data block is present in said cache memory; and storing said second main memory data block in said cache memory if said second main memory data block is not already stored in said cache memory.
Claim 20
Dependent Claim
61 words
A method according to claim 16 further comprising the step of: replacing identification of the second main memory data block with identification of a third main memory data block, in response to an access request to said main memory for a third main memory data block following said access request to said main memory for said first main memory data block.
Claim 21
Dependent Claim
76 words
A method according to claim 16 wherein said identifying step comprises the steps of: storing in a prediction table identifications of a plurality of succeeding main memory data blocks, each of which was accessed following an access request to a corresponding one of a plurality of preceding main memory data blocks; and indexing into said prediction table using the address of said first memory block, to thereby obtain identification of said second main memory data block.
Claim 22
Dependent Claim
76 words
A method according to claim 18 wherein said storing step comprises the steps of: determining if the second main memory data block is stored in said cache memory, in response to said prediction table containing identification of said second main memory data block; obtaining said second data block from said main memory in response to the second data block not being stored in said cache memory; and storing the second data block in said cache memory.
Claim 23
Dependent Claim
85 words
A method according to claim 16: wherein said cache memory comprises a first cache memory and a second cache memory; wherein said identifying step is responsive to an access request to said main memory of a first main memory data block which results from a first cache memory miss, such that said first cache memory does not contain said first main memory data block; and wherein said storing step comprises the step of storing said second main memory data block in said second cache memory.
Claim 24
Dependent Claim
271 words
A predictive cache memory method for a data processing system including a primary cache, a main memory, and a predictive cache which stores therein data blocks from main memory which are not in said primary cache and which are predicted to be used by said data processing system; said predictive cache memory method comprising the steps of: storing in a prediction table identifications of a plurality of succeeding main memory data blocks, each of which was accessed following an access request to a corresponding one of a plurality of immediately preceding main memory data blocks; indexing into said prediction table to obtain the stored identification of a second main memory block which was accessed following a previous access request to a first main memory data block in response to a first access request by said primary cache to said first main memory block which results from a cache memory miss, such that said first main memory data block is not in said primary cache, while ignoring a cache hit wherein said first main memory data block is present in said cache memory; fetching the second main memory block from said main memory into said predictive cache if said second main memory block is not already in said predictive cache; and replacing the stored identification of said second main memory block in said prediction table, with an identification of a memory block which is accessed during a second access request, in response to said second access request by said primary cache to main memory following said first access request, if said second access request does not access said second main memory block.
Claim 25
Dependent Claim
271 words
A predictive cache memory method for a data processing system including a primary cache, a main memory, and a predictive cache which stores therein data blocks from main memory which are not in said primary cache and which are predicted to be used by said data processing system; said predictive cache memory method comprising the steps of: storing in a prediction table identifications of a plurality of succeeding main memory data blocks, each of which was accessed following an access request to a corresponding one of a plurality of immediately preceding main memory data blocks; indexing into said prediction table to obtain the stored identification of a second main memory block which was accessed following a previous access request to a first main memory data block in response to a first access request by said primary cache to said first main memory block which results from a cache memory miss, such that said first main memory data block is not in said primary cache, while ignoring a cache hit wherein said first main memory data block is present in said cache memory; fetching the second main memory block from said main memory into said predictive cache if said second main memory block is not already in said predictive cache; and replacing the stored identification of said second main memory block in said prediction table, with an identification of a memory block which is accessed during a second access request, in response to said second access request by said primary cache to main memory following said first access request, if said second access request does not access said second main memory block.
Claim 26
Dependent Claim
56 words
A method according to claim 21 wherein said indexing step comprises the step of: indexing into a prediction table cache which stores therein identifications of a portion of said plurality of succeeding main memory blocks from said prediction table, if said stored identification of said second main memory block is stored in said prediction table cache.
References Cited (Backward Citations)
US4807110A
Cited
US4860199A
Cited
US5148538A
Cited
US5530941A
Cited
US5210845A
Cited
US5305389A
Cited
WO1993018459A1
Cited
US5499355A
Cited
US5418922A
Cited
US5521878A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-07-06 | 2002-01-05 | 2002-07-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-07-06 | 2006-01-05 | 2006-07-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-07-06 | 2010-01-05 | 2010-07-07 | $7700.00 | Window Closed / Lapsed |