Software pipelining a hyperblock loop

Abstract

An iterative software pipelining method promotes instructions of a program loop to previous loop iterations and then reschedules the instructions until either 1) the resultant schedule is optimal (i.e., the initiation interval is equal to the minimal initiation interval) or 2) the resultant schedule is not an improvement over the previous schedule generated. The method is applicable to a sequence of instructions within a program loop having a single control flow entry and one or more control flow exit points. First, a minimum initiation interval of the program loop is computed. Second, instruction level parallelism transformations are applied on the program loop. Third, a single iteration schedule is determined for the program loop. Fourth, selected instructions are percolated to a prior iteration of the program loop to generate a new instruction order for the program loop. Each of steps two through four is performed as long as a previous length of the program loop exceeds a single iteration schedule length and the single iteration schedule length exceeds the minimum initiation interval.

Claims

What is claimed is:

1. A machine-readable medium having stored thereon sequences of instructions that when executed by a processor cause the processor to:

a) compute a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit;

b) apply instruction level parallelism transformations on the program loop;

c) apply single iteration scheduling on the program loop;

d) percolate selected instructions to a prior iteration of the program loop to generate a new instruction order for the program loop;

e) repeat b) through d) as long as a previous single iteration length of the program loop is greater than or equal to a current single iteration schedule length of the program loop and the current single iteration schedule length exceeds the minimum initiation interval.

2. A machine-readable medium having stored thereon sequences of instructions that when executed by a processor cause the processor to:

a) compute a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit;

b) save the program loop as a recorded program loop;

c) apply instruction level parallelism transformations on the program loop to produce a revised program loop;

d) apply single iteration scheduling on the revised program loop;

e) determine a single iteration schedule length, SL, of the revised program loop;

f) restore the recorded program loop as the revised program loop, if a previous length is not greater than SL;

g) perform the following if the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval:

i) equate the previous length to SL; and

ii) percolate selected instructions of the revised program loop to a prior iteration of the revised program loop;

h) repeat b) through g) as long as the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval;

i) generate a loop prologue for the revised program loop; and

j) generate a loop epilogue for the revised program loop.

3. A machine-readable medium having stored thereon sequences of instructions that when executed cause the processor to:

a) compute a minimum initiation interval of a current loop having a single control flow entry and at least one control flow exit;

b) apply instruction level parallelism transformations on the current loop to generate a transformed loop, wherein the current loop becomes a previous loop and the transformed loop becomes the current loop;

c) apply single iteration scheduling on the current loop;

d) percolate selected instructions of the current loop to a prior iteration of the current loop to generate a new instruction order for the current loop; and

e) repeat b) through d) as long as a previous loop single iteration schedule length is greater than or equal to a current loop single iteration schedule length and the current loop single iteration schedule length exceeds the minimum iteration interval.

4. The machine-readable medium of claim 3 further comprising sequences of instructions that when executed cause the processor to:

f) select the previous loop as the current loop, if the current loop single iteration schedule length exceeds the previous loop single iteration schedule length.

5. The machine-readable medium of claim 3 further comprising sequences of instructions that when executed cause the processor to:

g) generate a current loop prologue; and

h) generate a current loop epilogue.

6. The machine-readable medium of claim 3 wherein the instruction level parallelism transformations include constant combining.

7. The machine-readable medium of claim 3 wherein the instruction level parallelism transformations include operation combining.

8. The machine-readable medium of claim 3 wherein the instruction level parallelism transformations include software based register renaming.

9. The machine-readable medium of claim 3 wherein the instruction level parallelism transformations include an LHS/RHS transformation.

10. An apparatus comprising:

a) means for computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit;

b) means for applying instruction level parallelism transformations on the program loop;

c) means for applying single iteration scheduling on the program loop;

d) means for percolating selected instructions to a prior iteration of the program loop to generate a new instruction order for the program loop;

e) means for repeating b) through d) as long as a previous single iteration length of the program loop is greater than or equal to a current single iteration schedule length of the program loop and the current single iteration schedule length exceeds the minimum initiation interval.

11. An apparatus comprising:

a) means for computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit;

b) means for saving the program loop as a recorded program loop;

c) means for applying instruction level parallelism transformations on the program loop to produce a revised program loop;

d) means for applying single iteration scheduling on the revised program loop;

e) means for determining a single iteration schedule length, SL, of the revised program loop;

f) means for restoring the recorded program loop as the revised program loop, if a previous length is not greater than SL;

g) means for performing the following if the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval:

i) equating the previous length to SL; and

ii) percolating selected instructions of the revised program loop to a prior iteration of the revised program loop;

