王振亚，叶友达

基于多核计算机集群系统的网格分区策略

王振亚，叶友达

(国家计算流体力学实验室，北京100191)

网格分区技术是提高并行计算效率的重要手段。基于图的分区技术(如Metis等)已经可以完全做到负载平衡，但是随着计算机集群系统的发展，节点间的通讯成为并行计算中的重要时间消耗部分。为此，提出一种适用于非结构网格的新分区策略(MC Partition method)，减少了节点间的通讯规模，结果表明，这种分区方法可以较大的提高并行计算效率。

非结构网格;多核;集群;并行;通信

0 引言

计算流体力学(CFD)在航空航天以及很多工业过程中都得到了非常广泛的应用。由于求解问题的复杂程度越来越高，需要的计算网格数量急剧增加，如果说10年以前的网格数量主要在百万量级的话，现在使用上千万量级的网格求解已经很常见的，对于一些复杂外形，网格规模甚至达到上亿量级，并行计算已成为必需的手段。对基于非结构网格的解算器而言，由于非结构网格不具有结构网格数据隐含的顺序性，用什么原则进行网格分区，怎样才能够提高非结构网格解算器的并行计算效率，一直是其中的一个重要问题。

在网格规模增加的同时，计算机技术也在飞速进步，虽然单核运算速度比十年前快了一个量级，但是计算机技术中最令人瞩目的属于大规模并行计算机的飞速发展。从2012年11月13日的第40届TOP500排名［1］中可以发现，排名第一的Titan系统的Linpack性能达到17.59Pflops，排在第十位的Fermi系统也达到1.72Pflops;而进入TOP100的系统性能也从一年前(38届)的115.9Tflops提升到243.9Tflops。工业标准化的集群系统(Cluster)已经牢牢占据了本届TOP 500HPC排行榜的垄断地位，从2001年6月只有32套，发展到2012年411套系统，82.2%的比重，十年间增长了近13倍。越来越强的计算能力对算法提出了更高的要求。由于采用GPU等加速技术，单个节点的计算速度可以得到大幅提高，但是现在大家发现当前大规模并行计算机遇到的瓶颈主要是数据交换的速度，包括网络速度，甚至I/O速度等［2］。新的集群系统每个节点都是由多核CPU组成，计算中的数据交换与通信就存在计算机节点内部的总线速度——节点之间的网络速度——I/O速度之间的平衡，从而需要计算软件用更多的注意力来解决这些新的问题。

本文将主要通过分区方法的改进来提高并行计算效率。第一部分将通过分析提出问题，并提出解决问题的方法;第二部分将在通过数值计算来验证新方法;第三部分将是本文的小结。

1 算法介绍

一直以来，负载平衡和减少通信量都是并行计算中必须考虑的两个问题。并行计算的计算时间一般可以如下表示:

并行计算时间=继承的串行计算时间+

并行的额外时间开销(1)

负载平衡就是要求分配到每个计算单元的计算规模基本一致，它和并行继承的串行计算时间有关，计算中不希望出现由于负载不平衡造成快的计算单元等待慢的计算单元的情况;通信量的减少就可以相应减少计算中不同计算单元间数据通信产生的时间。

对于非结构网格而言，随着很多基于图(graph)的分区软件(如Metis［3］等)的应用，负载平衡在基于非结构网格的计算流体力学软件中已经可以很方便做到［4］。对于同样的网格(约16 000 000单元)和同样的网格分区(用pmetis分成112个区域)，完全负载平衡，我们在两个不同的集群系统中做了测试(表1)。从结果可以发现，两个计算机系统的速度相差7倍，如果再仔细分析，可以发现其中由于每个计算单元的运算速度提高使得相应的计算速度提高了4倍，然而由于数据传输速度的提升使得计算时通信速度提高了24倍。

表1 不同集群系统比较Table 1Comparation of different clusters

