EFFICIENT ALGORITHMS FOR MAPPING AND PARTITIONING A CLASS OF PARALLEL COMPUTATIONS

We address the problem of mapping task graph modules to processors in a parallel machine. A mapping seeks to minimize the maximum load assigned to a processor, a metric which often determines the completion time of the entire task. We consider a special case where the task graph is a chain of modules and the processors communicate through a linear array interconnection network. We first present an O(mp) algorithm to optimally map a chain of m modules onto a linear array of p processors. This algorithm provides an improvement over the hitherto best known complexity for this problem, O(mp log m). We then address the problem of mapping n independent tasks, where each is a chain of m modules, onto a partitionable architecture consisting of a linear array of p processors and a host processor. We provide polynomial time algorithms for three different instances of this problem. © 1993 Academic Press, Inc.