MSP问题解法的并行化研究

周泰杨　樊硕　彭立宏

摘 要：为提高MSP问题的多项式时间算法ZH算法的计算速度，使其能够进行更大规模多级图的测试，本文对ZH算法进行了性能分析与并行的可行性评估，针对ZH算法中循环体较多的特点，分别在巨型机和普通PC机上进行MSP问题求解算法的首次并行化实践，随之对并行化算法提出优化方法，在实验中取得了较高的加速比。

关键词：MSP；并行化；巨型机

中图分类号：TP301.6 文献标识码：A

1 引 言

NP完全问题（NP complete）是指对任意的NP问题，都能在多项式时间内转化成为的问题，NPC问题一直以来都是计算科学领域的经典问题，具有很高的理论价值和应用价值，也吸引了很多学者的关注。文献[1]中提出了一个新的NP问题——多级图的简单路径问题（MSP问题），在文献中作者提出了MSP问题的一个多项式时间算法ZH算法，并且将哈密顿图问题归结到MSP问题上，从而证明了MSP问题是一个NP完全问题。大量的证明工作和测试显示，ZH算法是一个多项式时间的算法。但是由于该算法的复杂性的多项式的阶较高，导致运算需要耗费大量的时间和空间，普通的PC机难以支持较大规模多级图的测试。

有鉴于此，本文考虑利用超级计算机的强大计算能力对ZH算法进行并行化加速，并且在PC机上进行ZH算法的并行化研究。本文余下的本分按照如下的结构安排：第二节介绍MSP问题以及并行化研究的相关工作；第三节中本文提出了一种一般化的多项式时间算法的并行化思路，并对MSP问题的解决算法进行了并行化，之后提出了ZH算法并行化方案的优化方法；第四节分两个部分展示了ZH算法在超级计算机和普通PC机上的并行化实验结果，并对实验结果进行了分析；最后一节对本文工作进行了总结，并针对可能改进的方面提出了新的展望。

2 相关工作

2.1 MSP问题及相关工作

在文献[1]中，作者提出了一个新的NP完全问题，即MSP问题。该问题可简述如下：

对任意给定的一个单源单汇的多级图G，其中除源点外的其它所有顶点都附加有一个由图的边的构成的子集，问G中是否存在自源点到汇点的一条路径，使得对于路径上除源点外的所有顶点v，v附加的边集都包含该路径自源点至v的部分。

图1 一个多级图的例子

图1给出了一个多级图的例子。文献[1]找出了求解MSP问题的多项式算法ZH算法并给予了证明。MSP问题具有强大的表达能力，作者提出了一种解决MSP问题的算法，之后将图的撕裂或压缩的等价变形与归纳法进行了结合，证明了ZH算法是一个多项式时间算法。ZH算法主要是通过循环的方式对多级图中每一级上每个节点的边集和每条边的可达路径进行修改和约束，这个过程中多级图的边集信息将会进行收敛，直至整个多级图的信息不再发生变化。这些针对边集和路径所做的约束保证了多级图中的简单路径存在与否。ZH算法中的约束是一种复杂的耦合关系，某一个顶点的边集或者某一条边的可达路径都是依赖于多级图中其他节点的信息的，而这种约束反过来也会影响到多级图中其他节点和边信息的约束。

近几年，樊硕等人[4]将更多的NPC问题归结到了MSP问题上，并给予了证明，比如SAT问题、子集和问题等，扩展了MSP问题算法的应用空间。我们将由归结得到的SAT问题的多项式时间解法MSP-SAT进行了一定规模的测试，取得了较好的效果，但是受限于PC机的运算速度，没有进行更大规模的测试。

2.2 并行化方法介绍与相关工作

最近十年，中国的超级计算机取得了长足的发展与进步，超级计算机有着广泛的应用价值，已经与国计民生密不可分，其应用领域包括气候预测、生命科学、核物理模拟等等。文献[6]对高性能计算机的并行计算进行了理论方面的研究。[5]则将超算应用到了雷达信号的处理上，[7]利用超级计算机解决了卫星的重力测量问题，由此可见，超级计算机正在被应用到越来越重要的领域。在普通计算机或者是超级计算机的一个节点内，openMP库是进行算法并行化必须要考虑的工具，openMP是对并行算法的抽象，为程序员提供了简便地方法对程序进行并行化改造，openMP库提供的抽象使得程序员能够很大程度上忽略底层的硬件信息，从而投入更多地精力到并行算法本身，而不必过多关心具体实现。同时，openMP库能够部分地解决并行算法中的负载平衡，线程冲突等问题，为算法的并行化带来了很多便利。例如文献[12]中，作者利用openMP平台对语音识别算法进行了并行化，取得了可观的效率改进；白丽泽[10]等人则基于openMP平台改进了分子动力学算法。在文献[13]中，作者利用openMP对SAT问题进行了并行化改造。

