# US 2012/0084789 A1 · System and Method for Optimizing the Evaluation of Task Dependency Graphs > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2012/0084789 A1 - Document ID: US20120084789A1 - Status: Published application - Kind: A1 - Application number: 13/236,550 - Filed: 2011-09-19 - Published: 2012-04-05 - Earliest claimed: 2010-09-30 - Assignees: Autodesk, Inc. - Inventors: Francesco IORIO - Web page: https://patentgrep.com/patent/US20120084789A1 ## CPC - G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract 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. ## Claims ### Claim 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 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, and each task of the plurality of tasks belongs to only one set included 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; 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. ### Claim 2 (depends on 1) The method of claim 1, wherein the first task aggregation topology is defined based on the configuration of the parallel processing environment. ### Claim 3 (depends on 1) The method of claim 1, wherein two or more tasks included in a first set in the first collection of sets are compiled to generate a single unit of work that is executed by a first processing engine included in the parallel processing environment. ### Claim 4 (depends on 1) The method of claim 1, wherein the statistics include a total execution time associated with executing the units of work in the parallel processing environment. ### Claim 5 (depends on 1) The method of claim 1, wherein the execution statistics include a total amount of memory consumed when executing the units of work in the parallel processing environment. ### Claim 6 (depends on 1) The method of claim 1, wherein determining whether the first task aggregation topology is more optimal than a previously-defined task aggregation topology comprises comparing the statistics associated with executing the units of work in the parallel processing environment with previously-collected statistics associated with executing units of work in the parallel processing environment based on a previously-defined task aggregation topology. ### Claim 7 (depends on 1) The method of claim 1, further comprising generating the second task aggregation topology associated with the task graph that divides the plurality of tasks into a second collection of sets, wherein each set in the second collection of sets includes one or more tasks from the plurality of tasks, and each task of the plurality of tasks belongs to only one set in the second collection of sets. ### Claim 8 (depends on 7) The method of claim 7, wherein the second task aggregation topology comprises a previously-defined task aggregation topology. ### Claim 9 (depends on 7) The method of claim 7, wherein the second task aggregation is defined based on the first task aggregation topology and the statistics associated with the executing the units of work in the parallel processing environment. ### Claim 10 A computer readable medium storing instructions that, when executed by a processor, cause the processor to optimized a task graph that delineates a plurality of tasks to be evaluated in a parallel processing environment, by performing the steps of: generating a first 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, and each task of the plurality of tasks belongs to only one set included 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; 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. ### Claim 11 (depends on 10) The computer readable medium of claim 10, wherein the first task aggregation topology is defined based on the configuration of the parallel processing environment. ### Claim 12 (depends on 10) The computer readable medium of claim 10, wherein two or more tasks included in a first set in the first collection of sets are compiled to generate a single unit of work that is executed by a first processing engine included in the parallel processing environment. ### Claim 13 (depends on 10) The computer readable medium of claim 10, wherein the statistics include a total execution time associated with executing the units of work in the parallel processing environment. ### Claim 14 (depends on 10) The computer readable medium of claim 10, wherein the execution statistics include a total amount of memory consumed when executing the units of work in the parallel processing environment. ### Claim 15 (depends on 10) The computer readable medium of claim 10, wherein determining whether the first task aggregation topology is more optimal than a previously-defined task aggregation topology comprises comparing the statistics associated with executing the units of work in the parallel processing environment with previously-collected statistics associated with executing units of work in the parallel processing environment based on a previously-defined task aggregation topology. ### Claim 16 (depends on 10) The computer readable medium of claim 10, further comprising generating the second task aggregation topology associated with the task graph that divides the plurality of tasks into a second collection of sets, wherein each set in the second collection of sets includes one or more tasks from the plurality of tasks, and each task of the plurality of tasks belongs to only one set in the second collection of sets. ### Claim 17 (depends on 16) The computer readable medium of claim 16, wherein the second task aggregation topology comprises a previously-defined task aggregation topology. ### Claim 18 (depends on 16) The computer readable medium of claim 16, wherein the second task aggregation is defined based on the first task aggregation topology and the statistics associated with the executing the units of work in the parallel processing environment. ### Claim 19 A computer system, comprising: a parallel processing environment having one or more processing engines; and an optimization engine configured to optimize a task graph delineates a plurality of tasks to be evaluated in the parallel processing environment, by performing the steps of: generating a first 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, and each task of the plurality of tasks belongs to only one set included 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; collecting statistics associated with executing the units of work in the parallel processing environment; and determining whether the first task aggregation topology is more optimal than any previously-defined task aggregation topology based on the statistics; and if the task aggregation topology is more optimal 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 optimal than any previously-defined task aggregation topology, then selecting a second task aggregation topology as the most optimal task aggregation topology. ### Claim 20 (depends on 20) The computer system of claim 20, wherein the task graph is generated by an application executing within the computer system.