Mechanism for software pipelining loop nests

Abstract

A method is provided for processing nested loops that include a modulo-scheduled inner loop within an outer loop. The nested loop is scheduled to execute the epilog stage of the inner loop for a given iteration of the outer loop with the prolog stage of the inner loop for the next iteration of the outer loop. For one embodiment of the invention, this is accomplished by initializing an epilog counter for the inner loop to a value that bypasses draining the software pipeline. This causes the processor to exit the inner loop before it begins draining the inner loop pipeline. The inner loop pipeline is drained during the next iteration of the outer loop, while the inner loop pipeline fills for the next iteration of the outer loop.

Claims

What is claimed is:

1. A method, comprising:

iterating an inner loop of a nested loop in a no-drain mode;

determining if a final iteration of an outer loop of the nested loop has been reached; and

iterating the inner loop in a drain mode if the final iteration of the outer loop is reached.

2. The method of claim 1, wherein iterating an inner loop in a no-drain mode comprises bypassing pipeline draining operations associated with an epilog phase of the inner loop during a current iteration of the outer loop.

3. The method of claim 2, wherein bypassing pipeline draining operations comprises:

initializing a stage counter to a fall through value; and

executing the inner loop.

4. The method of claim 1, wherein iterating the inner loop in drain mode comprises executing the inner loop through all pipeline draining operations of its epilog phase.

5. The method of claim 4, wherein executing the inner loop through all pipeline-draining operations comprises:

initializing a stage counter to reflect all stages of the inner loop; and

executing the inner loop.

6. The method of claim 1, wherein the inner loop includes one or more additional inner loops.

7. The method of claim 1, wherein executing the inner loop of the nested loop in no-drain mode comprises executing the inner loop to an inner loop epilog stage that transfers data between the inner and outer loops.

8. The method of claim 1, wherein determining if a final iteration of an outer loop of the nested loop has been reached further comprises determining if the beginning of the final iteration of the outer loop of the nested loop has been reached.

9. A method for processing an outer loop that includes a software pipelined inner loop, the method comprising:

executing the inner loop until an epilog phase of the inner loop is reached for each of a first N-1 iterations of the outer loop;

completing the epilog phase of the inner loop for each of the first N-1 outer loop iterations in a subsequent iteration of the outer loop; and

executing the inner loop through the epilog phase for an N.sup.th iteration of the outer loop.

10. The method of claim 9, wherein executing the inner loop until an epilog phase is reached comprises:

initializing the inner loop to bypass selected stages of its epilog phase for the first N-1 iterations of the outer loop; and

executing the inner loop.

11. The method of claim 10, wherein the bypassed stages of the inner loop epilog stage are determined by which stages of the inner loop consume live-in values or generate live-out values.

12. The method of claim 11, wherein initializing the inner loop to bypass selected stages of its epilog phase comprises initializing a counter associated with the inner loop to indicate a number of stages of the inner loop to be drained.

13. The method of claim 9, wherein executing the inner loop through the epilog phase comprises:

initializing the inner loop to execute all pipeline-draining operations of its epilog phase; and

executing the inner loop.

14. A nested loop comprising:

an outer loop having N iterations; and

a software pipelined inner loop, the software pipelined inner loop to be executed in a no-drain mode for each of N-1 iterations of the outer loop and in a drain mode for an N.sup.th iteration of the outer loop.

15. The nested loop of claim 14, wherein the software pipelined inner loop executed in no-drain is executed up to its epilog phase during a current iteration of the outer loop and the epilog phase is executed during a subsequent iteration of the outer loop.

16. The nested loop of claim 15, wherein the software pipelined inner loop is a modulo-scheduled inner counted or while-type loop and the outer loop is a counted or while-type loop.

17. The nested loop of claim 14, wherein the software pipeline executed in drain mode is executed through its epilog phase during the N.sup.th iteration of the outer loop.

18. A machine readable medium on which are stored instructions to be executed by a processor to implement a method for processing a nested loop, the method comprising:

iterating an outer loop of the nested loop N times;

for a first N-1 iterations of the outer loop, executing an inner loop in a no-drain mode; and

for a final iteration of the outer loop, executing the inner loop in a drain mode.

19. The machine readable medium of claim 18, wherein executing an inner loop in the no-drain mode comprises:

executing the inner loop for a given iteration of the outer loop until an epilog phase of the inner loop is reached; and

executing the epilog phase of the inner loop in a subsequent iteration of the outer loop.

20. The machine readable medium of claim 18, wherein executing the inner loop in no drain mode comprises executing a prolog phase of the inner loop for the current iteration of the outer loop concurrently with an epilog phase of the inner loop for a preceding iteration of the outer loop.

