国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

Gauss—Seidel迭代法求解線性方程組的并行化研究

2016-11-25 20:36:38米瑞琪于朋
科技視界 2016年25期
關(guān)鍵詞:迭代法

米瑞琪 于朋

【摘 要】Gauss-Seidel迭代法在工程計算中具有廣泛應(yīng)用。高維矩陣對線性方程組的求解效率提出了新的要求。本文提出了兩種模式下的Gauss-Seidel并行計算方法,并對比了在不同矩陣維數(shù)下的加速效率,得到了具有較高加速比的并行迭代方法。

【關(guān)鍵詞】Gauss-Seidel;迭代法;并行;MPI;矩陣運算

1 問題背景與提出

在實際工程應(yīng)用中經(jīng)常需要用到求解維數(shù)較高的線性代數(shù)方程組,對于線性代數(shù)方程組的求解方法可以分成兩類:直接法和迭代法,其中直接法得到的是方程組的真解,其求解過程為通過有限步四則運算,常用的實現(xiàn)方式是Gauss消去方法和矩陣的三角分解方法,這種計算方式在求解過程中會產(chǎn)生大量的非零元素,存儲量和計算量均比較大,因此常用于求解低階、稠密線性方程組。對于高維線性方程組,可以采用并行運算的方式進(jìn)一步提高計算效率,Gauss-Seidel迭代法具有收斂速度快、計算穩(wěn)定性好等優(yōu)點,是求解高維線性方程組的常用方法,因此本文將對Gauss-Seidel迭代法的并行化進(jìn)行研究,期望獲取較高的運行效率和加速比。

2 Gauss-Seidel迭代法的并行算法描述

任務(wù)分配模式一:連續(xù)等分矩陣法

在《并行算法的設(shè)計與分析》一書中給出了一種矩陣分配的算法,設(shè)矩陣的階為N,采用m個線程進(jìn)行計算,則將矩陣等分成m塊,每一塊分到的任務(wù)量為N/m,每一個線程計算完自己的分量之后立刻向其他的線程進(jìn)行廣播。

由于Gauss-Seidel迭代法中,對于右端項的計算和中間項的計算是不需要用到下一次迭代值的,因此在這一階段各個線程工作量相同,同時完成,問題的關(guān)鍵在于首項的計算,順序等分矩陣時,以四個線程為例,在計算左端項的時候,各個線程的工作次序如下圖所示。其中不同的顏色代表不同線程的任務(wù),每個線程依次計算分給自己的一個子塊,每計算完一個分量后立刻沿上方箭頭所指方向進(jìn)行廣播。

任務(wù)分配模式二:離散等分矩陣法

為了改進(jìn)任務(wù)分配模式一中的缺陷,進(jìn)一步提高計算的并行程度,同時保持任務(wù)的均衡性,筆者對模式一中的任務(wù)分配方式作出了一定程度的改進(jìn),設(shè)線程數(shù)為m,則將矩陣以每m行作為一個單位,順序分配給m個線程,前一個線程完成自己的計算任務(wù)之后,立刻將計算結(jié)果廣播給其余的m個線程,同時開始下一個矩陣塊中自己應(yīng)完成的任務(wù),直到最后將自己所應(yīng)完成的N/m個分量計算完畢。任務(wù)分配模式見左圖,其中不同的顏色代表不同的線程的計算任務(wù),每個塊右端的箭頭表示變量的廣播方向。

這樣劃分任務(wù),每個線程的工作量沒有發(fā)生變化,但是第一個達(dá)到終點的線程和最后一個達(dá)到終點的線程的時間相差僅為m個分量的計算時間。假設(shè)矩陣的階為10000,采用4個線程進(jìn)行計算(m=4),那么第一個線程和最后一個線程到達(dá)終點的時間差為m=4個分量的計算時間。反觀第一種任務(wù)分配模式,假設(shè)第一個線程計算完自己的N/m=10000/4=2500個分量,則需要再經(jīng)過計算2500、5000、7500個分量的時間之后二、三、四號線程才能到達(dá)終點,并且隨著矩陣階的增大,這個時間差異還會繼續(xù)增大。

根據(jù)上面的分析,在理論上模式二具有更優(yōu)的時間性能。筆者也進(jìn)行了實驗,從實際操作上證明了模式二具有更優(yōu)的時間性能。因此選擇模式二作為并行化的基本算法,基本并行算法步驟可以描述如下:

(一)末項/中間項計算的并行化

(二)首項的并行計算

首項是下三角矩陣與本次迭代的結(jié)果相乘,因此不易實現(xiàn)并行化,但是借鑒并行計算中的流水線作業(yè)思想,可以采用步進(jìn)和廣播的方法進(jìn)行并行化。假設(shè)核數(shù)為4,則首項的并行化可以設(shè)計如下:

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

采用任務(wù)分配模式二,采用MPI的并行算法可以描述如下:

int N:矩陣的階數(shù)

int numProcs:用于計算的進(jìn)程數(shù)量

int m:每個進(jìn)程所分得的任務(wù)量,m=N/numProcs

int myID:標(biāo)識本進(jìn)程的進(jìn)程號

int task:記錄本次循環(huán)中本線程計算的未知量下標(biāo)

double A[m][numProcs]:每個進(jìn)程單獨

保存屬于自己的矩陣分塊

double x_old[N]:double類型的N維數(shù)組,用于保存本次迭代分量的數(shù)值

double sum[N]:保存迭代分量計算過程中的累加結(jié)果;

double x_diff:相鄰兩次迭代運算中的誤差,定義為:x_diff=(_1≤i≤N)|x_i^((k+1) )-x_i^((k) ) |

