US5603004A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for decreasing time penalty resulting from a cache miss in a multi-level cache system
Assignee: Hewlett Packard Development Co LP
•
Filing: 1994-02-14
•
Granted: 1997-02-11
•
Expires: 2014-02-14
Abstract
Abstract A cache system buffers data stored in a main memory and utilized by a processor. The cache system includes a first cache, a second cache, a first transfer channel, a second transfer channel and a third transfer channel. The first cache is fully associative. The second cache is directly mapped. The first transfer channel transfers data lines from the main memory to the first cache. The second transfer channel transfers data lines from the first cache to the second cache. The third transfer channel transfers data lines from the second cache to the main memory. Accesses of data lines from the first cache and the second cache are performed in parallel.
Inventors
- 👤 Gordon Kurpanek
- 👤 Eric Delano
- 👤 Michael A. Buckley
- 👤 William R. Bryg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 16:14
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0893; G06F12/0897; G06F12/0864; G06F12/12; G06F12/0862
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
188 words
In a computing system, a method for buffering data stored in a main memory and utilized by a processor, the method comprising the steps of: (a) transferring data lines from the main memory to a first cache, including the substep of: (a.1) storing with each data line in the first cache an indication which indicates a destination for the data line when the data line is moved out of the first cache, the indication indicating whether the data line will be forwarded to a second cache or whether the data line will be returned to the main memory; (b) when a first data line is moved out of the first cache, and the indication indicates the first data line is to be forwarded to the second cache, moving the first data line to the second cache; (c) when a second data line is moved out of the second cache and is dirty, returning the second data line to the main memory; and, (d) when the processor requests access to a third data line, searching the first cache and the second cache in parallel for the third data line.
Claim 2
Dependent Claim
188 words
In a computing system, a method for buffering data stored in a main memory and utilized by a processor, the method comprising the steps of: (a) transferring data lines from the main memory to a first cache, including the substep of: (a.1) storing with each data line in the first cache an indication which indicates a destination for the data line when the data line is moved out of the first cache, the indication indicating whether the data line will be forwarded to a second cache or whether the data line will be returned to the main memory; (b) when a first data line is moved out of the first cache, and the indication indicates the first data line is to be forwarded to the second cache, moving the first data line to the second cache; (c) when a second data line is moved out of the second cache and is dirty, returning the second data line to the main memory; and, (d) when the processor requests access to a third data line, searching the first cache and the second cache in parallel for the third data line.
Claim 3
Dependent Claim
110 words
A method as in claim 1 wherein step (d) comprises the substeps of: (d.1) generating an index into the second cache; (d.2) using the index to access a fourth data line within the second cache; (d.3) comparing a tag for the fourth data line with a tag for the third data line to determine whether the fourth data line is the third data line; and, (d.4) checking a tag for every data line stored in the first data cache to determine whether any data line in the first data cache is the third data line; wherein step (d.4) is performed in parallel to the performance of steps (d.1) through (d.3).
Claim 4
Dependent Claim
55 words
A method as in claim 1 wherein data lines within the first cache are managed first-in-first-out so that in step (b) the first data line at the time the first data line is moved out of the first cache has been in the first cache longer than any other data line in the first cache.
Claim 5
Dependent Claim
42 words
A method as in claim 1 wherein step (b) includes the substep of: (b.1) when the first cache contains more than a predetermined number of data lines, along with the first data line moving an additional data line from the first cache.
Claim 6
Dependent Claim
38 words
A method as in claim 4 wherein in step (b.1), when the additional data line maps a same location in the second cache as does the first data line, moving the second data line to the main memory.
Claim 7
Dependent Claim
88 words
A method as in claim 1, additionally comprising the step of: (e) when in step (d) the third data line is not in the first cache and is not in the second cache, transferring the third data line from the main memory to the first cache including the following substeps: (i) marking, in the first cache, the third data line as referenced; (ii) prefetching a fourth data line from main memory to the first cache; and, (iii) marking, in the first cache, the fourth data line as unreferenced.
Claim 8
Dependent Claim
64 words
A method as in claim 6 wherein step (e) additionally comprises the substep of: (iv) when the processor requests access to the fourth data line, performing the following substeps, marking, in the first cache, the fourth data line as referenced, prefetching a fifth data line from main memory to the first cache, and marking, in the first cache, the fifth data line as unreferenced.
Claim 9
Dependent Claim
202 words
A cache system for buffering data stored in a main memory and utilized by a processor, the cache system comprising: a first cache including data line storage for storing data lines, and storing means for storing with each data line stored in the data line storage an indication which indicates a destination for the data line when the data line is moved out of the first cache; a second cache; first transfer means, coupled to the first cache and to the main memory, for transferring data lines from the main memory to the first cache; second transfer means, coupled to the first cache, the second cache and the main memory, for transferring data lines from the first cache to the second cache and from the first cache to the main memory, wherein the destination for any first data line moved from the first cache is dependent on a value of the indication for the first data line stored within the storing means; third transfer means, coupled to the second cache and to the main memory means, for transferring data lines from the second cache to the main memory; and, access means for accessing the first cache and the second cache in parallel.
Claim 10
Dependent Claim
202 words
A cache system for buffering data stored in a main memory and utilized by a processor, the cache system comprising: a first cache including data line storage for storing data lines, and storing means for storing with each data line stored in the data line storage an indication which indicates a destination for the data line when the data line is moved out of the first cache; a second cache; first transfer means, coupled to the first cache and to the main memory, for transferring data lines from the main memory to the first cache; second transfer means, coupled to the first cache, the second cache and the main memory, for transferring data lines from the first cache to the second cache and from the first cache to the main memory, wherein the destination for any first data line moved from the first cache is dependent on a value of the indication for the first data line stored within the storing means; third transfer means, coupled to the second cache and to the main memory means, for transferring data lines from the second cache to the main memory; and, access means for accessing the first cache and the second cache in parallel.
Claim 11
Dependent Claim
86 words
A cache system as in claim 8, wherein the access means comprises: index generation means, coupled to the second cache, for generating an index into the second cache; comparison means, coupled to the second cache, for comparing a tag for a data line accessed by the index generated by the index generation mean with a tag for a desired data line; and, associative comparing means, coupled to the first cache for determining whether any data line in the first data cache is the desired data line.
Claim 12
Dependent Claim
16 words
A cache system as in claim 8 wherein the data line storage is a first-in-first-out memory.
Claim 13
Dependent Claim
37 words
A cache system as in claim 8 wherein the second transfer means moves out from the first cache two data lines at a time when the first cache contains more than a predetermined number of data lines.
Claim 14
Dependent Claim
49 words
A cache system as in claim 11 wherein when the second transfer means is moving out from the first cache two data lines which map to a same location in the second cache, the second transfer means will move one of the two data lines to the main memory.
Claim 15
Dependent Claim
130 words
A cache system for buffering data stored in a main memory and utilized by a processor, the cache system comprising: a first cache, the first cache being fully associative; a second cache, the second cache being directly mapped; first transfer means, coupled to the first cache and to the main memory, for transferring data lines from the main memory to the first cache; second transfer means, coupled to the first cache, the second cache and the main memory, for transferring data lines from the first cache to the second cache; third transfer means, coupled to the second cache and to the main memory means, for transferring data lines from the second cache to the main memory; and, access means for accessing the first cache and the second cache in parallel.
Claim 16
Dependent Claim
130 words
A cache system for buffering data stored in a main memory and utilized by a processor, the cache system comprising: a first cache, the first cache being fully associative; a second cache, the second cache being directly mapped; first transfer means, coupled to the first cache and to the main memory, for transferring data lines from the main memory to the first cache; second transfer means, coupled to the first cache, the second cache and the main memory, for transferring data lines from the first cache to the second cache; third transfer means, coupled to the second cache and to the main memory means, for transferring data lines from the second cache to the main memory; and, access means for accessing the first cache and the second cache in parallel.
Claim 17
Dependent Claim
86 words
A cache system as in claim 13, wherein the access means comprises: index generation means, coupled to the second cache, for generating an index into the second cache; comparison means, coupled to the second cache, for comparing a tag for a data line accessed by the index generated by the index generation mean with a tag for a desired data line; and, associative comparing means, coupled to the first cache for determining whether any data line in the first data cache is the desired data line.
Claim 18
Dependent Claim
35 words
A cache system as in claim 13 wherein first cache includes: data line storage for storing data lines; and, content addressable memory for storing tags for the data lines stored in the data line storage.
Claim 19
Dependent Claim
16 words
A cache system as in claim 15 wherein the data line storage is a first-in-first-out memory.
Claim 20
Dependent Claim
48 words
A cache system as in claim 15 wherein the first cache additionally includes storing means for storing with each data line stored in the data line storage an indication which indicates a destination for the data line when the data line is moved out of the first cache.
Claim 21
Dependent Claim
39 words
A cache system as in claim 13 wherein the second transfer means moves out from the first cache more than one data line at a time when the first cache contains more than a predetermined number of data lines.
Claim 22
Dependent Claim
49 words
A cache system as in claim 18 wherein when the second transfer means is moving out from the first cache two data lines which map to a same location in the second cache, the second transfer means will move one of the two data lines to the main memory.
Claim 23
Dependent Claim
37 words
A cache system as in claim 13 wherein the first cache includes storing means for storing with each data line stored in the data line storage an indication which indicates whether the data line has been referenced.
Claim 24
Dependent Claim
76 words
A cache system as in claim 20 wherein the first transfer means is additionally for marking, in the first cache, first data lines as referenced when the first data lines are brought into the first cache as a result of a reference to the first data lines, and for marking, in the first cache, second data lines as unreferenced when the second data lines are brought into the first cache as a result of a prefetch.
Claim 25
Dependent Claim
32 words
A cache system as in claim 21 wherein the access means is additionally for marking, in the first cache, the second data lines as referenced when the seconds data lines are referenced.
Claim 26
Dependent Claim
140 words
In a computing system, a method for buffering data stored in a main memory and utilized by a processor, the method comprising the steps of: (a) transferring data lines from the main memory to a first cache, so that when a first data line is moved from the main memory to the first cache, the first data line is not simultaneously moved to a second cache; (b) when a first data line is moved out of the first cache, moving the first data line to the second cache; (c) when a second data line is moved out of the second cache and is dirty, returning the second data line to the main memory; and, (d) when the processor requests access to a third data line, searching the first cache and the second cache in parallel for the third data line.
Claim 27
Dependent Claim
140 words
In a computing system, a method for buffering data stored in a main memory and utilized by a processor, the method comprising the steps of: (a) transferring data lines from the main memory to a first cache, so that when a first data line is moved from the main memory to the first cache, the first data line is not simultaneously moved to a second cache; (b) when a first data line is moved out of the first cache, moving the first data line to the second cache; (c) when a second data line is moved out of the second cache and is dirty, returning the second data line to the main memory; and, (d) when the processor requests access to a third data line, searching the first cache and the second cache in parallel for the third data line.
Claim 28
Dependent Claim
110 words
A method as in claim 23 wherein step (d) comprises the substeps of: (d.1) generating an index into the second cache; (d.2) using the index to access a fourth data line within the second cache; (d.3) comparing a tag for the fourth data line with a tag for the third data line to determine whether the fourth data line is the third data line; and, (d.4) checking a tag for every data line stored in the first data cache to determine whether any data line in the first data cache is the third data line; wherein step (d.4) is performed in parallel to the performance of steps (d.1) through (d.3).
Claim 29
Dependent Claim
55 words
A method as in claim 23 wherein data lines within the first cache are managed first-in-first-out so that in step (b) the first data line at the time the first data line is moved out of the first cache has been in the first cache longer than any other data line in the first cache.
Claim 30
Dependent Claim
42 words
A method as in claim 23 wherein step (b) includes the substep of: (b.1) when the first cache contains more than a predetermined number of data lines, along with the first data line moving an additional data line from the first cache.
Claim 31
Dependent Claim
38 words
A method as in claim 26 wherein in step (b.1), when the additional data line maps a same location in the second cache as does the first data line, moving the first data line to the main memory.
Claim 32
Dependent Claim
88 words
A method as in claim 23, additionally comprising the step of: (e) when in step (d) the third data line is not in the first cache and is not in the second cache, transferring the third data line from the main memory to the first cache including the following substeps: (i) marking, in the first cache, the third data line as referenced; (ii) prefetching a fourth data line from main memory to the first cache; and, (iii) marking, in the first cache, the fourth data line as unreferenced.
Claim 33
Dependent Claim
64 words
A method as in claim 28 wherein step (e) additionally comprises the substep of: (iv) when the processor requests access to the fourth data line, performing the following substeps, marking, in the first cache, the fourth data line as referenced, prefetching a fifth data line from main memory to the first cache, and marking, in the first cache, the fifth data line as unreferenced.
References Cited (Backward Citations)
US4774654A
Cited
US4928239A
Cited
US5058006A
Cited
US5146578A
Cited
US5307477A
Cited
US5327547A
Cited
EP0449540A2
Cited
US5261066A
Cited
US5317718A
Cited
US5369753A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-02-11 | 2000-08-12 | 2001-02-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-02-11 | 2004-08-12 | 2005-02-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-02-11 | 2008-08-12 | 2009-02-11 | $7700.00 | Window Closed / Lapsed |