基于配置文件的并行程序自动映射实现方法

摘要

基于配置文件的并行程序自动映射实现方法属于并行程序进程映射的技术领域，其特征是：自动获取目标平台的网络拓扑图，减少用户干预；对并行程序中每条组通信按照分解知识库中分解算法拆分成对应进程的点通信并形成组通信矩阵，把得到的组通信矩阵和并行程序中原有的点通信矩阵线性叠加得到并行程序的通信拓扑图；然后使用K－way图划分算法实现并行程序的进程映射。实验证明，通过本发明找到的最优进程映射方式，比MPI默认的进程映射方式在性能方面具有显著提高。

说明书

技术领域：

本发明属于并行程序进程映射的技术领域。

背景技术：

对称多处理器(Symmetric Multi-Processor，SMP)集群系统和网格系统被广泛的使用在基于消息传递的并行科学计算应用中。由于这些系统固有的通信异构性，映射虚拟进程到实际的物理处理器对并行程序的性能具有显著的影响。例如，当前大量使用多核处理器构建的集群服务器，节点内部的通信性能远大于节点之间的通信性能。对于像英特尔等公司的多核处理器，共享第二级缓存(L2 Cache)的两个核的通信性能要远大于节点内部其他核之间的通信性能。在网格系统中，同一个集群服务器内部节点之间的通信带宽远大于两个集群之间的带宽。因此，自动的映射虚拟进程到物理处理器对于提高并行程序的性能具有重要意义。

映射并行程序的任务拓扑到底层的物理拓扑的问题可以规约为图映射问题。例如，图G＝(V_G，E_G)用于描述表示并行程序的通信拓扑，节点代表虚拟进程，边权重代表进程间通信强度。图T(V_T，E_T)用于描述目标平台的物理拓扑，节点代表实际的物理节点，边的权重代表通信性能。我假设图G和图T节点数相同，每个进程计算的负载均衡。假设F是图G映射到图T后得到的图的边的权重之和。进程映射要解决的问题就是要找到一种映射方式，使得得到的图的边权重和F最小，该问题已经被证明为NP完全问题。

当前存在一些方法优化并行程序的进程映射问题。有些系统通过得到应用程序的通信拓扑，通过图划分算法找到最优的并行程序进程映射，但是他们的方法需要用户预先提供目标平台的网络拓扑。参见：A.Pant，H.Jafri，Communicating efficiently on clusterbased gridswith MPICH-VMI(2004 CLUSTER)。也有一些研究者提出了基于配置文件Profile实现并行程序的进程映射，但是他们的工具只能解决点通信的进程映射，不能处理组通信的映射。参见：H.Chen，W.G.Chen et.al.MPIPP：An automatic profile-guided parallel process placementtoolset for SMP clusters and multi-clusters(2006 ICS)。

总之，当前对于处理并行程序的进程映射问题的方法存在的缺陷包括：只能解决点通信的进程映射问题，不能处理组通信的进程问题；需要用户干预比较多，自动化程度不高。

发明内容：

本发明的目的就是寻找并行程序的最优映射，提高并行程序的性能。

本发明的思路是：自动获取目标平台的网络拓扑图，减少用户干预；对并行程序中每条组通信按照分解知识库中分解算法拆分成对应进程的点通信并形成组通信矩阵，把得到的组通信矩阵和并行程序中原有的点通信矩阵线性叠加得到并行程序的通信拓扑图；然后使用K-way图划分算法实现并行程序的最优进程映射。

本发明特征在于，所述方法是在计算机上依次按以下步骤实现：

步骤1)初始化

建立一个通信记录动态插装库SIM-MPI，

建立一个组通信分解算法知识库，其中集成了以太网、Myrinet、以及Infiniband三种网络平台的消息通信库MPI的组通信函数分解算法，以及与所述各组通信函数算法内含的点对点通信进程为基础的进程映射配置文件，以便把所有组通信函数分解为若干次设定的点对点通信并映射到对应的物理计算单元中；

