HODW ASSIG- IN DISIBIBUlED SYSlEYs
J. B. Sjnclair · 1984
The problem of finding a n optimal assignment of a modular program for n processors in a distributed system is studied. We characterize t he distributed programs by Stone's graph model, and attempt to find an assignment of modules to processors which minimizes the sum of module execution costs and intermodule communication costs. The problem is NP-complete for more than three processors. We first show how to identify all modules which must be assigned to a particular processor under any optimal assignment. This u sually results in a significant reduction in the complexity of the optimal assignment problem. We also present a heuristic algorithm for finding assignments and experimentally verify t hat it almost always finds an optimal assignment.