基于网格的地震模拟工作流调度
|
摘要
网格为地震模拟等大规模工作流应用提供了强大的计算能力,如何保障此类应用的软实时性要求是工作流调度问题的一个挑战.利用排队模型来描述网格资源的动态负载压力,提出了评估工作流健壮性量化指标及其计算方法.基于DAG图转换得出的任务执行优先级,根据最大健壮性优先的思想,确定了执行工作流子任务的候选资源;将工作流全局截止时间划分问题描述为一个约束下的非线性规划问题并通过已有方法求解该问题,提出了工作流全局截止时间动态划分方法;最后,提出了一种健壮性增强的地震模拟工作流调度算法RESAESW.仿真实验采用实际地震模拟工作流应用和实际系统数据来验证提出算法的性能表现,实验结果表明本文算法在网格环境的自适应性和地震模拟工作流应用的截止时间要求方面优于其他两个实际网格系统中的调度算法.
Grid provides large computing capability for programming scientific workflow such as earthquake simulation.How to guarantee soft real-time requirement of these applications is a challenging problem.Queuing model is utilized to describe volatile workload of Grid resource and then we proposed a metric that quantifying workflow robustness.According to thinking of biggest workflow robustness first,candidate resource for each workflow task is selected in order of their priorities calculated from DAG structure.We model workflow global deadline division as a constrained non-linear programming problem and resort to an interior point algorithm to solve it,and present a dynamic deadline division method.Then a Robustness Enhanced Scheduling Algorithm for Earthquake Simulation Workflow(RESAESW) is devised from resource selection and global deadline division.We conducted extensive simulations using a case for earthquake simulation workflow and real-world Grid workload to validate our algorithm.Experimental results show that our algorithm has better performance on adaption to dynamic Grid and application's deadline guarantee,and outperforms two other algorithms used in real Grid system.
Grid provides large computing capability for programming scientific workflow such as earthquake simulation.How to guarantee soft real-time requirement of these applications is a challenging problem.Queuing model is utilized to describe volatile workload of Grid resource and then we proposed a metric that quantifying workflow robustness.According to thinking of biggest workflow robustness first,candidate resource for each workflow task is selected in order of their priorities calculated from DAG structure.We model workflow global deadline division as a constrained non-linear programming problem and resort to an interior point algorithm to solve it,and present a dynamic deadline division method.Then a Robustness Enhanced Scheduling Algorithm for Earthquake Simulation Workflow(RESAESW) is devised from resource selection and global deadline division.We conducted extensive simulations using a case for earthquake simulation workflow and real-world Grid workload to validate our algorithm.Experimental results show that our algorithm has better performance on adaption to dynamic Grid and application's deadline guarantee,and outperforms two other algorithms used in real Grid system.
引文
[1]Deelman E,Callaghan S,Field E,et al.Managing Large-ScaleWorkflow Execution from Resource Provisioning to Provenancetracking:The CyberShake Example.IEEE InternationalConference on e-Science and Grid Computing,2006:14.
[2]Canon L C,Jeannot E.Evaluation and optimization of therobustness of DAG schedules in heterogeneous environments.IEEE Transactions on Parallel and Distributed Systems,2010,21(4):532-546.
[3]王润秋,李兰兰,李会俭.塔里木地区勘探地震正演模拟研究.地球物理学报,2010,53(8):1875-1882.Wang R Q,Li L L,Li H J.Forward modeling research forseismic exploration of Tarim area.Chinese J.Geophys.(inChinese),2010,53(8):1875-1882.
[4]龙桂华,赵宇波,李小凡等.三维交错网格有限差分地震波模拟的GPU集群实现.地球物理学进展,2011,26(6):1938-1949.Long G H,Zhao Y B,Li X F,et al.Accelerating 3Dstaggered-grid finite-difference seismic wave modeling on GPUcluster.Progress in Geophysics(in Chinese),2011,26(6):1938-1949.
[5]Topcuoglu H,Hariri S,Wu M Y.Performance-effective andlow-complexity task scheduling for heterogeneous computing.IEEE Transactions on Parallel and Distributed Systems,2002,13(3):260-274.
[6]N’Takpe T,Suter F,Casanova H.A comparison of schedulingapproaches for mixed-parallel Applications on heterogeneousplatforms.In Proceedings of the 6th International Symposiumon Parallel and Distributed Computing(ISPDC’07),Hagenberg,Austria:IEEE Computer Society,2007:35.
[7]Hunold S,Rauber T,Suter F.Scheduling dynamic workflowsonto clusters of clusters using postponing.In Proceedings ofthe 8th IEEE International Symposium on Cluster Computingand the Grid(CCGrid’08),Lyon,France:IEEE ComputerSociety,2008:669-674.
[8]苑迎春,李小平,王茜等.成本约束的网格工作流时间优化方法.计算机研究与发展,2009,46(2):194-201.Yuan Y C,Li X P,Wang Q,et al.Time optimizationheuristics for scheduling budget-constrained grid workflows.Journal of Computer Research and Development(in Chinese),2009,46(2):194-201.
[9]Hakem M,Butelle F.Dynamic critical path scheduling parallelprograms onto multiprocessors.In Proceedings of the 19thIEEE International Parallel and Distributed ProcessingSymposium(IPDPS‘05),Denver,USA:IEEE ComputerSociety,2005:203.
[10]蒋哲远,韩江洪,王钊.动态的QoS感知Web服务选择和组合优化模型.计算机学报,2009,32(5):1014-1025.Jiang Z Y,Han J H,Wang Z.An Optimization model fordynamic QoS-Aware web services selection and composition.Chinese Journal of Computers(in Chinese),2009,32(5):1014-1025.
[11]Yu J,Buya R.Scheduling scientific workflow applicationswith deadline and budget constraints using geneticalgorithms.Scientific Programming Journal,2006,14(3-4):217-230.
[12]Yan Y H,Chapman B.Scientific workflow scheduling incomputational grids planning,reservation,and data/network-awareness.In Proceedings of the 8th GridComputing Conference(Grid’07),Austin,Texas:IEEEComputer Society,2007:18-25.
[13]Nurmi D,Mandal A,Brevik J,et al.Evaluation of aworkflow scheduler using integrated performance modellingand batch queue wait time prediction.In Proceedings of the2006ACM/IEEE Conference on Supercomputing(SC’06),New York,USA:ACM,2006:119.
[14]Berten V,Goossens J,Jeannot E.On the distribution ofsequential jobs in random brokering for heterogeneouscomputational grids.IEEE Transactions on Parallel andDistributed Systems,2006,17(2):113-124.
[15]Lublin U,Feitelson D G.The workload on parallelsupercomputers:modeling the characteristics of Rigid Jobs.Journal of Parallel and Distributed Computing,2003,63(11):1105-1122.
[16]Iosup A,Jan M,Sonmez O O,et al.The characteristics andthe performance of groups of jobs in grids.Lecture Notes onComputer Science,2007,4641:382-393.
[17]Gross D,Harris C M.Fundamentals of Queueing Theory.New York:John Wiley and Sons,1998.
[18]杜晓丽,蒋昌俊,徐国荣等.一种基于模糊聚类的网格DAG任务图调度算法.软件学报,2006,17(11):2277-2288.Du X L,Jiang C J,Xu G R,et al.A grid DAG schedulingalgorithm based on fuzzy clustering.Journal of Software(inChinese),2006,17(11):2277-2288.
[19]Byrd R H,Hribar M E,Nocedal J.An interior pointalgorithm for large-scale nonlinear programming.SIAMJournal on Optimization,1999,9(4):877-900.
[20]Glatard T,Pennec X,and Montagnat J.Performance evaluation ofgrid-enabled registration algorithms using bronze-standards.In Proceedings of the 9th International Conference of MedicalImage Computing and Computer-Assisted Intervention(MICCAI’06),Copenhagen,Denmark:Springer,2006:152-160.
[21]Yeo C S,Buyya R.Pricing for utility-driven resource managementand allocation in clusters.International Journal of HighPerformance Computing Applications,2007,21(4):405-418.
[2]Canon L C,Jeannot E.Evaluation and optimization of therobustness of DAG schedules in heterogeneous environments.IEEE Transactions on Parallel and Distributed Systems,2010,21(4):532-546.
[3]王润秋,李兰兰,李会俭.塔里木地区勘探地震正演模拟研究.地球物理学报,2010,53(8):1875-1882.Wang R Q,Li L L,Li H J.Forward modeling research forseismic exploration of Tarim area.Chinese J.Geophys.(inChinese),2010,53(8):1875-1882.
[4]龙桂华,赵宇波,李小凡等.三维交错网格有限差分地震波模拟的GPU集群实现.地球物理学进展,2011,26(6):1938-1949.Long G H,Zhao Y B,Li X F,et al.Accelerating 3Dstaggered-grid finite-difference seismic wave modeling on GPUcluster.Progress in Geophysics(in Chinese),2011,26(6):1938-1949.
[5]Topcuoglu H,Hariri S,Wu M Y.Performance-effective andlow-complexity task scheduling for heterogeneous computing.IEEE Transactions on Parallel and Distributed Systems,2002,13(3):260-274.
[6]N’Takpe T,Suter F,Casanova H.A comparison of schedulingapproaches for mixed-parallel Applications on heterogeneousplatforms.In Proceedings of the 6th International Symposiumon Parallel and Distributed Computing(ISPDC’07),Hagenberg,Austria:IEEE Computer Society,2007:35.
[7]Hunold S,Rauber T,Suter F.Scheduling dynamic workflowsonto clusters of clusters using postponing.In Proceedings ofthe 8th IEEE International Symposium on Cluster Computingand the Grid(CCGrid’08),Lyon,France:IEEE ComputerSociety,2008:669-674.
[8]苑迎春,李小平,王茜等.成本约束的网格工作流时间优化方法.计算机研究与发展,2009,46(2):194-201.Yuan Y C,Li X P,Wang Q,et al.Time optimizationheuristics for scheduling budget-constrained grid workflows.Journal of Computer Research and Development(in Chinese),2009,46(2):194-201.
[9]Hakem M,Butelle F.Dynamic critical path scheduling parallelprograms onto multiprocessors.In Proceedings of the 19thIEEE International Parallel and Distributed ProcessingSymposium(IPDPS‘05),Denver,USA:IEEE ComputerSociety,2005:203.
[10]蒋哲远,韩江洪,王钊.动态的QoS感知Web服务选择和组合优化模型.计算机学报,2009,32(5):1014-1025.Jiang Z Y,Han J H,Wang Z.An Optimization model fordynamic QoS-Aware web services selection and composition.Chinese Journal of Computers(in Chinese),2009,32(5):1014-1025.
[11]Yu J,Buya R.Scheduling scientific workflow applicationswith deadline and budget constraints using geneticalgorithms.Scientific Programming Journal,2006,14(3-4):217-230.
[12]Yan Y H,Chapman B.Scientific workflow scheduling incomputational grids planning,reservation,and data/network-awareness.In Proceedings of the 8th GridComputing Conference(Grid’07),Austin,Texas:IEEEComputer Society,2007:18-25.
[13]Nurmi D,Mandal A,Brevik J,et al.Evaluation of aworkflow scheduler using integrated performance modellingand batch queue wait time prediction.In Proceedings of the2006ACM/IEEE Conference on Supercomputing(SC’06),New York,USA:ACM,2006:119.
[14]Berten V,Goossens J,Jeannot E.On the distribution ofsequential jobs in random brokering for heterogeneouscomputational grids.IEEE Transactions on Parallel andDistributed Systems,2006,17(2):113-124.
[15]Lublin U,Feitelson D G.The workload on parallelsupercomputers:modeling the characteristics of Rigid Jobs.Journal of Parallel and Distributed Computing,2003,63(11):1105-1122.
[16]Iosup A,Jan M,Sonmez O O,et al.The characteristics andthe performance of groups of jobs in grids.Lecture Notes onComputer Science,2007,4641:382-393.
[17]Gross D,Harris C M.Fundamentals of Queueing Theory.New York:John Wiley and Sons,1998.
[18]杜晓丽,蒋昌俊,徐国荣等.一种基于模糊聚类的网格DAG任务图调度算法.软件学报,2006,17(11):2277-2288.Du X L,Jiang C J,Xu G R,et al.A grid DAG schedulingalgorithm based on fuzzy clustering.Journal of Software(inChinese),2006,17(11):2277-2288.
[19]Byrd R H,Hribar M E,Nocedal J.An interior pointalgorithm for large-scale nonlinear programming.SIAMJournal on Optimization,1999,9(4):877-900.
[20]Glatard T,Pennec X,and Montagnat J.Performance evaluation ofgrid-enabled registration algorithms using bronze-standards.In Proceedings of the 9th International Conference of MedicalImage Computing and Computer-Assisted Intervention(MICCAI’06),Copenhagen,Denmark:Springer,2006:152-160.
[21]Yeo C S,Buyya R.Pricing for utility-driven resource managementand allocation in clusters.International Journal of HighPerformance Computing Applications,2007,21(4):405-418.
版权所有：© 2023 中国地质图书馆 中国地质调查局地学文献中心