步骤2)获得目标平台的网络拓扑图

对输入计算机的目标平台上N个节点的网络拓扑图，按下述方法使用N个进程测试，得到一个N*N大小的网络拓扑图，其步骤如下：

步骤(2.1)每次有N/2对进程同时进行通信，用基于消息通信库MPI的乒乓测试方法Ping-Pong，对所述目标平台上任意两点之间用不同大小的消息进行延迟测试和带宽测试，得到一个N*N大小的网络拓扑图，

步骤(2.2)按设定次数重复步骤(2.1)，得到一个用测试结果平均值表示的N*N大小的网络拓扑图NTG(Network Topology Graph)；

步骤3)获得并行程序的通信配置文件

用户在编译应用程序时，链接通信记录动态插装库SIM-MPI，运行插装后的并行程序，得到并行程序的通信配置文件Profile，其中，对于点通信，至少记录有消息类型，消息大小，消息源和目的地址，对于组通信，至少记录有消息大小，根进程，以及通信域，从而对不同的进程创建不同的通信配置信息，并以映射表形式保存各通信配置信息；

步骤4)提取点通信矩阵

从步骤(3)得到的通信配置文件Profile中直接提取点通信信息，得到并行程序的点通信矩阵，任意地从第M进程向第N进程发送一个消息K，则在点通信矩阵的M*N和N*M的位置都记录K，K是一个向量序列，对于点通信，至少记录有消息类型，消息大小，消息源和目的地址，

步骤5)分解组通信函数，得到组通信矩阵

其步骤如下：

步骤5.1)从通信配置文件中依次提取组通信信息，

步骤5.2)从步骤(5.1)得到的组通信信息中，提取对应的组通信号、目标平台通信库的名称和版本号，输入所述组通信分解知识库，

步骤5.3)在所述组通信分解知识库中寻找对应的组通信函数分解算法，

步骤5.4)对步骤(5.2)所述的组通信按照步骤(5.3)找到的分解算法进行分解，把分解后的结果记录到对应的组通信矩阵中，得到并行程序的组通信矩阵；

步骤6)获得并行程序的通信拓扑图

将步骤(4)，步骤(5)分别得到的并行程序的点通信矩阵和组通信矩阵线性叠加，得到并行程序的通信拓扑图CTG(Communication Topology Graph)；

步骤7)通过图划分算法得到最优进程映射

通过K-way图划分算法计算所述通信拓扑图CTG到目标平台网络拓扑图NTG的最小通信开销的映射方式，

其步骤如下：

步骤7.1)初始化，将所述通信拓扑图CTG随机映射到所述目标平台网络拓扑图NTG，得到映射图形CNG(Communication and Network Graph)，其中映射图形CNG的每个节点对应图CTG和图NTG中一个节点，假设CTG和NTG有相同节点个数，CTG的边的权重表示通信频率和通信量，NTG边的权重表示通信延迟和带宽，CTG映射到NTG得到CNG的边的权重使用Hockney通信模型计算，假设CNG所有边的权重和为W_i，

步骤7.2)从上述CNG图中任意取两个节点，交换对应的CTG和NTG节点，得到新的映射图CNG′，假设CNG′所有边的权重和为W_j，

ε＝W_j-W_i

其中，每个ε值对应一个映射图CNG′

步骤7.3)重复步骤(7.2)，直到图CNG中所有节点全交换一次，这样得到一组ε值，

步骤7.4)选取上述ε值最大时对应的映射图CNG′，分别记做ε_m和CNG′_m

步骤7.5)用步骤(7.4)得到的图CNG′_m作为新的初始值，重复步骤(7.2)到步骤(7.4)，重复次数为P/2-1次，其中P为进程数，这样得到P/2个ε_m值和映射图CNG′_m，

步骤7.6)分别计算步骤(7.5)得到的P/2个ε_m值的前K项和S_K，其中$S_k=\underset{i=1}{\overset{K}{\Sigma }}{ϵ}_m,$K＝1，2，...，P/2，一共P/2个前K项和S_K，选取S_K的最大值，记做S_m，如果该值为正数，按照步骤(7.5)得到的映射图CNG′交换对应节点对，

