OPTIMAL TASK ASSIGNMENT IN HOMOGENEOUS NETWORKS

This paper considers the problem oi assigning the tasks of a distribut ed application to the processors of a distributed system such that the sum of execution and communication costs is minimized. Previous work has shown this problem to be tractable for a system of two processors or a linear array of N processors, and for distributed programs of ser ial parallel structures. Here we focus on the assignment problem on a homogeneous network, which is composed of N functionally-identical pro cessors, each with its own memory. Some processors in the network may have unique resources, such as data files or certain peripheral device s. Certain tasks may have to use these unique resources; they are call ed attached tasks. The tasks of a distributed program should therefore be assigned so as to make use of specific resources located at certai n processors in the network while minimizing the amount of interproces sor communication. The assignment problem in such a homogeneous networ k is known to be NP-hard even for N = 3, thus making it intractable fo r a network with a medium to large number of processors. We therefore focus on task assignment in general array networks, such as linear arr ays, meshes, hypercubes, and trees. We first develop a modeling techni que that transforms the assignment problem in an array or tree into a minimum-cut maximum-flow problem. The assignment problem is then solve d for a general array or tree network in polynomial time.