21. The machine readable medium of claim 18, wherein executing the inner loop in drain mode comprises executing the inner loop through its epilog phase for the current iteration of the outer loop.

22. The machine readable medium of claim 18, wherein executing an inner loop in a no-drain mode comprises executing the inner loop to an inner loop epilog stage that transfers data between the inner and outer loops.

23. A method for software pipelining a nested loop comprising:

modulo-scheduling an inner loop of the nested loop, the modulo-scheduled inner loop having an epilog parameter;

initializing the modulo-scheduled inner loop to execute with a first value of the epilog parameter for a first N-1 iterations of an outer loop of the nested loop; and

initializing the modulo-scheduled inner loop to execute with a second value of the epilog parameter for an N.sup.th iteration of the outer loop.

24. The method of claim 23, wherein initializing modulo-scheduled inner loop to execute with a first value of the epilog parameter comprises setting the epilog parameter to bypass a portion of an epilog phase of the inner loop.

25. The method of claim 23, wherein initializing the modulo-scheduled inner loop to execute with a second value of the epilog parameter comprises setting the epilog parameter to execute all phases of the inner loop during the N.sup.th iteration of the outer loop.

26. A computer system comprising:

a processor to execute instructions; and

a memory in which are stored instructions executable by the processor to implement a method for processing a nested loop, the method comprising:

executing an inner loop of the nested loop until an epilog phase of the inner loop is reached for each of N-1 iterations of an outer loop of the nested loop;

executing the epilog phase of the inner loop for each of the N-1 outer loop iterations in a subsequent iteration of the outer loop; and

executing the inner loop through the epilog phase for an N.sup.th iteration of the outer loop.

27. The computer system of claim 26, wherein executing the inner loop until an epilog phase is reached comprises bypassing pipeline draining operations for the inner loop.

28. The computer system of claim 27, wherein executing the epilog phase of the inner loop comprises executing the bypassed pipeline draining operations for an inner loop associated with a prior iteration of the outer loop while executing a prolog phase for an inner loop associated with a current iteration of the outer loop.

29. A method for processing an outer loop that includes a software pipelined inner loop, the method comprising:

executing the inner loop until an epilog phase of the inner loop is reached for each of a first N-1 iterations of the outer loop;

completing the epilog phase of the inner loop for each of the first N-1 outer loop iterations in a subsequent iteration of the outer loop; and

executing the inner loop through the epilog phase for an N.sup.th iteration of the outer loop;

wherein executing the inner loop until an epilog phase is reached further comprises:

initializing the inner loop to bypass selected

stages of its epilog phase for the first N-1

iterations of the outer loop; and

executing the inner loop; and

wherein initializing the inner loop to bypass selected stages of its epilog phase comprises initializing a counter associated with the inner loop to indicate a number of stages of the inner loop to be drained.

Description

BACKGROUND OF THE INVENTION

1. Technical Field

The present invention relates to mechanisms for optimizing computer code, and in particular, to mechanisms for improving the performance of software pipelined loops.

2. Background Art

Software pipelining is a method for scheduling non-dependent instructions from different logical iterations of a program loop to execute concurrently. Overlapping instructions from different logical iterations of the loop increases the amount of instruction level parallelism (ILP) in the program code. Code having high levels of ILP uses the execution resources available on modern, superscalar processors more effectively.

A loop is software pipelined by organizing the instructions of the loop body into stages of one or more instructions each. These stages form a software pipeline having a pipeline depth equal to the number of stages (the "stage count" or "SC") of the loop body. The instructions for a given loop iteration enter the software pipeline stage by stage, on successive initiation intervals (II), and new loop iterations begin on successive initiation intervals until all iterations of the loop have been started. Each loop iteration is thus processed in stages through the software pipeline in much the same way that an instruction is processed in stages through a processor pipeline. When the software pipeline is full, stages from SC sequential loop iterations are in process concurrently, and one loop iteration completes every initiation interval. Various methods for software pipelining loops are discussed, for example, in B.R. Rau, M.S. Schlansker, P.P. Tirumalai, Code Generation Schema for Modulo Scheduled Loops IEEE MICRO Conference 1992 (Portland, Oregon).

FIG. 1A is a schematic representation of a software pipeline as it processes an exemplary loop through 100 iterations (trip count=100). The instructions of the loop are organized into five stages, labeled A through E (SC=5), and each stage is indexed by the logical iteration to which it corresponds. For example, A(1) is the first iteration of the loop body instruction(s) in stage A, and D(98) is the 98.sup.th iteration of the loop body instruction(s) in stage D. The software pipeline fills during a prolog phase 120, as stages from the first iterations of the loop begin on successive initiation intervals, II(1)-II(4). The software pipeline is full during a kernel phase 130 from II(5) through II(100), and it empties during an epilog phase 140, as the last four iterations complete during II(101)-II(104).

