Patent US5469347A successfully refreshed from Google Patents.
Patent US5630097A successfully refreshed from Google Patents.
US5630097A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Enhanced cache operation with remapping of pages for optimizing data relocation from addresses causing cache misses
Assignee: Hewlett Packard Development Co LP
•
Filing: 1994-01-07
•
Granted: 1997-05-13
•
Expires: 2014-01-07
Abstract
Abstract A computer system executing virtual memory management and having a cache is operated in a manner to reduce cache misses by remapping pages of physical memory from which cache misses are detected. The method includes detecting cache misses, as by observing cache fill operations on the system bus, and then remapping the pages in the main memory which contain the addresses of the most frequent cache misses, so that memory references causing thrashing can then coexist in different pages of the cache. For a CPU executing a virtual memory operating system, a page of data or instructions can be moved to a different physical page frame but remain at the same virtual address, by simply updating the page-mapping tables to reflect the new physical location of the page, and copying the data from the old page frame to the new one. The primary feature of the invention is to add bus activity sampling logic to the CPU and enhance the operating system to allow the operating system to detect when cache thrashing is occurring and remap data pages to new physical memory locations to eliminate the cache thrashing situation.
Inventors
- 👤 David A. Orbits
- 👤 Kenneth D. Abramson
- 👤 H. Bruce Butts, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 14:48
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/10; G06F12/0802; G06F12/0864; G06F2212/00; G06F2212/65; G06F2212/653
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
146 words
A method of operating a computer system, said computer system including a CPU, a cache having a plurality of cache page locations, and a main memory, said method comprising the steps of: a) detecting physical addresses of cache misses, wherein said detected physical addresses correspond to said cache page locations; b) recording said detected physical addresses in entries in a structure, wherein each of said entries in said structure corresponds to one of said cache page locations, and counting the number of occurrences of cache misses for each cache page location and recording a cache miss location count for each cache page location in said corresponding entries in said structure; and c) remapping data, corresponding to physical addresses recorded in said entries, having a cache miss location count greater than a predetermined threshold value, to a different physical address associated with a different cache page location.
Claim 2
Independent Claim
146 words
A method of operating a computer system, said computer system including a CPU, a cache having a plurality of cache page locations, and a main memory, said method comprising the steps of: a) detecting physical addresses of cache misses, wherein said detected physical addresses correspond to said cache page locations; b) recording said detected physical addresses in entries in a structure, wherein each of said entries in said structure corresponds to one of said cache page locations, and counting the number of occurrences of cache misses for each cache page location and recording a cache miss location count for each cache page location in said corresponding entries in said structure; and c) remapping data, corresponding to physical addresses recorded in said entries, having a cache miss location count greater than a predetermined threshold value, to a different physical address associated with a different cache page location.
Claim 3
Dependent Claim
27 words
The method according to claim 1, wherein said CPU is executing a virtual memory system and said cache is accessed via physical addresses and not virtual addresses.
Claim 4
Dependent Claim
13 words
The method according to claim 1, wherein said cache is a direct-mapped cache.
Claim 5
Dependent Claim
13 words
The method according to claim 1, wherein said cache is an associative cache.
Claim 6
Dependent Claim
45 words
The method according to claim 1, wherein said step of detecting includes: counting the number of cache misses and producing a detected cache miss count; and storing said detected physical addresses in a buffer each time said detected cache miss count reaches a predetermined number.
Claim 7
Dependent Claim
50 words
The method according to claim 5, wherein said recording step is executed each time said buffer is filled and operates on said stored physical addresses in said buffer and said recording step further includes the step of clearing said buffer after said stored physical addresses in said buffer are recorded.
Claim 8
Dependent Claim
161 words
A computer system, comprising: a) a CPU accessing a main memory and a cache, said cache having a plurality of cache page locations, data being stored in said main memory and in said cache page locations in pages; b) means for detecting physical addresses for accesses by said CPU producing cache misses, wherein said detected physical addresses correspond to said cache page locations; c) means for recording said detected physical address in entries in a structure, wherein each of said entries corresponds to one of said cache page locations, and for counting the number of occurrences of cache misses for each cache page location and recording a cache miss location count for each cache page location in said corresponding entries in said structure; and d) means for remapping data, corresponding to physical addresses recorded in said entries having a cache miss location count greater than a predetermined threshold value, to a different physical address corresponding to a different cache page location.
Claim 9
Dependent Claim
161 words
A computer system, comprising: a) a CPU accessing a main memory and a cache, said cache having a plurality of cache page locations, data being stored in said main memory and in said cache page locations in pages; b) means for detecting physical addresses for accesses by said CPU producing cache misses, wherein said detected physical addresses correspond to said cache page locations; c) means for recording said detected physical address in entries in a structure, wherein each of said entries corresponds to one of said cache page locations, and for counting the number of occurrences of cache misses for each cache page location and recording a cache miss location count for each cache page location in said corresponding entries in said structure; and d) means for remapping data, corresponding to physical addresses recorded in said entries having a cache miss location count greater than a predetermined threshold value, to a different physical address corresponding to a different cache page location.
Claim 10
Dependent Claim
15 words
The system according to claim 7, wherein said CPU is executing a virtual memory system.
Claim 11
Dependent Claim
21 words
The system according to claim 8, wherein said cache is a direct-mapped cache accessed via physical addresses and not virtual addresses.
Claim 12
Dependent Claim
13 words
The system according to claim 8, wherein said cache is an associative cache.
Claim 13
Dependent Claim
49 words
The system according to claim 10, wherein said detecting means includes: means for counting the number of cache misses and for producing a detected cache miss count; and means for storing said detected physical addresses in a buffer each time said detected cache miss count reaches a predetermined number.
Claim 14
Dependent Claim
42 words
The system according to claim 11, wherein said recording means executes, each time said buffer is filled, on said stored physical addresses in said buffer and includes means for clearing said buffer after said stored physical addresses in said buffer are recorded.
Claim 15
Dependent Claim
17 words
The system according to claim 12, including means for interrupting said CPU when said buffer is filled.
Claim 16
Independent Claim
263 words
A method of operating a computer system, comprising the steps of: a) storing in a main memory, pages of data used by a task executing on a CPU, where said CPU is using a virtual memory system; b) storing in a cache, a subset of said pages of data of said main memory in cache page locations; c) generating virtual page addresses in said CPU while executing said task; d) translating said virtual page addresses to physical page addresses to access said cache page locations in said cache and said pages in said main memory; e) detecting physical addresses of accesses that cause cache misses wherein said detected physical addresses correspond to said cache page locations; f) counting the number of cache misses and producing a detected cache miss count; g) storing said detected physical addresses in a buffer each time said detected cache miss count reaches a predetermined number; h) recording said stored physical addresses in entries in a structure, wherein each of said entries corresponds to one of said cache page locations, and counting the number of occurrences of cache misses for each cache page location and recording a cache miss location count for each cache page location in said corresponding entries in said structure, each time said buffer is filled and clearing said buffer after each of said stored physical addresses are recorded; and i) remapping data, corresponding to said physical addresses recorded in said entries, having a cache miss location count greater than a predetermined threshold value, to a different physical address corresponding to a different cache page location.
Claim 17
Independent Claim
263 words
A method of operating a computer system, comprising the steps of: a) storing in a main memory, pages of data used by a task executing on a CPU, where said CPU is using a virtual memory system; b) storing in a cache, a subset of said pages of data of said main memory in cache page locations; c) generating virtual page addresses in said CPU while executing said task; d) translating said virtual page addresses to physical page addresses to access said cache page locations in said cache and said pages in said main memory; e) detecting physical addresses of accesses that cause cache misses wherein said detected physical addresses correspond to said cache page locations; f) counting the number of cache misses and producing a detected cache miss count; g) storing said detected physical addresses in a buffer each time said detected cache miss count reaches a predetermined number; h) recording said stored physical addresses in entries in a structure, wherein each of said entries corresponds to one of said cache page locations, and counting the number of occurrences of cache misses for each cache page location and recording a cache miss location count for each cache page location in said corresponding entries in said structure, each time said buffer is filled and clearing said buffer after each of said stored physical addresses are recorded; and i) remapping data, corresponding to said physical addresses recorded in said entries, having a cache miss location count greater than a predetermined threshold value, to a different physical address corresponding to a different cache page location.
Claim 18
Dependent Claim
36 words
The method according to claim 14, wherein pages of data are swapped between said main memory and a disk memory when pages of data required by said CPU are not currently stored in said main memory.
Claim 19
Dependent Claim
18 words
The method according to claim 14, wherein said cache is a direct-mapped cache storing a number of pages.
Claim 20
Dependent Claim
273 words
A computer system, comprising: a) a CPU executing a virtual memory system; b) a main memory storing pages of data used by a task executing on said CPU under said virtual memory system; c) a direct-mapped cache storing a subset of said pages of data stored in said main memory in cache page locations; d) means for generating virtual page addresses in said CPU while executing said task; e) means for translating said virtual page addresses to physical page addresses to access said cache and said main memory; f) means for detecting physical addresses for accesses by said CPU that cause cache misses, wherein said detected physical addresses correspond to said cache page locations; g) means for counting the number of cache misses and for producing a detected cache miss count; h) means for storing said detected physical addresses in a buffer each time said detected cache miss count reaches a predetermined number; i) means for recording said detected physical addresses in entries in a structure, wherein each of said entries corresponds to one cache page locations, and for counting the number of occurrences of cache misses for each cache page location and recording a cache miss location count for each cache page location in said corresponding entries in said structure each time said buffer is filled and including means for clearing said buffer after said stored physical addresses in said buffer are recorded; and j) means for remapping data, corresponding to said physical addresses recorded in said entries, having a cache miss location count greater than a predetermined threshold value, to a different physical address corresponding to a different cache page location.
Claim 21
Dependent Claim
273 words
A computer system, comprising: a) a CPU executing a virtual memory system; b) a main memory storing pages of data used by a task executing on said CPU under said virtual memory system; c) a direct-mapped cache storing a subset of said pages of data stored in said main memory in cache page locations; d) means for generating virtual page addresses in said CPU while executing said task; e) means for translating said virtual page addresses to physical page addresses to access said cache and said main memory; f) means for detecting physical addresses for accesses by said CPU that cause cache misses, wherein said detected physical addresses correspond to said cache page locations; g) means for counting the number of cache misses and for producing a detected cache miss count; h) means for storing said detected physical addresses in a buffer each time said detected cache miss count reaches a predetermined number; i) means for recording said detected physical addresses in entries in a structure, wherein each of said entries corresponds to one cache page locations, and for counting the number of occurrences of cache misses for each cache page location and recording a cache miss location count for each cache page location in said corresponding entries in said structure each time said buffer is filled and including means for clearing said buffer after said stored physical addresses in said buffer are recorded; and j) means for remapping data, corresponding to said physical addresses recorded in said entries, having a cache miss location count greater than a predetermined threshold value, to a different physical address corresponding to a different cache page location.
Claim 22
Dependent Claim
37 words
The system according to claim 17, wherein said pages of data are swapped between said main memory and a disk memory when pages of data required by said CPU are not currently stored in said main memory.
References Cited (Backward Citations)
US4415970A
Cited
US4489378A
Cited
US4849879A
Cited
US5062055A
Cited
US4989134A
Cited
US4947319A
Cited
US5088036A
Cited
US5193191A
Cited
US5043885A
Cited
US5133058A
Cited
US5247653A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-12 | 2000-11-11 | 2001-05-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-12 | 2004-11-11 | 2005-05-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-12 | 2008-11-11 | 2009-05-13 | $7700.00 | Window Closed / Lapsed |