US6059841A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Updating data dependencies for loop strip mining
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1997-06-19
•
Granted: 2000-05-09
•
Expires: 2017-06-19
Abstract
Abstract The inventive system and method uses two relationships to update the distance vector after the loop strip-mining optimization has been performed by the compiler. The invention applies the original distance vector for the un-stripmined loop and the strip size from the strip-mining optimization to the relationships, and outputs either one or two distance vectors, depending upon whether the distance is a multiple of the strip size. The invention allows subsequent optimization to occur after strip-mining, and eliminates the need of having to normalize the stripmined loop to recompute the subscripts. The invention also eliminates the need to re-analyze the dependencies of the loop.
Inventors
- 👤 Terry J. Caracuzzo
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 16:35
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/45; G06F8/451; G06F8/452
Claims Analysis
Total Claims: 47
Claim 1
Independent Claim
83 words
A compiler system stored on a computer readable medium having computer programming logic recorded thereon for updating a distance vector pertaining to a section of code proximate to performing an optimization of the section of code, the system comprising: means for storing the distance vector for the section of code prior to the optimization; means for determining a criterion of the optimization; and means for updating the distance vector according to a predetermined expression that includes the criterion and the stored distance vector.
Claim 2
Dependent Claim
83 words
A compiler system stored on a computer readable medium having computer programming logic recorded thereon for updating a distance vector pertaining to a section of code proximate to performing an optimization of the section of code, the system comprising: means for storing the distance vector for the section of code prior to the optimization; means for determining a criterion of the optimization; and means for updating the distance vector according to a predetermined expression that includes the criterion and the stored distance vector.
Claim 3
Dependent Claim
17 words
The compiler system of claim 1, further comprising: means for determining a legality of performing the optimization.
Claim 4
Dependent Claim
18 words
The compiler system of claim 2, further comprising: means for performing the optimization if the legality is legal.
Claim 5
Dependent Claim
18 words
The compiler system of claim 2, further comprising: means for halting the optimization if the legality is illegal.
Claim 6
Dependent Claim
13 words
The compiler system of claim 1, further comprising: means for performing the optimization.
Claim 7
Dependent Claim
16 words
The compiler system of claim 1, further comprising: means for determining whether to perform further optimizations.
Claim 8
Dependent Claim
19 words
The compiler system of claim 1, wherein: the criterion is a strip size; and the optimization is loop strip-mining.
Claim 9
Dependent Claim
15 words
The compiler system of claim 7, wherein: the predetermined expression comprises first and second relationships.
Claim 10
Dependent Claim
30 words
The compiler system of claim 8, wherein: the first relationship includes first and second elements; the first element comprises a floor function; and the second element comprises a modulo function.
Claim 11
Dependent Claim
24 words
The compiler system of claim 9, wherein: the first element is the floor function of the stored distance vector divided by the strip size.
Claim 12
Dependent Claim
24 words
The compiler system of claim 9, wherein: the second element is the modulo function of the stored distance vector divided by the strip size.
Claim 13
Dependent Claim
22 words
The compiler system of claim 8, wherein: the second relationship includes first and second elements; and both elements comprise a ceiling function.
Claim 14
Dependent Claim
24 words
The compiler system of claim 12, wherein: the first element is the ceiling function of the stored distance vector divided by the strip size.
Claim 15
Dependent Claim
38 words
The compiler system of claim 12, wherein: the second element is difference of the stored distance vector minus the multiplication of the strip size times the ceiling function of the stored distance vector divided by the strip size.
Claim 16
Dependent Claim
45 words
The compiler system of claim 7, wherein: the stored distance vector is a multiple of the strip size; the predetermined expression comprises first and second elements; the first element is the stored distance vector divided by the strip size; and the second element is zero.
Claim 17
Dependent Claim
90 words
The compiler system of claim 7, wherein: the stored distance vector is less than the strip size; the predetermined expression comprises first and second relationships; the first relationship comprises first and second elements; the first element of the first relationship is zero; and the second element of the first relationship is the stored distance vector; and the second relationship comprises first and second elements; the first element of the second relationship is one; and the second element of the second relationship is the stored distance vector minus the strip size.
Claim 18
Dependent Claim
108 words
A compiler system stored on a computer readable medium having computer programming logic recorded thereon for updating a distance vector (D) pertaining to a section of code proximate to performing a loop strip-mining optimization of the section of code, the system comprising: means for storing the distance vector for the section of code prior to the strip-mining optimization; means for performing the strip-mining optimization; means for determining a strip size (S) of the strip-mining optimization; and means for updating the distance vector according to first and second predetermined relationships; wherein the first predetermined relationship is (floor(D/S), D mod S); and the second predetermined relationship is (ceiling(D/S), D-(ceiling(D/S)* S).
Claim 19
Dependent Claim
108 words
A compiler system stored on a computer readable medium having computer programming logic recorded thereon for updating a distance vector (D) pertaining to a section of code proximate to performing a loop strip-mining optimization of the section of code, the system comprising: means for storing the distance vector for the section of code prior to the strip-mining optimization; means for performing the strip-mining optimization; means for determining a strip size (S) of the strip-mining optimization; and means for updating the distance vector according to first and second predetermined relationships; wherein the first predetermined relationship is (floor(D/S), D mod S); and the second predetermined relationship is (ceiling(D/S), D-(ceiling(D/S)* S).
Claim 20
Dependent Claim
18 words
The compiler system of claim 17, further comprising: means for determining a legality of performing the strip-mining optimization.
Claim 21
Dependent Claim
16 words
The compiler system of claim 17, further comprising: means for determining whether to perform further optimizations.
Claim 22
Dependent Claim
32 words
The compiler system of claim 17, wherein: the stored distance vector (D) is a multiple of the strip size (S); and the first and second predetermined relationships both reduce to (D/S 0).
Claim 23
Dependent Claim
34 words
The compiler system of claim 17, wherein: the stored distance vector (D) is less than the strip size (S); the first relationship reduces to (0, D); and the second relationship reduces to (1, D-S).
Claim 24
Dependent Claim
69 words
A computer implemented method for updating a distance vector pertaining to a section of code proximate to performing an optimization of the section of code, the method comprising the steps of: storing the distance vector for the section of code prior to the optimization; determining a criterion of the optimization; and updating the distance vector according to a predetermined expression that includes the criterion and the stored distance vector.
Claim 25
Dependent Claim
69 words
A computer implemented method for updating a distance vector pertaining to a section of code proximate to performing an optimization of the section of code, the method comprising the steps of: storing the distance vector for the section of code prior to the optimization; determining a criterion of the optimization; and updating the distance vector according to a predetermined expression that includes the criterion and the stored distance vector.
Claim 26
Dependent Claim
17 words
The method of claim 22, further comprising the step of: determining a legality of performing the optimization.
Claim 27
Dependent Claim
18 words
The method of claim 23, further comprising the step of: performing the optimization if the legality is legal.
Claim 28
Dependent Claim
18 words
The method of claim 23, further comprising the step of: halting the optimization if the legality is illegal.
Claim 29
Dependent Claim
13 words
The method of claim 22, further comprising the step of: performing the optimization.
Claim 30
Dependent Claim
17 words
The method of claim 22, further comprising the step of: p1 determining whether to perform further optimizations.
Claim 31
Dependent Claim
18 words
The method of claim 22, wherein: the criterion is a strip size; and the optimization is loop strip-mining.
Claim 32
Dependent Claim
131 words
The method of claim 28, wherein the predetermined expression comprises first and second relationships; the first relationship includes first and second elements; the first element of the first relationship is the floor function of the stored distance vector divided by the strip size; and the second element of the first relationship is the modulo function of the stored distance vector divided by the strip size; and the second relationship includes first and second elements; the first element of the second relationship is the ceiling function of the stored distance vector divided by the strip size; and the second element of the second relationship is difference of the stored distance vector minus the multiplication of the strip size times the ceiling function of the stored distance vector divided by the strip size.
Claim 33
Dependent Claim
44 words
The method of claim 28, wherein: the stored distance vector is a multiple of the strip size; the predetermined expression comprises first and second elements; the first element is the stored distance vector divided by the strip size; and the second element is zero.
Claim 34
Dependent Claim
88 words
The method of claim 28, wherein: the stored distance vector is less than the strip size; the predetermined expression comprises first and second relationships; the first relationship comprises first and second elements; the first element of the first relationship is zero; and the second element of the first relationship is the stored distance vector; the second relationship comprises first and second elements; the first element of the second relationship is one; and the second element of the second relationship is the stored distance vector minus the strip size.
Claim 35
Dependent Claim
85 words
A computer program product having a computer readable medium having computer program logic recorded thereon that updates a distance vector pertaining to a section of code proximate to performing an optimization of the section of code, the computer program product comprising: code for storing the distance vector for the section of code prior to the optimization; code for determining a criterion of the optimization; and code for updating the distance vector according to a predetermined expression that includes the criterion and the stored distance vector.
Claim 36
Dependent Claim
85 words
A computer program product having a computer readable medium having computer program logic recorded thereon that updates a distance vector pertaining to a section of code proximate to performing an optimization of the section of code, the computer program product comprising: code for storing the distance vector for the section of code prior to the optimization; code for determining a criterion of the optimization; and code for updating the distance vector according to a predetermined expression that includes the criterion and the stored distance vector.
Claim 37
Dependent Claim
17 words
The computer program product of claim 1, further comprising: code for determining whether to perform further optimizations.
Claim 38
Dependent Claim
20 words
The computer program product of claim 32, wherein: the criterion is a strip size; and the optimization is loop strip-mining.
Claim 39
Dependent Claim
16 words
The computer program product of claim 34, wherein: the predetermined expression comprises first and second relationships.
Claim 40
Dependent Claim
31 words
The computer program product of claim 35, wherein: the first relationship includes first and second elements; the first element comprises a floor function; and the second element comprises a modulo function.
Claim 41
Dependent Claim
25 words
The computer program product of claim 36, wherein: the first element is the floor function of the stored distance vector divided by the strip size.
Claim 42
Dependent Claim
25 words
The computer program product of claim 36, wherein: the second element is the modulo function of the stored distance vector divided by the strip size.
Claim 43
Dependent Claim
23 words
The computer program product of claim 35, wherein: the second relationship includes first and second elements; and both elements comprise a ceiling function.
Claim 44
Dependent Claim
25 words
The computer program product of claim 39, wherein: the first element is the ceiling function of the stored distance vector divided by the strip size.
Claim 45
Dependent Claim
39 words
The computer program product of claim 39, wherein: the second element is difference of the stored distance vector minus the multiplication of the strip size times the ceiling function of the stored distance vector divided by the strip size.
Claim 46
Dependent Claim
46 words
The computer program product of claim 34, wherein: the stored distance vector is a multiple of the strip size; the predetermined expression comprises first and second elements; the first element is the stored distance vector divided by the strip size; and the second element is zero.
Claim 47
Dependent Claim
91 words
The computer program product of claim 34, wherein: the stored distance vector is less than the strip size; the predetermined expression comprises first and second relationships; the first relationship comprises first and second elements; the first element of the first relationship is zero; and the second element of the first relationship is the stored distance vector; and the second relationship comprises first and second elements; the first element of the second relationship is one; and the second element of the second relationship is the stored distance vector minus the strip size.
References Cited (Backward Citations)
US5274818A
Cited
US5491823A
Cited
US5802375A
Cited
US5797013A
Cited
US5812852A
Cited
US5822593A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-09 | 2003-11-08 | 2004-05-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-09 | 2007-11-08 | 2008-05-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-09 | 2011-11-08 | 2012-05-09 | $7700.00 | Window Closed / Lapsed |