In practice, the different stages of the loop body do not physically traverse a pipeline, as indicated in FIG. 1A. For example, a software pipelined loop that is implemented through predication provides all stages of the loop on each initiation interval. The pipeline filling/emptying behavior is effected by predicates associated with the stages ("stage predicates").

FIG. 1B represents the software pipeline of FIG. 1A in compact, predicated form. Here, stages A through E are associated with predicates p1 through p5, respectively. Setting the predicates p1 through p5 true on successive initiation intervals activates the associated stages and replicates the pipeline filling behavior of prolog phase 120. Similarly, setting predicates p1 through p5 false on successive initiation intervals, deactivates the associated stages and replicates the pipeline emptying behavior of epilog phase 140. During kernel phase 130, all predicates are true, and an instruction stage from each of five sequential loop iterations is active.

Predication thus simplifies the scheduling issues associated with software pipelined loops. All stages of the software pipeline are present in each initiation interval. Only instructions in those stages that are activated by their associated stage predicates update the architectural state of the processor ("processor state") when they retire. Instructions in stages that are deactivated by their associated stage predicates are treated as no-operations (NOPs), and any results they generate do not update the processor state.

The dynamics of a software pipelined loop depend, in part, on the relative sizes of its trip count (TC) and its stage count (SC). A kernel phase, in which a new iteration begins and one iteration ends on each iteration interval, is present only for loops in which the trip count is greater than the stage count. For loops having relatively short trip counts, e.g. those in which the number of iterations is less than SC, the software pipeline never fills because there are more stages than there are loop iterations to fill the stages. Consequently, a short trip count loop does not have a kernel phase.

Independent of the number of iterations and stages, prolog and epilog phases 120, 140, respectively, represent overhead associated with filling and emptying the software pipelined loop. The empty stages in FIG. 1A during prolog and epilog phases 120 and 140, respectively, or the deactivated stages in FIG. 1B, represent unused processor resources. These unused resources can lead to significant efficiency losses when the software pipelined loop is nested within an outer loop, because the overhead is incurred on each iteration of the outer loop.

FIG. 1C represents a nested loop 170 that includes the software pipelined loop of FIG. 1A within a counted outer loop. FIG. 1D represents a nested loop 180 that includes a short trip count loop within a counted outer loop. In both cases, overhead associated with inner loop prolog and epilog phases 120 and 140, respectively, is incurred on each iteration of the outer loop. Between each iteration of the inner loop, the outer loop implements any other instructions in its loop body, including those necessary to set up the inner loop for execution.

The present invention addresses these and other inefficiencies related to implementing nested loops using software pipelining techniques.

SUMMARY OF THE INVENTION

The present invention supports efficient processing of nested loops that include a software pipelined inner loop within an outer loop. The inner loop is executed without draining its software pipeline until the final iteration of the outer loop is reached. This eliminates the overhead associated with prolog and epilog stages of the inner loop for all but the first and last iterations, respectively, of the outer loop.

In accordance with the present invention, the software pipelined inner loop of the nested loop is executed in a "no-drain" mode for the first N-1 iterations of an N-iteration outer loop. For the last iteration of the outer loop, the software pipelined inner loop is executed in a "drain" mode.

For one embodiment of the present invention, no-drain mode is established by initializing an epilog counter for the inner loop to a first value for the first N-1 iterations of the outer loop. When the final iteration of the outer loop is detected, the epilog counter for the inner loop is set to a second value. The first value indicates that the pipeline should not be drained. The second value indicates the actual number of stages in the software pipelined inner loop to be drained. For other embodiments, the values written to the epilog counter for the drain and no-drain modes may be adjusted to account for instruction dependencies between the inner and outer loops.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention may be understood with reference to the following drawings, in which like elements are indicated by like numbers. These drawings are provided to illustrate selected embodiments of the present invention and are not intended to limit the scope of the invention.

FIG. 1A represents the prolog, kernel, and epilog phases of a software pipelined loop.

FIG. 1B represents a predicated implementation of the software pipelined loop of FIG. 1A.

FIG. 1C represents a nested loop that has been implemented using conventional software pipelining methods.

FIG. 1D represents a short trip count nested loop that has been implemented using conventional software pipelining methods.

FIG. 2A represents a nested loop that has been implemented in accordance with the present invention.

