Seo Kyung ryong, Yeo Jeong mo

The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 5, No. 5, pp. 1151-1161, May. 1998
10.3745/KIPSTE.1998.5.5.1151,   PDF Download:

Abstract

In this paper, we are considering a heterogeneous processor system in which each processor may have different performance and reliability characteristics. In other to fully utilize this diversity of processing power it is advantageous to assign the program modules of a distributed program to the processors in such a way that the execution time of the entire program is minimized. This assignment of tasks to processors to maximize performance is commonly called load balancing, since the overloaded processors can perform their own processing with the performance degradation. For the task assignment problem, we propose a new objective function which formulates this imbalancing cost. Thus the task assignment problem is to be carried out so that each module is assigned to a processor whose capabilities are most appropriate for the module, and the total cost is minimized that sum of inter-processor communication cost and execution cost and imbalance cost of the assignment. To find optimal assignment is known to be NP-hard, and thus we proposed an efficient heuristic algorithm with time complexity O(n^2m) in case of m task modules and n processors.

Statistics
Cite this article