bool x_status[N]:標(biāo)識每個迭代分量是否完成本次迭代

算法描述:

//進(jìn)入并行域

//0號進(jìn)程讀取矩陣A,右端項b,迭代初始值x0并向其他進(jìn)程進(jìn)行廣播

Do

x_old[n]=x[n];x_diff=diff;

For(i=0;i

{

task=i*numProcs+myID;//本次循環(huán)中需要計算的分量下標(biāo)

temp=x_old[task];//保存該該分量的原始值,以便計算誤差

//計算右端項

sum[task]=b[i]/A[i][task];//這里的A[i][task]對應(yīng)原迭代矩陣中的A[task][task],這里因為對矩陣重新分割,下標(biāo)也相應(yīng)發(fā)生變化

//計算中間項

For(j=task+1;j

sum[task]=sum[task]-A[i][j]/A[i][task]*x_old[j];

For(int j=0;j

sum[task]=sum[task]-A[i][j]/A[i][task]*x_old[j];

//全體進(jìn)程依次計算自己本次迭代中的左端項

For(int j=0;j

{

if(myID==j)//輪到當(dāng)前進(jìn)程計算自己的task對應(yīng)的分量并進(jìn)行廣播

{

for(int k=0;k

sum[task]=sum[task]-A[i][i*numProcs+k]/A[i][task]*x_old[i*numProcs+k];

//計算出新的解向量

x_old[task]=sum[task];

//將解進(jìn)行廣播

MPI_Bcast(&x_old[task],1,MPI_DOUBLE,myID,MPI_COMM_WORLD);

}

else//循環(huán)到的分量下標(biāo)不是當(dāng)前進(jìn)程的計算任務(wù),則當(dāng)前進(jìn)程接收新解向量

{

//接收解向量

MPI_Bcast(&x_old[i*numProcs+j],1,MPI_DOUBLE,j,MPI_COMM_

WORLD);

}

}

if(abs(x_new[i]-x_old[i])>x_diff)

x_diff= abs(x_new[i]-x_old[i]); //計算本次迭代的誤差

}

//全體進(jìn)程向其他進(jìn)程廣播自己本次誤差,通過全體進(jìn)程誤差最大值判斷是否需要繼續(xù)迭代

MPI_Allreduce(&thread_diff,&x_diff,1,MPI_DOUBLE,MPI_MAX,MPI_COMM_WORLD);

}While(x_diff

//若達(dá)到迭代精度則輸出運算結(jié)果

x[n]=x_new[n]

3 數(shù)值實驗和結(jié)論

可以測試串行算法的正確性,測試矩陣取為:

由于A是嚴(yán)格對角占優(yōu)矩陣,因此G-S迭代法一定收斂,并且該方法的精確解為全1向量。

從表1中不難看出,隨著矩陣維數(shù)的增大,MPI算法沒有體現(xiàn)出并行的優(yōu)勢,這說明對矩陣采用連續(xù)分塊的策略還是應(yīng)該改進(jìn)的。采用筆者的改進(jìn)算法之后的加速比與MPI對比如下:

表1 任務(wù)分配模式二下MPI與openMP加速比對比

與采用任務(wù)分配模式一和openMP相比,筆者改良的迭代法均有更高的加速比,加速比穩(wěn)定在1.7-1.8左右。理論上采用四個核加速比上限值為4,但是考慮到進(jìn)程之間通信需要一定的時間開銷,以及并行工具本身也需要時間開銷,因此加速比不會隨著核數(shù)增加而線性增長。

【參考文獻(xiàn)】

[1]陳國良.并行算法的設(shè)計與分析[M].高等教育出版社,1994.

[2]黃麗嫦.Gauss-Seidel迭代法的多核并行運算研究[J].科學(xué)技術(shù)與工程,2012(12):2674-2692.

[3]周偉明.多核計算與程序設(shè)計[M].武漢:華中科技大學(xué)出版社,2009.

[4]劉其成,胡佳男,孫雪姣,等.并行計算與程序設(shè)計[M].北京:中國鐵道出版社,2014.

[5]張武生,薛巍,李建江,等.MPI并行程序設(shè)計實例教程[M].北京:清華大學(xué)出版社,2009.

[責(zé)任編輯:李書培]

猜你喜歡
迭代法
迭代法求解一類函數(shù)方程的再研究
H-矩陣線性方程組的一類預(yù)條件并行多分裂SOR迭代法
用加速度和位移反饋修正無阻尼振動系統(tǒng)的一種迭代法
步進(jìn)迭代法井地聯(lián)合地震資料拓頻處理
Jacobi迭代法與Gauss-Seidel迭代法
多種迭代法適用范圍的思考與新型迭代法
修正無阻尼結(jié)構(gòu)系統(tǒng)的一種有效迭代法
基于分段迭代法的PMU的優(yōu)化配置研究
迭代法求解約束矩陣方程AXB+CYD=E
預(yù)條件SOR迭代法的收斂性及其應(yīng)用
互助| 高陵县| 松阳县| 北流市| 新营市| 西乡县| 湛江市| 张家港市| 香港| 左权县| 抚顺县| 白水县| 东乌珠穆沁旗| 普洱| 永吉县| 弋阳县| 武冈市| 南靖县| 平舆县| 邵阳县| 辉县市| 辽阳市| 永昌县| 淮滨县| 义马市| 赣榆县| 彩票| 昌都县| 青阳县| 尚义县| 西充县| 乌兰浩特市| 高碑店市| 伊吾县| 洪江市| 方正县| 分宜县| 莱阳市| 安远县| 东平县| 罗山县|