FIG. 2B represents a short trip count nested loop that has been implemented in accordance with the present invention.

FIG. 3 is a flow chart representing one embodiment of a modulo-scheduled counted loop branch instruction suitable for use with the present invention.

FIG. 4 represents the control flow in counted and while-type loops that have been modified in accordance with the present invention.

FIG. 5 is an overview of a method for processing nested loops in accordance with the present invention.

FIG. 6 is a more detailed flowchart representing one embodiment of the method of FIG. 5.

FIG. 7 is a block diagram of one embodiment of a computer system that is suitable for implementing the present invention.

DETAILED DESCRIPTION OF THE INVENTION

The following discussion sets forth numerous specific details to provide a thorough understanding of the invention. However, those of ordinary skill in the art, having the benefit of this disclosure, will appreciate that the invention may be practiced without these specific details. In addition, various well-known methods, procedures, components, and circuits have not been described in detail in order to focus attention on the features of the present invention.

The present invention supports efficient processing of nested loops that include software pipelined inner loops. It does so by reducing the overhead associated with the prolog and epilog phases of the software pipelined inner loops. In accordance with the present invention, the epilog phase of the inner loop for the J.sup.th iteration of the outer loop is overlapped with the prolog phase of the inner loop for J+1.sup.st iteration of the outer loop. This hides the overhead associated with filling and draining the inner loop's software pipeline for all but the first and last iterations of the outer loop, respectively.

For one embodiment of the invention, the inner loop is executed in a "no-drain" mode for each iteration of the outer loop but the final iteration. In "no-drain" mode, the inner loop is executed until the epilog phase is reached. The epilog phase of the inner loop (or a portion of it) is bypassed, while the next iteration of the outer loop initialized. When the next iteration of the outer loop executes, the inner loop pipeline corresponding to the previous iteration of the outer loop drains, while the inner loop pipeline corresponding to the current iteration of the outer loop fills. On the final iteration of the outer loop, the inner loop is executed in a "drain" mode. In "drain" mode, the epilog phase of the inner loop executes when it is reached, to fully drain the software pipeline.

The present invention is illustrated for a processor architecture that employs register rotation to manage the registers used in software pipelined loops and predication to activate and deactivate stages during the different phases of the loop. Register rotation is a register renaming method designed to manage registers in software pipelined loops. Register rotation maps the virtual register identifiers (IDs) specified by the loop body instructions to a different set of physical registers for each iteration of the loop. This prevents instructions in different iterations of the loop from writing to the same registers. Register rotation is described, for example, in Rau, B. R., Lee, M., Tirumalai, P., and Schlansker, M. S. Register Allocation For Software Pipelined Loops, Proceeding s of the SIGNPLAN '92 Conference on Programming Language Design and Implementation, (San Francisco, 1992).

Embodiments of the present invention may also be implemented without register rotation or predication. For these embodiments, the code will be substantially more complex and the footprint of the code in memory will be significantly larger (code expansion).

The illustrated processor architecture also employs a loop counter (LC) and an epilog counter (EC) to track the status of software pipelined loops. LC tracks the number of loop iterations that still have to be executed for a counted loop, indicating for example, whether the epilog phase has been reached (LC =0). For while-type loops, a predicate associated with the loop branch instruction ("branch predicate") indicates the status of the loop. For both while and counted loops, EC tracks the number of active stages in the software pipelined loop. Although these features simplify implementation of the present invention, they are not required. Embodiments of the present invention may be implemented in any processor architecture that allows the phase of the loop to be tracked.

FIG. 2A is a schematic representation of a nested loop 200 that is processed in accordance with the present invention. Nested loop 200 includes a modulo-scheduled inner loop 210 that is executed on each of four outer loop iterations 220(1)-220(4) (collectively, outer loop 220). Instantiations of inner loop 210 in different outer loop iterations 220 are designated by indices a, b, c, d. The body of inner loop 210 is organized into five stages, which are executed one hundred times for each iteration of outer loop 220. Since TC>SC, a kernal phase is present, as indicated by the curved arrow.

FIG. 2B illustrates application of the present invention to a nested loop 200' having a short trip count inner loop (TC=3<SC=5). While the present invention does not depend on the relative magnitudes of TC and SC, the benefits it provides may be more evident in short trip count loops, since they have lower ILP than loops having a kernal phase. Except where noted, the following discussion applies to both types of loop, regardless of the relative magnitudes of TC and SC.

