Early exit transformations for software pipelining

Details Early exit transformations for software pipelining Early exit transformations for software pipelining

1999-03-22

2003-05-27

Ingberg, Todd (Department: 2124)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C712S219000, C712S239000

Reexamination Certificate

active

06571385

ABSTRACT:

TECHNICAL FIELD
This invention relates generally to the field of computing environments and, more particularly, to a method of transforming software loops having early exits.
BACKGROUND INFORMATION
In order to accelerate the processing of data, many high-performance computing systems overlap the execution of loop iterations using a technique called software pipelining. This improves the utilization of available hardware resources by increasing instruction-level parallelism. The task of software pipelining is simplified when the loop consists of a single basic block that has a single loop exit. Thus, in order to generate code that can be software pipelined, compilers strive to transform loops that have multiple exits (a normal loop exit and one or more early exits) into loops having a single exit. Current techniques, however, often produce transformed loops that are inefficient and have high complexity. For these reasons, and for other reasons stated below which will become apparent to those skilled in the art upon reading and understanding the present specification, there is a need for the present invention.
SUMMARY OF THE INVENTION
As explained in detail below, the invention is directed to the transformation of software loops having early exit conditions. In one embodiment the invention transforms the software loop by assigning a predicate register for each early exit condition of the software loop such that the predicate registers are set within the software loop when the corresponding early exit condition is satisfied. The predicate registers are examined after termination of the transformed loop in order to determine which early exit condition prevailed.


REFERENCES:
patent: 4755966 (1988-07-01), Lee et al.
patent: 5471593 (1995-11-01), Branigin
patent: 5787013 (1998-07-01), Yui
patent: 5898865 (1999-04-01), Mahalingaiah
patent: 5901308 (1999-05-01), Cohn et al.
patent: 6141732 (2000-10-01), Adams
patent: 6178499 (2001-01-01), Stotzer et al.
patent: 6230317 (2001-05-01), Wu
patent: 6286135 (2001-09-01), Santhanam
Advanced Compiler Design & Implementation, Steven S. Muchnick, Chapters 17-20 , published Aug. 19, 1997.*
Compilers Principles, Techniques and Tools, Aho et al, Chapters 9-10, published Sep. 12, 1985.*
Tirumalai, P., et al., “Parallelization of Loops with Exits on Pipelined Architectures”,Supercomputing Conference, Sponsored by IEEE Computer Society, 200-212, (Dec. 1990).

Affiliated with

Also associated with

Rating

Early exit transformations for software pipelining does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Early exit transformations for software pipelining, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Early exit transformations for software pipelining will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3019071