US5854934A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimizing compiler having data cache prefetch spreading
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1996-08-23
•
Granted: 1998-12-29
•
Expires: 2016-08-23
Abstract
Abstract A method of scheduling prefetch instructions in a compiler is described that improves performance by minimizing the performance degradation due to dirty cache misses. The method determines the length N of a loop (step 66). The number of prefetch instructions were M within that loop are then determined (step 68). A prefetch spacing P is then calculated according to the formula P=N/M, where the length of the loop is expressed in cycles (step 70). This prefetch spacing is then attached to each prefetch instruction and the instruction scheduler schedules the prefetch instructions so as to space the prefetch instructions apart by approximately the prefetch spacing P (step 72). After the scheduler arranged for P cycles, a prefetch instruction will be assigned a higher priority for scheduling in the next lot.
Inventors
- 👤 Wei Hsu
- 👤 Loren Staley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 09:10
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443; G06F8/4441; G06F8/4442
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
57 words
A method of scheduling instructions for execution on a computer system including a data cache or data cache hierarchy, the method comprising the steps of: determining a length of a loop; generating a plurality (M) of prefetch instructions; and scheduling the plurality of prefetch instructions to space out the prefetch instructions throughout the length of the loop.
Claim 2
Independent Claim
57 words
A method of scheduling instructions for execution on a computer system including a data cache or data cache hierarchy, the method comprising the steps of: determining a length of a loop; generating a plurality (M) of prefetch instructions; and scheduling the plurality of prefetch instructions to space out the prefetch instructions throughout the length of the loop.
Claim 3
Dependent Claim
69 words
The method of scheduling instructions for execution on a computer system according to claim 1 wherein the step of spacing out the prefetch instructions throughout the length of the loop includes spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction so as to minimize performance degradation due to dirty misses in the cache caused by the prefetch instructions.
Claim 4
Dependent Claim
36 words
The method of scheduling instructions for execution on a computer system according to claim 2 wherein the step of determining a length of a loop includes determining a number of cycles (N) required by the loop.
Claim 5
Dependent Claim
43 words
The method of scheduling instructions for execution on a computer system according to claim 3 wherein the step of determining a number of cycles (N) required by the loop includes: determining resource constraints within the system; and determining latency constraints within the system.
Claim 6
Dependent Claim
63 words
The method of scheduling instructions for execution on a computer system according to claim 4 wherein the step of determining a number of cycles (N) required by the loop includes: determining a number of cycles required by each instruction in the loop; and adding the number of cycles required by each instruction together to determine the number of cycles required by the loop.
Claim 7
Dependent Claim
52 words
The method of scheduling instructions for execution on a computer system according to claim 3 wherein the step of spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction includes spacing a prefetch instruction approximately N/M cycles from a prior prefetch instruction.
Claim 8
Dependent Claim
52 words
The method of scheduling instructions for execution on a computer system according to claim 3 wherein the step of spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction includes spacing a prefetch instruction approximately N/M cycles from a subsequent prefetch instruction.
Claim 9
Dependent Claim
82 words
The method of scheduling instructions for execution on a computer system according to claim 3 wherein the step of spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction includes spacing each prefetch instruction apart from a subsequent prefetch instruction by a respective number of cycles, wherein the total spacing between a first prefetch instruction and a last prefetch instruction is equal to the number of cycles (N) required by the loop.
Claim 10
Dependent Claim
52 words
The method of scheduling instructions for execution on a computer system according to claim 2 wherein the step of spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction includes spacing each prefetch instruction approximately N/M cycles from a prior prefetch instruction.
Claim 11
Dependent Claim
62 words
An optimizing compiler stored in a computer-readable memory device and executable by a computer system having a data cache or data cache hierarchy, the compiler comprising: means for identifying a loop; means for determining a length of the loop; means for generating a plurality (M) of prefetch instructions; and means for spacing out the prefetch instructions throughout the length of the loop.
Claim 12
Dependent Claim
62 words
An optimizing compiler stored in a computer-readable memory device and executable by a computer system having a data cache or data cache hierarchy, the compiler comprising: means for identifying a loop; means for determining a length of the loop; means for generating a plurality (M) of prefetch instructions; and means for spacing out the prefetch instructions throughout the length of the loop.
Claim 13
Dependent Claim
45 words
The optimizing compiler according to claim 10 wherein the means for spacing out the prefetch instructions throughout the length of the loop includes means for spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction.
Claim 14
Dependent Claim
30 words
The optimizing compiler according to claim 11 wherein the means for determining a length of the loop includes means for determining a number of cycles (N) required by the loop.
Claim 15
Dependent Claim
39 words
The optimizing compiler according to claim 12 wherein the means for determining a number of cycles (N) required by the loop includes: means for determining resource constraints within the system; and means for determining latency constraints within the system.
Claim 16
Dependent Claim
78 words
The optimizing compiler according to claim 11 wherein the means for spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction includes: means for determining a number of cycles (N) required by the loop; means for dividing the number of cycles (N) by the number of prefetch instructions to produce a prefetch spacing (S); and means for spacing out the prefetch instructions by approximately the prefetch spacing (S).
Claim 17
Dependent Claim
34 words
The optimizing compiler according to claim 14 wherein the means for spacing out the prefetch instructions by approximately prefetch spacing (S) includes means for rounding the prefetch spacing to an integer number of cycles.
Claim 18
Dependent Claim
35 words
The optimizing compiler according to claim 15 wherein the means for spacing out the prefetch instructions by approximately prefetch spacing (S) includes means for rounding the prefetch spacing up to an integer number of cycles.
Claim 19
Dependent Claim
35 words
The optimizing compiler according to claim 15 wherein the means for spacing out the prefetch instructions by approximately prefetch spacing (S) includes means for rounding the prefetch spacing down to an integer number of cycles.
Claim 20
Dependent Claim
89 words
The optimizing compiler according to claim 11 wherein the means for spacing out the prefetch instructions within the loop so that there is approximately the same distance between each prefetch instruction includes: means for determining a number of cycles (N) required by the loop; and means for spacing each prefetch instruction apart from a subsequent prefetch instruction by a respective number of cycles, wherein the total spacing between a first prefetch instruction and a last prefetch instruction is equal to the number of cycles (N) required by the loop.
Claim 21
Dependent Claim
72 words
The optimizing compiler according to claim 18 wherein the means for spacing each prefetch instruction apart from a subsequent prefetch instruction by a respective number of cycles, wherein the total spacing between a first prefetch instruction and a last prefetch instruction is equal to the number of cycles (N) required by the loop includes means for spacing each prefetch instruction apart from a subsequent prefetch instruction by an equal number of cycles.
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) | 2001-12-28 | 2002-06-29 | 2002-12-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-28 | 2006-06-29 | 2006-12-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-28 | 2010-06-29 | 2010-12-29 | $7700.00 | Window Closed / Lapsed |