Title :
On the assignment problem of arbitrary process systems to heterogeneous distributed computer systems
Author :
Bowen, Nicholas S. ; Nikolaou, Christos N. ; Ghafoor, Arif
Author_Institution :
IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA
fDate :
3/1/1992 12:00:00 AM
Abstract :
The authors propose and evaluate an efficient hierarchical clustering and allocation algorithm that drastically reduces the interprocess communications cost while observing lower and upper bounds of utilization for the individual processors. They compare the algorithm with branch-and-bound-type algorithms that can produce allocations with minimal communication cost, and show a very encouraging time complexity/suboptimality tradeoff in favor of the algorithm, at least for a class of process clusters and their random combinations which it is believed occur naturally in distributed applications. The heuristic allocation is well suited for a changing environment, where processors may fail or be added to the system and where the workload patterns may change unpredictably and/or periodically
Keywords :
distributed databases; heuristic programming; performance evaluation; allocation algorithm; arbitrary process systems; assignment problem; branch-and-bound-type algorithms; heterogeneous distributed computer systems; heuristic allocation; hierarchical clustering; lower bounds; suboptimality tradeoff; time complexity; upper bounds; workload patterns; Aging; Application software; Clustering algorithms; Computer network management; Costs; Delay; Distributed computing; Performance analysis; Throughput; Upper bound;
Journal_Title :
Computers, IEEE Transactions on