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.