US5465342A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Dynamically adaptive set associativity for cache memories
Assignee: International Business Machines Corp
•
Filing: 1992-12-22
•
Granted: 1995-11-07
•
Expires: 2012-12-22
Abstract
Abstract A memory cache system for high speed computers provides adaptive set associativity by means of which the degree of associativity of the cache is temporarily and dynamically increased in response to the behavior of the system. More particularly, one or more microcaches is temporarily assigned to a particular location in the main cache memory in response to frequent probes and misses at that location. The temporarily assigned microcache increases the set associativity of that particular location until the microcache is assigned to another location. The reassignability of the microcache reduces the total cache size required as well as the complexity of the control circuitry needed to manage the cache. A cache miss threshold is established which must be exceeded before a location is assigned the microcache, and the microcache remains assigned for only a fixed number of cache accesses called the window size. A least recently used replacement algorithm is used to overwrite entries in the cache.
Inventors
- 👤 Stephen J. Walsh
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 18:04
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0864; G06F2212/00; G06F2212/10; G06F2212/1016; G06F2212/1021; G06F2212/50; G06F2212/502; G06F2212/60; G06F2212/601
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
98 words
A data processing system comprising a main memory for storing data and instructions for operating said data processing system, a set associative cache memory having a plurality of locations for temporarily storing selected ones of said data and instructions, means for temporarily and dynamically increasing a set associativity of at least one of said locations in said cache memory. means for counting cache accesses occurring since the most recent increase in the set associativity of said cache memory, and means responsive to said access counting means for reducing the set associativity of the most recently increased set associativity.
Claim 2
Dependent Claim
98 words
A data processing system comprising a main memory for storing data and instructions for operating said data processing system, a set associative cache memory having a plurality of locations for temporarily storing selected ones of said data and instructions, means for temporarily and dynamically increasing a set associativity of at least one of said locations in said cache memory. means for counting cache accesses occurring since the most recent increase in the set associativity of said cache memory, and means responsive to said access counting means for reducing the set associativity of the most recently increased set associativity.
Claim 3
Dependent Claim
17 words
The data processing system according to claim 1 wherein said cache memory comprises a direct mapped cache.
Claim 4
Dependent Claim
36 words
The data processing system according to claim 1 further comprising at least one auxiliary cache memory which can be temporarily assigned to said at least one location to increase the set associativity of that one location.
Claim 5
Dependent Claim
50 words
The data processing system according to claim 1 further comprising means for counting cache misses for each location in said cache memory, and means for increasing the set associativity of a location in said cache memory only if the number of cache misses for that location exceeds a preselected threshold.
Claim 6
Dependent Claim
27 words
The data processing system according to claim 1 further comprising means for overwriting the least recently used location in said cache memory when a cache miss occurs.
Claim 7
Independent Claim
102 words
A method for operating a data processing system comprising the steps of storing data and instructions for operating said data processing system in a main memory, temporarily storing selected ones of said data and instructions in a set associative cache memory having a plurality of locations, temporarily and dynamically increasing a set associativity of at least one location in said cache memory, counting cache accesses occurring since the most recent increase in the set associativity of said cache memory, and reducing the set associativity of the most recently increased set associativity in response to the results of said step of counting accesses.
Claim 8
Independent Claim
102 words
A method for operating a data processing system comprising the steps of storing data and instructions for operating said data processing system in a main memory, temporarily storing selected ones of said data and instructions in a set associative cache memory having a plurality of locations, temporarily and dynamically increasing a set associativity of at least one location in said cache memory, counting cache accesses occurring since the most recent increase in the set associativity of said cache memory, and reducing the set associativity of the most recently increased set associativity in response to the results of said step of counting accesses.
Claim 9
Dependent Claim
34 words
The method of operating said data processing system according to claim 6 wherein said step of temporarily storing includes the step of directly mapping the locations in said main memory into said cache memory.
Claim 10
Dependent Claim
38 words
The method of operating said data processing system according to claim 6 wherein said step of temporarily storing includes the step of associating a plurality of locations in said main memory with each location in said cache memory.
Claim 11
Dependent Claim
40 words
The method of operating said data processing system according to claim 8 further comprising the step of temporarily assigning at least one auxiliary cache memory to said at least one location to increase the set associativity of that one location.
Claim 12
Dependent Claim
53 words
The method of operating said data processing system according to claim 6 further comprising the steps of counting cache misses for each location in said cache memory, and increasing the set associativity of a location in said cache memory only if the number of cache misses for that location exceeds a preselected threshold.
Claim 13
Dependent Claim
32 words
The method of operating said data processing system according to claim 8 further comprising the step of overwriting the least recently used location in said cache memory when a cache miss occurs.
References Cited (Backward Citations)
US4654782A
Cited
US4493026A
Cited
US4724518A
Cited
US4985829A
Cited
US4914582A
Cited
US4811209A
Cited
US4802085A
Cited
US4833642A
Cited
US5113510A
Cited
US5025366A
Cited
US4905188A
Cited
US5029126A
Cited
US4928225A
Cited
US5029070A
Cited
US4991088A
Cited
US5091851A
Cited
US5043885A
Cited
US5014195A
Cited
US5301296A
Cited
US5210842A
Cited
US5367653A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-11-06 | 1999-05-08 | 1999-11-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-11-06 | 2003-05-08 | 2003-11-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-11-06 | 2007-05-08 | 2007-11-07 | $7700.00 | Window Closed / Lapsed |