US6129458A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cache optimization method
Assignee: Teradata US Inc
•
Filing: 1994-03-23
•
Granted: 2000-10-10
•
Expires: 2014-03-23
Abstract
Abstract A cache optimization method which analyzes an existing cache mapping scheme and determines a new cache mapping scheme that eliminates cache collisions. In a first embodiment, an application is traced while running in its main working set by a processor to obtain cache access statistics for objects within the working set under the first caching scheme. The cache access statistics are analyzed to obtain collision information which reveals lines of operating memory that collide in cache memory. Addresses are assigned to the objects using a cache-miss prediction algorithm. If the cache memory is too small to store all of the objects within the working set, the working set is divided into a plurality of working subsets which each contain a smaller number of objects than the working set. Finally, system calls are executed by the processor to effect the second cache mapping scheme. In a second embodiment, a rearrangement of functions within the application is determined using the cache-miss prediction algorithm and the functions are link edited in accordance with the determined rearrangement.
Inventors
- 👤 John H. Waters
- 👤 Hiram B. Curry, Jr.
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 20:43
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443; G06F8/4441; G06F8/4442; G06F11/00; G06F11/30; G06F11/34; G06F11/3409; G06F11/3466; G06F11/3471; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0864; G06F2201/00; G06F2201/815; G06F2201/885
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
140 words
A method for optimizing the storage of a working set of a plurality of lines of operating memory into a cache memory during execution of an application by a processor including the steps of: (a) tracing the application while it is running in the working set by the processor to obtain trace information. including cache access statistics for objects within the working set under a first caching scheme; (b) analyzing the cache access statistics by the processor to obtain collision information which reveals lines of operating memory that collide in cache memory; (c) determining a second cache mapping scheme which eliminates collisions between lines of operating memory by the processor, including the substep of: (c-1) assigning addresses to the objects using a cache-miss prediction algorithm; and (d) executing system calls by the processor to effect the second cache mapping scheme.
Claim 2
Independent Claim
140 words
A method for optimizing the storage of a working set of a plurality of lines of operating memory into a cache memory during execution of an application by a processor including the steps of: (a) tracing the application while it is running in the working set by the processor to obtain trace information. including cache access statistics for objects within the working set under a first caching scheme; (b) analyzing the cache access statistics by the processor to obtain collision information which reveals lines of operating memory that collide in cache memory; (c) determining a second cache mapping scheme which eliminates collisions between lines of operating memory by the processor, including the substep of: (c-1) assigning addresses to the objects using a cache-miss prediction algorithm; and (d) executing system calls by the processor to effect the second cache mapping scheme.
Claim 3
Dependent Claim
55 words
The method as recited in claim 1, wherein step (c) further comprises the substep of: (c-2) dividing the working set into a plurality of working subsets which each contain a smaller number of objects than the working set; and (c-3) assigning new addresses to the objects within each working subset using the cache-miss prediction algorithm.
Claim 4
Dependent Claim
26 words
The method as recited in claim 1, wherein substep (c-2) comprises the substep of: (c-2-A) dividing the trace information into a plurality of contiguous time blocks.
Claim 5
Independent Claim
161 words
A method for optimizing the storage of a working set of a plurality of lines of operating memory into a cache memory during execution of an application by a processor including the steps of: (a) tracing the application while it is running in the working set by the processor to obtain cache access statistics for objects within the working set under a first caching scheme; (b) analyzing the cache access statistics by the processor to obtain collision information which reveals lines of operating memory that collide in cache memory; (c) determining a second cache mapping scheme which eliminates collisions between lines of operating memory by the processor, including the substeps of: (c-1) determining an order in which to rearrange functions within an executable file within the application using a cache-miss prediction algorithm; and (c-2) link editing the functions to rearrange them into a new executable file; and (d) executing system calls by the processor to effect the second cache mapping scheme.
Claim 6
Independent Claim
161 words
A method for optimizing the storage of a working set of a plurality of lines of operating memory into a cache memory during execution of an application by a processor including the steps of: (a) tracing the application while it is running in the working set by the processor to obtain cache access statistics for objects within the working set under a first caching scheme; (b) analyzing the cache access statistics by the processor to obtain collision information which reveals lines of operating memory that collide in cache memory; (c) determining a second cache mapping scheme which eliminates collisions between lines of operating memory by the processor, including the substeps of: (c-1) determining an order in which to rearrange functions within an executable file within the application using a cache-miss prediction algorithm; and (c-2) link editing the functions to rearrange them into a new executable file; and (d) executing system calls by the processor to effect the second cache mapping scheme.
Claim 7
Independent Claim
180 words
A method for optimizing the storage of a working set of a plurality of lines of operating memory into a cache memory during execution of an application by a processor including the steps of: (a) tracing the application while it is running in the working set by the processor to obtain cache access statistics for objects within the working set under a first caching scheme; (b) analyzing the cache access statistics by the processor to obtain collision information which reveals lines of operating memory that collide in cache memory; (c) determining a second cache mapping scheme which eliminates collisions between lines of operating memory by the processor, including the substeps of: (c-1) compiling source code corresponding to an executable file within the application into object modules; (c-2) determining an order in which to arrange the object modules using a cache-miss prediction algorithm; (c-3) linking the object modules to form a second executable file; and (c-4) replacing the one executable file with the second executable file; and (d) executing system calls by the processor to effect the second cache mapping scheme.
Claim 8
Independent Claim
180 words
A method for optimizing the storage of a working set of a plurality of lines of operating memory into a cache memory during execution of an application by a processor including the steps of: (a) tracing the application while it is running in the working set by the processor to obtain cache access statistics for objects within the working set under a first caching scheme; (b) analyzing the cache access statistics by the processor to obtain collision information which reveals lines of operating memory that collide in cache memory; (c) determining a second cache mapping scheme which eliminates collisions between lines of operating memory by the processor, including the substeps of: (c-1) compiling source code corresponding to an executable file within the application into object modules; (c-2) determining an order in which to arrange the object modules using a cache-miss prediction algorithm; (c-3) linking the object modules to form a second executable file; and (c-4) replacing the one executable file with the second executable file; and (d) executing system calls by the processor to effect the second cache mapping scheme.
References Cited (Backward Citations)
US4985829A
Cited
US4860192A
Cited
US5113506A
Cited
US4928239A
Cited
US4825412A
Cited
US5003459A
Cited
US5226133A
Cited
US5073851A
Cited
US5452440A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-10-10 | 2004-04-10 | 2004-10-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-10-10 | 2008-04-10 | 2008-10-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-10-10 | 2012-04-10 | 2012-10-10 | $7700.00 | Window Closed / Lapsed |