Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1997-07-11
2001-05-08
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06230317
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention pertains to the field of compiling source code into executable code in computer systems. More particularly, this invention relates to software pipelining of nested loops.
2. Background of the Related Art
Generally, a compiler is a computer program that compiles or translates a computer program written in source code by a programmer into code that can be executed by a processor. Source code typically includes numerous loops, which are sections of code that may be executed more than once in succession. Many computer programs spend the majority of their execution time in loops. Among the many techniques for improving the execution time of computer programs is increasing the amount of instruction level parallelism that can be used by today's advanced processors.
One technique for increasing instruction level parallelism is software pipelining. Software pipelining is a method that restructures loops so that instructions from various iterations of the loop are executed at the same time.
FIG. 1
a
shows a scalar schedule of a simple loop consisting of operations A, B, and C. In the scalar schedule
110
each operation is scheduled to be executed one after the other. In the example shown in
FIG. 1
a
each operation is assumed to require one cycle to execute. The operations A, B, and C from the first iteration are labeled A
1
, B
1
, and C
1
, the operations from the second iteration of the loop are labeled A
2
, B
2
, and C
2
, etc.
FIG. 1
a
shows that the scalar schedule
110
requires fifteen cycles to complete.
FIG. 1
b
shows a software pipeline schedule of the same simple loop described in connection with
FIG. 1
a
, above. In the software pipeline schedule
120
, operations from different iterations of the loop are scheduled to be executed during the same cycle. In this example, the software pipeline schedule
120
requires 7 cycles to execute. Thus, a large improvement in execution time is achieved in this example by software pipelining the loop.
Computer programs typically do not consist of only a single loop, or multiple loops at the same level within a hierarchy. Rather, computer programs can include loops within loops (also referred to as nested loops) such that there are loops at numerous levels within a hierarchy. Typical processors/compilers allocate a single storage area for each function or procedure in the executable code regardless of whether that function or procedure contains nested loops.
FIG. 2
a
illustrates an example of nested loops (an outer loop
210
and an inner loop
215
) within a procedure or function written in source code that will be compiled to execute using a single storage area
220
. Since a single storage area is allocated, if two or more software pipelined loops from different levels in a loop hierarchy, for example the inner loop
215
and the outer loop
210
, are allowed to be active at a given moment in time, the execution of instructions included in the inner loop could overwrite storage locations used for execution of instructions included in the outer loop. As a result, prior methods for software pipelining are not able to pipeline nested loops efficiently, but typically pipeline the innermost loop(s) (i.e., the loop(s) at the lowest level of the hierarchy) and schedule the outer loops in a scalar fashion.
Computer programs spend significant execution time in other than the innermost loops, and as a result, pipelining only the innermost loops limits the amount of execution time improvement that can be achieved through prior software pipelining techniques. Therefore, a method for software pipelining nested loops is desirable.
SUMMARY OF THE INVENTION
A method and apparatus for executing software pipelined executable code generated by compiling code having an inner loop and an outer loop is disclosed. Instructions are executed that perform the operations specified in the outer loop portion of the code using a first storage area. A second storage area is allocated for use when performing the operations specified in the inner loop. Instructions are then executed that perform the operations specified in the inner loop using the second storage area, wherein at least certain storage locations in the first storage area are not alterable while the operations specified in the inner loop are being performed.
REFERENCES:
patent: 3787673 (1974-01-01), Watson et al.
patent: 4858115 (1989-08-01), Rusterholz et al.
patent: 5119495 (1992-06-01), King
patent: 5450588 (1995-09-01), Hoxey
patent: 5485629 (1996-01-01), Dulong
patent: 5657485 (1997-08-01), Streitenberger et al.
patent: 5710913 (1998-01-01), Gupta et al.
patent: 5794029 (1998-08-01), Babain et al.
patent: 5797013 (1998-08-01), Mahadevan et al.
patent: 5802375 (1998-09-01), Ngo et al.
patent: 5842022 (1998-11-01), Nakahira et al.
patent: 5881277 (1999-03-01), Bondi et al.
patent: 6088525 (2000-07-01), Peri
Title: A loop transformation algorithm for communication overlapping International journal for paralle.*
“Optimal software pipelining of nested loops” by Ramanujam, published by IEEE, 1994.*
“Parallelization of Loops with Exits on Pipelined Architecture”, by Tirumalai et al, published at IEEE, 1994.*
“Register Allocation for Modulo Scheduled Loops Strategies, Algorithms and Heuristics”, by Tirumalai et al, published at ACM Slgplan, 1992.*
Compilers Principles, Technniques, and Tools, by Aho et al, 1988.
Blakely, Sokloff, Taylor & Zafman LLP
Das Chameli Chaudhuri
Intel Corporation
Powell Mark R.
LandOfFree
Method and apparatus for software pipelining of nested loops does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for software pipelining of nested loops, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for software pipelining of nested loops will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2447062