Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2000-02-17
2003-02-25
Morse, Gregory (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06526573
ABSTRACT:
BACKGROUND OF THE INVENTION
Compiler optimization has its goal transforming code to increase its performance. One important factor in optimization is scheduling operations to increase the speed of predicated operations. The present invention relates to optimizing code executed on an Explicit Parallel Instruction Computing (EPIC) architecture and performs the global task of detecting and refining potential parallelism of the source code being compiled.
The present compiler transforms the source-code program represented as a set of Basic Blocks into Extended Scalar Blocks (ESBs) by applying a compiler technique called if-conversion. Extended Scalar Blocks are regions of the predicated code where all dependencies between operations are represented explicitly as a relation between two operations for a considerable number of operations. For each ESB the compiler works out the critical path which is defined as a sequence of operations that will take the longest CPU time and can't be executed in parallel because of dependencies.
The problem of balancing the amount of control flow and predication at schedule time is solved in IMPACT compiler and is described in the article by David I. August, Wen-mei W. Hwu and Scott A. Mahlke, entitled “A Framework for Balancing Control Flow and Predication,” in Proceedings of the 30th annual IEEE/ACM International Symposium on Microarchitecture, pp. 92-103, December 1997.
SUMMARY OF THE INVENTION
According to one aspect of the invention, a compiler optimization method balances the execution time of every set of operations depending on resolution of a condition. Subsequent to removing a condition from the critical path, alternative sets of operations dependent on which value the condition resolves may have different times of termination. A conditional branch selects one of the alternatives when the condition is resolved so that if the alternative with a shorter time of termination is selected it need not wait for the lengthier part of the other alternative to terminate.
According to another aspect of the invention, the difference between the times of termination of the alternative sets of operations is compared to an algorithmic parameter to determine whether to implement the optimization procedure.
According to another aspect of the invention, if either set of operations terminates before the condition is resolved a second successor to the merge is duplicated and moved ahead of the merge to lengthen time of termination of the sets of operations.
According to another aspect of the invention, critical paths are tuned depending on predicates to supply the more exact execution timings instead of common timing of a considered region. Thus, this transformation is a correction of predicated code, obtained after if-conversion, to remove some drawbacks of concurrent execution of if-alternatives (or-parallelism).
Other features and advantages of the invention will be apparent in view of the following detailed description and appended drawings.
REFERENCES:
patent: 5630157 (1997-05-01), Dwyer, III
patent: 5761483 (1998-06-01), Trimberger
patent: 5892936 (1999-04-01), Tran et al.
patent: 5903760 (1999-05-01), Farber et al.
Babaian Boris A.
Okunev Sergey K.
Volkonsky Vladimir Y.
Elbrus International Limited
Morse Gregory
Townsend and Townsned and Crew LLP
LandOfFree
Critical path optimization-optimizing branch operation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Critical path optimization-optimizing branch operation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Critical path optimization-optimizing branch operation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3176733