为了进一步研究数据通信在计算中的影响，我们在把一个网格(约39 000 000单元)分成不同数量的任务并行计算，计算结果见表2。可以发现，随着参与计算的计算单元数量超过128，并行计算效率逐渐下降。由于在网格分区时已做到负载平衡，并行计算效率降低主要原因是因为随着参与计算的计算单元数量增加，分配到每个计算单元的网格数量随之减少，相应造成了通信数据在总的计算数据中所占的比例增加，通信造成的时间开销在总计算时间中的比重不再是不可忽略的小量。

表2 并行计算效率比较Table 2Comparation of the parallel computing efficiency

从而可以发现，在达到负载平衡以后，通信速度已经成为当前的并行计算流体力学软件一个主要瓶颈，这个问题和连接计算集群每个节点的网络的物理特性有关，包括网络拓扑结构、网络带宽等，同时和通信数据的构成也有很大关系。当前计算机集群的每个节点的CPU一般都是由多核组成，节点内的多核之间的数据通信是基于总线，不同节点之间的数据通信是基于网络，而对于当前的计算机技术而言，计算机内部总线的速度比网络速度要快得多。显然可以发现，如果在分区时仅仅考虑负载平衡的话，则分区形成的每个子区基本上相互独立，那么会在并行计算中造成普遍以网络速度来衡量数据通信速度的情况，表3采用和表1同样的网格，用Metis分成48个分区，可以做到完全负载平衡，考察其在一个由6节点共48核(6×8)的集群上运行的结果，在每个节点中取一个核为代表，研究其通信数据的分布情况。

表3 只考虑负载平衡的分区通信数据分析(Metis)Table 3Analysis of communication data considering of load balancing

从表3中可以发现，根据这种分区原则得到的网格分区，节点之间的通信量在每个计算单元的全部通信量中所占比例非常大，有的计算单元甚至都在和本节点外的计算单元通信，而节点之间的通信是按照网络速度来计算的，这样的数据分布必然会大大降低通信速度。通过这样的分析，为了进一步提高数据通信速度，我们需要——调整计算单元内的通信数据分布，增加节点内通信数据的比例。

如果计算机集群系统由N个节点组成，每个节点内有M个核(记为N×M)，根据这个原则，我们提出多核集群分区策略(MultiCore Partition，简称MC)，可以如下描述:

MC Partition策略(如图1)

1)按照负载平衡的原则把网格分为N个区，对应N个节点;

2)For i=1 to N

按照负载平衡的原则把每一个子区分为M个区，生成的子区分别对应于第i个节点的M个核;

图1基于多核的分区方法(MC Partition)Fig.1Partition method by MC

采用表3对应的网格，我们在考虑计算机集群系统(6×8)上每个节点的多核性质后，按照MC方法进行分区，分区结果见表4。由于节点之间以及核之间的分区算法考察了负载平衡，所以也达到了完全负载平衡。从表4可以发现，基于这种分区策略的分区结果，使得每个计算单元的节点内通信数据所占比例大大增加，平均值提高了35%。这种分区策略实际上造成的结果是使得计算数据不仅仅在计算机内存中存放在一起，同时它们在几何上也是相邻的。根据基本常识判断，这样应该会带来通信时间的减少，从而提高计算速度和并行效率。

表4 多核分区方法(MC Partition)的通信数据分析Table 4Analysis of communication data by MC partition

2 数值结果

表5为表3和表4对应的两种不同分区方法在同一个6×8集群系统的测试计算结果，从中可以看到采用MC Partition方法的分区使得通信速度提高了32%，总的计算速度提高了10%。

并行加速比一般如下表示［5］:

表5 不同分区方法比较(6×8)Table 5Comparation of different partition methods(6×8)

为了更好地测试计算方法，我们用一个更大规模的网格(约33 600 000单元的非结构网格)来计算，分成112个分区，测试在同一个7×16集群系统进行。测试结果在表6给出。可以看出，虽然此计算机系统的网络性能已经比较好，但是在采用MC Partition方法之后，通信速度仍然提高了32%，计算速度提高了近10%。

表6 不同分区方法比较(7×16)Table 6Comparation of different partition methods(7×16)

