MSP問題解法的并行化研究

周泰楊　樊碩　彭立宏

摘 要：為提高M(jìn)SP問題的多項式時間算法ZH算法的計算速度，使其能夠進(jìn)行更大規(guī)模多級圖的測試，本文對ZH算法進(jìn)行了性能分析與并行的可行性評估，針對ZH算法中循環(huán)體較多的特點，分別在巨型機(jī)和普通PC機(jī)上進(jìn)行MSP問題求解算法的首次并行化實踐，隨之對并行化算法提出優(yōu)化方法，在實驗中取得了較高的加速比。

關(guān)鍵詞：MSP；并行化；巨型機(jī)

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A

1 引 言

NP完全問題（NP complete）是指對任意的NP問題，都能在多項式時間內(nèi)轉(zhuǎn)化成為的問題，NPC問題一直以來都是計算科學(xué)領(lǐng)域的經(jīng)典問題，具有很高的理論價值和應(yīng)用價值，也吸引了很多學(xué)者的關(guān)注。文獻(xiàn)[1]中提出了一個新的NP問題——多級圖的簡單路徑問題（MSP問題），在文獻(xiàn)中作者提出了MSP問題的一個多項式時間算法ZH算法，并且將哈密頓圖問題歸結(jié)到MSP問題上，從而證明了MSP問題是一個NP完全問題。大量的證明工作和測試顯示，ZH算法是一個多項式時間的算法。但是由于該算法的復(fù)雜性的多項式的階較高，導(dǎo)致運(yùn)算需要耗費大量的時間和空間，普通的PC機(jī)難以支持較大規(guī)模多級圖的測試。

有鑒于此，本文考慮利用超級計算機(jī)的強(qiáng)大計算能力對ZH算法進(jìn)行并行化加速，并且在PC機(jī)上進(jìn)行ZH算法的并行化研究。本文余下的本分按照如下的結(jié)構(gòu)安排：第二節(jié)介紹MSP問題以及并行化研究的相關(guān)工作；第三節(jié)中本文提出了一種一般化的多項式時間算法的并行化思路，并對MSP問題的解決算法進(jìn)行了并行化，之后提出了ZH算法并行化方案的優(yōu)化方法；第四節(jié)分兩個部分展示了ZH算法在超級計算機(jī)和普通PC機(jī)上的并行化實驗結(jié)果，并對實驗結(jié)果進(jìn)行了分析；最后一節(jié)對本文工作進(jìn)行了總結(jié)，并針對可能改進(jìn)的方面提出了新的展望。

2 相關(guān)工作

2.1 MSP問題及相關(guān)工作

在文獻(xiàn)[1]中，作者提出了一個新的NP完全問題，即MSP問題。該問題可簡述如下：

對任意給定的一個單源單匯的多級圖G，其中除源點外的其它所有頂點都附加有一個由圖的邊的構(gòu)成的子集，問G中是否存在自源點到匯點的一條路徑，使得對于路徑上除源點外的所有頂點v，v附加的邊集都包含該路徑自源點至v的部分。

圖1 一個多級圖的例子

圖1給出了一個多級圖的例子。文獻(xiàn)[1]找出了求解MSP問題的多項式算法ZH算法并給予了證明。MSP問題具有強(qiáng)大的表達(dá)能力，作者提出了一種解決MSP問題的算法，之后將圖的撕裂或壓縮的等價變形與歸納法進(jìn)行了結(jié)合，證明了ZH算法是一個多項式時間算法。ZH算法主要是通過循環(huán)的方式對多級圖中每一級上每個節(jié)點的邊集和每條邊的可達(dá)路徑進(jìn)行修改和約束，這個過程中多級圖的邊集信息將會進(jìn)行收斂，直至整個多級圖的信息不再發(fā)生變化。這些針對邊集和路徑所做的約束保證了多級圖中的簡單路徑存在與否。ZH算法中的約束是一種復(fù)雜的耦合關(guān)系，某一個頂點的邊集或者某一條邊的可達(dá)路徑都是依賴于多級圖中其他節(jié)點的信息的，而這種約束反過來也會影響到多級圖中其他節(jié)點和邊信息的約束。

近幾年，樊碩等人[4]將更多的NPC問題歸結(jié)到了MSP問題上，并給予了證明，比如SAT問題、子集和問題等，擴(kuò)展了MSP問題算法的應(yīng)用空間。我們將由歸結(jié)得到的SAT問題的多項式時間解法MSP-SAT進(jìn)行了一定規(guī)模的測試，取得了較好的效果，但是受限于PC機(jī)的運(yùn)算速度，沒有進(jìn)行更大規(guī)模的測試。

