US5418922A
Expired / Lapsed
US
⏱️ 0.0 years remaining
History table for set prediction for accessing a set associative cache
Assignee: International Business Machines Corp
•
Filing: 1992-04-30
•
Granted: 1995-05-23
•
Expires: 2012-04-30
Abstract
Abstract A cache control maintains a history table SETLAT for the prediction of line entry (i.e., set member) within a congruence class for cache accessing. For a given cache access, a SETLAT entry can be selected based on the requesting logical address bits directly. The selection of a SETLAT entry may also be based on the hashing of such logical address bits together with other information in order to achieve sufficient randomization. A similar hashing history table may be devised to predict virtual address translation information with high accuracy. Such prediction mechanisms not only allow efficient implementation of the cache access path but also offer the opportunity of achieving multiple accesses per cycle. The proposed prediction method also provides a generic approach to efficient implementations for various directory based table accesses.
Inventors
- 👤 Lishing Liu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 21:39
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0864; G06F12/10; G06F12/1027; G06F12/1045; G06F12/1054; G06F2212/00; G06F2212/60; G06F2212/608; G06F2212/6082
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
174 words
In a set-associative cache memory system of the type wherein data lines are stored in a two-dimensional logical array of rows (called sets) and columns (called congruence classes) of storage cells and a main memory (real) address corresponds to each of the stored data lines and is stored in an associated directory, apparatus for predicting a set position in the logical array for access to a desired data line from a virtual address of the desired data line before determination of a real address corresponding thereto, comprising: a history table for storing set positions of past successful accesses to data lines in said set-associative cache, at least some of said stored set positions being stored each at an address in said history table determined by a virtual address of the data line corresponding thereto; and means for accessing said history table at an access address determined by a virtual address of a desired data line and retrieving a stored set position at said access address, said predicted set position being said retrieved set position.
Claim 2
Dependent Claim
174 words
In a set-associative cache memory system of the type wherein data lines are stored in a two-dimensional logical array of rows (called sets) and columns (called congruence classes) of storage cells and a main memory (real) address corresponds to each of the stored data lines and is stored in an associated directory, apparatus for predicting a set position in the logical array for access to a desired data line from a virtual address of the desired data line before determination of a real address corresponding thereto, comprising: a history table for storing set positions of past successful accesses to data lines in said set-associative cache, at least some of said stored set positions being stored each at an address in said history table determined by a virtual address of the data line corresponding thereto; and means for accessing said history table at an access address determined by a virtual address of a desired data line and retrieving a stored set position at said access address, said predicted set position being said retrieved set position.
Claim 3
Dependent Claim
14 words
Apparatus as defined in claim 1 wherein said history table is a one-dimensional table.
Claim 4
Dependent Claim
29 words
Apparatus as defined in claim 1 wherein an access address in said history table corresponds to and can be determined from any virtual address of a desired data line.
Claim 5
Dependent Claim
33 words
Apparatus as defined in claim 1 wherein each data line stored in said logical array is stored at a congruence class position determined by a virtual address of said each stored data line.
Claim 6
Dependent Claim
93 words
Apparatus as defined in claim 4 and further comprising: means for providing a real address translation for said virtual address of said desired data line; means for providing from said directory real addresses corresponding to all set position possibilities for all congruence class possibilities corresponding to said virtual address of said desired data line; and comparator logic for comparing said real address translation with said real addresses provided from said directory to determine whether said desired data line is located in said cache and if so whether said predicted set position is correct.
Claim 7
Dependent Claim
33 words
Apparatus as defined in claim 1 wherein each data line stored in said logical array is stored at a congruence class position determined by the real address of said each stored data line.
Claim 8
Dependent Claim
67 words
Apparatus as defined in claim 6 and further comprising: a translation prediction history table (TLBLAT) for storing real address translations corresponding to virtual addresses for predicting a congruence class from said virtual address of said desired data line; and means for providing from said cache to a processor a data line stored in said cache at said predicted set position and at said predicted congruence class position.
Claim 9
Dependent Claim
91 words
Apparatus as defined in claim 7 and further comprising: means for providing a correct real address translation for said virtual address of said desired data line to determine whether said predicted congruence class is correct; means for providing from said directory real addresses corresponding to all set position possibilities for said predicted congruence class; and comparator logic for comparing said correct real address translation with said real addresses provided from said directory to determine in the event said predicted congruence class is correct whether said predicted set position is also correct.
References Cited (Backward Citations)
US5148538A
Cited
US5168571A
Cited
US5093778A
Cited
US5230068A
Cited
US5197132A
Cited
US5235697A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-05-22 | 1998-11-21 | 1999-05-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-05-22 | 2002-11-21 | 2003-05-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-05-22 | 2006-11-21 | 2007-05-23 | $7700.00 | Window Closed / Lapsed |