Algorithms for Optimal Dynamic Assignment in Distributed Processing Systems

Tech ReportThe 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