Park Chee Hang, Kim Joo Man, Lee Cheol Hoon

The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 5, No. 2, pp. 323-334, Feb. 1998
10.3745/KIPSTE.1998.5.2.323,   PDF Download:

Abstract

This paper deals with the static task-assignment problem in a distributed computing system. In assigning tasks, we have to persue maximization of load balancing and minimization of interprocessor communication(IPC) simultaneously. However, since these two goals conflict each other, one has to make a compromise between them according to the given task type. Most of the existing approaches minimize IPC subject to constraints on the degree to which the processors' loads are balances. Since they consider the minimization of IPC as the only objective while using load balancing just as a constraint, it is difficult to make a tradeoff between IPC and load balancing. However, it is desirable to simultaneously balance loads and minimize IPC by making an optimal tradeoff between the two conflicting goals. We therefore propose a new cost function to evaluate static task assignments, explicitly describing the tradeoff between the two goals. The variance statistics of load distribution are used to represent the degree of load balancing among the processors for a given assignment. Also suggested is a policy which enables the system designer to make a tradeoff between the two goals by systematically adjusting a weighting factor. It is shown that the task-assignment problem can be transformed into the minimum N-cut problem using a graph modification technique. We propose a heuristic algorithm for solving the transformed problem. Simulation results show that our approach outperforms an existing representative approach for a variety of task and processing systems.

Statistics
Cite this article