2.2 并行化方法介紹與相關(guān)工作

最近十年，中國的超級計算機(jī)取得了長足的發(fā)展與進(jìn)步，超級計算機(jī)有著廣泛的應(yīng)用價值，已經(jīng)與國計民生密不可分，其應(yīng)用領(lǐng)域包括氣候預(yù)測、生命科學(xué)、核物理模擬等等。文獻(xiàn)[6]對高性能計算機(jī)的并行計算進(jìn)行了理論方面的研究。[5]則將超算應(yīng)用到了雷達(dá)信號的處理上，[7]利用超級計算機(jī)解決了衛(wèi)星的重力測量問題，由此可見，超級計算機(jī)正在被應(yīng)用到越來越重要的領(lǐng)域。在普通計算機(jī)或者是超級計算機(jī)的一個節(jié)點內(nèi)，openMP庫是進(jìn)行算法并行化必須要考慮的工具，openMP是對并行算法的抽象，為程序員提供了簡便地方法對程序進(jìn)行并行化改造，openMP庫提供的抽象使得程序員能夠很大程度上忽略底層的硬件信息，從而投入更多地精力到并行算法本身，而不必過多關(guān)心具體實現(xiàn)。同時，openMP庫能夠部分地解決并行算法中的負(fù)載平衡，線程沖突等問題，為算法的并行化帶來了很多便利。例如文獻(xiàn)[12]中，作者利用openMP平臺對語音識別算法進(jìn)行了并行化，取得了可觀的效率改進(jìn)；白麗澤[10]等人則基于openMP平臺改進(jìn)了分子動力學(xué)算法。在文獻(xiàn)[13]中，作者利用openMP對SAT問題進(jìn)行了并行化改造。

3 MSP問題的求解算法的并行化研究

3.1 多項式時間算法的并行化思路

任務(wù)的并行是物理世界解決問題的一種基本思想，許多的實際問題可以被劃分為相關(guān)度不強(qiáng)的子任務(wù)同步進(jìn)行，在科學(xué)計算中，并行化也是一種重要的研究方法，其中，多項式時間的算法往往都存在循環(huán)結(jié)構(gòu)，而這些循環(huán)結(jié)構(gòu)非常適合進(jìn)行并行化，原本需要計算機(jī)一遍又一遍重復(fù)做的事情，可以通過并行化通過幾個線程、幾個核甚至是幾個節(jié)點同時計算來完成，將一個多項式時間的線性算法改造成并行化算法需要遵循以下的思路：

首先，熟悉串行算法，確定其中可以被并行化的部分。其中最主要的部分就是算法中的循環(huán)體，對于重復(fù)性的工作，可以對其進(jìn)行并行化處理；此外，在串行算法當(dāng)中，從時間上看具有先后關(guān)系的代碼塊可能并沒有邏輯關(guān)系，可以并行地執(zhí)行。這是改造串行算法的第一步，也是最重要的一步，之后的步驟會對確定要進(jìn)行并行化的代碼段進(jìn)行評估、修改以及優(yōu)化，確保并行算法的正確性。

其次，對可以進(jìn)行并行化的算法片段進(jìn)行讀寫沖突分析，采取措施在保證性能的同時，避免讀寫數(shù)據(jù)相關(guān)影響到算法結(jié)果，判斷代碼段的數(shù)據(jù)相關(guān)性按照如下的原則進(jìn)行：對于時間上有先后順序的代碼片段p1和p2，如果有以下關(guān)系，則p1和p2之間存在數(shù)據(jù)依賴關(guān)系，p2依賴于p1。

p2需要使用p1中計算出的數(shù)據(jù)，要保證語義正確性，p1必須先寫入數(shù)據(jù)，p2才能讀取；

p1中的輸入同時是p2中的輸出，此時要保證語義正確性，p1必須先讀取數(shù)據(jù)，p2才能寫入；

數(shù)據(jù)同時是p1和p2的輸出，此時要保證p1先寫入，p2才能寫入數(shù)據(jù)。

如果代碼片段中不存在以上的三種關(guān)系，則可以放心地進(jìn)行并行化，如果代碼段中至少存在三種關(guān)系中的一種，這就使得單純的代碼段的時間先后關(guān)系有了邏輯先后的關(guān)系，這樣的代碼的運(yùn)行結(jié)果就有了不確定性，不能隨意進(jìn)行并行化，在并行化的同時，需要使用臨界區(qū)、線程鎖等方式解決數(shù)據(jù)相關(guān)的問題，或者是能夠證明同時運(yùn)行代碼段帶來的不確定性對最后算法的結(jié)果沒有影響。