On the first iteration of outer loop 220, i.e. 220(1), inner loop 210(a) is initialized in "no-drain" mode. In "no-drain" mode, inner loop 210(a) is executed until its epilog phase is reached at t.sub.1. The second iteration of outer loop 220, i.e. 220(2), is initiated between t.sub.1 and t.sub.2 with inner loop 210(b) again initialized in "no-drain" mode. When the second iteration of the outer loop begins, the software pipeline for inner loop 210(a) drains, while the software pipeline for inner loop 210(b) fills. A similar pattern occurs for the third iteration of the outer loop. For the last iteration of outer loop 220, inner loop 210(d) is initialized in drain mode, which allows it to complete normally. That is, inner loop 210(d) enters an epilog phase following its kernel phase, allowing its software pipeline to drain.

Register rotation ensures that registers associated with different iterations of inner loop 210 in the same or different iterations of the outer loop remain segregated. This allows, for example, the epilog of inner loop 210(a) to execute concurrently with the prolog of inner loop 210(b).

For the short trip count inner loop of FIG. 2B, the epilog phase of inner loop 210 for the first outer loop iteration is reached before the prolog phase of the loop for the second iteration of the outer loop ends, and the two phases overlap during II(4). The first stage of the prolog phase of inner loop 210(b) also executes during II(4). As indicated in the figure, the pipeline of inner loop 210 can extend over more than two outer loop iterations. For example, the inner loops begun during the first and second outer loop iterations do not complete until the third and fourth outer loop iterations, respectively.

The present invention is illustrated with reference to the following nested loop:

                Real*4 A(10,100), B(10,100), C(10,100)
                DO J=1, 100
                       DO I = 1,3
                       A(I,J) = B(I,J)/C(I,J)
                    ENDDO
                ENDO

        (II)      Outer_Loop
                                 . . . . .
                                 mov pr.rot = 0x10000
                                 mov ar.ec = 12
                                 mov ar.lc = 2
                  Inner_Loop
                                 . . . . .
                                 . . . . .
                                 br.ctop           Inner_loop
                                 . . . . .
                                 cmp4.1e p7, p6 = r2, r14
                                 (p7) br.cond      Outer_Loop

        (III)                      mov pr.rot = 0x10000
                                   mov ar.ec = 1
                  Outer_Loop:
                                   mov ar.lc = 2
                                   . . . . .
            (IIIa) Inner_Loop:
                                   . . . . .
                                   . . . . .
                                   btr.ctop  Inner_Loop
                                   . . . . .
                                   cmp4.1e p7, p0 = r2, r14
                                   cmp4.eq p6, p0 = r2, r14
                                   (p7) cmp4e.eq p16 = r0, r0
                                   (p7) mov ar.ec = 1;;
                                   (p6) mov ar.ec = 12
                                   (p7) br.cond Outer_Loop

        (IV)                   mov pr.rot = 0x10000
                               mov r2 = 100
                               mov p6 = 0
                Outer_Loop:
                               (p16) add r2 = r2, -1
                               (p16) mov ar.ec = 1
                               (p16) mov ar.lc = 2
                               (p6) mov ar.ec = 11
                               (p6) move ar.lc = 0
                (IVa) Inner_Loop:
                               . . .
                               br.ctop       Inner_Loop
                               (p17) comp4.gt.unc p16, p6 = r2, r0
                               . . .
                               (p16) br.cond Outer_Loop
                               (p6) br.cond  Outer_Loop

        (V)                        mov   r14 = 99
                                   mov   pr.rot = 0x10000
                                   mov   ar.ec = 0
                                   mov   ar.lc = 2
              Outer_Loop (Va):
                                   A
                                   cmp.gt p7, p6 = r14, 1
                                   add   r14 = r14, -1;
                                   (p6) mov    ar.lc = 12
              Inner_Loop:
                                   . . .
                                   br.ctop     Inner_Loop;;
                                   B
                                   (p7) mov    ar.lc = 3
                                   br.ctop     Outer_Loop

• Inventors
  Muthukumar, Kalyan; Doshi, Gautam B.;
• Assignee
  Intel Corporation (Santa Clara, CA)
• Published
  Nov-16-2004
• Current US Classes:
  717/116
  717/150
• Application #
  143163
• International Classes
  G06F 009/44
• Field of Search
  712/241 712/244 717/9
• Examiner
  Ingberg; Todd
• Agent
  Bacon; Shireen I.
• US Patent References:
  5230053
  5361354
  5704053
  5774370
  5790859
  5842022
  5852734
  5901318
  5920724
  5950007
  5958048
  5974538
  6016399
  6055627
  6070011
  6074433
  6148437
  6173443
  6178498
  6178499
  6192515
  6438682
  6571385