步骤7.7)重复步骤(7.2)到步骤(7.6)，直到S_m为非正数结束，将该结果作为最终映射结果；

步骤8)重新运行并行程序

按照步骤(7)得到的映射方式重新运行并行程序。

本发明通过把MPI通信库中不同组通信函数分解成相应的点通信，然后和并行程序中原有的点通信线性叠加形成并行程序的通信拓扑图，利用图划分算法实现并行程序的进程映射。实验证明，通过本发明找到的最优进程映射方式，比MPI默认的进程映射方式在性能方面具有显著提高。

附图说明：

图1.基于Profile的并行程序自动映射框架图；

图2.64*64CPU通信延迟拓扑图；

图3.64*64CPU通信带宽拓扑图；

图4.64个进程下Ring算法分解后的通信拓扑图；

图5.64个进程下Bcast通信函数映射结果；

图6.64个进程下Reduce通信函数映射结果；

图7.64个进程下Barrier通信函数映射结果；

图8.64个进程下Allgather通信函数映射结果；

图9.64个进程下Allreduce通信函数映射结果；

图10.64个进程下Alltoall通信函数映射结果；

图11.64个进程下Gather通信函数映射结果；

图12.64个进程下Scatter通信函数映射结果；

图13.32个进程下Allreduce通信函数映射结果。

具体实现方式：

本发明提出了一个基于Profile的并行程序自动映射的实现方法，我们的方法可以对点通信和组通信进行分析，得到并行程序的最优映射方式，我们的系统框架如图1所示。该方法包括以下几个关键模块：

自动获得目标平台的网络拓扑图；

收集并行程序的通信Profile，包括点通信和组通信；

分解每条组通信函数，获得并行程序的拓扑图；

使用图划分算法计算应用拓扑图到网络拓扑图的最优映射方式。

目标平台的网络拓扑图

我们的测试原理是基于消息通信库(MPI)的乒乓(Ping-Pong)测试方法，针对目标平台任意两点之间进行Ping-Pong测试，就可以得到相应的两点之间延迟和带宽。为了保证测试效率，我们采用并发测试的方法，即如果目标平台有N个物理计算单元，我们的测试在每一步迭代的过程中都同时执行N/2对的测试，每一对之间采用Ping-Pong测试。这样的测试方法还有另外一点考虑，就是我们可以更有效的模拟MPI并行程序执行时的目标平台的网络特征。MPI并行程序在执行的过程中，会同时有多个进程在进行并发的通信，因此我们的测试方法是可以从一定程度上接近MPI并行程序实际的执行情况。

另外为了保证测试数据的准确性，尽量减少误差。在测试的时候，我们采取多次循环求平均的方法来得到相应的测试结果。同时在进行带宽测试时，为了能够更为准确的反映带宽情况，在进行带宽的Ping-Pong测试时，我们选取了6个不同大小的发送消息，分别从4K增大到4M。对于这6组测试结果，我们在求平均带宽之前，会将其中的最大值和最小值去掉，这样会更能够有效的减少误差的影响。

我们利用我们开发的网络拓扑矩阵测试工具，对我们的测试平台进行了测试。分别得到对应的延迟通信矩阵和带宽通信矩阵，具体请见说明书图2和图3。从测试结果中，我们可以看出，在延迟属性方面，目标平台节点内部的延迟要好于节点之间的传输延迟；在带宽方面，测试平台节点内部的通信带宽也要好于节点之间的传输带宽。这些测试结论也是与实际情况相一致的，这也说明我们的测试工具是能够很好的反映目标平台的网络拓扑信息。

获得并行程序的通信Profile

