Upper and lower bounds on the makespan of schedules for tree dags on linear arrays
We find, in polynomial time, a schedule for a complete binary tree directed acyclic graph (dag) with n unit execution time tasks on a linear array whose makespan is optimal within a factor of 1 + o(1). Further, given a binary tree dag T with n tasks and height h, we find, in polynomial time, a schedule for T on a linear array whose makespan is optimal within a factor of 5 + o(1). On the other hand, we prove that explicit lower and upper bounds on the makespan of optimal schedules of binary tree dags on linear arrays differ at least by a factor of 1 + root 2/2. We also find, in polynomial time, schedules for bounded tree dags with n unit execution time tasks, degree d, and height h is an element of o(n(1/2)) boolean OR omega(n(1/2)) on a linear array which are optimal within a factor of 1 + o(1), this time under the assumption of links with unlimited bandwidth. Finally, we compute an improved upper bound on the makespan of an optimal schedule for a tree dag on the architecture independent model of Papadimitriou and Yannakakis [14], provided that its height is not too large.
scheduling tree dags linear array multiprocessing parallel computation parallel architectures communication delay mesh array tree decomposition