Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2001-01-25
2003-06-24
Chaki, Kakali (Department: 2124)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06584611
ABSTRACT:
BACKGROUND OF THE INVENTION
Compiler optimization has as its goal transforming code to increase its performance. One important factor in optimization is scheduling operations to increase the speed of program execution by utilizing predicated and speculative operations. The present invention relates to optimizing code executed on an Explicit Parallel Instruction Computing (EPIC) architecture with full predication and speculation support 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 which replaces conditional branches in the code with comparison instructions which set a predicate. Each predicated instruction is guarded by a Boolean source operand having a value which determines whether the instruction is executed or nullified.
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 cannot be executed in parallel because of dependencies.
The ESBs ale blocks in a control flow graph where control may enter only from the top but may exit from one or more locations. A control flow graph is a set of nodes and directed edges. For an ESB, a node represents some speculative and predicated code that is executed from the beginning of the block to one of its exits. An edge between a first node and a second node indicates that the first node may pass control to a second node.
FIG. 1
depicts a control flow indicating some properties of the ESB. The ESB is preceded by control flow predecessor blocks CFP
1
and
2
. Note that control only enters from the top of the ESB. In this example control exits from the side and bottom of the ESB to control flow successors CFS
1
and
2
.
ESBs may have different lengths and summary run times depending on various factors such as the execution counter, the number of operations, and dependencies between them. The executable code will be more efficient when the execution workload is balanced between blocks in the control flow, i.e, the execution workload of some “hard” blocks will be thrown on to other ones, which are executed less frequently and/or have some free execution resources.
Migration of operations from between Basic Blocks (blocks not in predicated form) are disclosed in U.S. Pat. No. 5,557,761. However, no techniques applicable to ESBs are disclosed. Accordingly, existing compilers do not have facilities for efficiently balancing the ESBs in the control flow.
SUMMARY OF THE INVENTION
According to one aspect of the invention, a variant of code motion optimization is developed for more powerful regions than Basic Blocks, i.e., for Extended Scalar Blocks, which are a predicated form of the intermediate representation of a program based on such features of modem architectures as speculative execution, full predicated execution and enough processor resources for instruction level parallelism (ILP). Therefore, optimization is performed on a considerable number of operations with explicitly expressed dependencies between the operations, that gives more precise criteria to select “hard” regions (taking into account profiling information) and to select needed amount of migrated operations.
According to another aspect of the invention, the “hardness” of various blocks in a control flow is analyzed to identify which blocks consume more than a threshold level of execution resources. Blocks identified are then analyzed to determine whether resource consuming operations can be “unloaded” to be executed in parallel with operations of the blocks which are control flow predecessors.
According to another aspect of the invention, operations are unloaded to control flow predecessors when the predecessors have free resources to execute the unloaded operations without increasing the overall execution time of the program.
According to one aspect of the invention, an optimizing compiler includes code for migrating operations out of a hard ESB, i.e., an ESB having an excessive number of operations, to control flow predecessors of the hard ESB.
According to another aspect of the invention, critical operations are identified in a hard ESB and successively migrated out of the hard ESB to reduce its height.
According to another aspect of the invention, criteria for identifying critical operations include determining whether an operation requires either dynamic memory access, multiple cycles, or has a large number of successors.
According to another aspect of the invention, migrated operations are followed by a register write operation in the predecessor block and replaced by a register read operation in the hard ESB.
According to another aspect of the invention, operations migrated to a control flow predecessor block store result operands in virtual registers and critical operations in a source block are replace by read operations.
Other features and advantages of the invention will be apparent in view of the following detailed description and appended drawings.
REFERENCES:
patent: 4965724 (1990-10-01), Utsumi et al.
patent: 5202975 (1993-04-01), Rasbold et al.
patent: 5307478 (1994-04-01), Rasbold et al.
patent: 5557761 (1996-09-01), Chan et al.
patent: 5625835 (1997-04-01), Ebcioglu et al.
patent: 5684994 (1997-11-01), Tanaka et al.
patent: 5758051 (1998-05-01), Annen et al.
patent: 5835776 (1998-11-01), Tirumalai et al.
patent: 5958048 (1999-09-01), Babaian et al.
patent: 6247173 (2001-06-01), Subrahmanyam
patent: 0535107 (1993-04-01), None
“A Framework for Balancing Control Flow and Predication,” August et al., 1072-4451/97©IEEE.
Malkhe, S. A., Lin, D. C., William, Y. C., Hank, R. E., Bringmann, R. A.,Effective Compiler Support for Predicated Execution Using the Hyperblock,Center for Reliable and High-Performance computing, University of Illinois, Urbana-Champaign, IL 61801.
Babaian Boris A.
Okunev Sergey K.
Volkonsky Vladimir Y.
Chaki Kakali
Chavis John Q.
Elbrus International Limited
Townsend and Townsend / and Crew LLP
LandOfFree
Critical path optimization—unload hard extended scalar... 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—unload hard extended scalar..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Critical path optimization—unload hard extended scalar... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3147297