基于宏與全局變量Floyd并行算法的性能對比

李超燕，裴林滔

1.寧波職業(yè)技術學院電子信息工程系，浙江寧波 315800

2.國防科技大學計算機學院，長沙 410000

基于宏與全局變量Floyd并行算法的性能對比

李超燕1，裴林滔2

1.寧波職業(yè)技術學院電子信息工程系，浙江寧波 315800

2.國防科技大學計算機學院，長沙 410000

在Ubuntu操作系統(tǒng)上，實現(xiàn)多線程并行的Floyd算法。對實驗數(shù)據(jù)分析表明，基于全局變量定義代價矩陣A大小的并行程序所獲得的并行性能要優(yōu)于基于宏參數(shù)定義矩陣A大小的并行程序的性能。這與相應的用宏參數(shù)定義矩陣A大小的串行程序性能要更優(yōu)的結(jié)果相反。

宏參數(shù)；全局變量；Floyd算法；多線程

1 概述

Floyd算法在消防站選擇，火災消防救援，公交路線優(yōu)化，物流運輸路徑選擇，矢量地圖最短路徑搜索等領域中都有應用，對Floyd算法進行學習和研究是有實用價值的。在Ubuntu操作系統(tǒng)上對Floyd算法進行并行實現(xiàn)時，程序中對矩陣大小基于宏參數(shù)與全局變量的不同定義出現(xiàn)了并行程序所獲得的性能與串行程序所獲得的性能相反的結(jié)果。

在本文實驗中，F(xiàn)loyd算法的串行程序1中的矩陣A用宏定義的參數(shù)n（n為實驗數(shù)據(jù)的節(jié)點數(shù)）來定義二維數(shù)組大?。篈[n][n]；Floyd算法的串行程序2中的矩陣A用全局變量nodenum（nodenum所賦的值也為實驗數(shù)據(jù)的節(jié)點數(shù)）來定義二維數(shù)組大?。篈[nodenum][nodenum]，其他代碼與串行程序1完全相同；實驗顯示串行程序1的性能要優(yōu)于串行程序2的性能。對串行程序1和串行程序2實現(xiàn)并行化后分別得并行程序1和并行程序2，并行程序1和并行程序2所用的并行指導語句完全相同，在雙核的雙線程下運行出現(xiàn)了并行程序2的性能反而優(yōu)于并行程序1的結(jié)果。

2 算法原理

對于一個各邊權(quán)值都不小于1的有向圖，求解每對節(jié)點間的最短路徑長度和最短路徑可以以每個節(jié)點為源點，循環(huán)求出每對節(jié)點間的最短路徑長度和最短路徑，當然，F(xiàn)loyd算法也可求解任意兩節(jié)點之間的最短路徑長度和最短路徑。Floyd算法又被稱為傳遞閉包方法，串行算法的時間復雜度為O(n3)，其基本思想是遞推產(chǎn)生一個矩陣序列A(0)，A(1)…A(k)…A(n)，其中A(0)為給定的代價矩陣，A(k)[i][j]表示從節(jié)點i到節(jié)點j之間節(jié)點序號不大于k的最短路徑長度[1]。

Floyd串行算法的描述如下：

輸入：有限帶權(quán)圖的節(jié)點數(shù)n，圖的鄰接矩陣Edge[n][n]，＜vi，vj＞是Edge中從節(jié)點i到節(jié)點j的弧，Edge[i][j]是?。紇i，vj＞(1≤i，j≤N)的非負權(quán)值，權(quán)值表示從節(jié)點i到j的距離[2]；為了表示求得的任意兩個節(jié)點間的最短途徑，路徑矩陣Path對最短路徑途經(jīng)的節(jié)點作記錄。求A(k)[i][j]時，path[i][j]存放從節(jié)點i到節(jié)點j的中間節(jié)點編號不大于k的最短路徑上前一個節(jié)點的編號。在算法結(jié)束時，由path的值追溯得到節(jié)點i到j的最短路徑。Floyd串行算法[3]：

在并行算法的設計中，問題的分解通常有域分解和功能分解兩種。域分解將問題分解為若干個子問題，然后分別對其并行求解；功能分解，將問題按功能分解為若干個子問題，然后分別對其求解。對于Floyd算法，選擇域分解更為合適[4]。

3 算法實現(xiàn)

為了方便起見，約定線程數(shù)為p，節(jié)點數(shù)規(guī)模為n[5]。

for（k=0；k＜n；k++）循環(huán)開始，進行線程并行。各個任務執(zhí)行并行計算：

本文并行程序的設計很簡單，主要是在k循環(huán)內(nèi)層加并行指導命令，進行線程并行，對最短路徑進行并行計算[6]。在實驗中，串行程序1和并行程序1中矩陣A的維數(shù)用宏定義的n來定義大?。篿ntA[n][n]。串行程序2和并行程序2中矩陣A的維數(shù)用全局變量nodenum來定義大小：intA[nodenum][nodenum]。串行程序1和串行程序2的其他的代碼完全相同，并行程序1和并行程序2的其他代碼也完全相同。

4 實驗測試與分析

4.1 實驗環(huán)境及實驗數(shù)據(jù)

實驗環(huán)境為：

（1）Intel Pentium雙核T3400 CPU@2.16 GHz，2 GB內(nèi)存，操作系統(tǒng)為Ubuntu 11.10，由gcc+openmp3.0編譯[7]。

（2）Intel?CoreTMi5-2430M CPU@2.40 GHz，3 GB內(nèi)存，操作系統(tǒng)為Ubuntu12.04，由gcc+openm p3.0編譯。

（3）百萬億次巨型機，單計算節(jié)點為2路6核Intel Westmere EP6處理器，銀河麒麟Linux操作系統(tǒng)，gcc+ openmp3.0編譯。

