On the Assignment Problem of Arbitrary Process Systems to Heterogeneous Distributed Computer Systems

Abstract

In distributed computer systems, the mapping of the distributed applications onto the processors has to be achieved in such a way so that the performance goals of the applications (response time, throughput) are met. Balancing the load of the applications among the processors of the distributed system can increase the overall throughput. However, if highly interacting processes are assigned to different processors, overall throughput may suffer because of the communication overhead. We propose and evaluate an efficient hierarchical clustering and allocation algorithm that drastically reduces the interprocess communication cost while observing lower and upper bounds of utilization for the individual processors. We compare the algorithm with branch-and-bound-type algorithms that can produce allocations with minimal communication cost, and we show a very encouraging time complexity/suboptimality tradeoff in favor of our algorithm, at least for a class of process clusters and their random combinations, which we believe occur naturally in distributed applications. Our 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. © 1992 IEEE