3
$\begingroup$

I've been researching ways of modeling and executing tasks which are dependent on each other (but in an acyclic way) and came up with task graphs. But the question that's bugging me is how can I find out the maximum degree of concurrency in a given task graph.

In my case, I'm talking of a relatively small graph, around 100 nodes, but nodes, representing tasks, are long running tasks. So the occuracy, more then complexity of such an algorithm would matter.

Assuming I came up of such a degree, the second problem, is how should I distrubute tasks? I've read about topological sort, and transforming the result in a list of sets, with each set being run in parallel. But again, I suspect if this is the best approach.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Have you looked at make? It exactly does what you want--execute dependent tasks in parallel. $\endgroup$ – adrianN Nov 8 '13 at 15:11
5
$\begingroup$

If you turn an activity-on-node task graph into a partial order (by taking the transitive closure), then the largest independent set of tasks is what you are looking for.

(Taking a topological sort, as suggested in another answer, does not work in general. Consider the series-parallel task graph $((a|b)c)|(d(e|f))$, where $\alpha|\beta$ means parallel composition of task graphs and $\alpha\beta$ means every task in task graph $\alpha$ precedes every task in task graph $\beta$. Here $\{a,b,e,f\}$ is the largest independent set, yet the topological sort will produce $\{a,b,d\}$.)

Although finding largest independent sets is NP-complete in general, it can be done quickly for partial orders. This starts by noting the equivalence of an independent set in a poset with a set of witnesses that realise the width of the poset, and applying König's theorem to compute the witnesses by a perfect matching.

Some of these basic algorithms are already part of software toolkits, like the Graph CPAN module for Perl, and the Boost Graph Library for C++.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks. I suspect asking for more clarification on your first paragraph wouldn't do much help given the depth of the discussion you provided as a link for partial orders. It's apparent that I lack the knowledge on the field and there is no ready solution for it. I'll work on it. $\endgroup$ – SelimOber Nov 8 '13 at 23:29
  • $\begingroup$ Anyway, topological sort would give the execution schedule $\{a,b,d\}, \{c,e,f\}$ while aiming for the four-element set you propose yields $\{d\}, \{a,b,e,f\}, \{c\}$. I would certainly prefer the former schedule; it's done earlier (assuming uniform durations) and requires less machines. (This may relate to my above comment: do we want to maximise the number of concurrent task that occur, or maximise the minimum number of concurrent tasks? I'd say the latter is more reasonable, which your example supports.) $\endgroup$ – Raphael♦ Nov 9 '13 at 15:09
  • $\begingroup$ @Raphael: Clearly a level-based approach is preferable as a greedy scheduling strategy, and can be implemented easily (answering the second part of the question). My answer addresses the maximum parallelism, which seems to be what the OP is asking in the first part. $\endgroup$ – András Salamon Nov 9 '13 at 15:33
2
$\begingroup$

Running a topological sort on the graph is the right thing to do. Topological sorting is just the linear time version of the following very simple greedy approach:

while there are nodes left:
    let S be the set of all nodes with indegree 0
    run all tasks in S in parallel
    remove all nodes in S from the graph

(I use the convention that Task A depends on Task B if there is an edge B->A)

It's fairly obvious that you can't do better than the above algorithm, and the maximum concurrency you can achieve is the size of the largest S that you encounter.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Wouldn't the concurrency be limited by the minimum S encountered? (Matter of semantics, probably.) $\endgroup$ – Raphael♦ Nov 9 '13 at 15:05
  • $\begingroup$ In terms of number of processors you can reasonably use, the maximum is important. In terms of speedup, the longest dependence chain matters. $\endgroup$ – adrianN Nov 11 '13 at 10:36
  • 1
    $\begingroup$ While it is true that topological sort corresponds to greedy work-preserving scheduling, and is generally a good practical approach, it does not correspond to the maximum concurrency. One can often do better by finding the largest independent set in the transitive closure of the task graph; the largest set of tasks at any level of breadth-first search is an independent set but may not be the largest one. However, only quite artificial workloads are likely to actually allow use of any additional such concurrency. $\endgroup$ – András Salamon Dec 12 '13 at 6:33
1
$\begingroup$

Since you stated that, by hypothesis, your task dependency graph is acyclic, you can easily determine the maximum degree of concurrency by running the breadth-first search algorithm. The algorithm starts from the root node (if the initial level contains more then one node then any node can be chosen as the root node) and proceeds towards the leafs level-wise: before inspecting nodes located on the next level it explores all of the nodes belonging to the same level. Just modify it trivially to count the number of nodes on each level, and update a variable holding the maximum number of nodes per level as the algorithms descends through the levels. The worst-case complexity is $O(V + E)$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ See the counterexample in my answer; breadth-first search gives 3 vertices on each level while there may actually be 4 tasks active at once. $\endgroup$ – András Salamon Dec 8 '13 at 2:54
  • $\begingroup$ Andras, your answer covers the general case, in which you may have parallel composition of several task graphs; but the OP asked for just one task graph, a small one with about 100 nodes. I think it's good for him to know how to deal with both the general case, and his simple, particular case. $\endgroup$ – Massimo Cafaro Dec 8 '13 at 8:06
  • $\begingroup$ I don't follow. I gave a six-task acyclic and series-parallel task graph for which your approach does not work. $\endgroup$ – András Salamon Dec 8 '13 at 16:11
  • $\begingroup$ Andras, may be I am not understanding correctly your notation, but I understood that you are dealing in your example with the composition of two task dependency graphs, not one. If I am wrong, then you are, of course, right ;-) $\endgroup$ – Massimo Cafaro Dec 9 '13 at 16:31
  • $\begingroup$ You can always add a start and an end task, if your notion of task graph is PERT-ish and insists on this restriction: $s(((a|b)c)|(d(e|f)))t$. As before, an independent set of 4 tasks is $\{a,b,e,f\}$, whereas breadth-first yields 3, either $\{a,b,d\}$ or $\{c,e,f\}$. $\endgroup$ – András Salamon Dec 10 '13 at 23:27

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.