Data speculation within modulo scheduled loops

Details Data speculation within modulo scheduled loops Data speculation within modulo scheduled loops

2000-05-09

2004-12-14

Ingberg, Todd (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C712S241000

Reexamination Certificate

active

06832370

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to an apparatus and method for using a compiler in a computer system to perform data speculation within modulo scheduled loops.
BACKGROUND OF THE INVENTION
In software program compilers, it is desirable to increase the efficiency of the compiler. Two different methods of optimizing compiler performance include data speculation and use of a modulo scheduler. However, these methods operate independent of one another and thus do not gain the benefit of combining them. In particular, in the absence of a solution such as the data speculation, the modulo scheduler must make conservative assumptions with respect to memory dependencies, which reduces the efficiency of the scheduled code.
On the other hand, in the absence of modulo scheduling, data speculation within loops must rely upon techniques such as unrolling with acyclic scheduling to exploit instruction-level parallelism (ILP) across iterations. With this technique, however, the unroll factor required to achieve the same amount of overlap as modulo scheduling is difficult to determine. Also, unrolling can have undesirable side effects such excessive code expansion and negative cache performance.
Accordingly, a need exists for an apparatus method to perform data speculation within modulo scheduled loops.
SUMMARY OF THE INVENTION
An apparatus and method consistent with the present invention schedule instructions in a compiler. They include receiving instructions for scheduling along with data speculation code. They also include locating a schedule for specifying an order of execution of the instructions, generating recovery code for the data speculation code, and allocating rotating registers related to the scheduling of the instructions for execution and related to the recovery code. Based upon the locating and allocating, an initiation interval is determined specifying a number of instruction issue cycles between initiation of successive iterations related to the scheduling of the instructions.


REFERENCES:
patent: 5491823 (1996-02-01), Ruttenberg
patent: 5729723 (1998-03-01), Wada et al.
patent: 5764962 (1998-06-01), Buzbee
patent: 5781752 (1998-07-01), Moshovos et al.
patent: 5794029 (1998-08-01), Babaian et al.
patent: 5802337 (1998-09-01), Fielden
patent: 5835776 (1998-11-01), Tirumalai et al.
patent: 5867711 (1999-02-01), Subramanian et al.
patent: 6230317 (2001-05-01), Wu
patent: 6260190 (2001-07-01), Ju
Vinod Kathail, et al., “HPL-PD Architecture Specification: Version 1.1,” Feb. 2000, Hewlett-Packard Co., HPL-93-80 (R.1), pp. 1-58.*
Michael S. Schlansker, et al., “Achieving High Levels of Instruction-Level Parallelism with Reduced Hardware Complexity,” 1994, Hewlett-Packard Co., HPL-96-120, pp. 1-85.*
Mahadevan, Uma, et al., “Applying data speculation in modulo scheduled loops”, Copyright 2000, IEEE, p.p. 169-176, Hewlett-Packard Company.

Affiliated with

Also associated with

Rating

Data speculation within modulo scheduled 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 Data speculation within modulo scheduled loops, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data speculation within modulo scheduled loops will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3274169