|
Title:
|
Algorithms for Optimal Dynamic Assignment in Distributed Processing Systems |
|
Author:
|
Sinclair, J. Bartlett
|
|
Type:
|
Tech Report |
|
Keywords:
|
distributed systems; computer architecture |
|
Citation:
|
J. B. Sinclair, "Algorithms for Optimal Dynamic Assignment in Distributed Processing Systems," Rice University ECE Technical Report, no. 7912, 1979. |
|
Abstract:
|
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. |
|
Date Published:
|
1979-08-20 |