3 MSP问题的求解算法的并行化研究

3.1 多项式时间算法的并行化思路

任务的并行是物理世界解决问题的一种基本思想，许多的实际问题可以被划分为相关度不强的子任务同步进行，在科学计算中，并行化也是一种重要的研究方法，其中，多项式时间的算法往往都存在循环结构，而这些循环结构非常适合进行并行化，原本需要计算机一遍又一遍重复做的事情，可以通过并行化通过几个线程、几个核甚至是几个节点同时计算来完成，将一个多项式时间的线性算法改造成并行化算法需要遵循以下的思路：

首先，熟悉串行算法，确定其中可以被并行化的部分。其中最主要的部分就是算法中的循环体，对于重复性的工作，可以对其进行并行化处理；此外，在串行算法当中，从时间上看具有先后关系的代码块可能并没有逻辑关系，可以并行地执行。这是改造串行算法的第一步，也是最重要的一步，之后的步骤会对确定要进行并行化的代码段进行评估、修改以及优化，确保并行算法的正确性。

其次，对可以进行并行化的算法片段进行读写冲突分析，采取措施在保证性能的同时，避免读写数据相关影响到算法结果，判断代码段的数据相关性按照如下的原则进行：对于时间上有先后顺序的代码片段p1和p2，如果有以下关系，则p1和p2之间存在数据依赖关系，p2依赖于p1。

p2需要使用p1中计算出的数据，要保证语义正确性，p1必须先写入数据，p2才能读取；

p1中的输入同时是p2中的输出，此时要保证语义正确性，p1必须先读取数据，p2才能写入；

数据同时是p1和p2的输出，此时要保证p1先写入，p2才能写入数据。

如果代码片段中不存在以上的三种关系，则可以放心地进行并行化，如果代码段中至少存在三种关系中的一种，这就使得单纯的代码段的时间先后关系有了逻辑先后的关系，这样的代码的运行结果就有了不确定性，不能随意进行并行化，在并行化的同时，需要使用临界区、线程锁等方式解决数据相关的问题，或者是能够证明同时运行代码段带来的不确定性对最后算法的结果没有影响。

同时，还需要确定算法是否需要同步点以及同步点的位置。同步是一种协调各个进程的手段，在同步点进行进程间的同步可以保证接下来算法需要的数据或是条件得到满足，有的算法比较简单，算法前后数据关联不大，不需要考虑这个问题，大多数进行并行化的算法都是要确定同步点的，在同步的时候也要尤其注意死锁的出现使得某个或多个进程等待永远不会出现的条件或数据。

再次，分析算法中可并行化部分的负载平衡，尽量使得并行的每一个线程的运算量趋于一致。尤其在需要同步的算法中，需要尽量避免某些进程很快到达同步点无所事事地等待其他进程的现象，这种现象使得某些进程一直处在空等状态，大大降低了并行化效率，所以，为各进程分配差不多的运算量使得进程的负载保持平衡是并行算法优化的重要手段，此外在IO速度、内存读写、进程间通信等方面也有很多算法优化的办法。

最后，根据并行化算法的运算效率，计算最终的加速比。理论意义上的加速比的计算一般可以使用如下的公式，S=Ws+WpWs+Wp/p其中Ws是问题中串行化部分的规模，Wp是问题中并行化部分的规模，p是并行所用的线程数。实际上针对具体的一个算法，我们一般采用已知的最佳串行算法执行时间与并行算法执行时间的比值来定义并行算法的加速比。

3.2 ZH算法的并行化方案

在进行ZH算法并行化之前可以对随机生成多级图的算法进行并行化，由于这一部分在整个算法中仅占很小的一部分并且生成算法相对简单，所以只需要简单地在随机生成结点和边时进行并行化就好，在此不做赘述。ZH算法的并行化是本文的研究重点，本章在余下内容中会详细介绍ZH算法的并行化思路。

首先介绍ZH算法，在文献[1]中，如下表所示，作者使用了四个算子来对多级图信息进行约束：

ZH算法主要是通过循环的方式用这些算子对多级图中每一级上每个节点的边集和每条边的可达路径进行修改和约束，这个过程中多级图的边集信息将会进行收敛，直至整个多级图的信息不再发生变化。这些针对边集和路径所做的约束保证了多级图中的简单路径存在与否。ZH算法中的约束是一种复杂的耦合关系，某一个顶点的边集或者某一条边的可达路径都是依赖于多级图中其他节点的信息的，而这种约束反过来也会影响到多级图中其他节点和边信息的约束。

在这个收敛的过程中，信息变化的顺序并不会影响到最后收敛的结果，所以可以对多级图中每一个节点进行同步地节点边集约束，对每一条边进行同步地可达路径约束，这样与循环进行约束相比可能收敛的轮数会有变化，但是最后收敛的结果不会变化。所以可以针对这一点对ZH算法进行并行化。

