US5752037A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of prefetching data for references with multiple stride directions
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1996-04-26
•
Granted: 1998-05-12
•
Expires: 2016-04-26
Abstract
Abstract There are two separate, yet related, prefetching strategies used for data references used having multiple strides, which typically occur in data references within nested loop structures. The first approach attempts to reverse one or more of the nested loops so that the strides of the reference are in the same direction. Once the loop or loops are reversed, data elements can be prefetched in the common loop direction. Preferably, the inner loops are reversed as compared with the outer loops, but this is not essential. The second approach is used where the data reference has multiple strides and the loops cannot be reversed. In this case, the prefetching method prefetches in the opposite direction of the innermost loop that surrounds the data reference. The second approach is used when the first approach cannot be used and where the strides of the reference have different directions and the inner loop is expected to iterate relatively few times. In such a case the second approach produces better results than the prior art.
Inventors
- 👤 Edward H. Gornish
- 👤 Anne M. Holler
- 👤 Wei Chung Hsu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 13:48
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443; G06F8/4441; G06F8/4442; G06F8/447; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0862; G06F2212/00; G06F2212/60; G06F2212/6028
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
118 words
A method of prefetching data elements having multiple strides for a data reference at an inner loop of a nested loop structure, the method comprising the steps of: determining a direction of an inner loop; determining a direction of an outer loop, the inner loop being nested inside the outer loop; identifying a data reference within the inner loop, the data reference having strides determined by the directions of the inner and outer loop; reversing the direction of one of the loops so that both loops have the same direction if the direction of the inner loop is different than the direction of the outer loop; and prefetching a data element in the common direction of the loops.
Claim 2
Independent Claim
118 words
A method of prefetching data elements having multiple strides for a data reference at an inner loop of a nested loop structure, the method comprising the steps of: determining a direction of an inner loop; determining a direction of an outer loop, the inner loop being nested inside the outer loop; identifying a data reference within the inner loop, the data reference having strides determined by the directions of the inner and outer loop; reversing the direction of one of the loops so that both loops have the same direction if the direction of the inner loop is different than the direction of the outer loop; and prefetching a data element in the common direction of the loops.
Claim 3
Dependent Claim
38 words
A method of prefetching data elements according to claim 1 wherein the step of reversing the direction of one of the loops so that both loops have the same direction includes reversing the direction of the inner loop.
Claim 4
Dependent Claim
38 words
A method of prefetching data elements according to claim 1 wherein the step of reversing the direction of one of the loops so that both loops have the same direction includes reversing the direction of the outer loop.
Claim 5
Dependent Claim
84 words
A method of prefetching data elements according to claim 1 further comprising: determining a direction of a second outer loop, the outer loop being nested inside the second outer loop; reversing the direction of either the inner loop or the second outer loop so that both loops have the same direction if the direction of the inner loop is different than the direction of the second outer loop; and prefetching a data element in the common direction of the inner and second outer loops.
Claim 6
Dependent Claim
44 words
A method of prefetching data elements according to claim 4 wherein the step of reversing the direction of either the inner loop or the second outer loop so that both loops have the same direction includes reversing the direction of the second outer loop.
Claim 7
Dependent Claim
64 words
A method of prefetching data elements according to claim 4 wherein the step of reversing the direction of either the inner loop or the second outer loop so that both loops have the same direction includes: reversing the direction of the inner loop; and reversing the direction of the outer loop so that the inner loop and the outer loop have a common direction.
Claim 8
Dependent Claim
29 words
A method of prefetching data elements according to claim 6 wherein the step of reversing the direction of the inner loop includes reversing the direction of the outer loop.
Claim 9
Dependent Claim
64 words
A method of prefetching data elements according to claim 1 further comprising: determining whether one of the loops can be reversed if the direction of the inner loop is different than the direction of the outer loop; and reversing the direction of the loop that can be reversed so that both loops have the same direction if one of the loops can be reversed.
Claim 10
Dependent Claim
34 words
A method of prefetching data elements according to claim 1 further comprising the step of prefetching a data reference in the direction of the outer loop if one of the loops cannot be reversed.
Claim 11
Dependent Claim
41 words
A method of prefetching data according to claim 1 further comprising the steps of prefetching a data reference in the direction of the outer loop if the direction of the inner loop is different than the direction of the outer loop.
Claim 12
Dependent Claim
78 words
A method of prefetching data according to claim 1 wherein the step of prefetching a data reference in the direction of the outer loop if the direction of the inner loop is different than the direction of the outer loop includes the steps of: determining a prefetch distance (p); determining a number of times (m) the inner loop iterates; and prefetching a data reference in the direction of the outer loop if the following expression is satisfied: p>m/2.
Claim 13
Independent Claim
80 words
A method of prefetching data elements having multiple strides, the method comprising the steps of: is determining a direction of an outer loop; determining a direction of an inner loop, the inner loop being nested inside the outer loop and a data reference having multiple strides being made in the inner loop; and prefetching a data reference in the direction of the outer loop if the direction of the inner loop is different than the direction of the outer loop.
Claim 14
Independent Claim
80 words
A method of prefetching data elements having multiple strides, the method comprising the steps of: is determining a direction of an outer loop; determining a direction of an inner loop, the inner loop being nested inside the outer loop and a data reference having multiple strides being made in the inner loop; and prefetching a data reference in the direction of the outer loop if the direction of the inner loop is different than the direction of the outer loop.
Claim 15
Dependent Claim
92 words
A method of prefetching data according to claim 12 further comprising: determining a prefetch distance (p); determining a number of times (m) the inner loop iterates for each iteration of the outer loop; comparing the prefetch distance (p) to the number of times (m) the inner loop iterates for each iteration of the outer loop; and prefetching a data reference in the direction of the outer loop only if the prefetch distance (p) is greater than the number of times (m) the inner loop iterates for each iteration of the outer loop.
Claim 16
Dependent Claim
69 words
A method of prefetching data according to claim 13 wherein the step of prefetching a data reference in the direction of the outer loop only if the prefetch distance (p) is greater than the number of times (m) the inner loop iterates for each iteration of the outer loop includes prefetching a data reference in the direction of the outer loop only if the following expression is satisfied: p>m/2.
Claim 17
Dependent Claim
58 words
A method of prefetching data according to claim 12 further comprising: determining, according to a predetermined condition, that prefetching is not to be performed in the direction of outer loop; reversing the direction of one of the loops so that both loops have the same direction; and prefetching a data reference in the common direction of the loops.
Claim 18
Dependent Claim
37 words
A method of prefetching data according to claim 15 wherein the step of reversing the direction of one of the loops so that both loops have the same direction includes reversing the direction of the inner loop.
Claim 19
Dependent Claim
105 words
An optimizing compiler comprising: means for determining a direction of an inner loop; means for determining a direction of an outer loop, the inner loop being nested inside the outer loop; means for identifying a data reference having multiple strides within the inner loop, the strides being determined by the direction of the inner and outer loops; means for reversing the direction of one of the loops so that both loops have the same direction if the direction of the inner loop is different than the direction of the outer loop; and means for prefetching a data element in the common direction of the loops.
Claim 20
Dependent Claim
105 words
An optimizing compiler comprising: means for determining a direction of an inner loop; means for determining a direction of an outer loop, the inner loop being nested inside the outer loop; means for identifying a data reference having multiple strides within the inner loop, the strides being determined by the direction of the inner and outer loops; means for reversing the direction of one of the loops so that both loops have the same direction if the direction of the inner loop is different than the direction of the outer loop; and means for prefetching a data element in the common direction of the loops.
Claim 21
Dependent Claim
54 words
An optimizing compiler according to claim 17 wherein said means for reversing the direction of one of the loops so that both loops have the same direction includes means for reversing the direction of one of the loops so that both loops have the same direction includes reversing the direction of the inner loop.
Claim 22
Dependent Claim
37 words
An optimizing compiler according to claim 17 wherein said means for reversing the direction of one of the loops so that both loops have the same direction includes means for reversing the direction of the outer loop.
Claim 23
Dependent Claim
49 words
An optimizing compiler according to claim 17 further comprising: means for determining a prefetch distance (p); means for determining a number of times (m) the inner loop iterates; and means for prefetching a data reference in the direction of the outer loop if the following expression is satisfied: p>m/2.
References Cited (Backward Citations)
US5357618A
Cited
US5333291A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-11 | 2001-11-10 | 2002-05-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-11 | 2005-11-10 | 2006-05-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-11 | 2009-11-10 | 2010-05-12 | $7700.00 | Window Closed / Lapsed |