# US 2012/0254888 A1 · Pipelined loop parallelization with pre-computations

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254888 A1
- Document ID: US20120254888A1
- Status: Published application
- Kind: A1
- Application number: 13/074,253
- Filed: 2011-03-29
- Published: 2012-10-04
- Earliest claimed: 2011-03-29
- Assignees: Oracle International Corporation
- Inventors: SPIROS KALOGEROPULOS; PARTHA PAL TIRUMALAI
- Web page: https://patentgrep.com/patent/US20120254888A1

## CPC

- G06F 8/433: {Dependency analysis; Data or control flow analysis}
- G06F 8/443: {Optimisation}
- G06F 8/445: {Exploiting fine grain parallelism, i.e. parallelism at instruction level (run-time instruction scheduling G06F9/3836)}
- G06F 8/452: {Loops}
- G06F 8/456: {Parallelism detection}
- G06F 8/49: {Partial evaluation}
- G06F 9/3836: {Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Embodiments of the invention provide systems and methods for automatically parallelizing loops with non-speculative pipelined execution of chunks of iterations with pre-computation of selected values. Non-DOALL loops are identified and divided the loops into chunks. The chunks are assigned to separate logical threads, which may be further assigned to hardware threads. As a thread performs its runtime computations, subsequent threads attempt to pre-compute their respective chunks of the loop. These pre-computations may result in a set of assumed initial values and pre-computed final variable values associated with each chunk. As subsequent pre-computed chunks are reached at runtime, those assumed initial values can be verified to determine whether to proceed with runtime computation of the chunk or to avoid runtime execution and instead use the pre-computed final variable values.

## Claims

### Claim 1

A method comprising:
parallelizing a set of program instructions from a computer program into a plurality of threads to be executed on at least one processor, the program instructions identifying a computation to be performed over a plurality of iterations, such that each thread is configured to compute an output value as a function of an input variable according to a corresponding portion of the iterations of the computation;
during runtime execution of a first thread on the at least one processor, pre-computing the portion of the iterations of the computation corresponding to a second thread by:
determining a predicted input value of the input variable according to the portion of the iterations of the computation corresponding to the second thread;
computing the output value as a function of the predicted input value over the portion of the iterations of the computation corresponding to the second thread to generate a pre-computed output value; and
storing the predicted input value and the pre-computed output value in association with the second thread; and
subsequent to runtime execution of the first thread and prior to runtime execution of the second thread:
determining a current input value of the input variable according to the portion of the iterations of the computation corresponding to the second thread;
comparing the current input value to the predicted input value stored in association with the second thread; and
computing the output value as a function of the current input value over the portion of the iterations of the computation corresponding to the second thread only when the current input value does not equal the predicted input value stored in association with the second thread.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
using the pre-computed output value stored in association with the second thread as the output value for the portion of the iterations of the computation corresponding to the second thread when the current input value equals the predicted input value stored in association with the second thread.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
determining whether the set of program instructions includes any cross-iteration dependencies prior to parallelizing the set of program instructions into the plurality of threads,
wherein the parallelizing step is performed only when the set of program instructions is determined to include at least one cross-iteration dependency.

### Claim 4 (depends on 1)

The method of claim 1, wherein parallelizing the set of program instructions from the computer program into the plurality of threads to be executed on the at least one processor comprises:
generating a stripped down version of the set of program instructions, wherein the second thread executes the stripped down version of the set of program instructions when performing the pre-computing the portion of the iterations of the computation corresponding to the second thread step.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
synchronizing the threads to preserve an iteration order associated with the set of program instructions during runtime execution.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
during runtime execution of the first thread on the at least one processor, using the second thread to prefetch program components to a local data store associated with the second thread.

### Claim 7 (depends on 1)

The method of claim 1, wherein parallelizing the set of program instructions from the computer program into the plurality of threads to be executed on the at least one processor comprises assigning the first thread to be executed on a first logical processor and assigning the second thread to be executed on the second logical processor.

### Claim 8 (depends on 7)

The method of claim 7, wherein each of the first logical processor and the second logical processor corresponds either to a processor core or a processor core pipeline.

### Claim 9 (depends on 1)

The method of claim 1, further comprising:
estimating an execution time for runtime execution of the set of program instructions corresponding to a thread;
estimating a pre-computation time for pre-computing the portion of the iterations of the computation corresponding to a thread; and
during runtime execution of the first thread on the at least one processor, pre-computing the portion of the iterations of the computation corresponding to the second thread only when the pre-computation time is estimated to be less than the execution time.

### Claim 10 (depends on 1)

The method of claim 1, further comprising:
estimating an execution time for runtime execution of the set of program instructions corresponding to a thread;
estimating a pre-computation time for pre-computing the portion of the iterations of the computation corresponding to a thread; and
during runtime execution of the first thread on the at least one processor, performing only a partial pre-computing of the iterations of the computation corresponding to the second thread when the pre-computation time is estimated to be greater than the execution time.

### Claim 11 (depends on 1)

The method of claim 1, further comprising:
detecting completion of runtime execution of the first thread on the at least one processor prior to completing pre-computing the portion of the iterations of the computation corresponding to the second thread; and
asynchronously stopping the pre-computing step in response to detecting the completion of runtime execution of the first thread.

### Claim 12 (depends on 1)

The method of claim 1, further comprising:
determining whether the predicted input value of the input variable can be predicted with at least a threshold confidence level,
wherein the pre-computing step is performed only when the predicted input value of the input variable can be predicted with at least the threshold confidence level.

### Claim 13 (depends on 1)

The method of claim 1, further comprising:
determining whether the predicted input value of the input variable can be predicted with at least a threshold confidence level, such that, when the predicted input value of the input variable cannot be predicted with at least the threshold confidence level, pre-computing the portion of the iterations of the computation corresponding to the second thread further comprises:
re-computing a portion of the first thread to output a computed value of the input variable,
wherein determining the predicted input value of the input variable comprises using the computed value of the input variable output by the first thread.

### Claim 14 (depends on 1)

The method of claim 1, wherein parallelizing the set of program instructions from the computer program into the plurality of threads to be executed on the at least one processor comprises:
optimizing a size of the set of program instructions to parallelize according to minimizing synchronization overhead.

### Claim 15

A system comprising:
a first processing block in communication with a first cache;
a second processing block in communication with a second cache;
a parallelizing module, communicatively coupled with the first processing block and the second processing block, and configured to parallelize a set of program instructions from a computer program into a plurality of threads, the program instructions identifying a computation to be performed over a plurality of iterations, such that each thread is configured to compute an output value as a function of an input variable according to a corresponding portion of the iterations of the computation, and the parallelizing module further configured to assign a first thread to the first processing block, and to assign a second thread to the second processing block, such that:
during runtime execution of the first thread on the first processing block, the second processing block pre-computes according to the second thread by:
determining a predicted input value of the input variable according to the second thread;
computing the output value as a function of the predicted input value according to the second thread to generate a pre-computed output value; and
storing the predicted input value and the pre-computed output value in the second cache; and
the second processing block, subsequent to runtime execution of the first thread and prior to runtime execution of the second thread:
determines a current input value of the input variable according to the portion of the iterations of the computation corresponding to the second thread;
compares the current input value to the predicted input value stored in association with the second thread; and
computes the output value as a function of the current input value according to the second thread only when the current input value does not equal the predicted input value stored in the second cache.

### Claim 16 (depends on 15)

The system of claim 15, wherein each of the first processing block and the second processing block is either a processor core or a processor core pipeline.

### Claim 17 (depends on 15)

The system of claim 15, wherein the parallelizing module is further configured to assign a first thread to the first processing block, and to assign a second thread to the second processing block, such that:
the pre-computed output value stored in association with the second thread is used as the output value for the portion of the iterations of the computation corresponding to the second thread when the current input value equals the predicted input value stored in association with the second thread.

### Claim 18

A computer program product residing on a non-transitory, processor-readable medium and having processor-readable instructions, which, when executed, cause a processor to perform steps comprising:
parallelizing a set of program instructions from a computer program into a plurality of threads, the program instructions identifying a computation to be perfotuied over a plurality of iterations, such that each thread is configured to compute an output value as a function of an input variable according to a corresponding portion of the iterations of the computation; and
compiling the computer program so that:
during runtime execution of a first thread, the portion of the iterations of the computation corresponding to a second thread are pre-computed by:
determining a predicted input value of the input variable according to the portion of the iterations of the computation corresponding to the second thread; computing the output value as a function of the predicted input value over the portion of the iterations of the computation corresponding to the second thread to generate a pre-computed output value; and storing the predicted input value and the pre-computed output value in association with the second thread; and
subsequent to runtime execution of the first thread and prior to runtime execution of the second thread: a current input value of the input variable is determined according to the second thread; the current input value is compared to the predicted input value stored in association with the second thread; and the output value is computed as a function of the current input value and according to the second thread only when the current input value does not equal the predicted input value stored in association with the second thread.

### Claim 19 (depends on 18)

The computer program product of claim 18, having processor-readable instructions, which, when executed, cause the processor to perform steps further comprising:
using the pre-computed output value stored in association with the second thread as the output value for the portion of the iterations of the computation corresponding to the second thread when the current input value equals the predicted input value stored in association with the second thread.

### Claim 20 (depends on 18)

The computer program product of claim 18, wherein:
the processor comprises a plurality of logical processors; and
the processor-readable instructions, when executed, cause the processor to parallelize the set of program instructions from the computer program into the plurality of threads by assigning the first thread to be executed on a first logical processor and assigning the second thread to be executed on the second logical processor.
