楊菁蓓

中國(guó)石油大學(xué)（華東）理學(xué)院

復(fù)化梯形求定積分的并行計(jì)算方法

楊菁蓓

中國(guó)石油大學(xué)（華東）理學(xué)院

使用復(fù)化梯形法求積分，需要將區(qū)間［0，1］進(jìn)行分割，分割數(shù)越大求得的積分近似值就越精確。但是當(dāng)分割數(shù)N較大時(shí)，算法的計(jì)算量會(huì)比較大，算法的運(yùn)行效率比較低?？梢酝ㄟ^并行計(jì)算的方法提高運(yùn)算的速度。這樣在達(dá)到較高計(jì)算精度的同時(shí)提高了算法運(yùn)行的速度。

復(fù)化梯形法；并行計(jì)算；定積分

一、某問題的串行算法描述

1.1實(shí)現(xiàn)梯形積分法的基本步驟

（1）輸入?yún)^(qū)間［a，b］的端點(diǎn)a，b值以及分割數(shù)N；

（2）將區(qū)間［a，b］等分成N個(gè)小區(qū)間，每一個(gè)小區(qū)間的長(zhǎng)度h=（b-a）/N；

（3） 計(jì)算每一個(gè)等分點(diǎn)的函數(shù)值yi=f （a+ih）（i=0，1，…，N ）；

二、該問題的并行算法描述

2.1基于API的多核并行算法的設(shè)計(jì)

Windows系統(tǒng)提供很多API接口，可以利用WINAPI定義線程函數(shù)，函數(shù)內(nèi)部設(shè)計(jì)好改線程所要進(jìn)行的工作，然后主函數(shù)里創(chuàng)建線程，將線程函數(shù)導(dǎo)入創(chuàng)建好的線程中運(yùn)行，計(jì)算根據(jù)創(chuàng)建的線程數(shù)目，調(diào)用相應(yīng)數(shù)目的CPU進(jìn)行計(jì)算，保證每個(gè)CPU運(yùn)行一個(gè)線程，最終計(jì)算結(jié)束后將結(jié)果合并可得到正確結(jié)果。

2.2基于OpenMP的多核并行算法的設(shè)計(jì)

利用編譯指導(dǎo)語句parallelfor并行原理采用工作分配的執(zhí)行方式，將循環(huán)所需要工作量按一定方式分配到各個(gè)執(zhí)行線程，所有線程執(zhí)行工作總合是原串行完成的工作量。此方式對(duì)一個(gè)確定并且完整的for循環(huán)進(jìn)行分割，分割成多段在不同CPU上運(yùn)行。

可以將（2）分割成若干段獨(dú)立的計(jì)算，每段計(jì)算完成后進(jìn)行整理合并，在具體計(jì)算的過程中可以根據(jù)CPU的個(gè)數(shù)將多項(xiàng)式分成合適的個(gè)數(shù)。

三、算法實(shí)現(xiàn)

3.1串行算法的實(shí)現(xiàn)

3.2基于基于API的多核并行算法的實(shí)現(xiàn)

主要代碼：

3.3基于OpenMP的多核并行算法的實(shí)現(xiàn)

OpenMp提供了對(duì)并行算法的高層的抽象描述，通過在源代碼中加入專用pragma來指明自己的意圖，由此編譯器可以自動(dòng)將程序進(jìn)行并行化，并在必要之處加入同步互斥以及通信。歸約操作的方式是拷貝復(fù)制執(zhí)行

3.4基于MPI的并行算法實(shí)現(xiàn)

MPI是基于消息傳遞的并行計(jì)算模式，建立消息傳遞標(biāo)準(zhǔn)的主要優(yōu)點(diǎn)是可移植性和易于使用。以低級(jí)消息傳遞程序?yàn)榛A(chǔ)的較高級(jí)和抽象程序所構(gòu)成的分布儲(chǔ)存通信環(huán)境中，標(biāo)準(zhǔn)化的效益特別明顯。隨著高性能計(jì)算技術(shù)的普及，MPI標(biāo)準(zhǔn)如今已經(jīng)成為事實(shí)意義上的消息傳遞并行編程標(biāo)準(zhǔn)，也是最為流行的并行計(jì)算編程接口。

四、數(shù)值實(shí)驗(yàn)結(jié)論

（1）MPI模擬多節(jié)點(diǎn)計(jì)算的速度最快，線程調(diào)用以及初始化耗費(fèi)時(shí)間少，加速比接近理論值。并且節(jié)點(diǎn)數(shù)目增加時(shí)，計(jì)算效果更好，所以MPI并行計(jì)算最適合求解大規(guī)模問題。

（2）WinAPI 實(shí)現(xiàn)用線程號(hào)分配得每個(gè)線程不同的計(jì)算任務(wù)，加速效果比較好，但是線程數(shù)不變時(shí)，隨著計(jì)算步數(shù)的增加，加速比逐漸減少。

（3）利用OpenMP實(shí)現(xiàn)并行時(shí)，利用parallel for 進(jìn)行計(jì)算不用考慮如何歸約數(shù)據(jù)的問題，方便計(jì)算，并且計(jì)算速度也比較快。

楊菁蓓（1995—）女，漢族，河南鄧州人，中國(guó)石油大學(xué)（華東）理學(xué)院，2013級(jí)本科生，數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)

［1］高性能并行計(jì)算（陳華）

［2］ 由Euler_Maclaurin求和公式構(gòu)造修正復(fù)化梯形公式（劉明才）