Hybrid genetic algorithm for independent tasks scheduling in heterogeneous computing systems
-
摘要: 有效的任务调度是异构计算系统获取高性能的关键因素之一,由于任务调度问题是NP-困难的,为了获取尽可能好的解,文献中存在许多启发式调度算法.针对异构计算系统的独立任务调度问题,基于遗传算法和最小完成时间算法MCT(Minimum Completion Time),提出一种新的混合遗传算法,它采用遗传算法来进化任务调度的优先队列,然后再使用MCT算法把优先队列解码为一个有效的调度,与文献中其它算法进行比较表明,它不但能产生更好的调度结果,而且有很好的收敛速度.Abstract: Efficient tasks scheduling is critical for achieving high performa nce in heterogeneous computing systems. The tasks scheduling problem is NP-hard in general. In order to obtain better solutions, many scheduling heuristics were presented in the literature. Based on genetic algorithm and MCT(minimum complet ion time) algorithm, a new hybrid genetic algorithm was presented for independe nt tasks scheduling in heterogeneous computing systems. Genetic algorithm was us ed to evolve a priority queue first, and then the priority queue was mapped to a schedule using MCT algorithm. The simulation results comparing with other sched uling algorithm show that it produces better results in terms of schedule length , and it has good convergent speed.
-
[1] Armstrong R, Hensgen D, Kidd T. The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions . In:7th IEEE Heterogeneous Computing Workshop , 1998. 79~87 [2]Freund R, Gherrity M, Ambrosius S, et al. Scheduling resources in multi-user, heterogeneous, computing environments with SmartNet . In:7th IEEE Heterogeneous Computing Workshop , 1998. 184~199 [3]Ibarra O, Kim C. Heuristic algorithms for scheduling independent tasks on nonidentical processors[J]. Journal of the ACM, 1977, 77(2):280~289 [4]Wang L, Siegel H J, Roychowdhury V P, et al. Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based a pproach[J]. Journal of Parallel and Distributed Computing, 1997, 47(1):1~15 [5]Braun T, Siegel H, Beck N, et al. A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems . In:8th IEEE Heterogeneous Computing Workshop , 1999. 15~29 [6]Wu Minyou, Shu Wei, Zhang Hong. Segmented Min-min:a static mapping algorithm for meta-tasks on heterogeneous computing systems . In:9th IEEE He terogeneous Computing Workshop , 2000. 375~385 [7] 李敏强, 寇纪淞, 林 丹,等. 遗传算法的基本理论与应用[M]. 北京:科学出版社, 2002 Li Minqiang, Guan Jisong, Lin Dan, et al. The basic theory and application of genetic algorithm[M]. Beijing:Science Press, 2002(in Chinese) -
点击查看大图
计量
- 文章访问数: 2904
- HTML全文浏览量: 181
- PDF下载量: 1061
- 被引次数: 0
下载:
