Comparison of Genetic Algorithms and Simulated Annealing for Multiprocessor Task Allocation


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 6, No. 9, pp. 2311-2319, Sep. 1999
10.3745/KIPSTE.1999.6.9.2311,   PDF Download:

Abstract

We present two heuristic algorithms for the task allocation problem (NP-complete problem) in parallel computing. The problem is to find an optimal mapping of multiple communicating tasks of a parallel program onto the multiple processing nodes of a distributed-memory multicomputer. The purpose of mapping these tasks into the nodes of the target architecture is the minimization of the parallel execution time without sacrificing solution quality. Many heuristic approaches have been employed to obtain satisfactory mapping. Our heuristics are based on genetic algorithms and simulated annealing. We formulate an objective function as a total computational cost for a mapping configuration, and evaluate the performance of our heuristic algorithms. We compare the quality of solutions and times derived by the random, greedy, genetic, and annealing algorithms. Our experimental findings from a simulation study of the allocation algorithms are presented.


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]
P. K. Mo, "Comparison of Genetic Algorithms and Simulated Annealing for Multiprocessor Task Allocation," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 6, no. 9, pp. 2311-2319, 1999. DOI: 10.3745/KIPSTE.1999.6.9.2311.

[ACM Style]
Park Kyeong Mo. 1999. Comparison of Genetic Algorithms and Simulated Annealing for Multiprocessor Task Allocation. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 6, 9, (1999), 2311-2319. DOI: 10.3745/KIPSTE.1999.6.9.2311.