Patent ID: 8464271

Claim:
A method, in a data processing system, for a runtime dependence-aware scheduling of dependent iterations, the method comprising: receiving computer executable code that contains a plurality of iterations; executing one or more iterations in the plurality of iterations of the computer executable code by a main thread; and while the one or more iterations in the plurality of iterations are being executed by the main thread: determining dependence information for a plurality of memory accesses within the computer executable code, wherein determining the dependence information is performed using a set of dependence threads in the data processing system; using the dependence information, determining whether a subset of a set of uncompleted iterations in the plurality of iterations is capable of being executed ahead-of-time by a set of worker threads in the data processing system, wherein the plurality of iterations comprises at least one completed iteration that has been executed by the main thread; responsive to a determination that the subset of the set of uncompleted iterations in the plurality of iterations is capable of being executed ahead-of-time, signaling the main thread to skip the subset of the set of uncompleted iterations; and signaling the set of worker threads in the data processing system to execute the subset of the set of uncompleted iterations ahead of a time when the subset of uncompleted iteration would normally he executed.