（计算机软件与理论专业论文）有向图并行计算中的多目标剖分算法.pdf

摘要 在以离散网格为基础的科学计算数值模拟中，在某些情形下，网格间的计算 顺序是单方向数据依赖的，这种依赖关系可以抽象为有向图。于是，这类科学数 值模拟的并行计算可以抽象成为有向图的并行计算问题。如何剖分这些有向图成 多个子图，将各子图对应的数值模拟任务映射到不同的处理机，是该类数值模拟 有向图并行计算的基础。有向图并行计算可分解为三个部分，有向图剖分算法、 结点的优先级算法和基于有向图剖分算法和结点优先级算法的扫描并行算法。有 向图剖分算法中，我们需要综合考虑连通性、并行度、负载平衡、通信开销四个 目标。本文在传统有向图剖分算法的基础上，提出了一个权衡这四个目标的有向 图多目标剖分区域分解算法。应用于二维非结构网格上的柱对称中子输运并行计 算中，基于该剖分算法的通量扫描并行算法的并行效率比基于非结构网格无向图 剖分区域分解的相应并行算法的并行效率有明显的提高。具体分为六章。 第一章简单分析离散网格为基础的科学数值模拟中有向图剖分的应用，指出 了开展多目标剖分区域分解算法研究的必要性，总结了有向图剖分算法的发展状 况和以往有向图剖分算法的不足。最后，简述了本文的主要工作。 第二章介绍有向图并行计算的基本概念、有向图并行计算的评判准则和基于 区域分解的扫描并行算法。 第三章介绍有向图的结点优先级算法。 第四章介绍多目标剖分区域分解算法，即如何根据图中结点的单方向数据依 赖关系，将图剖分成p 个子图，分配给p 台不同的处理机，使得基于图剖分的 扫描并行算法获得最高的并行效率。我们将相邻结点引入多目标剖分区域分解算 法之后，相应地引入三个新概念，从而改进多目标剖分区域分解算法。 第五章利用扫描并行算法对l t e r a t i x ek e m i g h a m l i n ( i k l ) 方法和改进i 0 后 多目标剖分区域分解算法给出的剖分进行比较并对结果进行具体分析。实验结 果表明我们的多目标剂分区域分解算法达到了预期的目标，并且某些性质方面比 i k l 方法有更好的效果，而改进后的算法比改进前的多目标剖分区域分解算法有 更好的效粜。 第六章为结束语，总结了全文i ：作，喂望了将柬的研究重点。 天键词 ：有向图，并行汁算，多目标剖分区域分解 a b s t r a c t f o r g r i d b a s e ds c i e n t i f i cn u m e r i c a ls i m u l a t i o n s ，d a t a d e p e n d e n c i e s o f c o m p u t a t i o n so ng r i d si sd i r e c t e da n di t c a nb er e p r e s e n t e db yad i r e c t e dg r a p h t h e n t h e s ep a r a l l e ls c i e n t i f i cn u m e r i c a ls i m u l a t i o n sc a nb er e p r e s e n t e db yp a r a l l e ld i r e c t e d g r a p hc o m p u t i n g p a r t i t i o n i n gt h i sd i r e c t e dg r a p hi n t os o m es u b g r a p h sa n dm a p p i n g c o r r e s p o n d i n gt a s k so n t op r o c e s s o r sa r ec r i t i c a lf o rp a r a l l e ld i r e c t e dg r a p hc o m p u t i n g d i r e c t e dg r a p hp a r t i t i o n i n gi sc o n s t i t u t i v eo f p a r t i t i o n i n gd i r e c t e dg r a p h 、p r i o r i t y a l g o r i t h mo fd i r e c t e dg r a p hn o d e sa n dp a r a l ms w e e pa l g o r i t h m p a r t i t i o n i n g a l g o r i t h m sm u s ts y n t h e s i z et h ec o n s i d e r a t i o nf o rc o n n e c t i v i t y , d e g r e eo fp a r a l l e l i s m ， l o a d b a l a n c i n g ，a n d c o m m u n i c a t i o nc o s t b a s e do nt r a d i t i o n a ld i r e c t e d g r a p h p a r t i t i o n i n ga l g o r i t t m a s ，t h i sp a p e rp r e s e n t s am u l t i - o b j e c t i v ed i r e c t e d g r a p h p a r t i t i o n i n ga l g o r i t h mt h a tc a nc o n t r o lt h et r a d e o f f sa m o n ga b o v ef o u ro b j e c t i v e s i f a p p l i e dt o2 - d i m e n s i o n a lc y l i n d e rs y m m e t r i c a ln e u t r o nt r a n s p o r tc o m p u t a t i o n so n u n s t r u c t u r e d 鲥d ，t h ep a r a l l e le f f i c i e n c yo f p a r a l l e lf l u xs w e e p i n ga l g o r i t h mu s i n g o u r m u l t i o b j e c t i x ep a r t i t i o n i n ga l g o r i t h mi sm u c hl a r g e rt h a nt h a to fu s i n gu n d i r e c t e d g r a p hp a r t i t i o i n i n ga l g o r i t h m s e l e v e nc h a p t e r sa r ei n c l u d e di nt h i st h e s i s c h a p t e r1s i m p l ys u r v e y e dt h eu s eo fd i r e c t e dg r a p hp a r t i t i o n i n gi ng r i db a s e d s c i e n t i f i cn u m e r i c a l s i m u l a t i o n s ，p o i n t e do u tt h a t i tw a si n d i s p e n s a b l et o d e s i g n m u l t i o b j e c t i x ep a r t i t i o n i n ga l g o r i t h mf o rp a r a l l e lc o m p u t a t i o n so fd i r e c t e dg r a p h ， s u m m a r i z e dt h ed r a w b a c k so fg r a p hp a r t i t i o n i n ga l g o r i t h m se x i s t e db e f o r e a tl a s t ， t h em a i nr e s e a r c hr e s u l t si nt h i st h e s i sw e r eg i ；e n c h a p t e r2g i v e dap r e s e n t a t i o no fs o m ec o n c e p t sr e l a t e dt og r a p hp a r t i t i o n i n g ， l i s t e do u rj u d g e m e n to fe f f i c i e n c yt h a tc o m p a r i n ga l lk i n d so fa l g o r i t h m s ，i n t r o d u c e d p a r a l l e ls w e e pa l g o r i t h mw i t hs c a l a b l ep e r f o r m a n c ef o rd i r e c t e dg r a p h c h a p t e r3i n t r o d u c e dp r i o r i t ya l g o r i t h mo fd i r e c t e dg r a p hn o d e sa f t e rg i v i n g p r i o r i t yt oe 、e wn o d e i ti sc l e a ra b o u ts e l e c t i n go n ef r o ms o m ec o m p u t a b l en o d e s c h a p t e r4i n t r o d u c e dm u l t i - o b j e c t i v ep a r t i t i o n i n ga l g o r i t h m b a s e do nt h ed a t a d e p e n d e n c eo fn o d e s ，t h i sa l g o r i t h ma c h i e xe sh i g he f f i c i e n c yo fp a r a l l e l i s mb y p a r t i t i o n i n gad i r e c t e dg r a p ht ops u b - g r a p h sa n dm a p p i n gt h e s et opp r o c e s s o r s t h e nw em o d i f l e dm u l t i o b j e c t i v ep a r t i t i o n i n ga l g o r i t h mb yu s i n gn e i g h b o rn o d e sa n d t h r e en e wc o n c e p t s i ti sb e t t e rt h a nm u l t i o b j e c t i v ep a r t i t i o n i n ga l g o r i t h mi ns o m e w a y s c h a p t e r5c o m p a r e dt h ep a r t i t i o n i n gg i v e nb yi t e r a t i v ek e m i g h a m l i n ( i k l ) a l g o r i t h ma n dm u l t i o b j e c t i v ep a n i f i o n i n ga l g o r i t h m ，t h er e s u ro ft h ep e r f o r m a n c e i n d i c a t e st h a t m u l t i o b j e c t i v ep a r t i t i o n i n ga l g o r i t h m h a sa c h i e v e d e x p e c t a t i o n ， m u l t i o b j e c t i v ep a r t i t i o n i n ga l g o r i t h mi sb e t t e rt h a ni k la l g o r i t h mi ns o m ew a y s ， m o d i f i e d m u l t i o b j e c t i v ep a r t i t i o n i n ga l g o r i t h m i sb e t t e rt h a n m u l t i o b j e c t i v e p a r t i t i o n i n ga l g o r i t h mi ns o m ew a y s c h a p t e r6s u i n l i l a r i z e dt h i st h e s i s ，s u r v e y e dt h er e s e a r c hf i e l d si i lf u t u r e f k e yw o r d s 】d i r e c t e dg r a p h ，p a r a l l e lc o m p u t i n g ，m u l t i - o b j e c t i v ed i r e c t e dg r a p h p a r t i t i o n i n g 独创性声明 y8 u 9 9 5 1 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得中国工程物理研究院或其他 教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：金芄澎签字胁2 。年如目 学位论文版权使用授权书 本学位论文作者完全了解并接受中国工程物理研究院研究生部有关保存、使 用学位论文的规定，允许论文被查阅、借阅和送交国家有关部门或机构，同时授 权中国工程物理研究院研究生部可以将学位论文全部或部分内容编入有关数据 库进行检索，可以影印、缩印或扫描等复制手段保存、汇编学位论文。 学位论文作者签名：金牦港 签字日期：知艿年g 月曰 ， 导师签名：彩 签字日期：2 册阵g 月日 有向图并行计算中的多目标剖分算法 第一章绪论 1 1 研究背景 在以离散网格为基础的科学计算数直模拟中，存在这样一类应用，其数值模 拟过程可以分解为数千上万个时间步，在每个时间步，每个网格计算依赖的输入 数据来源于周围相邻的某几个网格的最新计算的数据，而其计算所得的新数据又 是周围相邻的另外几个网格计算的输入数据。于是，给定初值和边界条件后，在 每个时间步，所有网格计算顺序的单方向数据依赖关系可以抽象成一个有向图 1 ，图中的结点代表网格单元，其权重代表该网格单元的计算量，图中的有向 边代表网格间的数据依赖关系，边的权重代表依赖的数据量的大小。对此类应用， 并行计算的核心是如何设计并行算法，挖掘有向图标识的网格计算的数据依赖关 系之间隐藏的内在并行度。 在核科学和惯性约束聚变等应用中，中子输运方程和辐射输运方程是非常重 要的两类方程，间断有限元或者有限差分离散坐标计算方法是目前求解该类方程 的最重要的数值方法 2 ，3 。由于它们涉及几何空间三维、速度空间三维和时间一 维的7 维离散，因此，它们的计算量非常巨大，占据了相关应用9 0 以上的整体 计算量，对高性能并行计算的需求非常迫切。因此，设计适合离散坐标计算方法 的高效并行算法是关系到能否实现中子输运和辐射输运可扩展并行计算的关键。 通量扫描是离散坐标计算方法的核心之一，占据4 0 左右的计算量，其计算过程 可大致抽象描述如下：在每个时间步，对速度空间离散的每个方向，要求沿该方 向标识的计算顺序，依次计算每个离散的几何网格的通量。于是，几何网格计算 的数据依赖关系可用有向图表示，而通量扫描并行算法的目的就是要求充分挖掘 有向图内部的结点阳j 的内在并行度。 1 2 发展动态 在二维非结构网格上，莫则尧等 4 提出了求解柱对称中子输运方程的间断 有限元离散坐标计算方法的基于区域分解的通量扫描并行算法，讨论了中子输运 方程在数百个处理器上的并行求解。该算法没有显式地提出有向图的数据依赖关 系，它首先f e 定二维非结构网格己经按给定的处理器个数p ，采用无向图剖分算 法及软件工具f 5 ，6 ，分解为p 个子区域，然后根据网格通量扫描的数据依赖关系， 确定各个网恪被计算的顺序和优先级，设计了网格乱序计算的通量扫描并行算 法。更进一步，莫则尧等 8 对该并行算法还进行了可扩展分析，指出扫描并行 算法的性能对并行机延迟非常敏感，只有在延迟小于几个微秒的并行机上，爿可 能实现该类算法的可扩展并行计算。s p l i m p t o n 等 7 针对三维非结构网格，也讨 有向图并行计算中的多目标剖分算法 论了求解辐射输运模型b o l z m a n n 方程的离散坐标计算方法类似的并行算法，在 数百个处理器上均取得了很好的效果。 以上工作中，作者没有考虑将此类数据依赖关系的并行算法问题抽象成为有 向图的并行算法问题加以研究，而是在给定的非结构网格区域分解的基础上，根 据数据依赖关系设计通量扫描并行算法，而在区域分解方式中，也没有考虑数据 依赖关系，因此，这样的并行算法不一定是最优的。因此，为了充分地挖掘此类 数据依赖关系计算的内在并行度，我们不妨直接将问题抽象成为有向图，通过设 计有向图的并行计算，达到最优并行求解此类应用的目的。 有向图并行计算可分解为三个部分。第一部分是图剖分算法，即如何根据图 中结点的单方向数据依赖关系，将图剖分成户个子图，分配给p 台不同的处理 机，使得基于图剖分的扫描并行算法获得最高的并行效率；第二部分是结点的优 先级算法，即赋给每个结点一个优先级，使得在同一个处理机中，在同一个时刻， 输入数据已经具备的可被计算的多个结点中，可以挑选一个优先计算，目的同样 是使得扫描并行算法获得最高的并行效率；第三部分是基于有向图剖分算法和结 点优先级算法的扫描并行算法，实现有向图的具体并行计算。显然，这三个方面 是相互依存的，缺一不可。经过简单地修改，文 4 中提出的通量扫描并行算法 可以自动地成为有向图并行计算的第三部分，而本文研究的重点是有向图剖分算 法，同时兼顾结点的优先级算法。 传统的有向图并行算法研究不是面向科学数值模拟的，而是侧重于并行编译 等应用中的数据流分析，比较有代表性的是j a s h a r p 9 提出的剖分策略算法， 它按结点的最早和最晚可执行时间，尽量将数据相关的结点分配在同一台处理 机；y f l e e 9 ，1 1 1 提出的区域分析算法，它首先将数据相关的结点结合成区域， 然后，将区域再分配给各台处理机；c k o u t s o u g e r a s e ta 1 1 2 提出的极小化通信 开销算法，它首先将相互之间通信量大的结点结合成串，然后将这些串分配给各 台处理机；b l e e 1 3 提出的垂直分配算法，它首先将所有结点按各自的可执行时 间进行水平分层，位于同一层中的结点可以并行计算，然后根据处理机个数进行 垂直剖分，并进行优化，规定位于同一个垂直区域中的所有结点将被分配到同一 台处理机，第二章将具体介绍这些算法。 在以网格为基础的科学数值模拟中，有向图并行计算需要综合考虑四个目 标：连通性、并行度、负载平衡和通信开销。首先，必须保证图剖分得到的所有 子图中的结点是相互连通的，因为网格的计算通常依赖于周围邻居网格的信息， 连通性能减少处理机间的数据交换，易于并行实现；其次，假设并行机的通信丌 销可以忽略不计，则图剖分算法应该保证扫描算法具有尽可能挖掘内在并行度； 再次，为了将有向图并行计算更好地融入到科学数值模拟的全过程中需要保证 有向图并行计算中的多目标剖分算法 剖分的各个子图所拥有的结点的计算量尽可能的均衡；最后，类似于无向图的剖 分优化策略 5 ，尽可能减少各个子图的面体比，从而减少通信的次数和通信量。 显然，传统的数据流有向图剖分算法没有综合考虑这些目标。 1 3 本文的主要工作与创新 本文基于文【4 ，7 提出的通量扫描并行算法，初步探讨在以网格为基础的科学 数值模拟中，有向图并行计算的多目标图剖分问题，它们对核科学和惯性约束聚 变等重要应用中的中子输运和辐射输运等问题的并行数值模拟有较好的指导意 义。具体地，侧重于连通性、并行度和负载平衡的最优权衡，兼顾减少子图的面 体比，提出了一个有向图的多目标剖分算法。应用于二维非结构网格上的柱对称 中子输运间断有限元离散坐标计算方法的并行计算，对每个时间步的单个通量扫 描的速度方向，基于非结构网格有向图多目标区域分解的通量扫描并行算法，相 对于文 4 ，7 提出的基于非结构网格无向图剖分区域分解的通量扫描并行算法，并 行效率改进5 0 以上。 在有向图多目标剖分区域分解算法的研究过程中，我们发现引入相邻结点概 念会放宽有向图多目标剖分区域分解算法的约束。这样，在分配结点的时候选择 就会更多，从而达到提高并行效率的目的。依据这个观点，我们对有向图多目标 剖分区域分解算法进行改进，数值实验效果表明相对于改进前，在保证连通性的 前提下，负载平衡效率和通讯开销保持不变，而并行效率是改进前的1 2 倍。 4 有向图并行计算中的多目标剖分算法 第二章有向图并行计算基础 2 1 引言 为了更好地理解有向图多目标剖分区域分解算法及对其进行分析，我们介绍 对有向图并行计算相关的一些概念。有向图并行计算可分解为三个部分。第一部 分是图剖分算法，即如何根据图中结点的单方向数据依赖关系，将图剖分成p 个子图，分配给尸台不同的处理机，使得基于图剖分的扫描并行算法获得最高 的并行效率；第二部分是结点的优先级算法，即赋给每个结点一个优先级，使得 在同一个处理机中，在同一个时刻，输入数据已经具备的可被计算的多个结点中， 可以挑选个优先计算，目的同样是使得扫描并行算法获得最高的并行效率：第 三部分是基于有向图剖分算法和结点优先级算法的扫描并行算法，实现有向图的 具体并行计算。显然，这三个方面是相互依存的，缺一不可。 2 2 有向图基本概念 本文研究的重点是有向图剖分算法，同时兼顾结点的优先级算法。在介绍有 向图基本概念之前，首先介绍无向图及无向图剖分。 2 2 1 无向图及无向图剖分 一般来说，如果网格间计算没有数据依赖性或者数据依赖性是双向的，那么 将网格间计算抽象成无向图，否则抽象成有向图。有些情况下，即使网格间计算 有数据依赖性，也将网格间计算抽象成无向图，并采用无向图剖分方法给出剖分。 无向图g = ( k e ) 由结点集肛 v ，v 2 ，v i 年n 边集庐 e ，e 2 ，p 。 构成。结点 可以表示网格中结点或网格单元，而e j 可以表示当两个结点被分在两个不同处 理机时可能引起的通讯。以v 。) 为结点u v 的权重，表示结点的计算量大小。w ( e j ) 为目厅9 边的权重，表示通讯量的大小。每个结点可以有多个权重( 每个权重 对应不同物理量) 。同样，每条边可以有多个权重 5 】。上述量之间有如下关系。 v = u q ，e = u e ， ( 1 ) w ( y ) = w ( v ，) ，w ( e ) = n ，) ( 2 ) i = 1。= l 其中n 是结点个数，m 是边的个数； 上述无向图有如下性质： 1 )无向图g 中，由于一个结点只能被分在同一处理机中，这个结点和 自己的通讯不会影响处理机之间的通讯，所以可以忽略这详的通讯，即 有向图并行计算中的多目标剖分算法 无向图中没有环。 2 )假定两个结点v 衍“。之间有两条边。那么这两个结点被分在不同处 理机的时候，可以把这两条边变成一条边，端点分别为v l 和u r ，权重为 两条边权重之和。 注：一般地，假设结点的权重为l ，边的权重为1 。 无向图剖分将无向图g 按剖分算法剖分成结点互不重叠的p 个子图f g ， q ，g ) 。k 路剖分是指将无向图剖分成k 个子图。特别地，k 等于2 的时候称 为对分。无向图剖分的剖分目标一般为最小化总截权( 截权) 和最小化最大外度 【5 】。一个处理机连接的处理机个数称为这个处理机的外度。剖分约束对每个子 图的结点权重之和给出约束。那么k 路剖分问题就是在满足剖分约束的情况下， 将无向图g 剖分成k 个子图，使得最优化剖分的目标方程。 常用的无向图剖分方法有几何方法和组合方法。几何方法主要有坐标嵌套剖 分方法( c n o ) ，递归调用惯性对分法( r j b ) ，空间填充曲线方法( s p a c e f i l l i n g c u r v e ) 等。组合方法主要有级别嵌套方法，k l - f m 方法，贪婪图增长方法( g g g p ) ， 多水平方法( m u l t i l e v e ls c h e m e ) 等。下面简单介绍上述无向图剖分方法。 坐标嵌套剖分方法( c n d ) ： 坐标嵌套剖分方法对每个结点给出坐标，在所有这些点中，找出坐标值差最 大的两个结点，以这个坐标轴为剖分轴，按照每个结点在剖分轴上的位置，给出 一个排序。按照这个排序，在考虑负载平衡的前提下给出一个值，坐标值大于 r 的分为一组，其他分为另一组。c n d 方法的优点是比较直观、简单、割分速度 快。因为坐标值相同的结点有可能有多个，所以坐标嵌套割分方法有时候很难满 足负载平衡。 递归调用惯性对分法( r i b ) ： 递归调用惯性对分方法和坐标嵌套剖分方法相似，不同的是递归调用惯性对 分方法采用所有结点的惯性主轴为剖分轴。一般来说，r i b 方法的面体比小于 c n d 方法。 空间填充曲线方法( s p a c e f i l l i n gc u r v e ) ： 空间填充曲线方法按照网格单元沿着空间填充曲线的位置给出排列，然后按 照这个排序把网格分成k 个区域。这些曲线都采用l o c a l i t y - p r e s e r v i n g 方法( 如 p e a n o h i l b e n 曲线) 来填充空间：这样就保证了空间上相邻的结点被分在同一区 域，从而达到减少通讯丌销的目的。 级别嵌套方法( l e v e l i z e dn e s t e dd i s s e c t i o n ) ： 级别嵌套方法首先从一个结点开始，将这个结点标称0 ，然后所有跟这个结 点相连的结点标称l ，以此类推，直到一半的结点有标号。以所有标号的结点成 有向图并行计算中的多目标剖分算法 立一个区域，剩余结点被分在另一区域。相对于几何方法，该方法保证相连的结 点在同一区域，从而达到减少通讯开销的目的。 谱方法( s p e c t r a lm e t h o d s ) ： 对于无向图g 给出矩阵k f 1 如果g ，且g ，是相连的 ( 6 ) = 一d e g ( q ) 如果q = ， l 0否则 ( 3 ) d e g ( q ) 是结点的度，是指q 成为端点的次数。 然后利用次大特征值对应的特征向量，根据其分量的大小将相应的结点进行 排序，然后根据剖分约束给定一个，大于，的分量对应的结点分为一个区域， 剩下的结点分成一个区域。采用该方法进行对分的时候，如果产生的予区域不连 通，那么可以加一些虚拟的边，保证其子区域连通，然后再对子区域进行对分。 k l f m 方法： k l f m 方法是最优化策略，目的是满足剖分约束的情况下，改善剖分的质 量。k l 方法需要有一个初始剖分，然后对这个剖分进行优化。k l f m 方法每次 在两个子区域4 和雪里找出一对最大提高剖分质量的结点口和，然后区域4 和 b 互换结点q 和r 。当所有的结点都被考虑之后，这样的交换过程才算结束一次。 一般来说这样的交换过程会重复几次。 f m 方法的过程和k l 方法类似，不同的是每次只移动一个结点。当一个结 点从原来所属的区域移动到其他区域时通讯开销的改变值称为截币o ( g a i n ) 。f m 方 法对每个区域给出一个队列，将每个区域的结点按照其截j 1 ( g a i n ) 的大小进行排 序，每次考虑移动队列顶部的结点。 k l 和f m 方法给出的剖分质量跟初始输入的剖分质量有关。如果剖分约束 可以被适当地放宽，则k l 和f m 方法给出的剖分的质量会更好。 贪婪图增长方法( g g g p ) ： 贪婪图增长方法类似于级别嵌套方法。贪婪图增长方法按照每个结点的截利 ( g a i n ) 大小，将这些结点按截利( g a i n ) 不增加的顺序插入到队列中，结点按照这个 队列移动到丌始区域旱。每次移动之后更新队列中结点的截干l j ( g a i n ) 。 多水平方法： 多水平方法由三个过程组成，分别为粗化过程( c o a r s e n i n gp h a s e ) 、初始剖 分过程( p a r t i t i o n i n gp h a s e ) 、优化过程( u n c o a r s e n i n r e f i n e m e n tp h a s e ) 。粗化 过程分多个级别，每个级别罩采用一些粗化策略结合结点，得到下一级的粗化图。 粗化策略 5 一般有随机 兀酉e ( r a n d o m m a t c h i n g ) 、重边匹配( h e a v ye d g e m a t c h i n g ) 、 轻边匹配( 1 i g h te d g em a t c h i n g ) 等： 有向图并行计算中的多目标剖分算法 在粗化过程得到粗化图之后，在初始剖分过程里对该粗化图进行剖分。剖分方法 一般为贪婪图增长方法( g g g p ) 。优化过程按照粗化过程相反的方向，将初始剖 分过程得到的剖分映射到初始给出的图中。优化过程在映射过程中采用k i _ ，f m 方法对每次新映射得到的剖分进行优化。 上述各种无向图剖分方法广泛应用于c h a c o ，j o s t l e ，m e f i s ，p a r m e t i s ， p a r t y , s c o t c h ，s h a r p 等无向图剖分软件中【5 。 2 2 2 有向图及有向图剖分 有向图g = ( k e ) 同样由结点集净 v ，) 和边集e 主 e ，e 2 ，8 。) 构 成，称有向图的有向边改为无向边后得到的无向图为该有向图的基图b ( g ) = ( 以 b ( 目) ，如果基图是连通的，则称有向图是连通的。如果结点v f 和结点分别属 于某条有向边的始点和终点，则称结点v i 为结点的直接前继结点，结点为 结点v ，的直接后继结点。对有向图的结点v f ，称它的直接前继结点个数为该结点 的入度九( v 3 ，称它的直接后继结点个数为该结点的出度( h ) 。显然，按有向图给 定的单方向数据依赖关系，当且仅当结点v j 的所有丸( v f ) 个直接前继结点计算完 毕，结点u 才能被计算。定义g 中长度为上的路径为一组结点序列丁= ( “ “扣， u d ，满足( “f ，u j ) e ，如果u l = 札，则称该路径为回路。如果边的起点和始点是 同一个结点，则称该边为循环边。 如果有向图不包含回路，且不包含循环边，则该有向图中的结点按数据依赖 关系是可以依次被计算的，我们称该图为可计算的有向图。从实际应用中抽象出 来的有向图，一般均是可计算的。但是，如果有向图包含回路，需要根据不同的 应用特点，采取不同的策略，去掉这些回路，否则，有向图的计算就存在死循环。 文 7 针对辐射输运的特殊应用，提出在回路的数据依赖最薄弱的环节去掉相应 的有向边，避免了并行计算中的死循环。在本文以后的介绍中，我们均假设有向 图是可以计算的，即不包含回路或者循环边。 传统的有向图并行算法研究并不是面向科学数值模拟的，而是侧重于并行编 译等应用中的数据流分析，比较有代表性的是j a ，s h a r p 9 提出的剖分策略算法， y f l e e l 9 ，1 1 提出的区域分析算法，c k o u t s o u g e r a se ta 1 1 1 2 提出的极小化通信 开销算法， b l e e 1 3 提出的垂直分配算法等。下面介绍上述有向图剖分方法。 剖分策略算法： 剖分策略算法按结点的最早和最晚可执行时问，尽量将数据相关的结点分配 在同一台处理机 9 】。结点的最早可执行时间等于所有直接前继结点最早结束时 问的最大值。结点的最晚可执行时间等于所有直接后继结点最早可执行时问的最 小值，即保证所有直接后继结点能在最早可执行时间执行。该算法由于保证结点 有向图并行计算中的多目标剖分算法 在最晚可执行时间之前执行，所以并行效率比较高。由于数据相关的结点尽量被 分配在同一处理机上，该算法会减少通讯开销。但是由于该算法不考虑负载的均 衡，所以应用该算法得到的剖分的负载平衡效率不高。 区域分折算法： 区域分析算法将有向图中相连的结点结合成一些区域，每个区域大小满足一 定限制 9 ，1 1 ，然后再将这些区域分配到不同处理机。在区域分析算法中，每 个区域必须是单一入口的，即该区域只有一个最早可执行时间最小的结点。按照 结点结合区域的方向，区域分析算法分为顶部结合算法和底部结合算法。顶部结 合算法按照结点的执行顺序考虑结合结点，而底部结合算法从相反的方向考虑结 合结点。区域分析算法中一个区域内的结点被分在同一处理机，该算法可以减少 通讯开销。 极小化通信开销算法： 极小化通信开销算法将相互之间通信量大的结点结合成串，将其他结点放进 这些串里，然后将这些串分配给不同处理机。极小化通信开销算法给出的剖分质 量和最初结合的串有关。如果某个串的结点个数比较多，那么就会影响负载平衡。 由于极小化通信开销算法只能将通讯量大的结点结合成串，所以该算法不太适用 于剖分每个结点之间的通讯量大致相同的有向图。 垂直分配算法： 垂直分配算法首先按结点的最早可执行时间将结点进行水平分层，然后按照 处理机个数对这些结点进行垂直分层，再对垂直分层结果进行优化。进行优化的 时候主要考虑通讯丌销。在进行垂直分层及优化的时候，该算法不考虑连通性。 传统的有向图剖分方法不能综合考虑连通性、并行度、负载平衡、通信开销。 连通性是必须保证的，因为网格的计算通常依赖于周围邻居网格的信息，连通性 能减少处理机问的数据交换，易于并行实现。并行度影响有数据依赖关系的网格 计算的执行时间，所以我们要尽量提高算法内在并行度。为了将有向图并行计算 更好地融入到科学数值模拟的全过程中，需要保证剖分的各个子图的负载尽量均 衡= 2 3 并行计算的评判准则 我们需要找出综合考虑连通性、并行度、负载平衡、通信丌销四个目标的有 向图剖分方法。为了评价有向图并行计算的整个过程，我们引入如下概念。 1 ，最优加速比：假设有向图计算的串行时问为，可使用的处理机个数充分多 且处理机之间通信丌销为零时，有向图的最短并行执行时扫j 为咒，则称l 为 有向图的最优执行时问，并定义最优加速比s ft j l 。 有向图并行计算中的多目标剖分算法 2 算法加速比：当使用p 台处理机且处理机之间通信开销为零时，称有向图的 最短执行时间为阡为扫描并行算法的算法执行时间，并定义算法加速比都= t | | w pn 3 实际加速比：当使用p 台处理机且在具体并行机上运行时。称扫描并行算法 的运行时间昂为实际执行时间，并定义实际加速比昂= 乃昂。 显然，最优加速比代表了有向图内部隐藏的最大并行度，算法加速比真实地 反映了扫描并行算法的内在并行度，而实际加速比反映了具体并行机的通信开销 对性能的影响，是用户可以获得的真正的算法性能。当然，我们设计扫描并行算 法的目的是，希望算法加速比逼近最优加速比，而实际加速比又逼近算法加速比。 对于负载平衡目标，我们采用通常的负载平衡效率 1 4 给予评价。负载平衡 效率的定义如下： p y m ( g ) 孙2 面石i = l 面砑万 4 其中，o ( g i ) 代表子图g ，中所有结点的计算量的总和。 对通信开销，我们采用无向图剖分算法 5 的最大截边数给予评价，即 ，p = m a x ，p l 椤( g ，) j( 5 ) 其中，9 ( g ，) 代表子图g 与其他相邻子图连接的有向边的权重总和。 综合权衡这四个目标，连通性是必须首先确保的前提条件，否则无法保证我 们的剖分算法能够集成到数值模拟的整体中。并行度、负载平衡和通信开销是相 互关联的。对有向图，算法加速比高的剖分算法可能负载平衡效率较低，而通信 丌销又较大。文【8 】的可扩展分析表明，只要图中每个结点的计算量较大，在延 迟小于几个微秒的并行机上，通信丌销对并行性能的影响可以忽略，实际加速 比可以逼近算法加速比，但是，在延迟较大的并行机上，最大截边数冲将是影响 并行性能的一个关键因素，算f 去：d n 速比适当而挣较小的剖分算法将获得最优的实 际加速比。鉴于此，我们重点权衡算法加速比a p 和负载平衡效率仰，同时兼顾 考虑最大截边数伽。 将非规则网格间计算中的数据依赖性抽象成有向图，并采用有向图剖分方法 进行区域分解的时候，由于网格的拓扑结构的限制，在满足连通性的i i 提下，综 合考虑数值模拟的整体体，必须权衡算法加速比和负载平衡效率，同时兼顾考虑 最大截边数。一般来说，我们可以要求有向图剖分在满足连通性及负载平衡效率 达到一定数值范围的前提下，尽量提高算法加速比。 有向图并行计算中的多目标剖分算法 2 4 基于区域分解的扫描并行算法 给定p 台处理机，假设有向图g 按剖分算法被剖分成结点互不重叠的p 个 子图 g ，g e ，q ) ，分配给p 台处理机，且结点v 的优先级次序为t ( d 。九( 订为 结点v 的直接前继结点个数，蟛为可计算结点队列。0 ( v ) 开始的时候等于九( ， 当且仅当 ( v ) 等于零时，结点v 才能被计算。适当修改文 4 】提出的通量扫描并行 算法，可成为适合有向图并行计算的通用的扫描并行算法。 有向图并行计算的扫描并行算法 f o r ( f = 1 ，2 ”，p ) 处理机p fp a r a l l e l d o 1 并行初始化。 1 1 设置局部结点队列蟛为空集： 1 2 f o r ( 子图g j 的所有结点v ) 0 ( v ) = 九( v ) 1 3 f o r ( 子图g 的所有结点v ) f i f ( o ( y ) = = 0 ) 将v 按优先级t ( v ) 插入队列蟛中) 2 扫描并行计算。 w h i l e ( 有向子图g 中存在结点没有被计算) 2 1w h i l e ( 毋非空) 2 1 1从蟛中移出第一个结点u ，计算该结点，并将其从队列中 删除； 2 1 2 f o r ( 结点u 的每个直接后继结点订 i f ( v g i ) 0 ( v ) = 0 ( - 1 ； i f ( o ( v ) = = 0 ) 将v 按优先级t ( 插入队列蟛中 e l s e 将结点“的数据信息发送给拥有结点v 的子图所在 处理机 e n df o rw h i l e ( 蟛非空) 2 2 接收所有处理机发送来的信息： 2 3f o r ( 每个接收的信息) 2 3 1 存储信息中包含的结点“的数据； 2 3 ，2 f o r ( 结点“的每个直接后继结点v ) 0 ( v ) = 0 ( v ) - 1 ： 有向图并行计算中的多目标剖分算法 i f ( o ( 0 = = o ) 将v 按优先级t ( v ) 插入队列蟛中 ； ) ) e n df o r w h i l e ( 有向子图g 中存在结点没有被计算) ) e n df o rp a r a l l e ld o 按照并行计算模型的假设，有向图中结点的权重相同，可设为1 ，边的权重 相同，设为1 。按照该算法，将有向图剖分在具体并行机上执行之后便可得到实 际执行时间和实际加速比。 我们设计扫描并行算法的目的是，希望算法加速比逼近最优加速比，而实际 加速比又逼近算法加速比。所以在得到具体有向图剖分之后，需要利用单机计算 算法加速比，以便得到合适的有向图剖分。为了简单，不妨假设所有结点的计算 时间均等，都为1 。t i m e s t e p 为时间步。f ( o 为处理机a 计算结束的时间。w ( u ) 为计算u 所需要的时间，这里w ( “) = 1 。计算算法加速比的算法由修改扫描并行 算法而得，具体算法如下。 计算算法加速比 1 初始化队列蟛。 f o r ( f = 1 ，2 ，p ) 处理机肌d o 1 1 设置局部结点队列蟛为空集： 1 2f o r ( 子图g f 的所有结点v ) 0 ( v ) = 九( d ，w ( m ) = 1 ； 1 3f o r ( 子图g ，的所有结点v ) i f ( o ( v ) = = 0 ) 将v 按优先级t ( 订插入队列蟛中) ： ) e n d d o 2 计算算法并行计算时间。 w h i l e ( 有向图g ，中存在结点没有被计算) 2 1f o r ( 即，) i f ( f ( i ) = t i m e s t e p 且蟛非空) 2 1 1从奸中移出第一个结点址计算该结点，并将其从队 列中删除； 尺f ) = f ( j ) + w ( “) ； 2 1 2 f o r ( 结点“的每个直接后继结点v ) 0 ( 1 = 0 ( v ) 一1 ： i f ( 0 ( v ) = = o ) 将v 按优先级t ( v ) 插入v 所属子 有向图并行计算中的多目标割分