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" by Hendrickson and Kolda has pointed to the aforesaid problem but does not provide any solution to it.

  • 2
    $\begingroup$ 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? $\endgroup$ – Yoshio Okamoto Dec 15 '13 at 11:41
  • $\begingroup$ Sorry for my careless write-up. I updated the text. Yes, I want to minimize the makespan. $\endgroup$ – Javad Dec 15 '13 at 18:02
  • 2
    $\begingroup$ 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. I think other users can provide you with more insight. $\endgroup$ – M.S. Dousti Dec 15 '13 at 20:58
  • $\begingroup$ Thank you. Minimizing the makespan is NP-hard, even without precedence constraints. A simple reduction of the partition problem should be found. $\endgroup$ – Yoshio Okamoto Dec 16 '13 at 13:39
  • 1
    $\begingroup$ The paper TrellisDAG: A System for Structured DAG Scheduling faces a similar issue but focusses on practical aspects. Still, it may give you some ideas, or perhaps papers citing it may be relevant. $\endgroup$ – Abdallah Dec 18 '13 at 2:52

Your Answer

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

Browse other questions tagged or ask your own question.