同時，還需要確定算法是否需要同步點以及同步點的位置。同步是一種協(xié)調(diào)各個進(jìn)程的手段，在同步點進(jìn)行進(jìn)程間的同步可以保證接下來算法需要的數(shù)據(jù)或是條件得到滿足，有的算法比較簡單，算法前后數(shù)據(jù)關(guān)聯(lián)不大，不需要考慮這個問題，大多數(shù)進(jìn)行并行化的算法都是要確定同步點的，在同步的時候也要尤其注意死鎖的出現(xiàn)使得某個或多個進(jìn)程等待永遠(yuǎn)不會出現(xiàn)的條件或數(shù)據(jù)。

再次，分析算法中可并行化部分的負(fù)載平衡，盡量使得并行的每一個線程的運(yùn)算量趨于一致。尤其在需要同步的算法中，需要盡量避免某些進(jìn)程很快到達(dá)同步點無所事事地等待其他進(jìn)程的現(xiàn)象，這種現(xiàn)象使得某些進(jìn)程一直處在空等狀態(tài)，大大降低了并行化效率，所以，為各進(jìn)程分配差不多的運(yùn)算量使得進(jìn)程的負(fù)載保持平衡是并行算法優(yōu)化的重要手段，此外在IO速度、內(nèi)存讀寫、進(jìn)程間通信等方面也有很多算法優(yōu)化的辦法。

最后，根據(jù)并行化算法的運(yùn)算效率，計算最終的加速比。理論意義上的加速比的計算一般可以使用如下的公式，S=Ws+WpWs+Wp/p其中Ws是問題中串行化部分的規(guī)模，Wp是問題中并行化部分的規(guī)模，p是并行所用的線程數(shù)。實際上針對具體的一個算法，我們一般采用已知的最佳串行算法執(zhí)行時間與并行算法執(zhí)行時間的比值來定義并行算法的加速比。

3.2 ZH算法的并行化方案

在進(jìn)行ZH算法并行化之前可以對隨機(jī)生成多級圖的算法進(jìn)行并行化，由于這一部分在整個算法中僅占很小的一部分并且生成算法相對簡單，所以只需要簡單地在隨機(jī)生成結(jié)點和邊時進(jìn)行并行化就好，在此不做贅述。ZH算法的并行化是本文的研究重點，本章在余下內(nèi)容中會詳細(xì)介紹ZH算法的并行化思路。

首先介紹ZH算法，在文獻(xiàn)[1]中，如下表所示，作者使用了四個算子來對多級圖信息進(jìn)行約束：

ZH算法主要是通過循環(huán)的方式用這些算子對多級圖中每一級上每個節(jié)點的邊集和每條邊的可達(dá)路徑進(jìn)行修改和約束，這個過程中多級圖的邊集信息將會進(jìn)行收斂，直至整個多級圖的信息不再發(fā)生變化。這些針對邊集和路徑所做的約束保證了多級圖中的簡單路徑存在與否。ZH算法中的約束是一種復(fù)雜的耦合關(guān)系，某一個頂點的邊集或者某一條邊的可達(dá)路徑都是依賴于多級圖中其他節(jié)點的信息的，而這種約束反過來也會影響到多級圖中其他節(jié)點和邊信息的約束。

在這個收斂的過程中，信息變化的順序并不會影響到最后收斂的結(jié)果，所以可以對多級圖中每一個節(jié)點進(jìn)行同步地節(jié)點邊集約束，對每一條邊進(jìn)行同步地可達(dá)路徑約束，這樣與循環(huán)進(jìn)行約束相比可能收斂的輪數(shù)會有變化，但是最后收斂的結(jié)果不會變化。所以可以針對這一點對ZH算法進(jìn)行并行化。

需要指出的是，算法中的幾個算子的時間復(fù)雜度都不算低，其中的數(shù)據(jù)耦合程度也比較高，可以看出算法有以下的特征，首先，在數(shù)據(jù)量較大的情況下，由于算法復(fù)雜度高，所以需要很長的運(yùn)算時間；其次，算法中大量地循環(huán)遍歷每一條邊或者每一個頂點，對它們執(zhí)行操作，從這個角度來說，ZH算法比較適合于并行化；而另一方面，對其中每一條邊或者每個頂點的操作都會對使用到多級圖整體的信息，而在步驟2.3中，會有可能在并行化時出現(xiàn)寫入沖突，在其他步驟并行化的時候有可能造成同時讀寫沖突，所以ZH算法的并行化還需要解決讀寫沖突的問題。

