1
$\begingroup$

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
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.

$\endgroup$
  • $\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
1
$\begingroup$

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)$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.