h) means for repeating b) through g) as long as the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval;

i) generate a loop prologue for the revised program loop; and

j) generate a loop epilogue for the revised program loop.

12. An apparatus comprising:

a) means for computing a minimum initiation interval of a current loop having a single control flow entry and at least one control flow exit;

b) means for applying instruction level parallelism transformations on the current loop to generate a transformed loop, wherein the current loop becomes a previous loop and the transformed loop becomes the current loop;

c) means for applying single iteration scheduling on the current loop;

d) means for percolating selected instructions of the current loop to a prior iteration of the current loop to generate a new instruction order for the current loop; and

e) means for repeating b) through d) as long as a previous loop single iteration schedule length is greater than or equal to a current loop single iteration schedule length and the current loop single iteration schedule length exceeds the minimum iteration interval.

13. The apparatus of claim 12 further comprising:

f) means for selecting the previous loop as the current loop, if the current loop single iteration schedule length exceeds the previous loop single iteration schedule length.

14. The apparatus of claim 12 further comprising:

g) means for generating a current loop prologue; and

h) means for generating a current loop epilogue.

15. The apparatus of claim 12 wherein the instruction level parallelism transformations include constant combining.

16. The apparatus of claim 12 wherein the instruction level parallelism transformations include operation combining.

17. The apparatus of claim 12 wherein the instruction level parallelism transformations include software based register renaming.

18. The apparatus of claim 12 wherein the instruction level parallelism transformations include an LHS/RHS transformation.

19. A system comprising:

a memory to store a sequence of instructions;

a processor coupled to the memory, the processor scheduling the sequence of instructions within a loop by

a) computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit;

b) applying instruction level parallelism transformations on the program loop;

c) applying single iteration scheduling on the program loop;

d) percolating selected instructions to a prior iteration of the program loop to generate a new instruction order for the program loop;

e) repeating b) through d) as long as a previous single iteration length of the program loop is greater than or equal to a current single iteration schedule length of the program loop and the current single iteration schedule length exceeds the minimum initiation interval.

20. A system comprising:

a memory to store a sequence of instructions;

a processor coupled to the memory, the processor scheduling the sequence of instructions within a loop by

a) computing a minimum initiation interval of a program loop having a single control flow entry and at least one control flow exit;

b) saving the program loop as a recorded program loop;

c) applying instruction level parallelism transformations on the program loop to produce a revised program loop;

d) applying single iteration scheduling on the revised program loop;

e) determining a single iteration schedule length, SL, of the revised program loop;

f) restoring the recorded program loop as the revised program loop, if a previous length is not greater than SL;

g) performing the following if the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval:

i) equating the previous length to SL; and

ii) percolating selected instructions of the revised program loop to a prior iteration of the revised program loop;

h) repeating b) through g) as long as the previous length is greater than or equal to SL and SL is greater than the minimum initiation interval;

i) generating a loop prologue for the revised program loop; and

j) generating a loop epilogue for the revised program loop.

21. A system comprising:

a memory to store a sequence of instructions;

a processor coupled to the memory, the processor scheduling the sequence of instructions within a loop by

a) computing a minimum initiation interval of a current loop having a single control flow entry and at least one control flow exit;

b) applying instruction level parallelism transformations on the current loop to generate a transformed loop, wherein the current loop becomes a previous loop and the transformed loop becomes the current loop;

c) applying single iteration scheduling on the current loop;

d) percolating selected instructions of the current loop to a prior iteration of the current loop to generate a new instruction order for the current loop; and

e) repeating b) through d) as long as a previous loop single iteration schedule length is greater than or equal to a current loop single iteration schedule length and the current loop single iteration schedule length exceeds the minimum iteration interval.

22. The system of claim 21 wherein the processor further schedules the sequence of instructions by selecting the previous loop as the current loop, if the current loop single iteration schedule length exceeds the previous loop single iteration schedule length.

23. The system of claim 21 wherein the processor further schedules the sequence of instructions by:

g) generating a current loop prologue; and

h) generating a current loop epilogue.

24. The system of claim 21 wherein the instruction level parallelism transformations include constant combining.

25. The system of claim 21 wherein the instruction level parallelism transformations include operation combining.

26. The system of claim 21 wherein the instruction level parallelism transformations include software based register renaming.

27. The system of claim 21 wherein the instruction level parallelism transformations include an LHS/RHS transformation.

Description

FIELD OF THE INVENTION

This invention relates to software pipelining of instructions for subsequent execution on a processor. In particular, this invention relates to software pipelining of a sequence of instructions that has a single control flow entry and one or more control flow exits.

BACKGROUND OF THE INVENTION

A number of hardware and software techniques may be used to improve the execution speed of a software program. The time required to execute the program is dependent upon a number of factors including the number of instructions required to execute the program, the average number of processor cycles required to execute an instruction, and the processor cycle time.

Software scheduling of instructions can be used to enhance the program execution rate. This may be accomplished by using software to reorder the instructions so that they can be executed more efficiently. In other words, software scheduling helps to select the order of a sequence of instructions so that they execute correctly in a minimum amount of time within the constraints of the processor resource limitations.

One prior art software scheduling technique is known as basic block scheduling. Typically the program instructions are divided into code or instruction sequences called basic blocks. A program may consist of any number of basic blocks. A basic block has the property that if any instruction in the block is executed, then all other instructions within the basic block are executed. Thus, only the first instruction in the basic block can be a branch target or entry point. Similarly, only the last instruction in the basic block can be a branch instruction. This ensures that if any instruction in the code sequence is executed, then all instructions within the code sequence are executed. The technique of scheduling instructions or reordering the instructions within a basic block for optimal execution efficiency is called block scheduling.

The prior art technique of block scheduling suffers from the disadvantage that code optimization for each basic block may not result in overall optimal code. Basic block scheduling does not permit instructions to be moved across block boundaries such as branches. Thus although the execution time of each block may be nearly optimal, the overall program execution speed may not be optimal because the processor must hesitate at each branch (i.e., a basic block boundary) until all instructions preceding and including the branch are in execution.

Another class of prior art software scheduling techniques is specifically designed to improved the execution speed of program loops. A program loop is a sequence of instructions in which the last instruction is a branch instruction that may branch to the first instruction in the sequence under certain conditions. Thus the program loop might execute iteratively until some certain condition is met. Software pipelining is a technique used to improve processor throughput of a program loop.

Software pipelining effectively hides instruction latencies in a pipelined processor by overlapping the execution of different loop iterations of a loop structure in the program code. In other words, before one loop iteration completes, execution of successive iterations of the loop is initiated. The initiation interval is the number of processor cycles between the initiation of a given iteration and the initiation of the next iteration.

One disadvantage of prior art software pipelining techniques is that they are effective only for simple loop structures. In particular, some prior art software scheduling techniques are applicable only to a simple loop structure consisting of one basic block. Thus some prior art software pipelining methods are unable to handle more complicated loop structures such as nested loop structures or loops having more than one basic block.

Another disadvantage of some prior art software pipelining methods is that they only work for special hardware or for a narrow class of program loops.

What is needed is a software scheduling technique such as a software pipelining that is applicable to a broader class of instruction sequences including instruction sequences having one or more basic blocks. In particular, a method of software pipelining a sequence of instructions that have a single control flow entry and one or more control flow exits (i.e., a hyperblock program loop) is needed.

SUMMARY AND OBJECTS OF THE INVENTION

An iterative software pipelining method promotes instructions of a program loop to previous loop iterations and then reschedules the instructions until either 1) the resultant schedule is optimal (i.e., the initiation interval is equal to the minimal initiation interval) or 2) the resultant schedule is not an improvement over the previous schedule generated. The method is applicable to a sequence of instructions within a program loop having a single control flow entry and one or more control flow exit points (i.e., a hyperblock loop).

First, a minimum initiation interval of the program loop is computed. Second, instruction level parallelism transformations are applied on the program loop. Third, a single iteration schedule is determined for the program loop. Fourth, selected instructions are percolated to a prior iteration of the program loop to generate a new instruction order for the program loop. Each of steps two through four is performed as long as a previous length of the program loop exceeds a single iteration schedule length and the single iteration schedule length exceeds the minimum initiation interval.

Other features and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows below.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is illustrated by way of example and not limitation in the figures of the accompanying drawings, in which like references indicate similar elements and in which:

FIG. 1 contrasts instruction handling by a processor with and without hardware pipelining.

FIG. 2 contrasts scheduling for a minimum iteration time with scheduling for a minimum iteration interval.

FIG. 3 illustrates a flowchart for one embodiment of the software pipelining method.

DETAILED DESCRIPTION

Hardware pipelining and software pipelining are different approaches to improving the execution performance of a processor with respect to a sequence of instructions. Although similarly named, software pipelining uses software to reorder the sequence of instructions within a program loop in order that the next iteration of the program loop can be executed as soon as possible.

