Patent US5704053A successfully refreshed from Google Patents.
US5704053A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Efficient explicit data prefetching analysis and code generation in a low-level optimizer for inserting prefetch instructions into loops of applications
Assignee: Hewlett Packard Development Co LP
•
Filing: 1995-05-18
•
Granted: 1997-12-30
•
Expires: 2015-05-18
Abstract
Abstract A compiler that facilitates efficient insertion of explicit data prefetch instructions into loop structures within applications uses simple address expression analysis to determine data prefetching requirements. Analysis and explicit data cache prefetch instruction insertion are performed by the compiler in a machine-instruction level optimizer to provide access to more accurate expected loop iteration latency information. Such prefetch instruction insertion strategy tolerates worst-case alignment of user data structures relative to data cache lines. Execution profiles from previous runs of an application are exploited in the insertion of prefetch instructions into loops with internal control flow. Cache line reuse patterns across loop iterations are recognized to eliminate unnecessary prefetch instructions. The prefetch insertion algorithm is integrated with other low-level optimization phases, such as loop unrolling, register reassociation, and instruction scheduling. An alternative embodiment of the compiler limits the insertion of explicit prefetch instructions to those situations where the lower bound on the achievable loop iteration latency is unlikely to be increased as a result of the insertion.
Inventors
- 👤 Vatsa Santhanam
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 15:29
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443; G06F8/4441; G06F8/4442; G06F9/00; G06F9/06; G06F9/30; G06F9/30003; G06F9/3004; G06F9/30047; G06F9/38; G06F9/3824; G06F9/383
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
80 words
A compiler, comprising: means in a low level optimizer for analyzing and efficiently inserting explicit data prefetch instructions into loops of applications; subscript expression analysis means for determining data prefetching requirements; means for recognizing cache line reuse patterns across loop iterations to eliminate unnecessary prefetch instructions; and means for limiting insertion of explicit prefetch instructions to situations where a lower bound on an achievable loop iteration latency is unlikely to be increased as a result of said prefetch instruction insertion.
Claim 2
Dependent Claim
80 words
A compiler, comprising: means in a low level optimizer for analyzing and efficiently inserting explicit data prefetch instructions into loops of applications; subscript expression analysis means for determining data prefetching requirements; means for recognizing cache line reuse patterns across loop iterations to eliminate unnecessary prefetch instructions; and means for limiting insertion of explicit prefetch instructions to situations where a lower bound on an achievable loop iteration latency is unlikely to be increased as a result of said prefetch instruction insertion.
Claim 3
Dependent Claim
25 words
The compiler of claim 1, wherein analysis and explicit data cache prefetch instruction insertion are performed by said compiler in a machine instruction level optimizer.
Claim 4
Dependent Claim
30 words
The compiler of claim 1, further comprising: means for exploiting execution profiles from previous runs of an application during insertion of prefetch instructions into innermost loops with internal control flow.
Claim 5
Dependent Claim
17 words
The compiler of claim 1, wherein said prefetch insertion means is integrated with other low-level optimization phases.
Claim 6
Dependent Claim
20 words
The compiler of claim 4, said other low-level optimization phases comprising: any of loop Unrolling, register reassociation, and instruction scheduling.
Claim 7
Independent Claim
221 words
A method for mitigating or eliminating cache misses in a low level optimizer, comprising the steps of: performing loop body analysis; unrolling loops to reduce prefetch instruction overhead; identifying uniformly generated equivalence classes of memory references in a code stream, where said equivalence classes represent disjoint sets of memory references occurring in a loop whose address expressions can be expressed as a linear function of the same basic loop induction variable and are known to differ only by a compile time constant, allowing the detection of group spatial and group temporal locality among said different memory references; computing an effective memory stride for each of the equivalence classes; determining the number of prefetch instructions needed for full cache miss coverage for each equivalence class, where the number of prefetch instructions that needs to be inserted is a function of the style of prefetching desired, including dumb prefetching that inserts an explicit prefetch instruction for each memory reference, baseline prefetching that inserts as many prefetch instructions as possible without affecting the resource minimum loop iteration latency, and selective prefetching that inserts as many prefetch instructions as are required to ensure full cache miss coverage, exploiting any group-spatial or group-temporal locality that may be apparent among memory references within a uniformly generated equivalence class; and inserting prefetch instructions identified into said code stream.
Claim 8
Independent Claim
221 words
A method for mitigating or eliminating cache misses in a low level optimizer, comprising the steps of: performing loop body analysis; unrolling loops to reduce prefetch instruction overhead; identifying uniformly generated equivalence classes of memory references in a code stream, where said equivalence classes represent disjoint sets of memory references occurring in a loop whose address expressions can be expressed as a linear function of the same basic loop induction variable and are known to differ only by a compile time constant, allowing the detection of group spatial and group temporal locality among said different memory references; computing an effective memory stride for each of the equivalence classes; determining the number of prefetch instructions needed for full cache miss coverage for each equivalence class, where the number of prefetch instructions that needs to be inserted is a function of the style of prefetching desired, including dumb prefetching that inserts an explicit prefetch instruction for each memory reference, baseline prefetching that inserts as many prefetch instructions as possible without affecting the resource minimum loop iteration latency, and selective prefetching that inserts as many prefetch instructions as are required to ensure full cache miss coverage, exploiting any group-spatial or group-temporal locality that may be apparent among memory references within a uniformly generated equivalence class; and inserting prefetch instructions identified into said code stream.
Claim 9
Dependent Claim
52 words
The method of claim 6, further comprising the step of: estimating a prefetch iteration distance for a loop as the ratio of average miss latency and average loop iteration latency, where the average loop iteration latency is derived from a resource-constrained lower bound on a cycle count based on machine resource usage.
Claim 10
Dependent Claim
39 words
The method of claim 6, further comprising the step of: substituting a fixed constant value for unknown terms into the address expressions for memory references to run-time dimensioned arrays to facilitate partitioning of such references into disjoint equivalence classes.
Claim 11
Dependent Claim
30 words
The method of claim 6, further comprising the step of: determining the number of prefetch instructions that are needed for each uniformly generated equivalence class for a selective prefetching strategy.
Claim 12
Dependent Claim
28 words
The method of claim 9, further comprising the step of: sorting the address expressions for memory references belonging to an equivalence class based on their relative constant differences.
Claim 13
Dependent Claim
47 words
The method of claim 9, further comprising the step of: determining an effective memory stride for the memory references associated with each equivalence class and classifying the effective memory stride as being either large or small based on whether it is greater than the cache line size.
Claim 14
Dependent Claim
37 words
The method of claim 9, further comprising the step of: determining prefetch memory distance for the memory references associated with each equivalence class as the product of effective memory stride and prefetch iteration distance for the loop.
Claim 15
Dependent Claim
42 words
The method of claim 9, further comprising the step of: removing memory references within a small-stride equivalence class that trail other memory references within said equivalence class by less than the prefetch memory distance, wherein memory references that remain are cluster leaders.
Claim 16
Dependent Claim
54 words
The method of claim 9, further comprising the step of: grouping the memory references belonging to a large-stride equivalence class that are sorted by their constant address expression differences into clusters each of which has a distinct memory reference designated as the cluster leader and zero or more memory references designated as cluster trailers.
Claim 17
Dependent Claim
26 words
The method of claim 9, further comprising the step of: merging clusters represented by their leaders to profitably exploit group temporal locality in a pairwise fashion.
Claim 18
Dependent Claim
66 words
The method of claim 6, further comprising the steps of: deciding which equivalence classes to insert prefetch instructions for an under the baseline prefetching strategy by first sorting uniformly generated equivalence classes based on a prefetch cost/expected benefit criteria, and only committing to insert prefetch instructions for those equivalence classes with the best cost/expected benefit ratio, without causing resource-based minimum loop iteration latency to be exceeded.
Claim 19
Dependent Claim
33 words
The method of claim 6, further comprising the steps of: running through clusters in each equivalence class; generating explicit prefetch instructions for each cluster; and inserting said prefetch instructions into the code stream.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-12-29 | 2001-06-30 | 2001-12-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-12-29 | 2005-06-30 | 2005-12-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-12-29 | 2009-06-30 | 2009-12-30 | $7700.00 | Window Closed / Lapsed |