MODULE ASSIGNMENT IN DISTRIBUTED SYSTEMS. Conference Paper uri icon

abstract

  • The problem of finding an optimal assignment of a modular program for n processors in a distributed system is studied. The authors characterize the distributed programs by H. S. Stone's graph model (1977) and attempt to find an assignment of modules to processors that minimizes the sum of module execution costs and intermodule communication costs. The problem is NP-complete for more than three processors. They first show how to identify all modules that must be assigned to a particular processor under any optimal assignment. This usually results in a significant reduction in the complexity of the optimal assignment problem. They also present a heuristic algorithm for finding assignments and experimentally verify that it almost always finds an optimal assignment.

published proceedings

  • Proceedings - Computer Networking Symposium

author list (cited authors)

  • Lu, M., & Sinclair, J. B.

complete list of authors

  • Lu, M||Sinclair, JB

publication date

  • December 1984