需要指出的是，算法中的几个算子的时间复杂度都不算低，其中的数据耦合程度也比较高，可以看出算法有以下的特征，首先，在数据量较大的情况下，由于算法复杂度高，所以需要很长的运算时间；其次，算法中大量地循环遍历每一条边或者每一个顶点，对它们执行操作，从这个角度来说，ZH算法比较适合于并行化；而另一方面，对其中每一条边或者每个顶点的操作都会对使用到多级图整体的信息，而在步骤2.3中，会有可能在并行化时出现写入冲突，在其他步骤并行化的时候有可能造成同时读写冲突，所以ZH算法的并行化还需要解决读写冲突的问题。

之前介绍过，ZH算法是一个多级图信息的收敛过程，并行化过程中出现同时写入或者先读后写的冲突对最后收敛的结果没有影响；并且，算法中的公共变量并不是被线程所独占的，所有线程均可以读取资源，达不成产生死锁必须的互斥条件。综上所述，可以直接对ZH算法在步骤1、步骤2.3对每一级进行并行化操作，在步骤2.2可以对每个顶点做并行化操作，ZH算法的并行化算法的伪代码如图2所示，利用openMP库对PC机的线程进行负载分配，能够很轻松地在高级语言中实现算法的并行化，在确定可以进行并行化的算法片段之后，可以通过#pragma omp parallel for标记需要进行并行化的循环体。在每个循环体结束之后，openMP将会自动设置同步点，对数据进行同步，由于没有死锁的顾虑，所以无需做额外的设置。

3.3 优化

之前直接用openMP对ZH算法进行并行化处理，虽然其中的读写冲突对最后结果没有影响，但是这样会无谓地丢失写入的多级图信息，浪费宝贵的计算时间，从而导致无法快速地收敛从而在步骤3增加运算的轮数，继而增加总的时间长度，为了避免这种情况，本文提出一种优化方法。由于整个ZH算法运行过程中，多级图中的可达路径信息只会不断地精简，所以如果有两个进程同时要写入一条边的可达路径时，都只将需要精简的部分写入，这样一来，多次写入的结果将不会发生冲突，需要写入的量也相应会减少。

另一方面，考虑到负载均衡的因素，之前的算法中，本文是针对每一级做并行，而在实际测试中我们发现，由于每一级的顶点数可能并不相同，尤其是在步骤2.3中，需要的是对所有低于当前级数的顶点进行操作，所以每一级的计算所需要的时间并不一致，这样可能出现有的线程跑完了，有的线程还远远没有结束的现象，总体来说对于并行度的提升是很不利的，所以本文设想对每个点及每条边的运算做并行处理，通过更细粒度的并行让每个线程的负载趋于基本一致。设想一个简单的例子，在一个多级图的并行计算中的两个线程A、B，优化之前A、B分别负责一级的边，可能其中A需要计算50条边的信息，B只需要计算5条边的信息，这样会造成B线程长时间的空等；在优化后的细粒度并行方式下，包括A、B在内的每一个线程都会分配到相差不多数目的边进行运算，这样便提升了整体的并行效率。

4 实验设计与结果

本次实验分别使用了巨型机和普通PC机平台，其中巨型机部分是在银河10万亿次巨型机中进行的，使用了1个节点，其中一个节点中有双路四核的CPU总计8个逻辑CPU核；此外，还利用了一台八核的PC机进行了openMP并行化的实验。

本次实验的数据来自基于当前时间作为种子的随机数生成的多级图，在设定所需要的多级图级数和顶点数之后，多级图生成算法会随机地为每一级分配顶点，随后会将相邻两级的顶点进行全相连，生成多级图的所有边，这个边集记作E，对于多级图中的任意一个顶点v，需要分别确定顶点的边集，方法是遍历边集E中的每一条边e，让其有75%的几率使得e∈E（v）。

实验需要用到以下几个MSP问题的求解器，第一个求解器是当前所能得到的最快运算速度的ZH算法的串行算法，也就是按照文献[1]中的算法编写的程序；第二个求解器本文使用能够确保MSP问题被正确解答的指数时间算法回溯法；第三个求解器来自使用银河超算机并行化之后的ZH算法；最后，第四个求解器是PC上使用openMP并行化之后的ZH算法。本次实验将上一步随机生成的多级图实例输入到这些求解器之中，记录求解器的运算结果（即多级图中是否含有简单路径）与运算时间，最后经过统计总量与平均值来获得实验数据。

以下是实验结果与结果分析：

