US5548761A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Compiler for target machine independent optimization of data movement, ownership transfer and device control
Assignee: International Business Machines Corp
•
Filing: 1993-03-09
•
Granted: 1996-08-20
•
Expires: 2013-03-09
Abstract
Abstract A method and apparatus designed to expose the power of manipulating data transfer and ownership to the compiler has been given. The key ideas behind the XDP methodology are its separation of data transfer from local computation, its non-blocking semantics to allow overlapping of communication with computation, and its unified treatment of data and ownership transfer. In addition, XDP offers the compiler a convenient platform for doing optimizations involving data movement by providing mechanisms for delayed communication binding and generating generalized compute rules. Compile-time data and data ownership transfers are accomplished independent of the target machine architecture. The run-time symbol table given here to support XDP is implementable as an extension to most high-level compiler intermediate languages. The applicability of XDP is quite general, and is not restricted to the optimization of communication for distributed memory machines. For instance, it can be used to optimize data transfers across different levels of a memory hierarchy.
Inventors
- 👤 Vasanth Balasundaram
- 👤 John L. Carter
- 👤 Jeanne Ferrante
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 13:23
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
336 words
A method of compiling and executing a computer program on a general purpose target computer system, comprising the steps of: translating a high level source language into an intermediate language, the intermediate language stored in a computer memory; inserting one or more transfer statements into the intermediate language during one or more initial passes of an optimizer through the intermediate language, the transfer statements identifying a transfer of information, each of the transfer statements having a transfer operation and a transfer resolution, the transfer operation being a target machine independent part of the transfer of information and the transfer resolution being a target machine dependent part of the transfer of information; inserting compute rules into the intermediate language in one or more passes of the optimizer through a plurality of statements of the intermediate language, each of the compute rules determining which of one or more of the statements to execute during the executing of the computer program, the intermediate language with the inserted transfer statements and compute rules being an intermediate language plus XDP form; optimizing the intermediate language plus XDP form, including the transfer operations and compute rules by using the optimizer of the compiler; translating the optimized intermediate language plus XDP form into a target code in a back end of the compiler, the back end using one or more operations of the target computer system to resolve the transfer resolutions so that the target computer system can perform each transfer of information identified by the respective transfer statement, the transfer statement including the optimization of the transfer operation; updating a run-time table on each of one or more devices with run-time table information resulting from the execution of one or more target code representations of the transfer operations; and executing the target code on one or more devices of the computer system, the executing referencing one or more target code representations of the compute rules and one or more entries in a run-time table to control the execution of the target code.
Claim 2
Independent Claim
336 words
A method of compiling and executing a computer program on a general purpose target computer system, comprising the steps of: translating a high level source language into an intermediate language, the intermediate language stored in a computer memory; inserting one or more transfer statements into the intermediate language during one or more initial passes of an optimizer through the intermediate language, the transfer statements identifying a transfer of information, each of the transfer statements having a transfer operation and a transfer resolution, the transfer operation being a target machine independent part of the transfer of information and the transfer resolution being a target machine dependent part of the transfer of information; inserting compute rules into the intermediate language in one or more passes of the optimizer through a plurality of statements of the intermediate language, each of the compute rules determining which of one or more of the statements to execute during the executing of the computer program, the intermediate language with the inserted transfer statements and compute rules being an intermediate language plus XDP form; optimizing the intermediate language plus XDP form, including the transfer operations and compute rules by using the optimizer of the compiler; translating the optimized intermediate language plus XDP form into a target code in a back end of the compiler, the back end using one or more operations of the target computer system to resolve the transfer resolutions so that the target computer system can perform each transfer of information identified by the respective transfer statement, the transfer statement including the optimization of the transfer operation; updating a run-time table on each of one or more devices with run-time table information resulting from the execution of one or more target code representations of the transfer operations; and executing the target code on one or more devices of the computer system, the executing referencing one or more target code representations of the compute rules and one or more entries in a run-time table to control the execution of the target code.
Claim 3
Dependent Claim
34 words
A method of compiling, as in claim 1, where one or more of the transfer resolutions are resolved in one or more later passes of the optimizer through the intermediate language plus XDP form.
Claim 4
Dependent Claim
21 words
A method of compiling, as in claim 1, where the information transferred is data being moved from one device to another.
Claim 5
Dependent Claim
21 words
A method of compiling, as in claim 1, where the information transferred is ownership of data from one device to another.
Claim 6
Dependent Claim
49 words
A method of compiling, as in claim 1, where one or more of the transfer operations are ownership send statements and ownership receive statements, where the ownership send statement relinquishes ownership of a section of data and the ownership receive statement accepts the ownership of the section of data.
Claim 7
Dependent Claim
40 words
A method of compiling, as in claim 1, where one or more of the transfer operations are data send statements and data receive statements, where the data send statement relinquishes the data and the data receive statement accepts the data.
Claim 8
Dependent Claim
36 words
A method of compiling and executing a program, as in claim 1, where one or more of the compute rules comprise one or more intrinsic functions obtained from a library of one or more intrinsic functions.
Claim 9
Dependent Claim
22 words
A method of compiling and executing a program, as in claim 1, where the compute rules comprise one or more boolean expressions.
Claim 10
Dependent Claim
323 words
A general purpose target computer system, comprising: an intermediate language having a plurality of statements, the intermediate language translated from a computer program in a high level source language; a compiler means further comprising: means for inserting one or more transfer statements into the intermediate language during one or more initial passes of an optimizer through the intermediate language, the transfer statements identifying a transfer of information, each of the transfer statements having a transfer operation and a transfer resolution, the transfer operation being a target machine independent part of the transfer of information and the transfer resolution being a target machine dependent part of the transfer of information; means for inserting compute rules into the intermediate language in one or more passes of the optimizer through a plurality of statements of the intermediate language, each of the compute rules determining which of one or more of the statements to execute at an execution time, the intermediate language with the inserted transfer statements and compute rules being an intermediate language plus XDP form; means for optimizing the intermediate language plus XDP form, including the transfer operations and compute rules by using the optimizer of the compiler; and means for translating the optimized intermediate language plus XDP form into a target code in a back end of the compiler, the back end using one or more operations of the target computer system to resolve the transfer resolutions so that the target computer system can perform each transfer of information identified by the respective transfer statement, the transfer statement including the optimization of the transfer operation; and one or more devices each having a run-time table with run-time table information resulting from the execution of one or more target code representations of the transfer operations, the execution of the target code the devices during the execution time controlled by the run-time table information in the respective run-time table for the device and the compute rules.
Claim 11
Dependent Claim
323 words
A general purpose target computer system, comprising: an intermediate language having a plurality of statements, the intermediate language translated from a computer program in a high level source language; a compiler means further comprising: means for inserting one or more transfer statements into the intermediate language during one or more initial passes of an optimizer through the intermediate language, the transfer statements identifying a transfer of information, each of the transfer statements having a transfer operation and a transfer resolution, the transfer operation being a target machine independent part of the transfer of information and the transfer resolution being a target machine dependent part of the transfer of information; means for inserting compute rules into the intermediate language in one or more passes of the optimizer through a plurality of statements of the intermediate language, each of the compute rules determining which of one or more of the statements to execute at an execution time, the intermediate language with the inserted transfer statements and compute rules being an intermediate language plus XDP form; means for optimizing the intermediate language plus XDP form, including the transfer operations and compute rules by using the optimizer of the compiler; and means for translating the optimized intermediate language plus XDP form into a target code in a back end of the compiler, the back end using one or more operations of the target computer system to resolve the transfer resolutions so that the target computer system can perform each transfer of information identified by the respective transfer statement, the transfer statement including the optimization of the transfer operation; and one or more devices each having a run-time table with run-time table information resulting from the execution of one or more target code representations of the transfer operations, the execution of the target code the devices during the execution time controlled by the run-time table information in the respective run-time table for the device and the compute rules.
Claim 12
Dependent Claim
35 words
A computer system, as in claim 9, where the part of the target code representing compute rules and the execution referencing run-time table information is used to balance a load of execution on each device.
References Cited (Backward Citations)
US4642764A
Cited
US4667290A
Cited
US4802091A
Cited
US4956800A
Cited
US5146594A
Cited
US4953084A
Cited
US4885684A
Cited
US5088034A
Cited
US5093916A
Cited
US5313614A
Cited
US5083265A
Cited
US5339419A
Cited
US5355492A
Cited
US5355494A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-08-20 | 2000-02-19 | 2000-08-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-08-20 | 2004-02-19 | 2004-08-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-08-20 | 2008-02-19 | 2008-08-20 | $7700.00 | Window Closed / Lapsed |