1
$\begingroup$

I have a directed acyclic graph. Where each node is a task and each edge denotes a dependency. enter image description here

I want a method to effectively parallelize these tasks. One way would be to topological sort them based on depth. Node a which has no precedents will have depth 0. For other nodes, depth will be the depth of precedent with the highest depth +1. Like in the answer provided in this stack exchange question. But here I am not sure if we can get the most amount of parallelization. Tasks in each depth can be run in parallel. But to start processing tasks in a particular depth. All tasks in previous depth should be completed.

Then I came across the idea of transitive reduction of a DAG. transitive reduction of input graph

Transitive reduction reduces extra edges such that the same reach-ability relation in the original graph is maintained. Does this mean that transitive reduction is implicitly topological sorted? Does doing bfs over a transitively reduced task graph and executing tasks as they come in the bfs order equivalent to topological order?. For the input graph and its transitive reduced version, they seem equivalent. I don't know if there are any cases I am missing. What I want is a way to parallelize a task graph with maximum throughput.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I do not know whether I fully understand what you are asking for. So, let me start with a simple graph. It has only two paths from top node $a$ to bottom node $b$: path $a-c-d-e-b$ and $a-f-b$. Then with BFS node $b$ will be found before node $e$, and that is not what one wants in a topsort. So, I do not think that BFS is suitable to find a topsort, even as in this case where the graph is a Hasse diagram. $\endgroup$
    – Hendrik Jan
    Jul 25, 2021 at 22:06

1 Answer 1

Reset to default
0
$\begingroup$

Yes, using the approach you sketched based on topological sorting gives you the maximum throughput, assuming you have an unlimited number of processes (there is no limit on the number of tasks you can solve in parallel).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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