Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2000-03-24
2003-12-30
Das, Chameli C. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S150000, C717S141000, C717S151000, C717S160000, C712S215000, C712S241000, C712S244000
Reexamination Certificate
active
06671878
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to compiler software pipelining. More particularly, the present invention relates to enhanced modulo scheduling techniques for software pipelining.
2. The Prior Art
A recent trend in processor design is to build processors with increasing instruction issue capability and many functional units. At the same time the push toward higher clock frequencies has resulted in deeper pipelines and longer instruction latencies. To utilize the resources available in such processors it is important to employ scheduling techniques that can extract sufficient instruction level parallelism (ILP) from programs. Modulo scheduling is a known technique for extracting ILP from inner loops by overlapping the execution of successive iterations.
Modulo scheduling is a well known compiler optimization technique that calculates a theoretical minimum initiation interval (minimum II), which is a measure of the execution time, and then producing an instruction schedule using a modulo reservation table which is II cycles in length. If such a schedule can be determined, it is known to be optimal.
In standard modulo scheduling, if an acceptable schedule cannot be found for a minimum II, the value of II is incremented until a schedule can be found. As chips become faster, with more pipeline stages and higher latencies in terms of cycles, the lack of available registers in the instruction set becomes problematic. Fewer loops can be is scheduled with the minimum II, and the minimum acceptable II increase for those loops that cannot be scheduled with a minimum II. Therefore, it becomes harder and more time consuming for the compiler to find the minimum acceptable II or best practical II, resulting in an increase in compilation time.
BRIEF DESCRIPTION OF THE INVENTION
To overcome these and other shortcomings of the prior art, disclosed herein is an enhanced modulo scheduling technique. Register pressure, or the number of registers required for a given loop schedule, tends to decrease monotonically with increasing II. Hence, it is possible to apply a binary search method to locate the minimal acceptable II in an amount of time which is proportional to the logarithm of the size of the range of attempted IIs, rather than directly proportional to the size of the range itself.
Although the aforementioned monotonically decreasing condition does not necessarily hold for all loops, it nearly always does in practice. When this condition does not hold true, this method will still produce an acceptable schedule, although it may be for an II which is larger than the minimum acceptable II. Usually the same results will be achieved as with the conventional iterative method, i.e. same II provided. However, during compile time, this new method will provide the result in less time.
REFERENCES:
patent: 5361357 (1994-11-01), Kionka
patent: 5491823 (1996-02-01), Ruttenberg
patent: 5664193 (1997-09-01), Tirumalai
patent: 5805895 (1998-09-01), Breternitz, Jr. et al.
patent: 5809308 (1998-09-01), Tirumalai
patent: 5835745 (1998-11-01), Sager et al.
patent: 5835776 (1998-11-01), Tirumalai et al.
patent: 5862384 (1999-01-01), Hirai
patent: 5867711 (1999-02-01), Subramanian et al.
patent: 5930510 (1999-07-01), Beylin et al.
patent: 6341370 (2002-01-01), Tirumalai et al.
patent: 6438682 (2002-08-01), Morris et al.
patent: 6438747 (2002-08-01), Schreiber et al.
patent: 6460173 (2002-10-01), Schreiber
Microsoft Press, Microsoft Press Computer Dictionary, 1994, Microsoft Press, p.43.*
Title: Unrolling-Based Optimizations for Modulo Scheduling, author: Lavery et al, IEEE, 1995.*
Title: Optimum Modulo Schedules for Minimum Register Requirements, author: Eichenberger et al, ACM, 1995.*
Title: Lifetime-Sensitive Modulo Scheduling, author: Huff, ACM, 1993.*
Title: Parallelization of Loops with Exits on Pipelined Architectures, author: Tirumalai et al, IEEE, Nov., 1990.*
Title: Software Pipelining Showdown: Optimal vs. Heuristic Methods in Production Compiler, author: Ruttenberg et al, ACM, 1996.*
Title: Code Generation Schema for Modulo Scheduled Loops, author: Rau et al, IEEE, 1992.
Das Chameli C.
Martine & Penilla LLP
LandOfFree
Modulo scheduling via binary search for minimum acceptable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Modulo scheduling via binary search for minimum acceptable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modulo scheduling via binary search for minimum acceptable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3107464