Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Upper and Lower Bounds on the Makespan of Schedules for Tree Dags on Linear Arrays
| |
|
Upper and Lower Bounds on the Makespan of Schedules for Tree Dags on Linear Arrays
K. Kalpakis1 and Y. Yesha1
| (1) |
Department of Computer Science and Electrical Engineering, University of Maryland Baltimore County, 1000 Hilltop Circle,
Baltimore, MD 21250, USA. kalpakis@cs.umbc.edu, yayesha@cs.umbc.edu., US |
| (2) |
Institute for Advanced Computer Studies, University of Maryland at College Park, College Park, MD 20742, USA.
, US |
Abstract. 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+ . We also find, in polynomial time, schedules for bounded tree dags with n unit execution time tasks, degree d , and height 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.
Key words. Multiprocessing, Parallel computation, Parallel architectures, Communication delay, Scheduling, Tree dags, Linear
array, Mesh array, Tree decomposition.
Received January 21, 1997; revised June 5, 1997.
Fulltext Preview (Small, Large)
|
|
|
|
|
|