李超燕，裴林滔

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

2.國防科技大學(xué)計(jì)算機(jī)學(xué)院，長沙 410000

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

李超燕1，裴林滔2

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

2.國防科技大學(xué)計(jì)算機(jī)學(xué)院，長沙 410000

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

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

1 概述

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

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

2 算法原理

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

Floyd串行算法的描述如下：

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

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

3 算法實(shí)現(xiàn)

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

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

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

4 實(shí)驗(yàn)測試與分析

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

實(shí)驗(yàn)環(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）百萬億次巨型機(jī)，單計(jì)算節(jié)點(diǎn)為2路6核Intel Westmere EP6處理器，銀河麒麟Linux操作系統(tǒng)，gcc+ openmp3.0編譯。

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

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

4.2 實(shí)驗(yàn)結(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以雙線程運(yùn)行，運(yùn)行時(shí)間如表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)境下編譯運(yùn)行，其中并行程序1，2以雙線程運(yùn)行，運(yùn)行時(shí)間如表2所示（單位：s）。

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

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

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

表3 串行程序1，2運(yùn)行時(shí)間表s

表4 并行程序1運(yùn)行時(shí)間表s

表5 并行程序2運(yùn)行時(shí)間表s

本文實(shí)驗(yàn)數(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的性能相當(dāng)。對于Floyd算法，在串行程序中雖然宏參數(shù)帶來了性能優(yōu)勢，但在并行程序中反而不如全局變量。

5 結(jié)束語

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

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

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

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

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

[5]楊慶芳，劉冬，楊兆升.基于MPI+OpenMP混合編程模型的城市路網(wǎng)最短路徑并行算法[J].吉林大學(xué)學(xué)報(bào)，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].計(jì)算機(jī)工程，2006（24）.

[8]濮芳琍，盧炎生.一種并行程序可靠組合測試策略[J].華中科技大學(xué)學(xué)報(bào)，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—），女，副教授，研究方向?yàn)樗惴ㄔO(shè)計(jì)與應(yīng)用；裴林滔（1988—），男，碩士生，研究方向?yàn)椴⑿谐绦蚺c高性能計(jì)算。E-mail：190515528@qq.com

2012-09-09

2012-10-11

1002-8331（2014）16-0045-03

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