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:

Scheduling 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
e, f, h, g

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.

  • $\begingroup$ How can you be processing "e" in the second step if there is a dependency to it from "d" (which is only executed in the third step)? $\endgroup$ – dkaeae Mar 18 at 9:13
  • $\begingroup$ Can you give some precisions on the actual constraints ? You can execute any number of parrallel tasks ? All tasks have the same cost in time ? Your objective is to achieve $i$ task as soon as possible (can $j$ be executed a little later for instance as it is on a very short branch) ? $\endgroup$ – Vince Mar 18 at 9:19
  • $\begingroup$ @dkaeae I am sorry, that was a mistake $\endgroup$ – user10655827 Mar 18 at 9:21
  • $\begingroup$ @Vince There are no constraints on the number of tasks. Regarding j, no j 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 at 9:26

From your initial DAG $G(E, V)$ You start reversing all edges to build a new DAG $G'(E, V')$. Then do a BFS from $i$ in $G'$ to remove any unneeded tasks (unreached nodes in the BFS). This step is $O(N)$ with $N = |V'|$, the number of edges.

From $G$, build the number of requirements of each task ($R(V)$) and at the same time the list $L$ of the tasks with no requirements. this takes $O(N)$.

Then you iterate on this pseudo-algorithm:

while(root is not executed)
    L' = empty list
    for v in L
        for each node v' with an edge in G' from v to v'
             R(v') -= 1
             if R(v') == O then add v' to L'
    execute all L in a parrallel step
    L = L'

this is $O(N)$.

  • $\begingroup$ Thank you! I have added a Python implementation of this algorithm. $\endgroup$ – user10655827 Mar 19 at 9:42

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .