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 acyclic graph (dag), whose nodes represent tasks and whose edges represent both precedence constraints and functional dependencies among tasks. We prove that, for binary tree dags with unit execution time tasks, the linear array can simulate with constant slowdown the architecture independent model of C. H. Papadimitriou and M. Yannakakis when the message-to-instruction ratio is assumed to be equal to the diameter of the 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 interpretation of their model. Using our simulation result, we give polynomial time algorithms to find schedules for binary tree dags with n tasks and height h on linear arrays, when h ≥ n12 log n (achieving makespan O(h)), and when h ≤ n12-ϵ for any fixed ϵ > 0 (achieving makespan O(n12), where the constant inside the O depends on ϵ). The makespan achieved by our schedules is within a constant factor of optimal. The time-processors product achieved is within a constant factor of optimal when h ≤ n12-ϵ , and within an O(log n) factor of optimal when h ≥ n12log 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) factor (for h ≤ n12-ϵ or maintain their same time-processors product up to a constant (for h ≥ n12 log n). Further, for h ≤ n12/log2n, We provide a polynomial time computable schedule on a linear array that achieves makespan O(n12), using O(n12) processors (i.e., both optimal up to a constant), this time under an assumption that links have unlimited bandwidth. Using straightforward arguments as in D. Ghosal and co-workers′, we extend some of our polynomial time scheduling algorithms to deal with the more general case, where the trees have bounded degree d, and the architecture is a k-dimensional mesh.