并行任务图的优化调度算法
|
摘要
科学与工程计算中的很多复杂应用问题需要使用科学工作流技术,超算领域中的科学工作流常以并行任务图建模,并行任务图的有效调度对应用的高效执行有重要意义。给出了资源限制条件下并行任务图的调度模型;针对Fork-Join类并行任务图给出了若干最优化调度结论;针对一般并行任务图提出了一种新的调度算法,该算法考虑了数据通信开销对资源分配和调度性能的影响,并对已有的CPA算法在特定情况下进行了改进。通过实验与常用的CPR和CPA算法做比较,验证了提出的新算法能够获得很好的调度效果。本文提出的调度算法和得到的最优调度结论对工作流应用系统的高性能调度功能开发具有借鉴意义。
Many complex application problems in scientific and engineering computing can be solved through scientific workflow technology, and these scientific workflows in supercomputing domain are modeled by parallel task graphs. Effective scheduling of parallel task graphs is significant for efficient execution of applications. We propose a scheduling model of parallel task graphs under resource constraints. Some optimal scheduling conclusions are given for Fork-Join type parallel task graphs. In addition, we propose a new scheduling algorithm for general parallel task graphs. This algorithm considers the effect of data communication overhead on resource allocation and scheduling performance. We also improve the CPA algorithm under specific conditions. Our algorithms are compared with the commonly used CPR and CPA algorithms. Experimental results show that our new algorithms can achieve good scheduling results. The proposed scheduling algorithm and the optimal conclusions have reference significance for the development of high performance scheduling function for workflow application systems.
Many complex application problems in scientific and engineering computing can be solved through scientific workflow technology, and these scientific workflows in supercomputing domain are modeled by parallel task graphs. Effective scheduling of parallel task graphs is significant for efficient execution of applications. We propose a scheduling model of parallel task graphs under resource constraints. Some optimal scheduling conclusions are given for Fork-Join type parallel task graphs. In addition, we propose a new scheduling algorithm for general parallel task graphs. This algorithm considers the effect of data communication overhead on resource allocation and scheduling performance. We also improve the CPA algorithm under specific conditions. Our algorithms are compared with the commonly used CPR and CPA algorithms. Experimental results show that our new algorithms can achieve good scheduling results. The proposed scheduling algorithm and the optimal conclusions have reference significance for the development of high performance scheduling function for workflow application systems.
引文
[1] Zhang J,Luo J,Dong F.Scheduling of scientific workflow in non-dedicated heterogeneous multicluster platform[J].The Journal of Systems & Software,2013,86(7):1806-1818.
[2] Radulescu A,van Gemund A J C.A low-cost approach towards mixed task and data parallel scheduling [C]//Proc of the International Conference on Parallel Processing (ICPP’01),2001:69-76.
[3] Radulescu A,Nicolescu C,van Gemund A J C,et al.CPR:Mixed task and data parallel scheduling for distributed systems[C]//Proc of the 15th International Parallel and Distributed Processing Symposium (IPDPS’2001),2001:1-8.
[4] Yang T,Gerasoulis A.DSC:Scheduling parallel tasks on an unbounded number of processors[J].IEEE Transactions on Parallel Distributed Systems,1994,5(9):951-967.
[5] Topcuoglu H,Hariri S,Wu M.Performance-effective and low-complexity task scheduling for heterogeneous computing[J].IEEE Transactions on Parallel Distributed Systems,2002,13(3):260-274.
[6] Kwok Y,Ahmad I.Dynamic critical-path scheduling:An effective technique for allocation task graphs to multiprocessors[J].IEEE Transactions Parallel Distributed Systems,1996,7(5):506-521.
[7] Wu F,Wu Q,Tan Y.Workflow scheduling in cloud:A survey[J].Journal of Supercomputing,2015,71(9):3373-3418.
[8] Huang K C,Wu W Y,Wang F J,et al.An iterative expanding and shrinking process for processor allocation in mixed parallel workflow scheduling[J].Springerplus,2016,5(1):1138-1161.
[9] Vydyanathan N,Krishnamoorthy S,Sabin G M,et al.An integrated approach to locality-conscious processor allocation and scheduling of mixed-parallel applications[J].IEEE Transactions on Parallel Distributed Systems,2009,20(8):1158-1172.
[10] Ma Dan,Zhang Wei,Li Ken-li.Study on Dispatch algorithms of parallel Fash[J].Application Research of Computers,2004,21(11):91-94.(in Chinese)
[11] Luo Hong-bing,Zhang Bao-yin,Cao Li-qiang.Improve performance of FCFS combined with backfill based on moldability of parallel jobs[J].Computer Engineering and Applications,2007,43(24):41-46.(in Chinese)
[12] Feitelson D G,Rudolph L,Schweigelshohn U,et al.Theory and practice in parallel job scheduling [C] //Proc of Job Scheduling Strategies for Parallel Processing,1997:1-34.
[13] Kleinrock L,Huang J H.On parallel processing systems:Amdahl’s law generalized and some results on optimal design [J].IEEE Transactions on Software Engineering,1992,18(5):434-447.
[14] Casanova H,Giersch A,Legrand A,et al.Versatile,scalable and accurate simulation of distributed applications and platforms[J].Journal of Parallel and Distributed Computing,2014,74 (10):2899-2917.
[15] DAGGEN [EB/OL].[ 2017-07-26].https://github.com/frs69wq/daggen.
[10] 马丹,张薇,李肯立.并行任务调度算法研究[J].计算机应用研究,2004,21(11):91-94.
[11] 罗红兵,张宝印,曹立强.利用作业可塑性改进结合回填FCFS策略的性能[J].计算机工程与应用,2007,43(24):41-46.
[2] Radulescu A,van Gemund A J C.A low-cost approach towards mixed task and data parallel scheduling [C]//Proc of the International Conference on Parallel Processing (ICPP’01),2001:69-76.
[3] Radulescu A,Nicolescu C,van Gemund A J C,et al.CPR:Mixed task and data parallel scheduling for distributed systems[C]//Proc of the 15th International Parallel and Distributed Processing Symposium (IPDPS’2001),2001:1-8.
[4] Yang T,Gerasoulis A.DSC:Scheduling parallel tasks on an unbounded number of processors[J].IEEE Transactions on Parallel Distributed Systems,1994,5(9):951-967.
[5] Topcuoglu H,Hariri S,Wu M.Performance-effective and low-complexity task scheduling for heterogeneous computing[J].IEEE Transactions on Parallel Distributed Systems,2002,13(3):260-274.
[6] Kwok Y,Ahmad I.Dynamic critical-path scheduling:An effective technique for allocation task graphs to multiprocessors[J].IEEE Transactions Parallel Distributed Systems,1996,7(5):506-521.
[7] Wu F,Wu Q,Tan Y.Workflow scheduling in cloud:A survey[J].Journal of Supercomputing,2015,71(9):3373-3418.
[8] Huang K C,Wu W Y,Wang F J,et al.An iterative expanding and shrinking process for processor allocation in mixed parallel workflow scheduling[J].Springerplus,2016,5(1):1138-1161.
[9] Vydyanathan N,Krishnamoorthy S,Sabin G M,et al.An integrated approach to locality-conscious processor allocation and scheduling of mixed-parallel applications[J].IEEE Transactions on Parallel Distributed Systems,2009,20(8):1158-1172.
[10] Ma Dan,Zhang Wei,Li Ken-li.Study on Dispatch algorithms of parallel Fash[J].Application Research of Computers,2004,21(11):91-94.(in Chinese)
[11] Luo Hong-bing,Zhang Bao-yin,Cao Li-qiang.Improve performance of FCFS combined with backfill based on moldability of parallel jobs[J].Computer Engineering and Applications,2007,43(24):41-46.(in Chinese)
[12] Feitelson D G,Rudolph L,Schweigelshohn U,et al.Theory and practice in parallel job scheduling [C] //Proc of Job Scheduling Strategies for Parallel Processing,1997:1-34.
[13] Kleinrock L,Huang J H.On parallel processing systems:Amdahl’s law generalized and some results on optimal design [J].IEEE Transactions on Software Engineering,1992,18(5):434-447.
[14] Casanova H,Giersch A,Legrand A,et al.Versatile,scalable and accurate simulation of distributed applications and platforms[J].Journal of Parallel and Distributed Computing,2014,74 (10):2899-2917.
[15] DAGGEN [EB/OL].[ 2017-07-26].https://github.com/frs69wq/daggen.
[10] 马丹,张薇,李肯立.并行任务调度算法研究[J].计算机应用研究,2004,21(11):91-94.
[11] 罗红兵,张宝印,曹立强.利用作业可塑性改进结合回填FCFS策略的性能[J].计算机工程与应用,2007,43(24):41-46.