基礎(chǔ)并行算法與開源軟件.ppt

1、基礎(chǔ)并行算法及其開源軟件,計算力學(xué)研究所,算法是解題方法的精確描述，是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問題的一系列運算。并行算法（Parallel Algorithm）是一些可同時執(zhí)行的諸進程的集合，這些進程相互作用和協(xié)調(diào)動作從而達到給定問題的求解。并行算法可以分成數(shù)值計算和非數(shù)值計算的并行算法。并行數(shù)值算法就是求解諸如矩陣運算、多項式求值、求解線性方程組等數(shù)值計算問題的并行算法。,在科學(xué)與工程計算的許多問題中，數(shù)值計算問題，特別是矩陣相乘、求解線性方程組和矩陣特征值問題是最基本的內(nèi)核。隨著MPP(Massively Parallel Processing)并行計算機、機群以及消息傳

2、遞并行環(huán)境（MPI 等）的不斷發(fā)展和完善，為了充分發(fā)揮分布式并行計算機的功效，掌握針對分布式并行計算機的并行數(shù)值計算方法變得越來越重要。這里著重考慮矩陣向量運算和求解線性方程組的多種并行算法。,第一節(jié) 并行矩陣向量乘法,預(yù)備幾個記號,內(nèi)積,Saxpy,Gaxpy,串行矩陣向量乘法,稱之為Gaxpy,常規(guī)方式是每次修正一個分量,Gaxpy：行型算法,例：,Gaxpy：列型算法,例：,Ax表示成為A的列向量的線性組合。,矩陣的劃分,帶狀劃分：將矩陣整行或整列地分成若干個組，每組指派給一個處理器。這些行列可以是連續(xù)的，也可以是等距相間的，前者稱為塊帶狀劃分，后者稱為循環(huán)帶狀劃分。,nn的矩陣（0,1

3、,n-1)，p個處理器(0,1,p-1),塊帶狀劃分： 每個處理器均勻連續(xù)地分配有n/p行（列），其中第i個處理器上包含：,P0,P1,P2,P3,0 1 2 3,4 5 6 7,8 9 10 11,12 13 14 15,以4個處理器，16列矩陣為例,假設(shè)n能被p整除,循環(huán)帶狀劃分： 每個處理器均勻相間地分配有n/p行（列），其中第i個處理器上包含：,以4個處理器，16列矩陣為例,棋盤劃分：將方陣劃分成若干個子方陣，每個子方陣指派給一個處理器，此時每個處理器均不包含整行或整列。棋盤劃分也可分為塊棋盤劃分和循環(huán)棋盤劃分。,nn的矩陣（0,1,n-1)，p個處理器（組成 的二維處理器陣列），每個

4、處理器均勻地分配有 個矩陣元素。,塊棋盤劃分：,以16個處理器，88矩陣為例,循環(huán)棋盤劃分：,行塊帶狀劃分的矩陣向量乘法,劃分成p塊，假設(shè)n能被p整除，第k塊：（0k p-1),假設(shè)Ak，xk，yk存儲再進程k上，分別存在局部存儲器,在給定進程k上，每步計算中需要用到的子矩陣A的行標(biāo)號始終不變，說明在每步計算時用到的A的塊實際上都一直處于本進程上。而x的塊位于不同的處理機上，需要進行數(shù)據(jù)通信。本處采用每計算一次將x的塊在同列進程中循環(huán)上移一個位置的方式來實現(xiàn)這種數(shù)據(jù)通信。算法具體描述如下：,算法：,以p3，n3為例，yAx,第1步,第2步,第3步,P0,P1,P2,第二節(jié) 并行矩陣矩陣乘法,串

5、行矩陣矩陣乘法,矩陣乘法：ijk形式，標(biāo)量描述,矩陣乘法中三個求和循環(huán)可任意排序，從而一共3！6種形式，如jki形式（標(biāo)量描述）,這6種可能性（ijk,jik,ikj,jki,kij,kji）的任何一個都對應(yīng)一內(nèi)層運算，而且具有自己數(shù)據(jù)流動形式。例如ijk形式，內(nèi)層運算是點積，數(shù)據(jù)用到的是A的行和B的列。,矩陣乘法：點積形式（ijk）,記,則上述算法可表示為,進一步可表示為,其中,或表示為,ijk形式的內(nèi)部兩層循環(huán)實質(zhì)上是基于行的Gaxpy運算,矩陣乘法：Saxpy形式（jki）,假定A和C的列分劃為,比較兩邊第j列，可知,一系列Saxpy運算,k循環(huán)實質(zhì)上是一Gaxpy運算,得到如下算法,矩

6、陣乘法：外積形式,考慮kji形式,記,則內(nèi)部的兩層循環(huán)是一個外積修正,可得到以下算法,可見其中的AB是p個外積之和。,并行矩陣矩陣乘法,假設(shè),行列劃分算法,將A和B矩陣分別劃分為如下的行塊子矩陣和列塊子矩陣,算法中ClCmyid,l，AAmyid，B在處理器中每次循環(huán)向前移動一個處理器。mm1myid1p mod p。,初始狀態(tài)，Ai、Bi和Cij(j=0,1,p-1)存放在Pi中。,為 矩陣,將Cij的計算放在Pi上進行，這樣在初始數(shù)據(jù)分布時，數(shù)據(jù)Ai已經(jīng)在Pi上，但進程Pi上只有Bi，其它Bj處于其它進程上，需要對B的塊進行循環(huán)移位的方式實現(xiàn)。由于使用p個處理器，每次每個處理器計算出一個C

7、ij，計算C需要p次計算。Cij的計算是按對角線進行的，計算流程如下：,以p3，n3為例，CAB,第1步,第2步,第3步,P0,P1,P2,行行劃分算法,初始狀態(tài)，Aij、Bi和Ci(j=0,1,p-1)存放在Pi中。將Ci的計算放在Pi上進行，這樣在初始數(shù)據(jù)分布時，數(shù)據(jù)Ai已經(jīng)在Pi上，但進程Pi上只有Bi，其它Bj處于其它進程上，需要對B的塊進行循環(huán)移位的方式實現(xiàn)。,以p3，n3為例，CAB,第1步,第2步,第3步,P0,P1,P2,與Saxpy形式、ikj形式對應(yīng),列列劃分算法,初始狀態(tài)，Aj、Bi,j和Cj(i=0,1,p-1)存放在Pj中。將Cj的計算放在Pj上進行，這樣在初始數(shù)據(jù)分布時，數(shù)據(jù)Bj已經(jīng)在Pj上，但進程Pi上只有Aj，其它Ai處于其它進程上，需要對A的塊進行循環(huán)移位的方式實現(xiàn)。,以p3，n3為例，CAB,第1步,第2步,第3步,P0,P1,P2,與Saxpy形式、jki形式對應(yīng),列行劃分算法,假設(shè)C按列存放,初始狀態(tài)，Ai、Bi,j和Ci(i=0,1,p-1)存放在Pi中。將Cj的計算放在Pj上進行，這樣在初始數(shù)據(jù)分布時，數(shù)據(jù)Ai和Bi都已經(jīng)在Pi上，每次計算得到Cj的部分和，存儲在Pj上，需要數(shù)據(jù)通信實現(xiàn)這種存儲。,以p3，n3為例，CAB,第1步,第2步,第3