异构多核计算系统的Codelet任务调度策略
|
摘要
Codelet数据流计算模型在处理大规模并行计算任务时效果显著,但该模型目前缺少在异构多核环境中的任务调度策略。因此,提出了一种在异构多核环境下基于蚁群算法的Codelet任务调度策略。该调度策略将启发式算法与蚁群算法相融合,在发挥各自优势的同时克服了启发式算法不能得出最优解的缺陷以及蚁群算法初始信息匮乏的问题。实验结果表明,智能蚁群任务调度策略相比Codelet运行时系统中原生的动态调度和静态调度策略具有更高的执行效率。
Codelet dataflow model has significant effects on gaining high performance of computing large-scale parallel tasks,but the model currently lacks scheduling policy in heterogeneous multi-core environment. Regarding to this issue,this paper proposed a Codelet task scheduling strategy by fusing ant colony algorithm with a heuristic approach in heterogeneous multicore environment. It had both advantages of the heuristic algorithm and ant colony algorithm,and it overcame both defects of the heuristic algorithm that could not derive an optimal solution and the defects of the ant colony algorithm that was lack of the initial information. The experimental result shows,the smart ant colony scheduling policy is much more efficient than the native dynamic and static scheduling policies in the runtime system implementation of the Codelet model.
Codelet dataflow model has significant effects on gaining high performance of computing large-scale parallel tasks,but the model currently lacks scheduling policy in heterogeneous multi-core environment. Regarding to this issue,this paper proposed a Codelet task scheduling strategy by fusing ant colony algorithm with a heuristic approach in heterogeneous multicore environment. It had both advantages of the heuristic algorithm and ant colony algorithm,and it overcame both defects of the heuristic algorithm that could not derive an optimal solution and the defects of the ant colony algorithm that was lack of the initial information. The experimental result shows,the smart ant colony scheduling policy is much more efficient than the native dynamic and static scheduling policies in the runtime system implementation of the Codelet model.
引文
[1]Dennis J B.First version of a data flow procedure language[C]//Proc of Symposium Programming.Berlin:Springer,1974:362-376.
[2]Yazdanpanah F,Alvarez-Martinez C,Jimenez-Gonzalez D,et al.Hybrid dataflow/Von-Neumann architectures[J].IEEE Trans on Parallel and Distributed Systems,2014,25(6):1489-1509.
[3]Grafe V G,Hoch J E,Davidson G S.Eps’88:combining the best features of Von Neumann and dataflow computing[R].Albuquerque:Sandia National Labs,1989.
[4]Zuckerman S,Suetterlein J,Knauerhase R,et al.Using a“codelet”program execution model for exascale machines:position paper[C]//Proc of the 1st International Workshop on Adaptive Self-Tuning Computing Systems for the Exaflop Era.New York:ACM Press,2011:64-69.
[5]Suettlerlein J,Zuckerman S,Gao G R.An implementation of the Codelet model[M]//Wolf F,Mohr B,Mey D.Euro-Par 2013 Parallel Processing Workshops.Berlin:Springer.2013:633-644.
[6]Suetterlein J.DARTS:a runtime based on the Codelet execution model[D].Delaware:University of Delaware,2014.
[7]Pei Songwen,Wang Jinkai,Cui Wenyang,et al.Codelet scheduling by genetic algorithm[C]//Proc of IEEE Trustcom/Big Data SE/ISPA.Piscataway,NJ:IEEE Press,2016:1492-1499.
[8]Kumar R,Tullsen D M,Jouppi N P,et al.Heterogeneous chip multiprocessors[J].IEEE Computer,2005,38(11):32-38.
[9]Augonnet C,Thibault S,Namyst R,et al.Star PU:a unified platform for task scheduling on heterogeneous multicore architectures[J].Concurrency and Computation:Practice and Experience,2011,23(2):187-198.
[10]赵国亮,李云飞,王川.异构多核系统任务调度算法研究[J].计算机工程与设计,2014,35(9):3099-3106.(Zhao Guoliang,Li Yunfei,Wang Chuan.Research on task scheduling in heterogeneous multi-core system[J].Computer Engineering and Design,2014,35(9):3309-3106.)
[11]裴颂文,宁静,张俊格.CPU-GPU异构多核系统的动态任务调度算法[J].计算机应用研究,2016,33(11):3315-3319.(Pei Songwen,Ning Jing,Zhang Junge.Dynamic task scheduling algorithm based on CPU-GPU heterogeneous multi-core system[J].Application Research of Computers,2016,33(11):3315-3319.)
[12]Topcuoglu H,Hariri S,Wu M.Performance-effective and low-complexity task scheduling for heterogeneous computing[J].IEEE Trans on Parallel and Distributed Systems,2002,13(3):260-274.
[13]Chiang Chuanwen,Huang Yuqing,Wang Yuqing.Ant colony optimization with parameter adaptation for multi-mode resource-constrained project scheduling[J].Journal of Intelligent and Fuzzy Systems,2008,19(4):345-358.
[14]Chiang Chuanwen,Lee Y C,Lee C N,et al.Ant colony optimisation for task matching and scheduling[J].IEE Proceedings-Computers and Digital Techniques,2006,153(6):373-380.
[15]Li Min,Wang Hui,Li Ping.Tasks mapping in multi-core based system:hybrid ACO&GA approach[C]//Proc of the 5th International Conference on ASIC.Piscataway,NJ:IEEE Press,2003:355-340.
[16]Tobita T,Kasahara H.A standard task graph set for fair evaluation of multiprocessor scheduling algorithms[J].Journal of Scheduling,2002,5(5):379-394.
[2]Yazdanpanah F,Alvarez-Martinez C,Jimenez-Gonzalez D,et al.Hybrid dataflow/Von-Neumann architectures[J].IEEE Trans on Parallel and Distributed Systems,2014,25(6):1489-1509.
[3]Grafe V G,Hoch J E,Davidson G S.Eps’88:combining the best features of Von Neumann and dataflow computing[R].Albuquerque:Sandia National Labs,1989.
[4]Zuckerman S,Suetterlein J,Knauerhase R,et al.Using a“codelet”program execution model for exascale machines:position paper[C]//Proc of the 1st International Workshop on Adaptive Self-Tuning Computing Systems for the Exaflop Era.New York:ACM Press,2011:64-69.
[5]Suettlerlein J,Zuckerman S,Gao G R.An implementation of the Codelet model[M]//Wolf F,Mohr B,Mey D.Euro-Par 2013 Parallel Processing Workshops.Berlin:Springer.2013:633-644.
[6]Suetterlein J.DARTS:a runtime based on the Codelet execution model[D].Delaware:University of Delaware,2014.
[7]Pei Songwen,Wang Jinkai,Cui Wenyang,et al.Codelet scheduling by genetic algorithm[C]//Proc of IEEE Trustcom/Big Data SE/ISPA.Piscataway,NJ:IEEE Press,2016:1492-1499.
[8]Kumar R,Tullsen D M,Jouppi N P,et al.Heterogeneous chip multiprocessors[J].IEEE Computer,2005,38(11):32-38.
[9]Augonnet C,Thibault S,Namyst R,et al.Star PU:a unified platform for task scheduling on heterogeneous multicore architectures[J].Concurrency and Computation:Practice and Experience,2011,23(2):187-198.
[10]赵国亮,李云飞,王川.异构多核系统任务调度算法研究[J].计算机工程与设计,2014,35(9):3099-3106.(Zhao Guoliang,Li Yunfei,Wang Chuan.Research on task scheduling in heterogeneous multi-core system[J].Computer Engineering and Design,2014,35(9):3309-3106.)
[11]裴颂文,宁静,张俊格.CPU-GPU异构多核系统的动态任务调度算法[J].计算机应用研究,2016,33(11):3315-3319.(Pei Songwen,Ning Jing,Zhang Junge.Dynamic task scheduling algorithm based on CPU-GPU heterogeneous multi-core system[J].Application Research of Computers,2016,33(11):3315-3319.)
[12]Topcuoglu H,Hariri S,Wu M.Performance-effective and low-complexity task scheduling for heterogeneous computing[J].IEEE Trans on Parallel and Distributed Systems,2002,13(3):260-274.
[13]Chiang Chuanwen,Huang Yuqing,Wang Yuqing.Ant colony optimization with parameter adaptation for multi-mode resource-constrained project scheduling[J].Journal of Intelligent and Fuzzy Systems,2008,19(4):345-358.
[14]Chiang Chuanwen,Lee Y C,Lee C N,et al.Ant colony optimisation for task matching and scheduling[J].IEE Proceedings-Computers and Digital Techniques,2006,153(6):373-380.
[15]Li Min,Wang Hui,Li Ping.Tasks mapping in multi-core based system:hybrid ACO&GA approach[C]//Proc of the 5th International Conference on ASIC.Piscataway,NJ:IEEE Press,2003:355-340.
[16]Tobita T,Kasahara H.A standard task graph set for fair evaluation of multiprocessor scheduling algorithms[J].Journal of Scheduling,2002,5(5):379-394.