I have a set of compute tasks I want to schedule, these tasks have dependencies and a task may not be executed until all its dependencies are executed.
The problem can be represented as a directed acyclic graph:
The current scheduler ensures correctness, and capable of culling unneeded tasks such as k in the previous graph (assuming the end goal is i).
I am struggling to find another equivalent algorithm to maximize number of tasks running in parallel (tasks on the same line may be executed in any order):
a, b, j
c
d
e, f, h, g
i
Flatten form, what is between ()
may be in any order and represent parallel tasks:
(a, b, j), (c), (d), (e, f, h, g), (i)
The idea here I want to fill the compute engine with as much work as possible.
j
, noj
should be executed as soon as possible. The idea here I want to fill the compute engine with as much work as possible. $\endgroup$ – user10655827 Mar 18 '19 at 9:26