DocumentCode :
928094
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
Volume :
41
Issue :
3
fYear :
1992
fDate :
3/1/1992 12:00:00 AM
Firstpage :
257
Lastpage :
273
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;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/12.127439
Filename :
127439
Link To Document :
بازگشت