标准MPI接口提供给开发人员一个插装MPI函数的接口，而不需要用户修改程序的源代码。我们使用这个标准接口，实现了插装库，用户在编译程序的时候需要连接这个动态插装库(SIM-MPI)。对于点通信，主要记录消息类型，消息大小，消息源和目的地址；对于组通信，需要记录消息大小，根进程，通信域；由于MPI支持进程组概念，在不同的进程创建不同的通信域，我们维护了一个映射表用来保存通信域信息。程序执行结束后，事件保存在本地节点，然后使用脚本把事件记录文件收集起来。

分解组通信

以前的进程映射方法只考虑了点通信对程序性能的影响，我们把MPI的组通信分解成点通信来解决这个问题。在不同的MPI通信库，针对不同的网络平台，不同的消息大小，不同的进程数量，分别有不同的组通信算法实现。我们对这些算法进行分类，创建了一个包含各种分解算法的知识库。按照知识库里面的分解算法，我们可以将组通信函数分解成若干次特定进程之间的点对点通信，并以这些点对点通信为基础，利用启发式算法，将不同的进程映射到相应的物理计算单元，即提供进程映射配置文件。

目前，我们的知识库已经将三种常见网络平台，以太网(Ethernet)、Myrinet和Infiniband的MPI组通信函数算法集成进来，我们的方法可以为上述三套常用网络平台下的组通信函数提供性能更好的进程映射配置文件。

我们的组通信分解算法可以将一条组通信分解成若干次不同消息大小的点对点的通信，这样的分解不仅可以全面、准确的展示一条组通信的全部信息，分析组通信的算法信息，同时利用我们的组通信分解算法所分解出来的信息，可以为我们随后的组通信进程映射提供有效的数据基础。图4显示了一个64进程的Ring算法分解成点对点后的通信拓扑图。从图中可以看出，消息主要分布在矩阵的对角进程上。

产生新的进程映射

在我们的发明中，进程映射的主要工作是将进程之间的通信拓扑图映射到目标平台的网络拓扑图上，映射的原则是保证整个系统的通信开销最小。因为制约并行程序性能的一个很重要的因素是通信，通过进程映射寻找到一个进程映射配置，可以使得整个并行程序的通信开销最小，进而提高整个并行程序的性能。

进行进程映射需要两方面信息，一个是目标平台的网络拓扑图，另外一个是并行程序的通信图。目标平台的网络拓扑图可以通过我们开发的网络拓扑测试工具得到。

在我们的发明中，并行程序的通信拓扑图是通过两个矩阵线性叠加得到。一个是并行程序的点对点通信矩阵，另外一个是并行程序的组通信矩阵。针对点对点通信矩阵，使用插装通信库(SIM-MPI)，该工具可以自动的分析此前通过对并行程序进行插装所得到的日志记录，通过分析其中的每一条点对点通信，将其中的发送进程、接收进程、和通信字节记录在点对点的通信矩阵中。

针对组通信矩阵，在我们的发明中，我们首先将此前插装所得到的Profile输入我们的知识库，在我们的知识库中，通过我们的组通信分解算法，对Profile中记录的每一条组通信进行分解，转换成相应的若干条点对点的通信。然后再通过我们的分析工具(集成到SIM-MPI)，对转换生成的点对点通信进行分析，记录其中的发送进程、接收进程和通信字节记录在组通信的通信矩阵中。在得到并行程序的点对点通信矩阵和组通信矩阵之后，我们通过线性叠加的方式，将这两个矩阵统一为一个并行程序的通信矩阵。

在得到了并行程序的通信矩阵，目标平台的网络拓扑图之后，我们就可以使用启发式的进程映射方法来进行进程映射。进程映射的实质是将不同的进程映射到不同的计算单元，即将通信拓扑图映射到网络拓扑图。我们采用K-way的图划分算法来实现进程映射，我们映射目标是使得并行程序的通信开销最小。在计算通信权重时，我们采用的是Hockney提出的通信模型。

我们把我们计算得到的最优映射方式Map与Block和Cyclic映射方式进行了对比。例如有四个计算节点，每个节点有2个处理器，Block的映射方式是：Node1，Node1，Node2，Node2，Node3，Node3，Node4，Node4；Cyclic的映射方式是：Node1，Node2，Node3，Node4，Node1，Node2，Node3，Node4。

