Sorting tasks with dependencies and resource sharing
AssigneeSap SE
InventorsGabriel MOITA, Daniel BOSSLE
Life of this patent
Estimating the term…
Abstract
Disclosed herein are system, method, and computer program product embodiments for resolving an execution order for a plurality of tasks, such as solving complex calculations in order, installing new software in order, or scheduling instructions by compilers in order. The approach uses a dependency graph to perform a topological sort, and applies a heuristic to determine which node to execute next from remaining nodes without dependency issues. The approach favors reducing resource conflicts with a resource used by a previous node, resolving larger numbers of dependencies early, and forcing early resolution of resource conflicts.
Claims20
A computer implemented method for resolving an execution order for a plurality of tasks, comprising:
- selecting, by one or more computing devices, a list of nodes having no incoming directed edges from a graph comprising a plurality of nodes and one or more directed edges connecting out from parent nodes of the plurality of nodes into respective child nodes of the plurality of nodes, wherein the directed edges specify a dependency by the child nodes on the respective parent nodes, and wherein each node represents a task of the plurality of tasks;
- determining, by the one or more computing devices, a next node from the list of nodes that minimizes resource conflicts with a previous node;
- and
- inserting, by the one or more computing devices, the task of the plurality of tasks represented by the next node into the execution order.
A system for resolving an execution order for a plurality of tasks, comprising:
- a memory configured to store operations;
- and
- one or more processors configured to perform the operations, the operations comprising:
- selecting a list of nodes having no incoming directed edges from a graph comprising a plurality of nodes and one or more directed edges connecting out from parent nodes of the plurality of nodes into respective child nodes of the plurality of nodes, wherein the directed edges specify a dependency by the child nodes on the respective parent nodes, and wherein each node represents a task of the plurality of tasks,
- determining a next node from the list of nodes that minimizes resource conflicts with a previous node, and
- inserting the task of the plurality of tasks represented by the next node into the execution order.
A computer readable storage device having instructions stored thereon for resolving an execution order for a plurality of tasks, execution of the instructions which, by one or more processing devices, causes the one or more processing devices to perform operations comprising:
- selecting a list of nodes having no incoming directed edges from a graph comprising a plurality of nodes and one or more directed edges connecting out from parent nodes of the plurality of nodes into respective child nodes of the plurality of nodes, wherein the directed edges specify a dependency by the child nodes on the respective parent nodes, and wherein each node represents a task of the plurality of tasks;
- determining a next node from the list of nodes that minimizes resource conflicts with a previous node;
- and
- inserting the task of the plurality of tasks represented by the next node into the execution order.
Dependencies are inferred from the claim text.