之前介紹過，ZH算法是一個多級圖信息的收斂過程，并行化過程中出現(xiàn)同時寫入或者先讀后寫的沖突對最后收斂的結(jié)果沒有影響；并且，算法中的公共變量并不是被線程所獨占的，所有線程均可以讀取資源，達(dá)不成產(chǎn)生死鎖必須的互斥條件。綜上所述，可以直接對ZH算法在步驟1、步驟2.3對每一級進(jìn)行并行化操作，在步驟2.2可以對每個頂點做并行化操作，ZH算法的并行化算法的偽代碼如圖2所示，利用openMP庫對PC機(jī)的線程進(jìn)行負(fù)載分配，能夠很輕松地在高級語言中實現(xiàn)算法的并行化，在確定可以進(jìn)行并行化的算法片段之后，可以通過#pragma omp parallel for標(biāo)記需要進(jìn)行并行化的循環(huán)體。在每個循環(huán)體結(jié)束之后，openMP將會自動設(shè)置同步點，對數(shù)據(jù)進(jìn)行同步，由于沒有死鎖的顧慮，所以無需做額外的設(shè)置。

3.3 優(yōu)化

之前直接用openMP對ZH算法進(jìn)行并行化處理，雖然其中的讀寫沖突對最后結(jié)果沒有影響，但是這樣會無謂地丟失寫入的多級圖信息，浪費寶貴的計算時間，從而導(dǎo)致無法快速地收斂從而在步驟3增加運(yùn)算的輪數(shù)，繼而增加總的時間長度，為了避免這種情況，本文提出一種優(yōu)化方法。由于整個ZH算法運(yùn)行過程中，多級圖中的可達(dá)路徑信息只會不斷地精簡，所以如果有兩個進(jìn)程同時要寫入一條邊的可達(dá)路徑時，都只將需要精簡的部分寫入，這樣一來，多次寫入的結(jié)果將不會發(fā)生沖突，需要寫入的量也相應(yīng)會減少。

另一方面，考慮到負(fù)載均衡的因素，之前的算法中，本文是針對每一級做并行，而在實際測試中我們發(fā)現(xiàn)，由于每一級的頂點數(shù)可能并不相同，尤其是在步驟2.3中，需要的是對所有低于當(dāng)前級數(shù)的頂點進(jìn)行操作，所以每一級的計算所需要的時間并不一致，這樣可能出現(xiàn)有的線程跑完了，有的線程還遠(yuǎn)遠(yuǎn)沒有結(jié)束的現(xiàn)象，總體來說對于并行度的提升是很不利的，所以本文設(shè)想對每個點及每條邊的運(yùn)算做并行處理，通過更細(xì)粒度的并行讓每個線程的負(fù)載趨于基本一致。設(shè)想一個簡單的例子，在一個多級圖的并行計算中的兩個線程A、B，優(yōu)化之前A、B分別負(fù)責(zé)一級的邊，可能其中A需要計算50條邊的信息，B只需要計算5條邊的信息，這樣會造成B線程長時間的空等；在優(yōu)化后的細(xì)粒度并行方式下，包括A、B在內(nèi)的每一個線程都會分配到相差不多數(shù)目的邊進(jìn)行運(yùn)算，這樣便提升了整體的并行效率。

4 實驗設(shè)計與結(jié)果

本次實驗分別使用了巨型機(jī)和普通PC機(jī)平臺，其中巨型機(jī)部分是在銀河10萬億次巨型機(jī)中進(jìn)行的，使用了1個節(jié)點，其中一個節(jié)點中有雙路四核的CPU總計8個邏輯CPU核；此外，還利用了一臺八核的PC機(jī)進(jìn)行了openMP并行化的實驗。

本次實驗的數(shù)據(jù)來自基于當(dāng)前時間作為種子的隨機(jī)數(shù)生成的多級圖，在設(shè)定所需要的多級圖級數(shù)和頂點數(shù)之后，多級圖生成算法會隨機(jī)地為每一級分配頂點，隨后會將相鄰兩級的頂點進(jìn)行全相連，生成多級圖的所有邊，這個邊集記作E，對于多級圖中的任意一個頂點v，需要分別確定頂點的邊集，方法是遍歷邊集E中的每一條邊e，讓其有75%的幾率使得e∈E（v）。