實驗數(shù)據(jù)為：節(jié)點數(shù)分別為n=100，200，…，1 000，權(quán)值范圍限定不大于100，邊數(shù)為n×n的10個*.txt文檔。

為了驗證實驗的結(jié)果，本實驗在三個環(huán)境下進行，用來驗證實驗結(jié)果的可靠性[8]。

4.2 實驗結(jié)果

串行程序1，2和并行程序1，2在（1）Intel Pentium雙核T3400@2.16 GHz CPU，2 GB內(nèi)存，操作系統(tǒng)為Ubuntu 11.10的環(huán)境下編譯，其中并行程序1，2以雙線程運行，運行時間如表1所示（單位：s）。

串行程序1，2和并行程序1，2在（2）Intel?CoreTMi5-2430M CPU@2.40 GHz 2.40 GHz，3 GB內(nèi)存，操作系統(tǒng)為Ubuntu12.04的環(huán)境下編譯運行，其中并行程序1，2以雙線程運行，運行時間如表2所示（單位：s）。

表1 在Intel Pentium雙核T3400@2.16 GHz CPU，2 GB內(nèi)存下運行的時間表s

表2 在Intel?CoreTMi5-2430M CPU@2.40 GHz，3 GB內(nèi)存下運行的時間表s

串行程序1，2和并行程序1，2在（3）百萬億次巨型機，單計算節(jié)點為2路6核Intel Westmere EP6處理器，銀河麒麟Linux操作系統(tǒng)，gcc+openmp3.0的環(huán)境下編譯運行，其中并行程序1，2以多線程運行，運行時間如表3至表5所示（單位：s）。

表3 串行程序1，2運行時間表s

表4 并行程序1運行時間表s

表5 并行程序2運行時間表s

本文實驗數(shù)據(jù)表明：在Ubuntu操作系統(tǒng)下，串行程序1除了n=200，400，800外，其余的性能優(yōu)于串行程序2；而并行程序2的性能都優(yōu)于并行程序1。在銀河麒麟Linux操作系統(tǒng)下，串行程序1的性能都優(yōu)于串行程序2；而并行程序1的性能與并行程序2的性能相當。對于Floyd算法，在串行程序中雖然宏參數(shù)帶來了性能優(yōu)勢，但在并行程序中反而不如全局變量。

5 結(jié)束語

Floyd算法在Ubuntu操作系統(tǒng)下基于全局變量所定義的代價矩陣A大小的串行程序性能雖然不如基于宏參數(shù)所定義代價矩陣A大小的串行程序性能，但前者實現(xiàn)并行化后其性能反而優(yōu)于后者程序并行化的性能，程序加速比前者大于后者。在巨型機的銀河麒麟Linux操作系統(tǒng)下，基于全局變量所定義代價矩陣A大小的串行程序性能同樣不如基于宏參數(shù)所定義的代價矩陣A大小的串行程序性能，但前者實現(xiàn)并行化后其性能幾乎與后者程序并行化的性能等同，加速比也是前者大于后者。對于Floyd的并行程序，宏參數(shù)并不能給程序帶來性能的改善，這與串行程序的情況相反。

[1]吳向君，任凱.交互網(wǎng)絡上任意節(jié)點對的最短路徑集解法[J].海軍工程大學學報，2011（4）.

[2]葉金平，朱征宇，王麗娜，等.智能交通中的高效多準最短路徑混合算法[J].計算機應用研究，2011（9）.

[3]李春葆，尹為民，李蓉蓉，等.數(shù)據(jù)結(jié)構(gòu)教程[M].3版.北京：清華大學出版社，2009.

[4]單瑩，吳建平，王正華.基于SMP集群的多層次并行編程模型與并行優(yōu)化技術[J].計算機應用研究，2006（10）.

[5]楊慶芳，劉冬，楊兆升.基于MPI+OpenMP混合編程模型的城市路網(wǎng)最短路徑并行算法[J].吉林大學學報，2011（6）.

[6]Mocean L，Ciaca M.About parallel programm ing：paradigms，parallel execution and collaborative systems[J].Informatica Econom ic?，2009，13（2）.

[7]張平，李清寶，趙榮彩.OpenMP并行程序的編譯器優(yōu)化[J].計算機工程，2006（24）.

[8]濮芳琍，盧炎生.一種并行程序可靠組合測試策略[J].華中科技大學學報，2009（6）.

LI Chaoyan1,PEI Lintao2

1.Department of Information Technology,Ningbo Professional Technology Institute,Ningbo,Zhejiang 315800,China
2.National University of Defense Technology,Changsha 410000,China

A multi-thread parallel Floyd algorithm is achieved on the Ubuntu operating system.Analysis of experimental data show s that the parallel performance of the parallel program with matrixAwhose size is defined with global variable is better than the parallel program with matrixAwhose size is defined with macro parameter.This is contrary to the much better performance of the serial program with matrixAwhose size is defined with global variable.

macro parameter;global variable;Floyd algorithm;multi-thread

A

TP301.6

10.3778/j.issn.1002-8331.1209-0045

LI Chaoyan,PEI Lintao.Difference of multi-thread parallel Floyd algorithm with macro parameter and global variable.Computer Engineering and Applications,2014,50（16）：45-47.

李超燕（1978—），女，副教授，研究方向為算法設計與應用；裴林滔（1988—），男，碩士生，研究方向為并行程序與高性能計算。E-mail：190515528@qq.com

2012-09-09

2012-10-11

1002-8331（2014）16-0045-03

CNKI網(wǎng)絡優(yōu)先出版：2012-12-18,http://www.cnki.net/kcms/detail/11.2127.TP.20121218.1520.005.htm l