Patent ID: 8214831

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, wherein determining the dependence information for the plurality of memory accesses within the computer executable code comprises: allocating and initializing version arrays and data structures for each array accessed by the computer executable code and monitored by a set of computed dependence slices extracted from the computer executable code, wherein allocating and initializing the version arrays and the data structures comprises: allocating and initializing one version array per array tracked in a dependence slice in the set of computed dependence slices, wherein the one version array tracks a last iteration that touched each element of the array; and allocating and initializing one dependence array, wherein the one dependence array tracks a latest dependent iteration that must complete before another iteration may execute; for each iteration in the plurality of iterations, generating an ordered list of tupples generated from the iteration using the set of computed dependence slices; for each tupple in the ordered list of tupples, processing the tupple using one of a set of dependence analyzing algorithms; using results of the processing, outputting a sequence of iterations that the iteration depends on; and outputting distance information from the iteration to the latest dependent iteration that the iteration depends on; 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 be executed.