有向图并行计算中一种新的结点调度算法

《有向图并行计算中一种新的结点调度算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《计算机学报》2009年11期，2009，32（11）有向图并行计算中一种新的结点调度算法∗张爱清**莫则尧***(北京应用物理与计算数学研究所高性能计算中心，北京，100094)摘要：在基于有向图的并行计算中，给定图剖分后，如何设计结点调度方案使得并行执行时间最短，是典型的NP完全问题。针对此问题，本文提出一种新的基于顺逆交替迭代技术的启示性调度算法，并给出该算法的并行实现。严格的理论推导证明，新算法在一定的假设条件下，从任何初始调度方案出发，均可以单调收敛。在数百个处理器上的并行数值实验表明，与常用的调度算法相比，新算法可在付出很少的开销代价下显著提高整体并行效率。关键词：

2、有向图，并行计算，结点调度算法，顺逆交替迭代技术ANewSchedulingAlgorithmforDigraph-basedParallelComputingAiqingZhang,ZeyaoMo(HighPerformanceComputingCenter,InstitutionofAppliedPhysicsandComputationalMathematics,Beijing100094,China)Abstract:Theschedulingalgorithmiscrucialfortheefficiencyofthedigraph-basedparallelcomp

3、uting.However,itisclassicallyNP-completetofindaschedulewiththeshortestdurationforagivendigraphpartition.Inthispaper,anewheuristicalgorithmispresentedusingthewellknownforward-backwarditerations.Itisprovedthatthisnewalgorithmisconvergentlocallyundersomeconditions.Furthermore,theparallelimpleme

4、ntationofthealgorithmisgivenindetail.Onhundredsprocessors,thebenchmarkresultssuggestthatthenewalgorithmoutperformsmanyschedulingalgorithmswidelyusednow.Keywords:digraph,parallelcomputing,schedulingalgorithm,forward-backwarditerations*本课题获国家973项目(2005CB321702)、国家自然科学基金(60533020、60603050、90718

5、029)资助。**张爱清，女，1976年生，博士，副研究员，主要从事大规模科学与工程计算中并行算法与并行应用软件的研究，Email：zhang_aiqing@iapcm.ac.cn.***莫则尧，男，1971年生，博士，研究员，主要从事大规模科学与工程计算中并行算法与并行应用软件的研究，Email：zeyao_mo@iapcm.ac.cn.1《计算机学报》2009年11期，2009，32（11）决策。优先级策略是调度算法的核心，对调度1引言方案的并行执行时间起决定性作用。当前，优先级策略分为两类。一类是通用型策略，如最在基于网格离散的科学计算应用中存在晚完成时间策略[9]、最晚

6、开始时间策略[10]、一类计算方法，它们的并行计算可以等价地转最小松弛时间策略[9]、最多后继结点数策略换为有向图的并行计算[1]：有向图中的结点表[11]、多优先级策略[12,13]、采样策略[14,15]、示计算方法中网格单元上的计算任务，结点权Forward-Backward策略[16]、DFDS策略[17]、重表示计算开销，图中的弧表示任务间的数据最短内部边界路径策略[1]等。另一类是适合具依赖关系，弧权重表示数据通信开销。这类方体应用问题的有向图特征的优先级策略，如针法普遍存在于科学计算领域。例如，在核科对粒子输运方程多方向输运扫描的KBA优先学和惯性约束聚变数值模拟

7、应用中，求解多群策略[18]、randomdelay策略[19]等。在这些基粒子输运方程的离散纵标数值方法[2,3]，以及于优先级的调度算法中，Forward-Backward算在流体力学中，求解对流占优方程的隐式迎风法，简称FB算法，是当前运筹学界公认的最格式、顺流松弛方法[4,5,6]等，均是此类方法。简单有效的调度算法之一。针对有向图设计的并行算法，可以直接应用到除基于优先级策略的调度算法外，后启示这类方法的并行计算中。性调度算法是当前流行的另一类调度算法，如在有向图中，一方面，弧对应