Patent ID: 8726251

Claim:
A method comprising: generating, using a compiler, a set chunks for each of a plurality of non-DOALL loops within a set of program instructions of a computer program; determining, using the compiler, a subset of the set of chunks for which an estimated time saved by pre-computing the chunk outweighs an estimated overhead time associated with pre-computing the chunk; parallelizing, using the compiler, the set of program instructions associated with the subset of chunks 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; and compiling executable program code from the parallelized set of program instructions, so that, during runtime execution of a first thread on the at least one processor, 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: 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.