Algorithms for Optimal Dynamic Assignment in Distributed Processing Systems
Sinclair, J. Bartlett
distributed systems; computer architecture
The problem of determining an optimal dynamic assignment of a modular program in a loosely coupled distributed processing system is considered. An optimal dynamic assignment minimizes the sum of all module execution costs, intermodule commmunication costs, and module reassignment costs. The two-processor problem is shown to be efficiently solvable through the application of a max-flow min-cut algorithm to a dynamic processor flow graph. The general p-processor problem can be solved using a dynamic programming approach which is equivalent to a simple shortest path algorithm to construct a dynamic assignment tree for the program's execution.
MetadataShow full item record
- ECE Publications