第一组对比实验中，我们将相同的多级图作为输入同时输入到回溯法、串行算法和并行算法中，其中L=20，N=100的实例共计5341组，L=30，N=150的实例共计748组，其中没有一组出现回溯法与ZH算法或者是并行化后的ZH算法的运算结果有出入，保证了ZH算法以及ZH算法的并行化的正确性。

第二组对比实验是在银河巨型机上进行ZH算法的运算，其中在一个节点上并行总共进行了10组10分钟一组L=20，N=100图的实验，共计算出2960个实例的结果平均一组用时2027ms；而在一个线程上进行串行计算同样的十组，共计算出381个实例的结果，平均每个实例用时15748ms，加速比达到7.76；在L=30，N=150图的实验中，100分钟的时间内并行组一共计算出了667个图，平均用时9996ms，串行组中共计算出81个实例，平均用时74074ms，加速比约为7.41。

第三组对比实验中，本文在PC机上利用openMP库进行了ZH算法并行化的实验，由于PC机内存空间的限制，只进行了L=20，N=100的多级图实例的计算，在并行组中，本文一共进行了10组100个实例的实验，一共用去8105266ms，平均每个实例耗时8105.2ms；在串行组中，1000个实例总共用去12170007ms，平均每个实例耗时12170ms，加速比约为1.50。

由以上的对比实验可以得出，首先，ZH算法及其并行化的正确性得到了保证，其次，在巨型机上，由于巨型机本身是为大数据的并行化计算设计的，程序员可以不用关注底层的任务分配与相关的计算资源分配，就能获得近似于线程数的加速比（分别为7.76和7.41），同时，由于巨型机的大内存，使得较大规模的多级图运算成为了可能；最后，在PC机上，利用OpenMP平台对ZH算法进行并行化也能够大幅度地提高ZH算法的效率，加速比达到1.50。

5 结 语

MSP问题是一个较为新颖的NP完全问题，其多项式时间的解法ZH算法在多级图问题较大的时候需要的运算时间过长，本文采用超级计算机的多任务并行以及CPU内的多线程技术对MSP问题进行了并行化解法的研究，取得了较高的加速比，同时从多个角度考虑针对并行化解法做出了优化，取得了一定的效果，同时，本文的考虑也有许多不周全的地方，没有更细致地做出优化，在线程冲突、内存占用等问题上仍有很大的继续研究的空间。

参考文献

[1] JIANG X.A Polynomial Time Algorithm for the Hamilton Circuit Problem[J]. arXiv preprint cs/1305.5976， 2013.

[2] JIANG X，LIU W，WU T，ZHOU L.Reductions from MSP to SAT and from SUBSET SUM to MSP[J].Journal of Computational Information Systems， 2014， 10（3）： 1287-1295.

[3] JIANG X，PENG L，WANG Q.MSP problem： Its NPcompleteness and its algorithm[J]. In Proceedings of CUTE'2010， 2010.

[4] 樊硕， 姜新文. SAT问题可多项式归结到MSP问题[J]. 计算机科学， 39（11）：179-182， 2012.

[5] 杨玥， 王秀坛. 基于超级计算机的通用并行雷达信号处理[J]. 微计算机信息， 2005， 21（20）：139-141. DOI：10.3969/j.issn.1008-0570.2005.30.055.

[6] 陈科. 基于高性能计算机的并行计算研究[D].大连：大连理工大学， 2011.

[7] 聂琳娟， 申文斌， 王正涛，等. 基于超级计算机平台的并行解技术在卫星重力测量中的应用[J]. 大地测量与地球动力学， 2012， 32（2）：64-68. DOI：10.3969/j.issn.1671-5942.2012.02.015.

[8] DAGUML，ENON R. OpenMP： an industry standard API for sharedmemory programming[J]. Computational Science & Engineering， IEEE， 1998， 5（1）： 46-55.

[9] CLARK D. OpenMP： A parallel standard for the masses[J]. Concurrency， IEEE， 1998， 6（1）： 10-12.

[10]BLUME H，LIVONIUS J，ROTENBERG L. OpenMPbased parallelization on an MPCore multiprocessor platformA performance and power analysis[J]. Journal of Systems Architecture the Euromicro Journal， 2008， 54（11）：1019-1029.

[11]白明泽， 程丽， 豆育升，等. 基于OpenMP的分子动力学并行算法的性能分析与优化[J]. 计算机应用， 2012， 32（1）：163-166. DOI：10.3724/SP.J.1087.2012.00163.

[12]YOU K，LEE Y，SUNG W. OpenMPbased parallel implementation of a continuous speech recognizer on a multicore system[C]// Acoustics， Speech， and Signal Processing， IEEE International Conference on. IEEE， 2009：621-624.

[13]VANDRSWALMEN P，DEQUEN G，KRAJECKI M.A collaborative approach for multithreaded sat solving[J]. International Journal of Parallel Programming， 2009， 37（3）： 324-342.