Processor performance can generally be increased by hardware pipelining of the instructions to be executed. Instruction execution generally requires 1) fetching the instruction; 2) decoding the instruction and assembling operands; and 3) executing the instruction and writing the results. To pipeline instruction execution, the various steps of instruction execution are performed by independent units called pipeline stages. The steps of different instructions are executed independently in different pipeline stages. Thus while one instruction can be fetched while another instruction is being decoded. The result of each pipeline stage is communicated to the next pipeline stage. Hardware pipelining does not reduce the total amount of time to execute a given instruction. Hardware pipelining is able to improve processor performance by reducing the average number of processor cycles required to process an instruction (i.e., pipelining increases processor performance by increasing the number of instructions handled at one time).

For example, consider a scalar processor. A scalar processor only executes one instruction at a time. Although some instructions may take more than one cycle to complete, the use of hardware pipelining in a scalar processor may theoretically be able to achieve an average execution rate of one instruction per machine cycle (e.g., in a Reduced Instruction Set Computer (i.e., RISC) architecture). Hardware pipelining permits concurrent execution of instructions in different pipeline stages to achieve this result. Alternatively, a superscalar processor is able to reduce the average number of cycles per instruction by permitting concurrent execution of instructions in the same pipeline stage as well as concurrent execution of instructions in different pipeline stages.

Thus hardware pipelining focuses on improving the processor while software pipelining focuses on optimizing a given application to be executed on the processor. Therefore software pipelining techniques can typically be use to help improve the performance of hardware pipelined processors regardless of whether such processors are scalar or superscalar processors and regardless of the processor architecture (e.g., RISC, Complex Instruction Set Computer (CISC), Very Long Instruction Word (VLIW) computer, etc.)

FIG. 1 illustrates timing guidelines which contrast instruction handling for a scalar processor without hardware pipelining (110) and a scalar processor with hardware pipelining (120). From timing diagram 110, if the scalar processor without hardware pipelining is working on instruction n, the processor cannot handle the next instruction until instruction n is executed. Thus the time required to fetch, decode, and execute a subsequent instruction must be stacked end-to-end on the time required to fetch, decode, and execute the nth instruction.

The scalar processor with hardware pipelining (120) can handle more than one instruction. In a three stage pipeline, this permits the fetching of instruction n+1 while instruction n is decoding. While the third stage of the pipeline is executing instruction n, the second stage of the pipeline can be decoding instruction n+1, and the first stage of the pipeline can be fetching instruction n+2. In the example provided in FIG. 1, the scalar pipelined processor has completed execution of instruction n+3 at time 112 while the scalar processor without hardware pipelining is only beginning to process instruction n+2. Thus instruction latencies are effectively "hidden" or reduced by overlapping the fetching, decoding, and execution steps of different instructions.

Software pipelining helps to hide instruction latencies in a pipelined processor by overlapping the execution of different loop iterations of a loop structure in the program code. In other words, before one loop iteration completes, execution of successive iterations of the loop is initiated. The initiation interval is the number of processor cycles between the initiation of a given iteration and the initiation of the next iteration. Software pipelining seeks to minimize the initiation interval in order to accelerate the overall execution of the program loop. Software pipelining achieves this by reordering the instructions within the program loop.

Block scheduling of a program loop attempts to minimize the execution time of a single iteration of the program loop. Theoretically, this might seem to produce minimum execution time for the program loop. Theoretically, because of the repetitive nature of the program loop structure, small performance improvements in each execution of the loop an be aggregated into greater performance gains. In other words, the mall performance gain is reaped for each iteration of the loop. In practice, however, such scheduling does not account for latencies or delays incurred between the initiation of subsequent iterations of the program loop (i.e., the initiation interval). For example, in order to minimize the single iteration execution time of a program loop containing a single basic block, resources needed for a subsequent iteration of such a program loop might be assigned by the software scheduler. This tends to increase the initiation interval between program loop iterations and therefore results in increased execution time for the program loop. Thus basic block scheduling tends to be in conflict with the goals of minimizing the initiation interval of a program loop.

FIG. 2 contrasts the processor throughput for a program loop that has been optimized with block scheduling (210) and with software pipelining (220). The block scheduler minimizes the single iteration length of the program loop. Thus the single iteration length, 214, of the block scheduled program loop is less than the single iteration length, 224, of the software pipelined program loop. The n+1 iteration of the block scheduled program loop cannot begin until iteration n is complete so that the time required to complete each iteration must be stacked end-to-end. The minimum initiation interval, 212, in the block scheduled code is greater than the minimum initiation interval, 222, in the software pipelined code. Thus iteration n+1 of the software pipelined program loop can begin before iteration n has completed so that the single iteration length, 224, is overlapped on each iteration. This results in a reduced total execution time for the program loop as illustrated by .DELTA.t, 216.

