US 2001/0020294 A1 · Optimization apparatus that decreases delays in pipeline processing of loop and computer-readable storage medium storing optimization program

Abstract

An optimization apparatus is capable of improving the execution efficiency of a loop that includes a loop carry dependency between consecutive iterations of the loop. For example, a value resulting from one iteration is used in an immediately following iteration. When the arithmetic expression “a[i+1]=a[i]*3+2;” is included in a loop body, and a value resulting from the arithmetic expression “a[i+1]=a[i]*3+2;” in one iteration is used in a following iteration, execution delays occur in pipeline processing of the loop. Here, the arithmetic expression “a[i+1]=a[i]*3+2;” is transformed into the arithmetic expression “a[i+4]=a[i]*81+80;” to expand the dependency distance. By doing so, the execution delays can be decreased.

Claims16

Dependent claims

An optimization apparatus that optimizes a program so as to be suitable for pipeline processing, the program including a loop structure composed of a body and a control statement, the body including at least one arithmetic expression, the control statement prescribing a repeat condition for the body,

the optimization apparatus comprising:
a detection means for detecting a first arithmetic expression that defines a value in an i-th repetition of the body, the value being to be referred to in an (i+x)th repetition of the body, where i and x are positive integers;
an estimation means for estimating, based on a value of x, an execution delay that will occur when the body is repeatedly executed in pipeline processing;
and
a conversion means for converting, when the execution delay exceeds a predetermined threshold level, the detected arithmetic expression into a second arithmetic expression that defines a value in the i-th repetition, the value being to be referred to in an (i+y)th repetition of the body, where y is an integer that is greater than x.

2 more elements

A computer-readable storage medium that stores an optimization program for optimizing a program so as to be suitable for pipeline processing, the program including a loop structure composed of a body and a control statement, the body including at least one arithmetic expression, the control statement prescribing a repeat condition for the body,

the optimization program comprising:
a detection step for detecting a first arithmetic expression that defines a value in an i-th repetition of the body, the value being to be referred to in an (i+x) th repetition of the body, where i and x are positive integers;
an estimation step for estimating, based on a value of x, an execution delay that will occur when the body is repeatedly executed in pipeline processing;
and
a conversion step for converting, when the execution delay exceeds a predetermined threshold level, the first arithmetic expression into a second arithmetic expression that defines a value in the i-th repetition, the value being to be referred to in an (i+y)th repetition of the body, where y is an integer that is greater than x.

2 more elements

Dependencies are inferred from the claim text.

Optimization apparatus that decreases delays in pipeline processing of loop and computer-readable storage medium storing optimization program

Life of this patent

Optimization apparatus that decreases delays in pipeline processing of loop and computer-readable storage medium storing optimization program

Life of this patent

Abstract

Claims16