Minimum Distance: A Method for Partitioning Recurrences for Multiprocessors

Abstract

We consider parallel execution of nonvectorizable uniform recurrences. When naively scheduled, such recurrences could create unacceptable communication and synchronization on a multiprocessor. The minimum-distance method partitions such recurrences into totally independent computations without increasing redundancy or perturbing numerical stability. The independent computations are well-suited for execution on a multiprocessor, but they may not utilize all available processors. We address how extra processors can be applied to the independent computations. Our methods are especially attractive for multiprocessors comprised of clusters. © 1989 IEEE