测试环境

我们的测试平台是一个由千兆以太网络连接起来共20个计算节点的集群服务器，每个节点由2个5110处理器组成，处理器频率1.6GHz，每个处理器有2个内核，两个内核共享4MB的L2Cache。每个节点的内存是4GB，操作系统是Red Hat EnterpriseLinux AS release 4，内核版本是2.6.9。我们使用的编译器是Compiler 9.1，MPI通信库是MPICH-1.2.7。

影响MPI程序性能的一个很重要的因素是通信，高效率的通信可以很大程度的提升MPI并行程序的性能。在MPI中，通信由两方面组成，一方面是点对点通信；另一方面是组通信，这两方面对于MPI并行程序的性能均有很大的影响。我们的发明主要针对MPI组通信的性能优化，从进程映射的角度提升MPI组通信的性能，从而使MPI并行程序在性能方面得到显著的提高。

相比于点通信，MPICH-1.2.7包含有多条实现不同语义的组通信，对于这些组通信，我们在测试平台上针对不同消息大小进行了测试。测试结果表明，在不同的消息大小情况下，通过我们所发明的处理MPI组通信进程映射的方法，均可以提高MPI组通信的性能(即找到一种使MPI组通信性能提升的进程映射配置)。

我们的测试分为两部分，一部分是针对进程数为2的整数次幂的情况；另一部分为进程数不为2的整数次幂的情况。我们的测试采用英特尔的IMB基准测试程序(Intel MPIBenchmark，IMB Benchmark)以及我们所开发编写的MPI组通信测试程序，利用这些工具分别测试MPI默认进程映射文件下的组通信性能，以及通过我们的发明所寻找到的进程映射文件下的组通信性能。如下为详细的测试结果以及相应的原理分析。

1)2的整数次幂的测试

针对常用的MPI组通信函数，我们在测试平台上进行了64进程的测试，具体的测试结果请见说明书附图5～13。其中，无填充表示block映射方式，横线填充表示cyclic映射方式，竖线填充表示我们得到的映射方式(Map)。

MPI_Bcast是并行程序中经常使用的一条组通信，它实现的功能是将一条消息从根进程广播发送给所有的进程，实现消息的广播和共享。对于MPI_Bcast的测试采用IMBBenchmark。从测试结果中可以看出，相比于block的MPI默认进程映射方式，我们的发明所提供的进程映射方式平均有102.2％的性能提升；相比于cyclic的MPI默认进程映射方式，我们的发明所提供的进程映射方式平均有126.1％的性能提升。这些测试结果均说明使用我们的发明能够比MPI并行编程者经常使用的默认进程映射方式(block和cyclic)得到更好的性能提升。

MPI_Reduce实现的功能是每个进程输入缓冲区中的数据按给定的操作进行运算，并将其结果返回给根进程的输出缓冲区的组通信操作。对于MPI_Reduce的测试采用IMBbenchmark。从测试结果中可以看出，相比于block的MPI默认进程映射方式，我们的发明所提供的进程映射方式平均有1.7％的性能提升；相比于cyclic的MPI默认进程映射方式，我们的发明所提供的进程映射方式平均有109.4％的性能提升。

MPI_Barrier实现的功能是同步所有进程的组通信操作。对于MPI_Barrier的测试采用IMB benchmark。从测试结果中可以看出，我们的发明所提供的进程映射方式相比于block的MPI默认进程映射方式，平均有6.7％的性能提升；相比于cyclic的MPI默认进程映射方式，平均有6.2％的性能提升。

MPI_Allgather是每个进程都将所有的其它进程的发送缓冲区的数据收集到一起的操作。对于MPI_Allgather的测试采用IMB benchmark。从测试结果中可以看出，我们的发明所提供的进程映射方式相比于block的MPI默认进程映射方式，平均有35.6％的性能提升；相比于cyclic的MPI默认进程映射方式，我们的发明所提供的进程映射方式平均有114.4％的性能提升。

