US5778435A
Expired / Lapsed
US
⏱️ 0.0 years remaining
History-based prefetch cache including a time queue
Assignee: Avago Technologies International Sales Pte Ltd
•
Filing: 1996-05-30
•
Granted: 1998-07-07
•
Expires: 2016-05-30
Abstract
Abstract A history-based prefetch cache which includes a time queue. The time queue correlates past events with cache misses in a microprocessor. The time queue is set to N cycles, N being a predetermined, arbitrary or programmable amount. The prefetch cache is a prefetch target buffer which receives inputs from a time queue and a cache and determines if an event is present in the cache. If an address is not present in the cache it is prefetched based on past events and inserted into the prefetch target buffer so that the microprocessor will not miss it the next time.
Inventors
- 👤 Alan David Berenbaum
- 👤 Tor E. Jeremiassen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 00:42
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3802; G06F9/3804; G06F9/3806; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0862; G06F9/3814; G06F9/3824; G06F9/383; G06F9/3832; G06F2212/00; G06F2212/60; G06F2212/6024
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
79 words
A history-based prefetch method, said method comprising the steps of: a) selecting an event from a time queue to correlate with a miss of an address of a cache block; b) storing the address of the cache block miss in a cache indexed by the event; c) performing a lookup in the cache for every event in a predetermined class of events; and d) issuing a prefetch for the address of the cache block if a match is found.
Claim 2
Dependent Claim
79 words
A history-based prefetch method, said method comprising the steps of: a) selecting an event from a time queue to correlate with a miss of an address of a cache block; b) storing the address of the cache block miss in a cache indexed by the event; c) performing a lookup in the cache for every event in a predetermined class of events; and d) issuing a prefetch for the address of the cache block if a match is found.
Claim 3
Dependent Claim
19 words
A method according to claim 1, wherein in said step d) the prefetch occurs to a prefetch target buffer.
Claim 4
Dependent Claim
17 words
A method according to claim 1, wherein in said step a) the event is an instruction address.
Claim 5
Dependent Claim
17 words
A method according to claim 1, wherein in said step a) the event is a data address.
Claim 6
Dependent Claim
95 words
A history-based prefetch method, said method comprising the steps of: a) entering an event into a time queue; b) looking up an address of the event in a prefetch target buffer; c) determining if the address of the event is found in the prefetch target buffer; d) issuing a prefetch for an address indexed by the event if a match is found; and e) correlating an address of a cache miss with an event in the time queue and inserting the cache miss address into the prefetch target buffer indexed and tagged by the event.
Claim 7
Dependent Claim
95 words
A history-based prefetch method, said method comprising the steps of: a) entering an event into a time queue; b) looking up an address of the event in a prefetch target buffer; c) determining if the address of the event is found in the prefetch target buffer; d) issuing a prefetch for an address indexed by the event if a match is found; and e) correlating an address of a cache miss with an event in the time queue and inserting the cache miss address into the prefetch target buffer indexed and tagged by the event.
Claim 8
Dependent Claim
28 words
A method according to claim 5, further comprising, after said step d), a step of performing a cache lookup if a match is found in said step d).
Claim 9
Dependent Claim
116 words
A history-based prefetch method, said method comprising the steps of: a) inserting, when a cache miss occurs, a missing address of a cache block into an associative buffer having a tag and address field; b) indexing the associative buffer by an address of an instruction that was fetched N cycles ago, N being a delay time and being greater than or equal to a memory access time; c) using the address of the instruction to perform a lookup into the associative buffer; d) determining if a tag of the instruction is found in the associative buffer; and e) performing a cache prefetch operation using the address indexed by the tag if found in the associative buffer.
Claim 10
Dependent Claim
116 words
A history-based prefetch method, said method comprising the steps of: a) inserting, when a cache miss occurs, a missing address of a cache block into an associative buffer having a tag and address field; b) indexing the associative buffer by an address of an instruction that was fetched N cycles ago, N being a delay time and being greater than or equal to a memory access time; c) using the address of the instruction to perform a lookup into the associative buffer; d) determining if a tag of the instruction is found in the associative buffer; and e) performing a cache prefetch operation using the address indexed by the tag if found in the associative buffer.
Claim 11
Dependent Claim
27 words
A method according to claim 7, further comprising the step of looking up in the cache the address indexed by the tag found in the associative buffer.
Claim 12
Dependent Claim
23 words
A method according to claim 8, wherein the delay time N is any amount greater than or equal to a memory access time.
Claim 13
Dependent Claim
24 words
A method according to claim 8, wherein the delay time N is a predetermined amount greater than or equal to a memory access time.
Claim 14
Dependent Claim
24 words
A method according to claim 8, wherein the delay time N is a programmable amount greater than or equal to a memory access time.
Claim 15
Dependent Claim
19 words
A method according to claim 7, wherein in said step a) the associative buffer is a prefetch target buffer.
Claim 16
Dependent Claim
24 words
A method according to claim 12, wherein in said step a) the addresses stored in the prefetch target buffer are addresses in data space.
Claim 17
Dependent Claim
19 words
A method according to claim 13, wherein the addresses in the data space trigger prefetches to a data cache.
Claim 18
Dependent Claim
24 words
A method according to claim 12, wherein in said step a), the addresses stored in the prefetch target buffer are addresses in instruction space.
Claim 19
Dependent Claim
20 words
A method according to claim 15, wherein the addresses stored in the instruction space trigger prefetches to an instruction cache.
Claim 20
Dependent Claim
35 words
A method according to claim 12, wherein said step e) comprises the substep of prefetching the address of the instruction in the prefetch target buffer and placing it in the cache to prevent future misses.
Claim 21
Dependent Claim
78 words
A history-based prefetch system, comprising: a time queue for receiving events and outputting delayed events; a prefetch target buffer, coupled to the time queue, for receiving the events and the delayed events from the time queue; an interface unit, coupled to the prefetch target buffer, for receiving the output from the prefetch target buffer; and a cache for receiving an output from the interface unit and outputting an address to the prefetch target buffer and the interface unit.
Claim 22
Dependent Claim
78 words
A history-based prefetch system, comprising: a time queue for receiving events and outputting delayed events; a prefetch target buffer, coupled to the time queue, for receiving the events and the delayed events from the time queue; an interface unit, coupled to the prefetch target buffer, for receiving the output from the prefetch target buffer; and a cache for receiving an output from the interface unit and outputting an address to the prefetch target buffer and the interface unit.
Claim 23
Dependent Claim
22 words
A system according to claim 18, wherein the time queue delays events N cycles, N being a predetermined amount greater than zero.
Claim 24
Dependent Claim
17 words
A system according to claim 18, wherein the time queue delays events N cycles, N being programmable.
Claim 25
Dependent Claim
21 words
A system according to claim 18, wherein the time queue delays events N cycles, N being any amount greater than zero.
References Cited (Backward Citations)
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 |