US5737565A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for diallocating stream from a stream buffer
Assignee: International Business Machines Corp
•
Filing: 1995-08-24
•
Granted: 1998-04-07
•
Expires: 2015-08-24
Abstract
Abstract A system and method to use stream filters to defer deallocation of a stream based on the activity level of the stream, thereby preventing a stream thrashing situation from occurring. The least recently used ("LRU") stream is deallocated only after a number of potential new streams are detected. In a data processing system, a method for prefetching cache lines from a main memory to an L1 cache coupled to a processor coupled by a bus to the main memory, wherein the prefetching is augmented with the utilization of a stream buffer and a stream filter, wherein the stream buffer includes an address buffer and a data buffer, wherein the stream buffer hold one or more active streams, and wherein the stream filter contains one or more entries corresponding to one or more active streams, the method comprising the steps of monitoring a sequence of L1 cache misses; replacing entries in the stream filter in response to the L1 cache misses on an LRU basis; and maintaining one of the one or more active streams in the stream buffer until all of the one or more entries corresponding to the one of the one or more active streams have been replaced by the replacing step.
Inventors
- 👤 Michael John Mayfield
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 19:11
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0862; G06F12/12; G06F2212/00; G06F2212/60; G06F2212/6022; G06F2212/6026
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
73 words
An apparatus operable for prefetching data to a memory subsystem from a main memory, wherein said memory subsystem is associated with a processor coupled to said main memory, said apparatus comprising: a stream buffer operable for containing X streams, wherein X is a positive integer; and means operable for de-allocating one of said X streams after a predetermined number of potential new streams are detected, wherein said predetermined number is greater than 1.
Claim 2
Independent Claim
73 words
An apparatus operable for prefetching data to a memory subsystem from a main memory, wherein said memory subsystem is associated with a processor coupled to said main memory, said apparatus comprising: a stream buffer operable for containing X streams, wherein X is a positive integer; and means operable for de-allocating one of said X streams after a predetermined number of potential new streams are detected, wherein said predetermined number is greater than 1.
Claim 3
Dependent Claim
47 words
The apparatus as recited in claim 1, further comprising means operable for allocating a new stream in said stream buffer after said predetermined number, wherein said new stream replaces said one of said X streams, wherein X is a maximum number of streams within said stream buffer.
Claim 4
Dependent Claim
25 words
The apparatus as recited in claim 2, wherein said one of said X streams remains in said stream buffer until said new stream is allocated.
Claim 5
Dependent Claim
18 words
The apparatus as recited in claim 1, wherein said memory subsystem is a cache associated with said processor.
Claim 6
Dependent Claim
19 words
The apparatus as recited in claim 4 wherein said memory subsystem is a primary cache coupled to said processor.
Claim 7
Dependent Claim
19 words
The apparatus as recited in claim 5, wherein said primary cache is embedded on a chip with said processor.
Claim 8
Dependent Claim
20 words
The apparatus as recited in claim 1, wherein said de-allocating means further comprises a means for counting said predetermined number.
Claim 9
Dependent Claim
30 words
The apparatus as recited in claim 1, wherein said predetermined number is greater than or equal to a number of stream filter entries minus a number of stream buffer entries.
Claim 10
Dependent Claim
25 words
The apparatus as recited in claim 1, wherein a head of each of said X streams resides within a primary cache coupled to said processor.
Claim 11
Independent Claim
122 words
An apparatus operable for prefetching data to a memory subsystem from a main memory, wherein said memory subsystem is associated with a processor coupled to said main memory, said apparatus comprising: a stream buffer operable for containing X streams, wherein X is a positive integer; and means operable for de-allocating one of said X streams after a predetermined number of potential new streams are detected, wherein said de-allocating means further comprises a stream filter operable for containing Y entries, wherein Y is a positive integer, wherein said Y entries are allocated on a least recently used basis (LRU), wherein said Y entries correspond to memory subsystem misses, and wherein an entry is aged out of said stream filter after said predetermined number.
Claim 12
Independent Claim
122 words
An apparatus operable for prefetching data to a memory subsystem from a main memory, wherein said memory subsystem is associated with a processor coupled to said main memory, said apparatus comprising: a stream buffer operable for containing X streams, wherein X is a positive integer; and means operable for de-allocating one of said X streams after a predetermined number of potential new streams are detected, wherein said de-allocating means further comprises a stream filter operable for containing Y entries, wherein Y is a positive integer, wherein said Y entries are allocated on a least recently used basis (LRU), wherein said Y entries correspond to memory subsystem misses, and wherein an entry is aged out of said stream filter after said predetermined number.
Claim 13
Dependent Claim
15 words
The apparatus as recited in claim 10, wherein two of said Y entries are identical.
Claim 14
Dependent Claim
13 words
The apparatus as recited in claim 10, wherein said predetermined number equals Y.
Claim 15
Dependent Claim
42 words
The apparatus as recited in claim 10, further comprising means operable for reallocating said one of said X streams when there is a memory subsystem access for said one of said X streams before a memory subsystem access for said new stream.
Claim 16
Independent Claim
100 words
A system for prefetching data from a main memory to a cache associated with a processor coupled to said main memory by a bus, said system comprising: a stream buffer for allocating X streams; a stream filter having Y entries each representing a cache miss, wherein X and Y are positive integers, and wherein each of said X streams is represented by at least one of said Y entries; and means for maintaining a stream in said stream buffer until all of said at least one of said Y entries representing said stream have been deallocated from said stream filter.
Claim 17
Independent Claim
100 words
A system for prefetching data from a main memory to a cache associated with a processor coupled to said main memory by a bus, said system comprising: a stream buffer for allocating X streams; a stream filter having Y entries each representing a cache miss, wherein X and Y are positive integers, and wherein each of said X streams is represented by at least one of said Y entries; and means for maintaining a stream in said stream buffer until all of said at least one of said Y entries representing said stream have been deallocated from said stream filter.
Claim 18
Dependent Claim
54 words
The system as recited in claim 14, further comprising means for allocating a new stream in said stream buffer in response to a cache miss of data corresponding to said new stream after said all of said at least one of said Y entries representing said stream have been deallocated from said stream filter.
Claim 19
Dependent Claim
25 words
The system as recited in claim 15, wherein said stream remains in said stream buffer until said new stream is allocated in said stream buffer.
Claim 20
Dependent Claim
48 words
The system as recited in claim 14, further comprising means for reallocating said stream in said stream buffer after all of said at least one of said Y entries representing said stream have been deallocated from said stream filter when a cache miss occurs corresponding to said stream.
Claim 21
Dependent Claim
21 words
The system as recited in claim 14, wherein said Y entries are deallocated from said stream filter on an LRU basis.
Claim 22
Dependent Claim
29 words
The system as recited in claim 14, wherein a head of each said X streams resides on a processor-side of a bus coupling said processor to said main memory.
Claim 23
Dependent Claim
154 words
In a data processing system, a method for prefetching cache lines from a main memory to a cache coupled to a processor coupled by a bus to said main memory, wherein said prefetching is augmented with the utilization of a stream buffer and a stream filter, wherein said stream buffer includes an address buffer and a data buffer, wherein said stream buffer holds one or more active streams, and wherein said stream filter contains one or more entries corresponding to said one or more active streams, said method comprising the steps of: monitoring a sequence of cache misses; replacing entries in said stream filter in response to said cache misses on an LRU basis; and maintaining one of said one or more active streams in said stream buffer until all of said one or more entries corresponding to said one of said one or more active streams have been replaced by said replacing step.
Claim 24
Dependent Claim
154 words
In a data processing system, a method for prefetching cache lines from a main memory to a cache coupled to a processor coupled by a bus to said main memory, wherein said prefetching is augmented with the utilization of a stream buffer and a stream filter, wherein said stream buffer includes an address buffer and a data buffer, wherein said stream buffer holds one or more active streams, and wherein said stream filter contains one or more entries corresponding to said one or more active streams, said method comprising the steps of: monitoring a sequence of cache misses; replacing entries in said stream filter in response to said cache misses on an LRU basis; and maintaining one of said one or more active streams in said stream buffer until all of said one or more entries corresponding to said one of said one or more active streams have been replaced by said replacing step.
Claim 25
Dependent Claim
62 words
The method as recited in claim 20, further comprising the step of allocating a new active stream in said stream buffer in response to a cache miss of data corresponding to said new active stream after said all of said one or more entries corresponding to said one of said one or more active streams have been replaced by said replacing step.
Claim 26
Dependent Claim
69 words
The method as recited in claim 21 further comprising the step of reallocating said one of said one or more active streams in said stream buffer after said all of said one or more entries corresponding to said one of said one or more active streams have been replaced by said replacing step when a cache miss occurs corresponding to said one of said one or more active streams.
Claim 27
Dependent Claim
33 words
The method as recited in claim 21, wherein said one of said one or more active streams remains in said stream buffer until said new active stream is allocated in said stream buffer.
Claim 28
Dependent Claim
33 words
The method as recited in claim 20, wherein a head of each of said one or more active streams resides on a processor-side of a bus coupling said processor to said main memory.
References Cited (Backward Citations)
US4442488A
Cited
US4980823A
Cited
US5146578A
Cited
US5317718A
Cited
US5473764A
Cited
WO1992020027A1
Cited
US5345560A
Cited
US5353419A
Cited
US5371870A
Cited
US5361391A
Cited
US5566324A
Cited
US5586295A
Cited
US5586294A
Cited
US5388247A
Cited
US5490113A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-04-06 | 2001-10-06 | 2002-04-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-04-06 | 2005-10-06 | 2006-04-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-04-06 | 2009-10-06 | 2010-04-07 | $7700.00 | Window Closed / Lapsed |