2
$\begingroup$

Suppose we have a DAG of tasks:

enter image description here

Arrows represent flow (reversed dependencies: 8 must be run after 7). Some of the tasks (like 4, 5, 6) can be run in parallel (Par block). Dependent tasks (like 7, 8, 9) must be run sequentially (Seq block).

I need to parse this DAG into recursive structure of Seq and Par blocks (collections). DAG from the image above may be represented by the following structure:

Seq(
    1,
    2,
    Par(
        Seq(7, 8, 9),
        Seq(
            3,
            Par(4, 5, 6),
            10
        )
    )
)

Each DAG may be represented by a set of Seq-Par structures. I want to search for the most optimal. Optimality criteria — run in parallel as much as possible (without breaking dependencies).

More on optimality criteria: all tasks' have the same execution time T. Execution time of Seq(1, 2 ... N) equals to N * T. Par(1, 2 ... N) = T.

I believe, that this task is pretty well-known and simple. Can you, please, name some algorithm solving this problem.

If we add edge from 7 to 4 (proposal from comments), then one of representations may be:

Seq(
    1,
    2,
    Par(
        7,
        3
    ),
    Par(
        Seq(8, 9),
        Seq(
            Par(4, 5, 6),
            10
        )
    )
)
$\endgroup$
17
  • 4
    $\begingroup$ You might need to look in to topological sorting. $\endgroup$ Jul 13 '15 at 19:02
  • 1
    $\begingroup$ I doubt topological sorting is any help here. --- Is the DAG defined as a set of ordered pairs? --- What came to mind is there might be a connection with intervals as used in dataflow analysis, though it is for directed graphs, not just DAGs. $\endgroup$
    – babou
    Jul 13 '15 at 20:18
  • 4
    $\begingroup$ Is this even possible? If you add an edge from 7 to 4 in your example, how would it be represented? $\endgroup$ Jul 13 '15 at 20:45
  • 3
    $\begingroup$ If 4, 5 and 6 had a single child each which connects with 10, would you want Par(Seq(4,4'), Seq(5,5'), Seq(6,6')) or Seq(Par(4,5,6),Par(4',5',6'))? Or, putting the question differently: what's an unambiguous definition of your mapping? (If you have that, the algorithm is likely immediate.) $\endgroup$
    – Raphael
    Jul 13 '15 at 21:21
  • 1
    $\begingroup$ Finding the best schedule may not be simple. Scheduling dags to minimize time and communication by Afrati et al. may be a helpful reference. $\endgroup$
    – Raphael
    Jul 14 '15 at 13:50
1
$\begingroup$

Your problem is equivalent to scheduling unit-time tasks on infintely many machines with precedence constraints (which are by necessity DAGs) minimizing the maximum completion time. In scheduling literature, this is called project scheduling and also denoted as $P_{\infty} \mid \text{prec} \mid C_{\max}$.

This problem is known to be amenable to the critical path method (CPM) which creates an optimal schedule in time $O(n^2)$, $n$ the number of tasks.

Given a schedule $s : \mathbb{N}^2 \to T$ that maps pairs of time slot and machine indices to tasks, you can derive a tree consistent with the precedence DAG of the form

$\qquad\displaystyle \mathrm{Seq}\bigl( \mathrm{Par}(s(1,1), \dots, s(1,i_{1})),\ \dots,\ \mathrm{Par}(s(t,1), \dots, s(t,i_{t}))\bigr)$;

here, $t$ is the time of the last scheduled task, and $i_j$ is the maximum index of busy machines at time $j$. (I assume that at any given time $j$, machines $1, \dots, i_j$ are busy and $i_j+1, \dots$ idle.)

If that schedule is optimal, the tree is, too. It does not hold information about the original DAG, though.

$\endgroup$
4
  • $\begingroup$ In simple words, I can find critical path, map it to time slots, spread all remaining tasks with respect to their dependencies (and this operation won't add more slots, because of critical path properties). Easily convert these time slots into single sequence: if there is single task in slot t, I just add it. If many — I wrap them into Par block. $\endgroup$ Jul 14 '15 at 14:57
  • $\begingroup$ "If that schedule is optimal" — in my case of unlimited machines and all tasks taking the same time to run, I guess, I'll always have optimal schedules through CP method? $\endgroup$ Jul 14 '15 at 15:00
  • $\begingroup$ @Oroboros102 Yes, I should have made that clearer. $\endgroup$
    – Raphael
    Jul 14 '15 at 15:08
  • $\begingroup$ Mere words on CPM: algs4.cs.princeton.edu/44sp $\endgroup$ Jul 17 '15 at 13:04

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.