US5317718A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data processing system and method with prefetch buffers
Assignee: Hewlett Packard Development Co LP
•
Filing: 1993-01-25
•
Granted: 1994-05-31
•
Expires: 2013-01-25
Abstract
Abstract A memory system (10) utilizes miss caching by incorporating a small fully-associative miss cache (42) between a cache (18 or 20) and second-level cache (26). Misses in the cache (18 or 20) that hit in the miss cache have only a one cycle miss penalty, as opposed to a many cycle miss penalty without the miss cache (42). Victim caching is an improvement to miss caching that loads a small, fully associative cache (52) with the victim of a miss and not the requested line. Small victim caches (52) of 1 to 4 entries are even more effective at removing conflict misses than miss caching. Stream buffers (62) prefetch cache lines starting at a cache miss address. The prefetched data is placed in the buffer (62) and not in the cache (18 or 20). Stream buffers (62) are useful in removing capacity and compulsory cache misses, as well as some instruction cache misses. Stream buffers (62) are more effective than previously investigated prefetch techniques when the next slower level in the memory hierarchy is pipelined. An extension to the basic stream buffer, called multi-way stream buffers (62), is useful for prefetching along multiple intertwined data reference streams.
Inventors
- 👤 Norman P. Jouppi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 16:57
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0862; F; F02; F02B; F02B75/00; F02B75/02; F02B2075/022; F02B2075/027; G06F2212/00; G06F2212/60; G06F2212/6022
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
189 words
A data processing system, comprising: a first memory for storing information to be supplied to a processor; a second memory for storing information to be supplied to said processor through said first memory; and a stream buffer connected between said first memory and said second memory, for supplying information from said second memory to said first memory when a miss occurs in said first memory for addressed information at a processor specified address, said stream buffer including prefetch means for retrieving from said second memory, in addition to said information supplied to said first memory, additional information at at least one address successive with respect to said processor specified address and for storing said additional retrieved information; said stream buffer having substantially smaller storage than said first memory; and said stream buffer including means for storing an address tag corresponding to said information stored in said stream buffer, for comparing said address tag with said processor specified address when a miss occurs in said first memory, and when said address tag matches said processor specified address supplying the corresponding information stored in said stream buffer to said first memory.
Claim 2
Dependent Claim
189 words
A data processing system, comprising: a first memory for storing information to be supplied to a processor; a second memory for storing information to be supplied to said processor through said first memory; and a stream buffer connected between said first memory and said second memory, for supplying information from said second memory to said first memory when a miss occurs in said first memory for addressed information at a processor specified address, said stream buffer including prefetch means for retrieving from said second memory, in addition to said information supplied to said first memory, additional information at at least one address successive with respect to said processor specified address and for storing said additional retrieved information; said stream buffer having substantially smaller storage than said first memory; and said stream buffer including means for storing an address tag corresponding to said information stored in said stream buffer, for comparing said address tag with said processor specified address when a miss occurs in said first memory, and when said address tag matches said processor specified address supplying the corresponding information stored in said stream buffer to said first memory.
Claim 3
Dependent Claim
75 words
The data processing system of claim 1, wherein said stream buffer is connected to an address path between said first memory and said second memory such that said second memory and said stream buffer simultaneously receive said processor specified address; and said stream buffer is positioned in an information path between said first memory and second memory such that information supplied from said second memory to said first memory is conveyed through said stream buffer.
Claim 4
Dependent Claim
25 words
The data processing system of claim 1, further comprising a plurality of parallel disposed stream buffers connected between said first memory and said second memory.
Claim 5
Dependent Claim
127 words
The data processing system of claim 1, wherein said prefetch means in said stream buffer includes means for retrieving from said second memory additional information at a plurality of addresses successive with respect to said processor specified address and storing said additional retrieved information; and said address tag storing means in said stream buffer includes means for storing a plurality of address tags corresponding to said information stored in said stream buffer, for comparing at least one of said address tags with said processor specified address when a miss occurs in said first memory, and for supplying, when said at least one address tag matches said processor specified address, information corresponding to said one matching address tag and stored in said stream buffer to said first memory.
Claim 6
Dependent Claim
21 words
The data processing system of claim 4, wherein said stream buffer further includes means for shifting information within said stream buffer.
Claim 7
Dependent Claim
124 words
The data processing system of claim 1, wherein said prefetch means in said stream buffer includes means for retrieving from said second memory additional information at a plurality of addresses successive with respect to said processor specified address and storing said additional retrieved information; and said address tag storing means in said stream buffer includes means for storing a plurality of address tags corresponding to said information stored in said stream buffer, for comparing a plurality of said address tags with said processor specified address when a miss occurs in said first memory, and for supplying, when one of said address tags matches said processor specified address, information corresponding to said one address tag and stored in said stream buffer to said first memory.
Claim 8
Dependent Claim
34 words
The data processing system of claim 6, wherein said stream buffer further includes means for shifting information within said stream buffer after information stored in said stream buffer is supplied to said first memory.
Claim 9
Dependent Claim
75 words
The data processing system of claim 6, wherein said stream buffer is connected to an address path between said first memory and said second memory such that said second memory and said stream buffer simultaneously receive said processor specified address; and said stream buffer is positioned in an information path between said first memory and second memory such that information supplied from said second memory to said first memory is conveyed through said stream buffer.
Claim 10
Dependent Claim
25 words
The data processing system of claim 8, further comprising a plurality of parallel disposed stream buffers connected between said first memory and said second memory.
Claim 11
Independent Claim
234 words
A method for operating a memory system having a first memory for storing information to be supplied to a processor and a second memory for storing information to be supplied to said processor through said first memory, comprising the steps of: providing a stream buffer connected between said first memory and said second memory for storing information to be supplied to said processor through said first memory and having a substantially smaller storage than said first memory; addressing said first memory with a processor specified address, determining if information corresponding to said processor specified address is present in said first memory and supplying information to said processor from said first memory if a hit occurs in said first memory, determining if information corresponding to said processor specified address is present in said stream buffer and supplying information to said processor from said stream buffer if a miss occurs in said first memory and information corresponding to said processor specified address is determined to be present in said stream buffer, and when a miss occurs in said first memory and a miss occurs in said stream buffer, supplying information corresponding to said processor specified address from said second memory to said processor via said first memory, supplying additional information at at least one address successive with respect to said processor specified address to said stream buffer and storing said additional information in said stream buffer.
Claim 12
Independent Claim
234 words
A method for operating a memory system having a first memory for storing information to be supplied to a processor and a second memory for storing information to be supplied to said processor through said first memory, comprising the steps of: providing a stream buffer connected between said first memory and said second memory for storing information to be supplied to said processor through said first memory and having a substantially smaller storage than said first memory; addressing said first memory with a processor specified address, determining if information corresponding to said processor specified address is present in said first memory and supplying information to said processor from said first memory if a hit occurs in said first memory, determining if information corresponding to said processor specified address is present in said stream buffer and supplying information to said processor from said stream buffer if a miss occurs in said first memory and information corresponding to said processor specified address is determined to be present in said stream buffer, and when a miss occurs in said first memory and a miss occurs in said stream buffer, supplying information corresponding to said processor specified address from said second memory to said processor via said first memory, supplying additional information at at least one address successive with respect to said processor specified address to said stream buffer and storing said additional information in said stream buffer.
Claim 13
Dependent Claim
71 words
The method of claim 10, wherein said step of supplying additional information from said second memory includes storing in said stream buffer an address tag corresponding to said additional information stored in said stream buffer; and said step of determining if information corresponding to said processor specified address is present in said stream buffer is performed by comparing said address tag stored in said stream buffer with said processor specified address.
Claim 14
Dependent Claim
98 words
The method of claim 10, wherein: said step of supplying additional information from said second memory includes supplying information from said second memory at a plurality of addresses successive with respect to said processor specified address to said stream buffer and storing in said stream buffer address tags corresponding to said additional information stored in said stream buffer; and said step of determining if information corresponding to said processor specified address is present in said stream buffer is performed by comparing at least one of said address tags stored in said stream buffer with said processor specified address.
Claim 15
Dependent Claim
28 words
The method of claim 12, further including: shifting said stored information within said stream buffer after information stored in said stream buffer is supplied to said first memory.
Claim 16
Dependent Claim
19 words
The method of claim 10, wherein said addressing step includes simultaneously addressing said first memory and said stream buffer.
Claim 17
Independent Claim
262 words
A method of operating a memory system having a first memory for storing information to be supplied to a processor and a second memory for storing information to be supplied to said processor through said first memory, comprising the steps of: providing a plurality of parallel disposed stream buffers connected between said first memory and said second memory for storing information to be supplied to said processor through said first memory and having substantially smaller storage than said first memory; addressing said first memory with a processor specified address, determining if information corresponding to said processor specified address is present in said first memory and supplying information to said processor from said first memory if a hit occurs in said first memory, determining if information corresponding to said processor specified address is present in any of said plurality of stream buffers and, when a miss occurs in said first memory and a hit occurs in a determined one of said plurality of stream buffers, supplying information corresponding to said processor specified address from said determined one stream buffer to said processor, and when a miss occurs in said first memory and misses occur in all of said plurality of stream buffers, supplying information corresponding to said processor specified address from said second memory to said processor via said first memory, supplying additional information at at least one address successive with respect to said processor specified address to one of said plurality of stream buffers selected in accordance with predefined criteria, and storing said supplied additional information in said one selected stream buffer.
Claim 18
Independent Claim
262 words
A method of operating a memory system having a first memory for storing information to be supplied to a processor and a second memory for storing information to be supplied to said processor through said first memory, comprising the steps of: providing a plurality of parallel disposed stream buffers connected between said first memory and said second memory for storing information to be supplied to said processor through said first memory and having substantially smaller storage than said first memory; addressing said first memory with a processor specified address, determining if information corresponding to said processor specified address is present in said first memory and supplying information to said processor from said first memory if a hit occurs in said first memory, determining if information corresponding to said processor specified address is present in any of said plurality of stream buffers and, when a miss occurs in said first memory and a hit occurs in a determined one of said plurality of stream buffers, supplying information corresponding to said processor specified address from said determined one stream buffer to said processor, and when a miss occurs in said first memory and misses occur in all of said plurality of stream buffers, supplying information corresponding to said processor specified address from said second memory to said processor via said first memory, supplying additional information at at least one address successive with respect to said processor specified address to one of said plurality of stream buffers selected in accordance with predefined criteria, and storing said supplied additional information in said one selected stream buffer.
Claim 19
Dependent Claim
81 words
The method of claim 15, wherein said step of supplying additional information from said second memory includes storing in said one selected stream buffer an address tag corresponding to said additional information stored in said stream buffer; and said step of determining if information corresponding to said processor specified address is present in any of said plurality of stream buffers is performed by comparing said address tag stored in each of said plurality of stream buffers with said processor specified address.
Claim 20
Dependent Claim
110 words
The method of claim 16, wherein said step of supplying additional information from said second memory includes supplying information from said second memory at a plurality of addresses successive with respect to said processor specified address to said one selected stream buffer and storing in said one selected stream buffer address tags corresponding to said additional information stored in said stream buffer; and said step of determining if information corresponding to said processor specified address is present in any of said plurality of stream buffers is performed by comparing at least one of said address tags stored in each of said plurality of stream buffers with said processor specified address.
Claim 21
Dependent Claim
32 words
The method of claim 17, further including: shifting said stored information within said determined one stream buffer after information stored in said determined one stream buffer is supplied to said first memory.
Claim 22
Dependent Claim
28 words
The data processing method of claim 16 wherein said predefined criteria comprises storing said additional information in a least recently used one of said plurality of stream buffers.
Claim 23
Dependent Claim
21 words
The method of claim 16 wherein said addressing step includes simultaneously addressing said first memory and said plurality of stream buffers.
References Cited (Backward Citations)
US3938097A
Cited
US4467414A
Cited
US4458310A
Cited
US4464717A
Cited
US4897783A
Cited
US4823259A
Cited
GB2193356A
Cited
US4847753A
Cited
US4942520A
Cited
US5023776A
Cited
US4926323A
Cited
US4974156A
Cited
US5148536A
Cited
US5101341A
Cited
US5136697A
Cited
US5214765A
Cited
US5163140A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-05-30 | 1997-11-29 | 1998-05-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-05-30 | 2001-11-29 | 2002-05-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-05-30 | 2005-11-29 | 2006-05-31 | $7700.00 | Window Closed / Lapsed |