Optimal architecture-independent scheduling of fine-grain tree-sweep computations

We present algorithms for optimally scheduling computations that comprise a sequence of complete up- and/or down-sweeps on a complete binary tree, on a parallel architecture in which the communication delay between any two processors is uniform. Such computations include, for instance, those that implement broadcast, accumulation, and the parallel-prefix operator; such architectures include, for instance, networks of workstations. Our schedules are optimal in the sense of having the actual minimum time-to-completion-not just on approximation thereof-considering the time for both computation and communication. We concentrate on schedules for fine-grain tree-sweep computations-wherein communication costs are rather large relative to per-task computation cost