US5515535A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for parallel variable optimization
Assignee: RTPC Corp
•
Filing: 1994-09-15
•
Granted: 1996-05-07
•
Expires: 2014-09-15
Abstract
Abstract An optimizer for optimizing an intermediate representation (IR) tree having multiple nodes. The IR tree represents a partial compilation of a source code. The source code is written using a high level language supporting data parallel processing. According to the present invention, the optimizer optimizes the IR tree by minimizing the number and size of temporary parallel variables in the IR tree. Such minimization optimizes the IR tree because temporary parallel variables require an enormous amount of space in memory.
Inventors
- 👤 James L. Frankel
- 👤 Steven J. Sistare
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 18:56
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
268 words
A system for optimizing an intermediate representation (IR) of a source program to generate a target program, the target program to be executed in a data parallel computer, the source program written using a data parallel computer programming language supporting parallel variables having different precision, the system comprising: promotion operation locating means for determining whether the intermediate representation includes a promotion operation associated with a source parallel variable of a first precision and a destination parallel variable of a second precision, said second precision being greater than said first precision, said promotion operation, when executed in the data parallel computer, enabling the data parallel computer to promote the source parallel variable to said destination parallel variable; demotion operation locating means, responsive to said promotion operation locating means determining that said intermediate representation includes a promotion operation, for determining whether the intermediate representation includes a demotion operation to be executed by the data parallel computer after the data parallel computer executes the promotion operation; determining means, responsive to a positive determination by the demotion operation locating means, for determining whether the destination parallel variable of the demotion operation is of a data type which is equal to a data type of said source parallel variable of the promotion operation; and intermediate representation modifying means responsive to a positive determination by said determining means, for inserting into the intermediate representation an instruction which, when executed by the data parallel computer, enables the data parallel computer to assign said destination parallel variable of the demotion operation a data type corresponding to that of the source parallel variable of the promotion operation.
Claim 2
Independent Claim
268 words
A system for optimizing an intermediate representation (IR) of a source program to generate a target program, the target program to be executed in a data parallel computer, the source program written using a data parallel computer programming language supporting parallel variables having different precision, the system comprising: promotion operation locating means for determining whether the intermediate representation includes a promotion operation associated with a source parallel variable of a first precision and a destination parallel variable of a second precision, said second precision being greater than said first precision, said promotion operation, when executed in the data parallel computer, enabling the data parallel computer to promote the source parallel variable to said destination parallel variable; demotion operation locating means, responsive to said promotion operation locating means determining that said intermediate representation includes a promotion operation, for determining whether the intermediate representation includes a demotion operation to be executed by the data parallel computer after the data parallel computer executes the promotion operation; determining means, responsive to a positive determination by the demotion operation locating means, for determining whether the destination parallel variable of the demotion operation is of a data type which is equal to a data type of said source parallel variable of the promotion operation; and intermediate representation modifying means responsive to a positive determination by said determining means, for inserting into the intermediate representation an instruction which, when executed by the data parallel computer, enables the data parallel computer to assign said destination parallel variable of the demotion operation a data type corresponding to that of the source parallel variable of the promotion operation.
Claim 3
Dependent Claim
37 words
A system as defined in claim 1 wherein the intermediate representation modifying means further comprises means for deleting the promotion operation from the intermediate representation in response to a positive determination by said demotion operation locating means.
Claim 4
Dependent Claim
33 words
A system as defined in claim 1 further comprising means for copy propagating the assignment of said destination parallel variable of the demotion operation to the source parallel variable of the promotion operation.
Claim 5
Dependent Claim
294 words
A computer-implemented method for optimizing an intermediate representation (IR) of a source program to generate a target program, the target program to be executed in a data parallel computer, the source program written using a data parallel computer programming language supporting parallel variables having different precision, the method comprising the steps of: determining whether the intermediate representation includes a promotion operation associated with a source parallel variable of a first precision and a destination parallel variable of a second precision, said second precision being greater than said first precision, said promotion operation, when executed in the data parallel computer, enabling the data parallel computer to promote the source parallel variable to said destination parallel variable; in response to determining that the intermediate representation includes a promotion operation, determining whether the intermediate representation includes a demotion operation to be executed by the data parallel computer after the data parallel computer executes the promotion operation; in response to determining that the intermediate representation includes a demotion operation to be executed by the data parallel computer after the data parallel computer executes the promotion operation, determining whether the destination parallel variable of the demotion operation is of a data type which is equal to a data type of said source parallel variable of the promotion operation; and in responsive to a determination that the destination parallel variable of the demotion operation is of a data type which is equal to a data type of said source parallel variable of the promotion operation, inserting into the intermediate representation an instruction which, when executed by the data parallel computer, enables the data parallel computer to assign said destination parallel variable of the demotion operation a data type corresponding to that of the source parallel variable of the promotion operation.
Claim 6
Dependent Claim
294 words
A computer-implemented method for optimizing an intermediate representation (IR) of a source program to generate a target program, the target program to be executed in a data parallel computer, the source program written using a data parallel computer programming language supporting parallel variables having different precision, the method comprising the steps of: determining whether the intermediate representation includes a promotion operation associated with a source parallel variable of a first precision and a destination parallel variable of a second precision, said second precision being greater than said first precision, said promotion operation, when executed in the data parallel computer, enabling the data parallel computer to promote the source parallel variable to said destination parallel variable; in response to determining that the intermediate representation includes a promotion operation, determining whether the intermediate representation includes a demotion operation to be executed by the data parallel computer after the data parallel computer executes the promotion operation; in response to determining that the intermediate representation includes a demotion operation to be executed by the data parallel computer after the data parallel computer executes the promotion operation, determining whether the destination parallel variable of the demotion operation is of a data type which is equal to a data type of said source parallel variable of the promotion operation; and in responsive to a determination that the destination parallel variable of the demotion operation is of a data type which is equal to a data type of said source parallel variable of the promotion operation, inserting into the intermediate representation an instruction which, when executed by the data parallel computer, enables the data parallel computer to assign said destination parallel variable of the demotion operation a data type corresponding to that of the source parallel variable of the promotion operation.
Claim 7
Dependent Claim
55 words
A method as defined in claim 4 wherein the intermediate representation modification step includes the step of deleting the promotion operation from the intermediate representation in response to a determination that the intermediate representation includes a demotion operation to be executed by the data parallel computer alter the data parallel computer executes the promotion operation.
Claim 8
Dependent Claim
34 words
A method as defined in claim 4 further comprising the step of copy propagating the assignment of said destination parallel variable of the demotion operation to the source parallel variable of the promotion operation.
References Cited (Backward Citations)
US4589400A
Cited
US4773038A
Cited
US5142681A
Cited
US4843545A
Cited
US4827403A
Cited
US4984235A
Cited
US5230050A
Cited
US5276881A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-05-07 | 1999-11-06 | 2000-05-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-05-07 | 2003-11-06 | 2004-05-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-05-07 | 2007-11-06 | 2008-05-07 | $7700.00 | Window Closed / Lapsed |