串行计算的CPU时间是不变的，并行计算时间按照(1)式计算，由于并行计算中负载平衡的实现，每个计算单元所继承的串行计算量也是基本固定的，如果共有K个参与计算的单元，则每个计算单元所继承的串行计算量可以近似为1/K;如果通信效率提高30%，那么就可以提高并行加速比，尤其在数据通信时间在计算中所占比例很大的时候，将会得到更明显的表现。

从表5和表6可以发现，由于两种分区算法都能够很好的保证负载平衡，所以并行计算中的串行计算部分的时间开销都基本保持不变。为了提高并行计算中的串行计算部分的速度，当前的并行计算机集群系统已经大量采用了如GPU等加速计算技术，但是数据传输部分的通信时间开销也是并行计算中需要重点注意的部分。对比表6和表2，可以发现对于总的网格量而言，112个分区基本上还在并行计算的线性加速区内，由于计算条件限制，没有采用更多的计算单元，我们可以预计在分区增加、计算单元增加的情况下，这种分区方法仍然是可以有效提高通信速度的。

3 结论

本文提出了一种适合现代多核计算机集群系统的分区方法(MC Partition)，分区时不仅可以达到每个计算单元之间的负载平衡，而且由于考虑了计算机集群系统每个节点内多核的特点，让计算机内更高速的数据传输部件传输尽可能多的数据，大大减少了并行计算中依靠节点间的网络传输的数据量，较大的提高了数据传输速度，提高了计算速度和并行效率。

当然，对于CFD而言，并行计算的数据传输不可能做到速度为零，但是我们通过考虑计算机系统的特点，确实可以提高并行计算的效率。

致谢:感谢国家计算流体力学实验室的周越同志大力提供计算资源。

［1］http://www.top500.org/

［2］Hu Q F，Numerical simnulation and high-performance computer［C］//Beijing:seminar on key technology in high performance numerical simulation of military engineering，2010.(in Chinese)胡庆丰.数值模拟和高性能计算机［C］//北京:军工高性能数值模拟中重大基础关键技术研讨会会议论文集.2010年1月.

［3］Karypis G，Kumar V.Multilevel k-way partitioning scheme for irregular graphs［J］.Journal of Parallel and Distributed Computing，1998，48:96-129.

［4］Wang Z Y，Lu S，Ye Y D，Grid partition of unstructured grid［C］//14thComputational Fluid Dynamics Conference，2004(in Chinese)王振亚，卢笙，叶友达.非结构网格分区技术研究［C］//第十二届全国计算流体力学会议论文集，2004.

［5］Michael J Quinn.Parallel programming in C with MPI and OpenMP［M］.Beijing:Tsinghua University Press.

A new grid partition strategy for muliti-core cluster system

Wang Zhenya，Ye Youda
(National Laboratory of Computational Fluid Dynamics，Beijing100191，China)

Grid partition method is important to the efficiency of parallel computing.By now，partition method on graph，as Metis，can do load balancing very well.While as the cluster systems improve，communication between node of cluster becomes important.A new partition strategy for unstructured grid according to the new multi-core computer cluster system is proposed.As it is realized and proven to reduce the communication between the nodes，it can improve the parallel computing efficiency about 10%.

unstructured grids;multi-core cluster;parallel;communication

V211.3

Adoi:10.7638/kqdlxxb-2013.0013

0258-1825(2015)01-0087-04

2013-01-24;

2013-05-06

王振亚(1974-)，男，湖南醴陵人，博士，助理研究员，主要从事非结构网格生成以及基于非结构网格的数值计算软件研制工作.E-mail:niels_wang@163.com

王振亚，叶友达.基于多核计算机集群系统的网格分区策略［J］.空气动力学学报，2015，33(1):87-90.

10.7638/kqdlxxb-2013.0013.Wang Z Y，Ye Y D.A new grid partition strategy for muliti-core cluster system［J］.Acta Aerodynamica Sinica，2015，33(1):87-90.