Consider the following instruction sequence for software pipelining:

    ______________________________________
    L10:
    r1 <- memory[r0];
                     cycle 1 (3 cycle load latency)
    r2 <- r2 + r1;   cycle 3 (floating point add
                             latency of 3 cycles)
    r0 <- r0 + 8;    cycle 2
    branch to L10 if (r0 < r3);
                     cycle 3
    ______________________________________

    ______________________________________
    L10:
    r2 <- r2 + r1;         cycle 1 I1
    r0 <- r0 + 8;          cycle 1 I1
    r1 <- memory[r0];      cycle 2 I2
    branch to L10 if (r0 < r3);
                           cycle 2
    ______________________________________

    ______________________________________
    L10:
    r2 <- r2 + r1;         cycle 1 I1
    r0 <- r0 + 8;          cycle 1 I1
    r1 <- memory[r0];      cycle 2 I2
    branch to L10 if (r0 < r3);
                           cycle 2
    ______________________________________

    ______________________________________
    L10:
    r2 <- r2 + r1;           cycle 1
    r1 <- memory[r0 + 8];    cycle 1
    r0 <- r0 + 8;            cycle 1
    branch to L10 if (r0 < r3);
                             cycle 2
    ______________________________________

    ______________________________________
             r0 <- memory[r1];
             if (r2)
             r0 <- memory[r3];
             r1 <- memory[r0];
    ______________________________________

    ______________________________________
               r0 <- memory [r1];
               r0 <- memory[r3];
               if (r2);
               r1 <- memory[r0];
    ______________________________________

    ______________________________________
               r0 <- memory [r1];
               r4 <- memory[r3];
               if (r2)
               r0 <- r4;
               r1 <- memory[r0];
    ______________________________________

    ______________________________________
    APPENDIX I
    ______________________________________
    A "pseudo-C" representation of the software for computer
    implementation of the software pipelining algorithm is presented below.
    Calculate MII;  (Minimum Initiation Interval)
    prior.sub.-- length = INFINITY;
                    (Length of previous schedule)
    do {
    L' = L;         (Record original state of loop L)
    Apply ILP-Transformations on loop L;
    Apply Single-Iteration Scheduling on loop L;
    SL = length of the single iteration schedule;
    if (prior length <= SL) {
    L=L';
    continue = FALSE;
    else if ((prior.sub.-- length > SL) and (SL > MII)) {
    prior.sub.-- length = SL;
    continue = TRUE;
    Apply Select-Instructions-To-Be-Percolated(L);
    Apply Percolate-Instructions(L);
    } else {
    continue = FALSE;
    }
    } while (continue)
    Generate loop prologue and epilogue;
    ______________________________________


______________________________________
    APPENDIX II
    ______________________________________
    The following "pseudo C" code offers one approach to software
    based register renaming to help remove antidependencies and
    output dependencies.
    for (each antidependency and output dependence arc A) {
    let p1 = A.src;
    let p2 = A.dst;
    if ((p2 is not flow dependent on any instruction) and
    (p2 is critical) and
    (p2.destination is live only within current loop
    iteration) and
    (there is a register available for renaming)) {
    rename p2.destinatidn;
    apply copy propagation to all uses of old
    p2.destination;
    }
    ______________________________________

    ______________________________________
    APPENDIX III
    ______________________________________
    The following "pseudo-C" code is provided as an example for
    implementing the LHS/RHS transformation.
    for (each antidependency and output dependent arc A) {
    let p1 = A.src;
    let p2 = A.dst;
    if (p1 is not a branch)
    continue;
    if p2.destination is not in LIVE.sub.-- OUT(p1))
    continue;
    if ((p2 is not flow dependent on any instruction in the same
    basic block as where p2 resides) and
    (p2 is critical) and
    (p2.destination is live only within current loop
    iteration) and
    (there is a register for renaming)) {
    rename p2.destination;
    apply copy propagation to all uses of old
    p2.destination;
    }
    ______________________________________

• Inventors
  Chang, Pohua;
• Assignee
  Intel Corporation (Santa Clara, CA)
• Published
  Jan-18-2000
• Current US Classes:
  712/241
  717/142
  717/150
  717/160
• Application #
  212549
• International Classes
  G06F 009/45; G06F 009/44
• Field of Search
  395/705 395/706 395/707 395/709 712/216 712/219 712/241
• Examiner
  Hafiz; Tariq R.
• Agent
  Blakely, Sokoloff, Taylor & Zafman LLP
• US Patent References:
  5265253
  5303357
  5317743
  5367651
  5375238
  5386562
  5920724