MPI_Alltoall是实现通信域内进程之间完全信息交换的组通信操作。对于MPI_Alltoall的测试采用IMB benchmark。从测试结果中可以看出，我们的发明所提供的进程映射方式相比于block的MPI默认进程映射方式，平均有22.7％的性能提升；相比于cyclic的MPI默认进程映射方式，平均有2.4％的性能提升。

MPI_Allreduce是实现组规约的一条组通信。对于MPI_Allreduce的测试采用IMBbenchmark。从测试结果中可以看出，我们的发明所提供的进程映射方式相比于block的MPI默认进程映射方式，平均有2.2％的性能提升；相比于cyclic的MPI默认进程映射方式，平均有46.3％的性能提升。

MPI_Gather和MPI_Scatter，分别是实现收集和散发功能的组通信。由于IMB只提供了上述6条组通信的测试benchmark，所以对于MPI_Gather，MPI_Scatter的测试我们采用了我们自己开发的测试程序。测试程序主体如下(以MPI_Gather为例)：

MPI_Barrier(MPI_COMM_WORLD)；gettimeofday(&start，NULL)；for(i＝0；i＜LOOP；i++){MPI_Gather(sendbuf，size，MPI_CHAR，recvbuf，size，MPI_CHAR，0，MPI_COMM_WORLD)；}gettimeofday(&end，NULL)；

从测试结果中可以看出，对于MPI_Gather，我们的发明所提供的进程映射方式相比于block的MPI默认进程映射方式，平均有34.2％的性能提升；相比于cyclic的MPI默认进程映射方式，平均有5.6％的性能提升。对于MPI_Scatter，我们的发明所提供的进程映射方式相比于block的MPI默认进程映射方式，平均有51.7％的性能提升；相比于cyclic的MPI默认进程映射方式，平均有12.0％的性能提升。

针对上述组通信函数，我们将通过我们的发明所提供的进程映射方式，以及block和cyclic进程映射方式得到的不同组通信函数的执行时间统计如下(该统计结果按照我们发明所提供的进程映射方式所得到的时间进行正规化)：

  组通信  Block时间  Cyclic时间  Map时间  MPI_Bcast  2.02  2.26  1.00  MPI_Reduce  1.02  2.09  1.00  MPI_Barrier  1.07  1.06  1.00  MPI_Allgather  1.36  2.14  1.00  MPI_Alltoall  1.23  1.02  1.00

  MPI_Allreduce  1.02  1.46  1.00  MPI_Gather  1.34  1.06  1.00  MPI_Scatter  1.52  1.12  1.00  平均  1.32  1.53  1.00

2)非2的整数次幂的测试

MPI的并行程序除了要在2的整数次幂的情况下执行，经常还要在非2的整数次幂的情况下运行。并行度的变化，导致MPI组通信函数中的算法特性也随之发生了一定的变化。因此针对非2的整数次幂的情况，我们也做了测试。针对不同的组通信函数，测试均验证了在非2的整数次幂的情况下，我们的发明能够提供优于MPI默认进程映射方式(block和cyclic)的进程映射方式。

我们以33个进程的MPI_Allreduce为例对非2的整数次幂的情况进行说明，具体的测试结果请见说明书附图13。

从测试结果中，我们可以看出，在33个进程下，MPI_Allreduce的block映射方式要优于cyclic的映射方式，而通过我们的发明能够提供比block和cyclic的性能都要好的进程映射方式。相比于block的映射方式，我们的发明能够有30.0％的性能提升；相比于cyclic的映射方式，我们的发明能够有165.2％的性能提升。

综合上述结果说明，在不同的进程数下(2的整数幂或非整数幂)，在通信消息大小不同的情况下，使用我们的发明能够比MPI程序员经常使用的默认进程映射方式(block和cyclic)得到更好的性能提升。我们的发明为MPI程序员在解决进程映射方面，尤其在组通信的进程映射方面，提供了更方便的、更具有广泛意义的工具。