US 5,958,048 A · Architectural support for software pipelining of nested loops

Abstract

For certain classes of software pipelined loops, prologue and epilogue portions of adjacent inner loops in a nested loop can be overlapped. In this way, outer loop code, as well as inner loop code, can be software pipelined. Architectural support for software pipelined nested loops is provided by a set of loop parameter and status registers and by an implementation of loop state dependent, multiway control transfers. For loop body code compatible with two simple constraints, the present invention does not require additional code elements for disabling garbage operations during prologue and epilogue loop periods of adjacent inner loops. Nested loop control allows overlap between the epilogue period of a prior inner loop and the prologue period of a next inner loop. As a result, nested loop code can be more efficiently scheduled by a compiler for execution on a processor such as VLIW processor which provides architectural support for software pipelined nested loops, thereby providing improved loop performance. Loop state dependent, multiway control transfers are provided by multi-way control transfer logic which includes the loop parameter and status registers and a branch target selector for selecting control transfer addresses corresponding to inner loop body code, a start patch, and a finish patch from control transfer address registers in accordance with loop state.

Claims24

Dependent claims

An apparatus comprising:

a first register complex responsive to physical iterations of inner loop body code, wherein a state of the first register complex advances toward a beginning of last iteration state in correspondence with the physical iterations of the inner loop body code;
a second register complex responsive to physical iterations of inner loop body code, wherein a state of the second register complex advances toward an end of last iteration state in correspondence with the physical iterations of the inner loop body code;
and
multiway control transfer logic coupled to the first and second register complexes, the multiway control transfer logic selective for one of a plurality of control transfer addresses, wherein the multiway control transfer logic selects a first control transfer address in response to an asserted beginning of last iteration state and selects a second control transfer address in response to an asserted end of last iteration state.

1 more element

A method of controlling execution of software pipelined inner loop body code, the method comprising the steps of:

initializing a first register complex with an indication corresponding to a number of logical iterations in the inner loop body code;
initialing a second register complex with an indication corresponding to a number of overlapped logical iterations minus one (NOVL-1) in the inner loop body code;
advancing a state of the first register complex toward a beginning of last iteration state in correspondence with physical iterations of the inner loop body code;
advancing a state of the second register complex toward an end of last iteration state in correspondence with physical iterations of the inner loop body code;
when the first register complex reaches the beginning of last iteration state, transferring control, during a next physical iteration thereafter, to a start patch;
and
when the second register complex reaches the end of last iteration state, transferring control, during a next physical iteration thereafter, to a finish patch.

4 more elements

Dependencies are inferred from the claim text.

Architectural support for software pipelining of nested loops

Life of this patent

Architectural support for software pipelining of nested loops

Life of this patent

Abstract

Claims24