并行图剖分优化策略研究
发布时间：2020-08-28 09:20
大规模数值并行计算应用通常采用“分而治之”思想进行任务划分。确保计算负载均衡和处理机间通信开销最小,是获得高效率的关键,因此如何合理有效地对任务剖分至关重要。图剖分是借助图论知识,将计算依赖关系抽象成图,把任务划分转换成图剖分问题。如何在并行平台下高效地将图剖分为多个子图,确保计算和通信负载均衡,是并行图剖分的主要研究内容。在设计图剖分算法时,需要综合考虑连通性、并行度、负载平衡、通信开销等因素。 传统图剖分算法和软件未考虑当前多核机群平台中结点内和跨结点通信开销之间的差异,而是将通信开销单一化处理。随着单结点内处理器核数不断增加,结点内通信的比重日趋增加,结点内外这种通信开销差异的影响日益显著,对并行计算综合性能影响愈来愈不容忽视。为此,本文针对多核集群平台大规模并行计算,给出了一种新的图剖分策略,在尽可能满足计算负载平衡的前提下,使结点间通信开销最小,对剖分策略进行了性能分析和数值实验,结果显示该策略可以进一步用来减少多核集群平台上的通信开销。 很多实际数值模拟问题(如动网格CFD计算、粒子模拟等)需要动态调整计算任务以满足计算和通信负载均衡,图(超图)重剖分策略重在解决此类并行任务动态划分问题。本文综合分析了基于扩散的重剖分策略和重映射重剖分策略,对现有的重剖分模型进行了量化,以权衡重剖分过程中的通信和迁移开销;在此基础上对超图的重剖分方法进行了改进,给出了一种适合超图的重剖分策略,开展了算法分析设计,并将该重剖分策略在典型并行剖分软件ParMetis中加以实现,与ParMetis中的已有两种剖分策略进行了对比分析和数值实验。结果显示该新重剖分策略的开销要优于ParMetis中的扩散方法和重映射方法,而执行时间也比较接近。
【学位单位】：国防科学技术大学
【学位级别】：硕士
【学位年份】：2010
【中图分类】：TP338.6
【部分图文】：
指不在W 中而且与W 中顶点相邻的所有adj (W ) {u V W : v W ( u , v ) E} 与顶点 6 相邻，而且这两个顶点的度都10}。当某个子图中的顶点两两相邻时，点 3、7 与 11 构成的子图为完全子图。顶点组成的有序集（u1,u2,…,um+1），其此时称 m 为该路径的长度。一条长 m u1,u2,),(u2,u3),…,(um,um+1)。如果存在一条以 v 连通。当 um+1=u1时，称路径(u1,u2,…不同，则称之为简单路径，而所有的顶点回路中(u1,u2,…,um+1)中，如果所有边都…，um互不相同，则称之为基本回路。
国防科学技术大学研究生院工程硕士学位论文任务抽象为图，在网格节点或是网格单元上进行模拟计算，也可以同时二者网格单元上模拟计算。如果计算主要是在网格节点上进行，可按如下方法把网格转换成图：网格的每个节点变成图中的顶点，顶点之间的连线即为图的边，由此得到的图称为节点图。如果计算主要在网格单元上进行，则每个网格单元对应图中的一个顶点，如果有两个单元共享同一个边，则相应的顶点之间存在着边，由此得到的图称为对偶图。如图 2.4(a)中，在计算中需要多次对每个三角网格进行计算，因此需要使用其相邻三角网格的数据，所以可以把该问题用图顶点权重来表示每个三角网格的计算量，而边则用于表示相邻两个网格之间的数据通信。然后把抽象成的数据关系图的顶点剖分成 k 个不相交的子集，也就是把网格节点或网格单元剖分成了 k 个具有相同顶点数的剖分域，并把这 k 个部分域分配到不同的处理机来执行以提高并行执行的效率。
国防科学技术大学研究生院工程硕士学位论文1 2 (V V))，在同一子集中，任何两顶点间都没有边相连1V和2V。对分图模型特别适合于初始任务和最终任务不同问模拟计算中的各阶段任务的相互转换、非方阵矩阵-向量相非方阵矩阵-向量相乘的对分图[25]，矩阵的行列元素分别)的顶点集1V ,2V 表示，顶点集1V中的顶点的权重等于该顶点元素的个数，例如顶点4r 的权重为 1，其顶点的权重反映了量，任何拥有顶点ir 的处理机都会获得 y Ax的部分解iy ，则可影响到向量 x 的求解。另外还可以通过设置列顶点为权最小化，对2V 中的顶点赋予权重可以用于另一个操作的相乘的结果作为迭代模型中的前瞻子等。
本文编号：2807391
【学位单位】：国防科学技术大学
【学位级别】：硕士
【学位年份】：2010
【中图分类】：TP338.6
【部分图文】：
指不在W 中而且与W 中顶点相邻的所有adj (W ) {u V W : v W ( u , v ) E} 与顶点 6 相邻，而且这两个顶点的度都10}。当某个子图中的顶点两两相邻时，点 3、7 与 11 构成的子图为完全子图。顶点组成的有序集（u1,u2,…,um+1），其此时称 m 为该路径的长度。一条长 m u1,u2,),(u2,u3),…,(um,um+1)。如果存在一条以 v 连通。当 um+1=u1时，称路径(u1,u2,…不同，则称之为简单路径，而所有的顶点回路中(u1,u2,…,um+1)中，如果所有边都…，um互不相同，则称之为基本回路。
国防科学技术大学研究生院工程硕士学位论文任务抽象为图，在网格节点或是网格单元上进行模拟计算，也可以同时二者网格单元上模拟计算。如果计算主要是在网格节点上进行，可按如下方法把网格转换成图：网格的每个节点变成图中的顶点，顶点之间的连线即为图的边，由此得到的图称为节点图。如果计算主要在网格单元上进行，则每个网格单元对应图中的一个顶点，如果有两个单元共享同一个边，则相应的顶点之间存在着边，由此得到的图称为对偶图。如图 2.4(a)中，在计算中需要多次对每个三角网格进行计算，因此需要使用其相邻三角网格的数据，所以可以把该问题用图顶点权重来表示每个三角网格的计算量，而边则用于表示相邻两个网格之间的数据通信。然后把抽象成的数据关系图的顶点剖分成 k 个不相交的子集，也就是把网格节点或网格单元剖分成了 k 个具有相同顶点数的剖分域，并把这 k 个部分域分配到不同的处理机来执行以提高并行执行的效率。
国防科学技术大学研究生院工程硕士学位论文1 2 (V V))，在同一子集中，任何两顶点间都没有边相连1V和2V。对分图模型特别适合于初始任务和最终任务不同问模拟计算中的各阶段任务的相互转换、非方阵矩阵-向量相非方阵矩阵-向量相乘的对分图[25]，矩阵的行列元素分别)的顶点集1V ,2V 表示，顶点集1V中的顶点的权重等于该顶点元素的个数，例如顶点4r 的权重为 1，其顶点的权重反映了量，任何拥有顶点ir 的处理机都会获得 y Ax的部分解iy ，则可影响到向量 x 的求解。另外还可以通过设置列顶点为权最小化，对2V 中的顶点赋予权重可以用于另一个操作的相乘的结果作为迭代模型中的前瞻子等。
【参考文献】
相关期刊论文 前1条
1 岳菲菲;王海军;王新;黄东波;;高性能计算通信机制分析与研究[J];计算机工程与科学;2009年S1期
本文编号：2807391
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/2807391.html
