<p>Consider a set of processes ($P=\{p_1, p_2,\dots, p_n \}$) and their data dependencies. Each process $p_i$ has an execution runtime which is denoted by $d_i$. We are interested to parallelize these processes on $k$ processors. Note that if process $p_i$ depends on process $p_j$ (which is denoted by $p_j \rightarrow p_i$), it cannot be executed until $p_j$ is finished so it can provide the necessary data that $p_i$ requires. Moreover, if processes $p_i$ and $p_j$ are assigned to different processors and $p_i \rightarrow p_j$, there is a delay associated for moving data from one processor to another. On the other hand, if processes $p_i$ and $p_j$ are assigned to one processor $p_i \rightarrow p_j$, the data can be provided to $p_i$ in zero time.</p>

<p>Now we want to divide these processes into $k$ partitions such that the overall execution time of them (i.e., their makespan) are minimized. </p>

<p>Please note that this problem is different from the standard graph partitioning problem since we are dealing with a DAG rather than an undirected graph. "<a href="http://www.sandia.gov/~tgkolda/pubs/bibtgkfiles/Parallel-Computing-2000.pdf" rel="nofollow">Graph partitioning models for parallel computing</a>" by Hendrickson and Kolda has pointed to the aforesaid problem but does not provide any solution to it.</p>

CC BY-SA 3.0
2013-12-15T11:41:33.407Z
It's not clear to me what you want to minimize. Do you want to minimize the makespan, the average completion time, or something else?
Yoshio Okamoto
CC BY-SA 3.0
2013-12-15T18:02:50.267Z
Sorry for my careless write-up. I updated the text. Yes, I want to minimize the makespan.
Javad
CC BY-SA 3.0
2013-12-15T20:58:22.843Z
I'm not much familiar with scheduling algorithms, but you may find this paper useful: [Workflow Scheduling to Minimize Data Movement Using Multi-Constraint Graph Partitioning](http://www.hpcs.cs.tsukuba.ac.jp/~tanaka/publications/open/CCGrid2012-paper-tanaka.pdf). I think other users can provide you with more insight.
Sadeq Dousti
CC BY-SA 3.0
2013-12-16T13:39:14.847Z
Thank you. Minimizing the makespan is NP-hard, even without precedence constraints. A simple reduction of the partition problem should be found.
Yoshio Okamoto
CC BY-SA 3.0
2013-12-16T17:47:01.983Z
Yes, indeed it is an NP-hard problem. I was looking for the state-of-the-art heuristic on this problem or the best available reduction for the abovementioned problem to the standard partitioning problem.
Javad
CC BY-SA 3.0
2013-12-18T02:52:33.580Z
The paper [TrellisDAG: A System for Structured DAG Scheduling](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.9.7947&rep=rep1&type=pdf) faces a similar issue but focusses on practical aspects. Still, it may give you some ideas, or perhaps papers citing it may be relevant.
Abdallah
<graph-theory><dc.parallel-comp><partition-problem>
DAG partitioning for parallel computing
Javad
# DAG partitioning for parallel computing

(Asked by: username_0 on 2013-12-15)

Consider a set of processes ($P=\{p\_1, p\_2,\dots, p\_n \}$) and their data dependencies. Each process $p\_i$ has an execution runtime which is denoted by $d\_i$. We are interested to parallelize these processes on $k$ processors. Note that if process $p\_i$ depends on process $p\_j$ (which is denoted by $p\_j \rightarrow p\_i$), it cannot be executed until $p\_j$ is finished so it can provide the necessary data that $p\_i$ requires. Moreover, if processes $p\_i$ and $p\_j$ are assigned to different processors and $p\_i \rightarrow p\_j$, there is a delay associated for moving data from one processor to another. On the other hand, if processes $p\_i$ and $p\_j$ are assigned to one processor $p\_i \rightarrow p\_j$, the data can be provided to $p\_i$ in zero time.

Now we want to divide these processes into $k$ partitions such that the overall execution time of them (i.e., their makespan) are minimized.

Please note that this problem is different from the standard graph partitioning problem since we are dealing with a DAG rather than an undirected graph. "[Graph partitioning models for parallel computing](http://www.sandia.gov/~tgkolda/pubs/bibtgkfiles/Parallel-Computing-2000.pdf)" by Hendrickson and Kolda has pointed to the aforesaid problem but does not provide any solution to it.

**Tags:** graph-theory, dc.parallel-comp, partition-problem

> **Comments:**
> **username_1**: It's not clear to me what you want to minimize. Do you want to minimize the makespan, the average completion time, or something else?  
> **username_0**: Sorry for my careless write-up. I updated the text. Yes, I want to minimize the makespan.  
> **username_2**: I'm not much familiar with scheduling algorithms, but you may find this paper useful: [Workflow Scheduling to Minimize Data Movement Using Multi-Constraint Graph Partitioning](http://www.hpcs.cs.tsukuba.ac.jp/~tanaka/publications/open/CCGrid2012-paper-tanaka.pdf). I think other users can provide you with more insight.  
> **username_1**: Thank you. Minimizing the makespan is NP-hard, even without precedence constraints. A simple reduction of the partition problem should be found.  
> **username_0**: Yes, indeed it is an NP-hard problem. I was looking for the state-of-the-art heuristic on this problem or the best available reduction for the abovementioned problem to the standard partitioning problem.  
> **username_3**: The paper [TrellisDAG: A System for Structured DAG Scheduling](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.9.7947&rep=rep1&type=pdf) faces a similar issue but focusses on practical aspects. Still, it may give you some ideas, or perhaps papers citing it may be relevant.  

---

## 0 answers

