Abstract
In loosely-coupled multiprocessor systems, a parallel program has its modules distributedly assigned among the processors. The assignment policy is to minimize interprocessor communication cost and to balance the workload of processors. However, there exists conflict between these two criteria and a compromise must be made to obtain an optimal solution. In this paper, we propose a new task assignment model for distributed computing systems, and for solving the assignment problem based on partitioning graphs. The problem of finding an optimal solution had been shown to be in the class of NP-complete. For the sake of computation efficiency, we propose some heuristics for obtaining suboptimal solutions. © 1987 Taylor & Francis Group, LLC.