實驗需要用到以下幾個MSP問題的求解器，第一個求解器是當(dāng)前所能得到的最快運(yùn)算速度的ZH算法的串行算法，也就是按照文獻(xiàn)[1]中的算法編寫的程序；第二個求解器本文使用能夠確保MSP問題被正確解答的指數(shù)時間算法回溯法；第三個求解器來自使用銀河超算機(jī)并行化之后的ZH算法；最后，第四個求解器是PC上使用openMP并行化之后的ZH算法。本次實驗將上一步隨機(jī)生成的多級圖實例輸入到這些求解器之中，記錄求解器的運(yùn)算結(jié)果（即多級圖中是否含有簡單路徑）與運(yùn)算時間，最后經(jīng)過統(tǒng)計總量與平均值來獲得實驗數(shù)據(jù)。

以下是實驗結(jié)果與結(jié)果分析：

第一組對比實驗中，我們將相同的多級圖作為輸入同時輸入到回溯法、串行算法和并行算法中，其中L=20，N=100的實例共計5341組，L=30，N=150的實例共計748組，其中沒有一組出現(xiàn)回溯法與ZH算法或者是并行化后的ZH算法的運(yùn)算結(jié)果有出入，保證了ZH算法以及ZH算法的并行化的正確性。

第二組對比實驗是在銀河巨型機(jī)上進(jìn)行ZH算法的運(yùn)算，其中在一個節(jié)點上并行總共進(jìn)行了10組10分鐘一組L=20，N=100圖的實驗，共計算出2960個實例的結(jié)果平均一組用時2027ms；而在一個線程上進(jìn)行串行計算同樣的十組，共計算出381個實例的結(jié)果，平均每個實例用時15748ms，加速比達(dá)到7.76；在L=30，N=150圖的實驗中，100分鐘的時間內(nèi)并行組一共計算出了667個圖，平均用時9996ms，串行組中共計算出81個實例，平均用時74074ms，加速比約為7.41。

第三組對比實驗中，本文在PC機(jī)上利用openMP庫進(jìn)行了ZH算法并行化的實驗，由于PC機(jī)內(nèi)存空間的限制，只進(jìn)行了L=20，N=100的多級圖實例的計算，在并行組中，本文一共進(jìn)行了10組100個實例的實驗，一共用去8105266ms，平均每個實例耗時8105.2ms；在串行組中，1000個實例總共用去12170007ms，平均每個實例耗時12170ms，加速比約為1.50。

由以上的對比實驗可以得出，首先，ZH算法及其并行化的正確性得到了保證，其次，在巨型機(jī)上，由于巨型機(jī)本身是為大數(shù)據(jù)的并行化計算設(shè)計的，程序員可以不用關(guān)注底層的任務(wù)分配與相關(guān)的計算資源分配，就能獲得近似于線程數(shù)的加速比（分別為7.76和7.41），同時，由于巨型機(jī)的大內(nèi)存，使得較大規(guī)模的多級圖運(yùn)算成為了可能；最后，在PC機(jī)上，利用OpenMP平臺對ZH算法進(jìn)行并行化也能夠大幅度地提高ZH算法的效率，加速比達(dá)到1.50。

5 結(jié) 語

MSP問題是一個較為新穎的NP完全問題，其多項式時間的解法ZH算法在多級圖問題較大的時候需要的運(yùn)算時間過長，本文采用超級計算機(jī)的多任務(wù)并行以及CPU內(nèi)的多線程技術(shù)對MSP問題進(jìn)行了并行化解法的研究，取得了較高的加速比，同時從多個角度考慮針對并行化解法做出了優(yōu)化，取得了一定的效果，同時，本文的考慮也有許多不周全的地方，沒有更細(xì)致地做出優(yōu)化，在線程沖突、內(nèi)存占用等問題上仍有很大的繼續(xù)研究的空間。

參考文獻(xiàn)

[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問題可多項式歸結(jié)到MSP問題[J]. 計算機(jī)科學(xué)， 39（11）：179-182， 2012.

[5] 楊玥， 王秀壇. 基于超級計算機(jī)的通用并行雷達(dá)信號處理[J]. 微計算機(jī)信息， 2005， 21（20）：139-141. DOI：10.3969/j.issn.1008-0570.2005.30.055.

[6] 陳科. 基于高性能計算機(jī)的并行計算研究[D].大連：大連理工大學(xué)， 2011.

[7] 聶琳娟， 申文斌， 王正濤，等. 基于超級計算機(jī)平臺的并行解技術(shù)在衛(wèi)星重力測量中的應(yīng)用[J]. 大地測量與地球動力學(xué)， 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的分子動力學(xué)并行算法的性能分析與優(yōu)化[J]. 計算機(jī)應(yīng)用， 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.