Runtime handling of task dependencies using dependence graphs

Patent metadata

Field	Value
Publication number	US-9652286-B2
Application number	US-201414222273-A
Country	US
Kind code	B2
Filing date	Mar 21, 2014
Priority date	Mar 21, 2014
Publication date	May 16, 2017
Grant date	May 16, 2017

Abstract

Embodiments include systems and methods for handling task dependencies in a runtime environment using dependence graphs. For example, a computer-implemented runtime engine includes runtime libraries configured to handle tasks and task dependencies. The task dependencies can be converted into data dependencies. At runtime, as the runtime engine encounters tasks and associated data dependencies, it can add those identified tasks as nodes of a dependence graph, and can add edges between the nodes that correspond to the data dependencies without deadlock. The runtime engine can schedule the tasks for execution according to a topological traversal of the dependence graph in a manner that preserves task dependencies substantially as defined by the source code.

First claim

What is claimed is:

1. A computational runtime environment comprising:
a processor;
a memory having compiled code stored thereon, the compiled code comprising a plurality of tasks compiled from corresponding task constructs of a source code, at least a subset of the tasks having associated tags that indicate data dependencies reflecting respective task dependencies of the source code; and
a scheduler that operates to:
generate a dependence graph dynamically at runtime according to the subset of tasks of the compiled code and their associated tags by:
determining, as each task is encountered at runtime, whether the task has a respective data dependency according to its associated tags;
adding a corresponding node to the dependence graph for the task when it is determined to have the respective data dependency; and
adding a set of edges to the dependence graph that each terminate in the corresponding node in accordance with the respective data dependency; and

schedule the subset of tasks for execution by the processor in a manner that preserves the task dependencies of the source code by traversing the dependence graph.

2. The computational runtime environment of claim 1 , wherein adding the set of edges comprises:
determining that the corresponding node depends from a set of other nodes according to the respective data dependency; and
adding each of the set of edges to correspond to a respective one of the set of other nodes, so that each edge originates from the respective other node and terminates in the corresponding node.

3. The computational runtime environment of claim 1 , wherein the scheduler operates to schedule the subset of tasks for execution by the processor by iteratively, until no nodes remain in the dependence graph, performing steps comprising:
identifying a set of the remaining nodes of the dependence graph as having no incoming edges;
scheduling the tasks corresponding to the identified set of the remaining nodes for execution by the processor; and
removing the identified set of the remaining nodes and any edges originating therefrom from the dependence graph upon execution of the scheduled tasks.

4. The computational runtime environment of claim 3 , wherein the scheduled tasks are sibling tasks each having an associated tag that points to a common location in the memory.

5. The computational runtime environment of claim 3 , wherein scheduling the set of tasks corresponding to the identified set of the remaining nodes for execution by the processor comprises scheduling at least some of the set of tasks for parallel execution.

6. The computational runtime environment of claim 1 , wherein the dependence graph is a direct acyclic graph.

7. The computational runtime environment of claim 1 , wherein the scheduler further operates to:
cause the processor to execute the subset of tasks according to the schedule.

8. The computational runtime environment of claim 1 , wherein the memory comprises a plurality of memory locations, and each associated tag corresponds to a read/write operation that designates one of the memory locations.

9. The computational runtime environment of claim 8 , wherein each associated tag is one of an “IN(x)” tag or an “OUT(x)” tag, the “IN(x)” tag corresponding to an operation that reads from one of the memory locations identified by “x,” the “OUT(x)” tag corresponding to an operation that writes to the memory location identified by “x ”.

10. The computational runtime environment of claim 1 , wherein the scheduler operates to generate the dependence graph dynamically at runtime according to a sequence: IL(0); O(0); . . . ; IL(n); O(n), wherein:
“IL(i)” represents an i-th list of tasks having associated tags corresponding to the operation that reads from the designated memory location of the memory, where i represents an integer between 0 and n; and
“O(i)” represents an i-th task having an associated tag corresponding to an operation that writes to the designated memory location of the memory.

11. The computational runtime environment of claim 10 , wherein the scheduler operates to generate the dependence graph dynamically at runtime by:
determining, when IL(0) is encountered at runtime, whether IL(0) is an empty list;
adding a first set of nodes to the dependence graph corresponding to each task of IL(0), when IL(0) is determined not to be an empty list;
adding a second node to the dependence graph corresponding to the task of O(0) when O(0) is encountered at runtime;
adding an edge originating from each of the first set of nodes and terminating in the second node, when IL(0) is determined not to be an empty list;
for each remaining IL(i) in the sequence, as it is encountered at runtime:
adding a respective node to the dependence graph corresponding to each task of IL(i), when IL(i) is not an empty list;
determining whether there exists a node corresponding to O(i−1); and
adding a respective edge originating from the node corresponding to O(i−1) and terminating in the respective node corresponding to each task of IL(i), when there exists a node corresponding to O(i−1); and
for each remaining O(i) in the sequence, as it is encountered at runtime:
adding a respective node to the dependence graph corresponding to the task of O(i);
determining whether there exist any nodes corresponding to IL(i−1);
adding a respective edge originating from each node corresponding to IL(i−1) and terminating in the respective node corresponding to the task of O(i), when there exist any nodes corresponding to IL(i−1); and
adding a respective edge originating from the node corresponding to the task of O(i−1) and terminating in the respective node corresponding to the task of O(i), when there exists a node corresponding to O(i−1) and there do not exist any nodes corresponding to IL(i−1).

12. The computational runtime environment of claim 1 , wherein the processor implements multi-threading, and the scheduler operates to schedule the subset of tasks further in a manner that exploits the multi-threading.

13. The computational runtime environment of claim 1 , wherein the task constructs and task dependencies of the source code are defined according to an OpenMP programming specification.

14. A method for runtime handling of task dependencies, the method comprising:
loading a compiled code from a data store, the compiled code comprising a plurality of tasks compiled from corresponding task constructs of a source code, at least a subset of the tasks having associated tags that indicate data dependencies reflecting respective task dependencies of the source code;
generating a dependence graph dynamically at runtime according to the subset of tasks of the compiled code and their associated tags by:
determining, as each task is encountered at runtime, whether the task has a respective data dependency according to its associated tags;
adding a corresponding node to the dependence graph for the task when it is determined to have the respective data dependency; and
adding a set of edges to the dependence graph that each terminate in the corresponding node in accordance with the respective data dependency; and

scheduling the subset of tasks for execution by a processor in a manner that preserves the task dependencies of the source code by traversing the dependence graph.

15. The method of claim 14 , wherein scheduling the subset of tasks for execution by the processor comprises performing iteratively, until no nodes remain in the dependence graph, steps comprising:
identifying a set of the remaining nodes of the dependence graph as having no incoming edges;
scheduling

Assignees

• Oracle Int Corp

Inventors

• Fan Bin

Classifications

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F2209/484

  Precedence · CPC title