高 瑛，嚴(yán)正國(guó)

（1，西安石油大學(xué)電子工程學(xué)院，陜西西安,710065;2，延安大學(xué)物電學(xué)院，陜西延安,716000；3，西安石油大學(xué)電子工程學(xué)院，陜西西安,710065）

0 引言

目前多核計(jì)算機(jī)可以實(shí)現(xiàn)系統(tǒng)中多個(gè)進(jìn)程與線程的并行運(yùn)算。并行算法的實(shí)現(xiàn)主要基于三種并行標(biāo)準(zhǔn)：PVM標(biāo)準(zhǔn)；MPI標(biāo)準(zhǔn)；OpenMP標(biāo)準(zhǔn)。對(duì)于大部分串行程序而言，直接在多核處理器上運(yùn)行依然不能夠獲得加速。因此，為提高系統(tǒng)的性能，提出將單一任務(wù)分解成若干個(gè)子任務(wù)，分別在不同的節(jié)點(diǎn)上運(yùn)行。在多核處理機(jī)上，研究并行算法的實(shí)現(xiàn)技術(shù)與并行后系統(tǒng)的性能，具有非常重要的理論與現(xiàn)實(shí)意義。

1 并行計(jì)算性能分析

并行算法的性能通常以加速比和效率作為衡量的標(biāo)準(zhǔn)，下面給出二者的定義。

系統(tǒng)對(duì)加速比的定義：加速比為系統(tǒng)執(zhí)行串行程序所用時(shí)間與在同一臺(tái)計(jì)算機(jī)上使用多個(gè)并行部件執(zhí)行所花費(fèi)時(shí)間之比。

系統(tǒng)對(duì)效率的定義：效率為加速比與所有參與并行執(zhí)行部件的個(gè)數(shù)之比。比值越大，則效率越高。

2 OpenMP

OpenMP是共享存儲(chǔ)體系結(jié)構(gòu)編程的工業(yè)標(biāo)準(zhǔn)，采用標(biāo)準(zhǔn)的Fork/Join式并行執(zhí)行模型，如圖1所示，使用由運(yùn)行庫(kù)提供的編譯指導(dǎo)語(yǔ)句來(lái)實(shí)現(xiàn)并行化。在程序開(kāi)始執(zhí)行時(shí)，只存在一個(gè)主線程，在執(zhí)行過(guò)程中，如果遇到并行編譯指令要求并行執(zhí)行時(shí)，這時(shí)候，主線程會(huì)派生出子線程或者啟用系統(tǒng)原有線程來(lái)并行執(zhí)行任務(wù)。在執(zhí)行的過(guò)程中，主線程協(xié)同子線程共同工作，等待并行代碼執(zhí)行完畢后，子線程退出或者掛起，不再參與任務(wù)的執(zhí)行，程序回到原來(lái)的主線程上繼續(xù)執(zhí)行，直到整個(gè)程序運(yùn)行結(jié)束。

3 性能測(cè)試

本文采用對(duì)求解QAP的粒子群優(yōu)化算法用OpenMP技術(shù)進(jìn)行并行來(lái)驗(yàn)證OpenMP的性能。

3.1 PSO算法的并行化

二次分配問(wèn)題（QAP）是一種經(jīng)典的組合優(yōu)化問(wèn)題，易于描述而難于求解，已經(jīng)歸入NP-hard問(wèn)題。QAP不僅以各種不同的形式存在于實(shí)際生活領(lǐng)域中，而且問(wèn)題本身又包含著組合優(yōu)化的要求，在諸多領(lǐng)域廣泛應(yīng)用。因此，研究QAP具有重要的理論與現(xiàn)實(shí)意義。然而，當(dāng)問(wèn)題的規(guī)模足夠大時(shí)，QAP的解空間呈現(xiàn)爆炸特征,致使無(wú)法在多項(xiàng)式時(shí)間內(nèi)求解最優(yōu)解。因此，人們通常采用元啟發(fā)式算法來(lái)有效地解決這一問(wèn)題。

粒子群優(yōu)化算法（PSO）是一種基于群體的新型隨機(jī)元啟發(fā)式搜索算法，起源于鳥(niǎo)類(lèi)群體智能,可以被納入多主體優(yōu)化系統(tǒng) (MAOS)，已在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)、分類(lèi)、模式識(shí)別、信號(hào)處理、機(jī)器人技術(shù)等許多領(lǐng)域取得了成功的應(yīng)用。因此，粒子群優(yōu)化算法具有很好的并行性。

3.2 實(shí)驗(yàn)結(jié)果

實(shí) 驗(yàn) 環(huán) 境 為 Intel（R）Core(TM) 2 Duo CPU T5670@1.8GHZ,內(nèi)存為2GB，WinXP SP3操作系統(tǒng)，以Intel Fortran 10.1.014 with vs2005作為開(kāi)發(fā)軟件。實(shí)驗(yàn)選取QAPLIB（http://www.seas.upenn.edu/qaplib）中典型實(shí)例進(jìn)行了測(cè)試。結(jié)果如表1所示。

4 結(jié)論

本文從分析OpenMP本身的特點(diǎn)及編程模型入手，通過(guò)實(shí)驗(yàn)證明了基于OpenMP的并行算法的有效性，而且并行PSO算法在所選的測(cè)試實(shí)例上都獲得了超線性的加速比。充分利用了OpenMP共享存儲(chǔ)體系結(jié)構(gòu)的特點(diǎn)，避免了消息傳遞帶來(lái)的開(kāi)銷(xiāo)，但是它的不足之處在于可擴(kuò)展性差。因此，今后的工作將放在對(duì)基于SMP集群的MPI與OpenMP混合編程模型的研究，從而克服系統(tǒng)擴(kuò)展性差的缺點(diǎn)，進(jìn)而提高系統(tǒng)的易用性和可移植性。

圖1 Fork/Join并行模型

表1 并行算法的加速比、效率

[1]OpenMP C application program interface version 2.0[EB/OL].(2000-11).http://www.openmp.org.

[2]周洪斌，呂強(qiáng).利用混合粒子群優(yōu)化算法求解二次分配問(wèn)題[J].計(jì)算機(jī)應(yīng)用與軟件，2009,26（11）.259-260.

[3]S.Sahniand T.Gonzalez.Pcomplete approximation problems[J].Journal of the ACM,1976,23(3).555-565.

[4]張慧珍，馬良，（西）羅佑.二次分配問(wèn)題及其線性化技術(shù)[M].上海人民出版社，2013,01（10）.40-55.

[5]Eberhart R.C,Kennedy J.A New Optimizer Using Partical Swarm Theory.Proc.on 6th International Symposium on Microma chine and Human Science[C].Piscataway:IEEE Service Center,1995.39-43.