Critical path optimization-unzipping

Details Critical path optimization-unzipping Critical path optimization-unzipping

2000-02-15

2003-05-13

Morse, Gregory (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S150000, C717S152000, C717S140000, C717S149000

Reexamination Certificate

active

06564372

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 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. 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.
SUMMARY OF THE INVENTION
According to one aspect of the present invention, a condition resolving instruction is removed from the critical path so that the path of longest execution time will be dependent on resolving a condition determined by other operations not on the critical path.
According to another aspect of the invention, the condition resolving instruction is followed by a merge operation which selects between input results based on the resolution of the condition (Boolean T or F). The merge outputs the selected result to a successor operation. An “unzipping” procedure duplicates the successor operation and schedules the duplicate successor operations prior to the merge. The input results are provided directly to the duplicate successor operations.
According to another aspect of the invention, the outputs of duplicate successor operations are provided as inputs to the merge. Thus, during execution the duplicate successor operations will be executed in parallel while the condition is being resolved. The outputs of duplicate successor operations will be ready when the condition is resolved and the merge will select between these outputs. The “unzipping” operation will remove the condition resolving instruction from the critical path if the combined time of execution of both the predecessor and successor operations exceeds the time of execution of the condition resolving instruction.
According to another aspect of the invention, in the case where a second successor operation, not on the critical path, receives an output from the merge,the merge is duplicated and scheduled in parallel with the duplicate successor operations. The output of the duplicate merge operation is provided to the second successor operation.
Another aspect of the invention is using critical path strategy on a predicated representation of a program based on speculative operation mode and full predicated operation mode and implementing optimizing transformations that take into account predicate dependences and data flow dependencies.
Other advantages and features of the invention will be apparent in view of the following detailed description and appended drawings.


REFERENCES:
patent: 5175856 (1992-12-01), Van Dyke et al.
patent: 5202975 (1993-04-01), Rasbold et al.
patent: 5367651 (1994-11-01), Smith et al.
patent: 5671403 (1997-09-01), Shekita et al.
patent: 5724565 (1998-03-01), Dubey et al.
patent: 5812811 (1998-09-01), Dubey et al.
patent: 5893086 (1999-04-01), Schmuck et al.
patent: 5937195 (1999-08-01), Ju et al.
patent: 5940622 (1999-08-01), Patel
patent: 6026241 (2000-02-01), Chow et al.
patent: 6044221 (2000-03-01), Gupta et al.
patent: 6151706 (2000-11-01), Lo et al.
patent: 6212666 (2001-04-01), Gohl et al.
patent: 6286135 (2001-09-01), Santhanam
patent: 6332214 (2001-12-01), Wu
patent: 6427234 (2002-07-01), Chambers et al.
TITLE: Fast Effective Dynamic Compilation, author: Auslander et al, ACM, 1996.*
TITLE: A program form based on data dependency in predicated region, author: Ferrante et al, ACM, 1983.*
TITLE: Interprocedural Conditional Branch Elimination, author: Bodik et al, ACM, 1997.*
TITLE: Annotation-Directed Run-Time Specialization in C, author: Grant et al, ACM, 1997.*
TITLE: Two Step Approach to Optimize Parallel Execution of Multi join Queries, Publication Date: Mar. 1, 1992, IBM Technical Disclosure Bulletin.*
TITLE: Parallel Simulated Annealing Method for Highly Parallel Multiple Computer Processors, Publication Date: Dec. 1987, IBM Technical disclosure Bulletin.*
TITLE: On Parallelizing and Optimizing the Implementation of Communication Protocols, author: Leue, IEEE, 1996.*
TITLE: Static Single Assignment for Explicity Parallel Program, author: Srinivasan et al, ACM, 1993.

Affiliated with

Also associated with

Rating

Critical path optimization-unzipping 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-unzipping, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Critical path optimization-unzipping will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3041221