A Heuristic Task Allocation Scheme Based on Clustering


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 6, No. 10, pp. 2659-2669, Oct. 1999
10.3745/KIPSTE.1999.6.10.2659,   PDF Download:

Abstract

This paper proposes a heuristic, clustering based task allocation scheme applicable to non-directed task graph on a distributed system. This scheme firstly builds a task-machine graph, and then applies a clustering process wherein a pair of tasks that are connected to the highest cost edge is merged into a big one or a task is allocated to a machine. During the process, the proposed scheme figure out a machine onto which the task allocation may cause deduction of large communication overhead that has incurred between the task and tasks that are already allocated to the machine while the computation costs is slightly increased in the machine. Simulation for the various task graphs shows that the scheduling using the proposed scheme result far better than ones by using the traditional schemes. A comparison with optima task scheduling also promises that our scheme derives optimal results more occasionally than the traditional schemes do.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
K. S. Il, J. J. Nam, K. K. You, "A Heuristic Task Allocation Scheme Based on Clustering," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 6, no. 10, pp. 2659-2669, 1999. DOI: 10.3745/KIPSTE.1999.6.10.2659.

[ACM Style]
Kim Suk Il, Jeon Joong Nam, and Kim Kwan You. 1999. A Heuristic Task Allocation Scheme Based on Clustering. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 6, 10, (1999), 2659-2669. DOI: 10.3745/KIPSTE.1999.6.10.2659.