ON THE POWER OF THE LINEAR-ARRAY ARCHITECTURE FOR PERFORMING TREE-STRUCTURED COMPUTATIONS

We consider the problem of scheduling the execution of programs on the linear array architecture. A program is represented by a directed acy clic graph (dag), whose nodes represent tasks and whose edges represen t both precedence constraints and functional dependencies among tasks. We prove that, for binary tree dags with unit execution time tasks, t he linear array can simulate with constant slowdown the architecture i ndependent model of C. H. Papadimitriou and M. Yannakakis when the mes sage-to-instruction ratio is assumed to be equal to the diameter of th e linear array. (This is the interpretation im plied in their article. ) Furthermore, we prove that for binary tree dags with unit execution time tasks the linear array is strictly more powerful than the above i nterpretation of their model, Using our simulation result, we give pol ynomial time algorithms to find schedules for binary tree dags with n tasks and height h on linear arrays, when h greater than or equal to n (1/2) log n (achieving makespan O(h)), and when h less than or equal t o n(1/2-epsilon) for any fixed epsilon > 0 (achieving makespan O(n(1/2 )), where the constant inside the O depends on epsilon). The makespan achieved by our schedules is within a constant factor of optimal, The time-processors product achieved is within a constant factor of optima l when h less than or equal to n(1/2-epsilon) , and within an O(log n) factor of optimal when h greater than or equal to n(1/2)log n. These schedules improve upon the makespan of the schedules of D. Ghosal and coworkers by an O(log n) factor for those ranges of h, and at the same time also improve upon.their time-processors product by an O(log n) f actor (for h less than or equal to n(1/2-epsilon) or maintain their sa me time-processors product up to a constant (for h greater than or equ al to n(1/2) log n). Further, for h less than or equal to n(1/2)/log(2 ) n, We provide a polynomial time computable schedule on a linear arra y that achieves makespan O(n(1/2)), using O(n(1/2)) processors (i.e., both optimal up to a constant), this time under an assumption that lin ks have unlimited bandwidth. Using straightforward arguments as in D. Ghosal and co-workers', we extend some of our polynomial time scheduli ng algorithms to deal with the more general case, where the trees have bounded degree d, and the architecture is a k-dimensional mesh. (C) 1 995 Academic Press, Inc.