高 瑛，嚴(yán)正國

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

0 引言

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

1 并行計算性能分析

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

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

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

2 OpenMP

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

3 性能測試

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

3.1 PSO算法的并行化

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

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

3.2 實驗結(jié)果

實 驗 環(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作為開發(fā)軟件。實驗選取QAPLIB（http://www.seas.upenn.edu/qaplib）中典型實例進(jìn)行了測試。結(jié)果如表1所示。

4 結(jié)論

本文從分析OpenMP本身的特點及編程模型入手，通過實驗證明了基于OpenMP的并行算法的有效性，而且并行PSO算法在所選的測試實例上都獲得了超線性的加速比。充分利用了OpenMP共享存儲體系結(jié)構(gòu)的特點，避免了消息傳遞帶來的開銷，但是它的不足之處在于可擴(kuò)展性差。因此，今后的工作將放在對基于SMP集群的MPI與OpenMP混合編程模型的研究，從而克服系統(tǒng)擴(kuò)展性差的缺點，進(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)化算法求解二次分配問題[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]張慧珍，馬良，（西）羅佑.二次分配問題及其線性化技術(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.