System and method for optimizing the evaluation of task dependency graphs

摘要

One embodiment of the present invention is a technique for optimizing a task graph that specifies multiple tasks and the dependencies between the specified tasks. When optimizing the task graph, the optimization engine performs multiple iterations of runtime optimization operations on the task graph. At each iteration, an optimized task graph is generated based on a different task aggregation topology. The optimized task graph is then compiled and executed. Runtime statistics related to the execution are collected, and, in subsequent iterations, the task graph is further optimized based on the collected statistics. Once the optimization process is complete, the most optimal task graph topology that was identified during the process is used to generate an optimized task graph for execution.

主权项

1. A computer-implemented method for optimizing a task graph that delineates a plurality of tasks to be evaluated in a parallel processing environment, the method comprising:
generating a first task aggregation topology associated with the task graph that divides the plurality of tasks into a first collection of sets, wherein each set in the first collection of sets includes one or more tasks from the plurality of tasks, each task of the plurality of tasks belongs to only one set included in the first collection of sets, and the first task aggregation topology comprises a bit mask that indicates two or more tasks of the plurality of tasks that are included in a first set in the first collection of sets; compiling the plurality of tasks according to the first task aggregation topology to generate units of work to be executed in the parallel processing environment, wherein the two or more tasks included in the first set are compiled to generate a single unit of work that is executed by a first processing engine included in the parallel processing environment; collecting statistics associated with executing the units of work in the parallel processing environment; and determining whether the first task aggregation topology is more efficient in execution than any previously-defined task aggregation topology based on the statistics; and if the task aggregation topology is more efficient in execution than any previously-defined task aggregation topology, then selecting the first task aggregation topology as the most optimal task aggregation topology, or if the first task aggregation topology is not more efficient in execution than any previously-defined task aggregation topology, then selecting a second task aggregation topology as the most optimal task aggregation topology.