第六講矩陣計(jì)算并行算法

1、1第六講矩陣計(jì)算并行算法2主要內(nèi)容主要內(nèi)容n 并行算法基礎(chǔ)知識(shí)并行算法基礎(chǔ)知識(shí)n 矩陣向量乘積的并行算法矩陣向量乘積的并行算法n 矩陣矩陣乘積的并行算法矩陣矩陣乘積的并行算法n 矩陣的矩陣的 LU 分解并行算法分解并行算法n 下三角線性方程組的并行算法下三角線性方程組的并行算法3并行算法基礎(chǔ)知識(shí)并行算法基礎(chǔ)知識(shí)n 一些基本概念一些基本概念l 加速比加速比其中其中 Ts 串行程序運(yùn)行時(shí)間，串行程序運(yùn)行時(shí)間，Tp(q) 為為 q 個(gè)進(jìn)程的運(yùn)行時(shí)間個(gè)進(jìn)程的運(yùn)行時(shí)間 l 并行效率并行效率4程序性能優(yōu)化程序性能優(yōu)化n 串行程序性能優(yōu)化串行程序性能優(yōu)化 并行程序性能優(yōu)化的基礎(chǔ)并行程序性能優(yōu)化的基礎(chǔ)l 調(diào)用

2、高性能庫(kù)。如：調(diào)用高性能庫(kù)。如：BLAS、LAPACK、FFTWl 選擇編譯器優(yōu)化選項(xiàng)：選擇編譯器優(yōu)化選項(xiàng)：-O2、-O3l 合理定義數(shù)組維數(shù)合理定義數(shù)組維數(shù)l 注意嵌套循環(huán)次數(shù)：注意嵌套循環(huán)次數(shù)：數(shù)據(jù)訪問(wèn)的空間局部性和時(shí)間局部性數(shù)據(jù)訪問(wèn)的空間局部性和時(shí)間局部性l 數(shù)據(jù)分塊數(shù)據(jù)分塊l 循環(huán)展開(kāi)循環(huán)展開(kāi) 例例: ex4performance.c5程序性能優(yōu)化程序性能優(yōu)化n 并行程序性能優(yōu)化并行程序性能優(yōu)化l 設(shè)計(jì)好的并行算法和通信模式設(shè)計(jì)好的并行算法和通信模式l 減少通信次數(shù)、提高通信粒度減少通信次數(shù)、提高通信粒度l 多進(jìn)程通信時(shí)盡量使用高效率的聚合通信算法多進(jìn)程通信時(shí)盡量使用高效率的聚合通信算

3、法l 負(fù)載平衡負(fù)載平衡l 通信與計(jì)算的重疊通信與計(jì)算的重疊l 減少進(jìn)程的空閑時(shí)間減少進(jìn)程的空閑時(shí)間l 通過(guò)引入重復(fù)計(jì)算來(lái)減少通信通過(guò)引入重復(fù)計(jì)算來(lái)減少通信6矩陣并行矩陣并行算法算法n 一些記號(hào)和假定一些記號(hào)和假定l 假設(shè)有假設(shè)有 p 個(gè)處理器，每個(gè)處理器上運(yùn)行一個(gè)進(jìn)程個(gè)處理器，每個(gè)處理器上運(yùn)行一個(gè)進(jìn)程 l Pj 表示第表示第 j 個(gè)處理器，個(gè)處理器，Pmyid 表示當(dāng)前的處理器表示當(dāng)前的處理器l send(x; j) 表示在表示在 Pmyid 中把數(shù)據(jù)塊中把數(shù)據(jù)塊 x 發(fā)送給發(fā)送給 Pj 進(jìn)程進(jìn)程l recv(x; j) 表示從表示從 Pj 進(jìn)程接收數(shù)據(jù)塊進(jìn)程接收數(shù)據(jù)塊 xl i mod p

4、表示表示 i 對(duì)對(duì) p 取模運(yùn)算取模運(yùn)算 程序設(shè)計(jì)與機(jī)器實(shí)現(xiàn)是密不可分的，計(jì)算結(jié)果的好壞與編程序設(shè)計(jì)與機(jī)器實(shí)現(xiàn)是密不可分的，計(jì)算結(jié)果的好壞與編程技術(shù)有很大的關(guān)系，尤其是在并行計(jì)算機(jī)環(huán)境下，開(kāi)發(fā)程技術(shù)有很大的關(guān)系，尤其是在并行計(jì)算機(jī)環(huán)境下，開(kāi)發(fā)高質(zhì)量的程序?qū)Πl(fā)揮計(jì)算機(jī)的性能起著至關(guān)重要的作用高質(zhì)量的程序?qū)Πl(fā)揮計(jì)算機(jī)的性能起著至關(guān)重要的作用7主要內(nèi)容主要內(nèi)容n 并行算法基礎(chǔ)知識(shí)并行算法基礎(chǔ)知識(shí)n 矩陣向量乘積的并行算法矩陣向量乘積的并行算法n 矩陣矩陣乘積的并行算法矩陣矩陣乘積的并行算法n 矩陣的矩陣的 LU 分解并行算法分解并行算法n 下三角線性方程組的并行算法下三角線性方程組的并行算法8矩陣向

5、量乘積矩陣向量乘積n 串行算法串行算法l 實(shí)現(xiàn)方法一：實(shí)現(xiàn)方法一：i-j 循環(huán)循環(huán)yAx , m nnAx RRfor i=1 to m y(i)=0.0 for j=1 to n y(i)=y(i)+A(i,j)*x(j) end forend for9矩陣向量乘積矩陣向量乘積n 串行算法串行算法l 實(shí)現(xiàn)方法二：實(shí)現(xiàn)方法二：j-i 循環(huán)循環(huán)例：例：ex4matvec.fy=0 % 先賦初值先賦初值for j=1 to n for i=1 to m y(i)=y(i)+A(i,j)*x(j) end forend for10矩陣向量乘積矩陣向量乘積n 并行算法一并行算法一l 矩陣的劃分方法：按

6、行劃分和按列劃分矩陣的劃分方法：按行劃分和按列劃分l 按按行劃分并行算法劃分并行算法將矩陣將矩陣 A 按行劃分成如下的行按行劃分成如下的行塊子矩陣塊子矩陣將將 Ai 存放在結(jié)點(diǎn)存放在結(jié)點(diǎn) Pi 中，每個(gè)結(jié)點(diǎn)計(jì)算中，每個(gè)結(jié)點(diǎn)計(jì)算 Ai x，最后，最后調(diào)用調(diào)用 MPI_GATHER 或或 MPI_GATHERV 即可即可則則11矩陣向量乘積矩陣向量乘積n 并行算法二并行算法二l 按按列劃分并行算法劃分并行算法將將 Ai 和和 xi 存放在結(jié)點(diǎn)存放在結(jié)點(diǎn) Pi 中，每個(gè)結(jié)點(diǎn)計(jì)算中，每個(gè)結(jié)點(diǎn)計(jì)算 Ai xiT，最后調(diào)用最后調(diào)用 MPI_REDUCE 或或 MPI_ALLREDUCE 即可即可將矩陣將矩

7、陣 A 按列劃分，并對(duì)按列劃分，并對(duì) x 也做相應(yīng)的劃分也做相應(yīng)的劃分其中其中 xi 的長(zhǎng)度與的長(zhǎng)度與 Ai 的列數(shù)相同，則有的列數(shù)相同，則有12矩陣向量乘積矩陣向量乘積示例示例n 例：例：按按列劃分，用劃分，用 p 個(gè)進(jìn)程并行計(jì)算矩陣向量乘積，其中個(gè)進(jìn)程并行計(jì)算矩陣向量乘積，其中示例程序示例程序：ex4matvec.f(), n nijAa 1R1 1ijaij 1, 1, , 1, Tnx 1R13上機(jī)作業(yè)上機(jī)作業(yè)l 上機(jī)作業(yè)上機(jī)作業(yè)：1、編寫(xiě)按、編寫(xiě)按行劃分計(jì)算矩陣向量乘積的通用并行程序劃分計(jì)算矩陣向量乘積的通用并行程序2、按按列劃分，編寫(xiě)通用并行程序計(jì)算上面的乘積劃分，編寫(xiě)通用并行程序

8、計(jì)算上面的乘積14主要內(nèi)容主要內(nèi)容n 并行算法基礎(chǔ)知識(shí)并行算法基礎(chǔ)知識(shí)n 矩陣向量乘積的并行算法矩陣向量乘積的并行算法n 矩陣矩陣乘積的并行算法矩陣矩陣乘積的并行算法n 矩陣的矩陣的 LU 分解并行算法分解并行算法n 下三角線性方程組的并行算法下三角線性方程組的并行算法15矩陣矩陣矩陣乘積矩陣乘積n 串行算法一串行算法一：i-j-k 循環(huán)循環(huán)CAB, m ll nAB RRfor i=1 to m for j=1 to l C(i,j)=0 for k=1 to n C(i,j)=C(i,j)+A(i,k)*B(k,j) end for end forend for16矩陣矩陣矩陣乘積矩陣乘積

9、n 串行算法二串行算法二：j-k-i 循環(huán)循環(huán)CAB, m ll nAB RRC=0for j=1 to l for k=1 to n for i=1 to m C(i,j)=C(i,j)+A(i,k)*B(k,j) end for end forend for17并行并行矩陣矩陣乘積乘積n 假定：假定：n 基于基于 A、B 的不同劃分，的不同劃分，矩陣乘積的并行算法可分為矩陣乘積的并行算法可分為l 行列劃分行列劃分l 行行劃分行行劃分l 列列劃分列列劃分l 列行劃分列行劃分CAB, m ll nAB RRm, l, n 均能能均能能 p 整除，其中整除，其中 p 為進(jìn)程個(gè)數(shù)為進(jìn)程個(gè)數(shù)18行列

10、劃分行列劃分n 行列劃分行列劃分：A 按行劃分、按行劃分、 B 按列劃分按列劃分l 令令 C = (Cij)，其中，其中 Cij = AiBjl 將將 Ai, Bj 和和 Cij ( j = 0, 1, ., p-1) 存放在第存放在第 i 個(gè)處理器中個(gè)處理器中(這樣的存儲(chǔ)方式使得數(shù)據(jù)在處理器中不重復(fù)這樣的存儲(chǔ)方式使得數(shù)據(jù)在處理器中不重復(fù))l Pi 負(fù)責(zé)計(jì)算負(fù)責(zé)計(jì)算 Cij ( j = 0, 1, ., p-1)l 由于使用由于使用 p 個(gè)處理器，每次每個(gè)處理器只計(jì)算一個(gè)個(gè)處理器，每次每個(gè)處理器只計(jì)算一個(gè) Cij, 故計(jì)算出整個(gè)故計(jì)算出整個(gè) C 需要需要 p 次完成次完成l Cij 的計(jì)算是按

11、對(duì)角線進(jìn)行的的計(jì)算是按對(duì)角線進(jìn)行的19行列劃分行列劃分n 并行算法一：行列劃分并行算法一：行列劃分for i=0 to p-1 j=(i+myid) mod p Cj=A*B src = (myid+1) mod p dest = (myid-1+p) mod p if (i!=p-1) send(B,dest) recv(B,src) end ifend forl 本算法中，本算法中，Cj = Cmyid, j , A = Amyid , B 在處理器中每次循環(huán)向前移在處理器中每次循環(huán)向前移動(dòng)一個(gè)處理器，即每次交換一個(gè)子矩陣數(shù)據(jù)塊，共交換動(dòng)一個(gè)處理器，即每次交換一個(gè)子矩陣數(shù)據(jù)塊，共交換 p-

12、1 次次20行列劃分程序示例行列劃分程序示例n 例：例：按按行列行列劃分并行計(jì)算矩陣乘積，其中劃分并行計(jì)算矩陣乘積，其中示例程序示例程序：ex4matmul01.f1(), 1n nijijAaaij 1R(), 1n nijijBbbij 1R21行行劃分行行劃分n 行行行行劃分劃分：A 按行劃分、按行劃分、 B 按行劃分按行劃分22行行劃分行行劃分23列列劃分列列劃分n 列列列列劃分劃分：A 按列劃分、按列劃分、 B 按列劃分按列劃分24列列劃分列列劃分25列行劃分列行劃分n 列列行行劃分劃分：A 按列劃分、按列劃分、 B 按行劃分按行劃分26列行劃分列行劃分27Cannon 算法算法28

13、Cannon 算法算法29Cannon 算法算法30Cannon 算法示例算法示例n 以以 33 分塊為例：分塊為例：9 個(gè)進(jìn)程，進(jìn)行三輪計(jì)算個(gè)進(jìn)程，進(jìn)行三輪計(jì)算l A、B 的起始存放位置：的起始存放位置：A00 A01 A02A10 A11 A12A20 A21 A22B00 B01 B02B10 B11 B12B20 B21 B22l 第一輪：計(jì)算第一輪：計(jì)算(0)(0)ADBA00 A00 A00A11 A11 A11A22 A22 A22B00 B01 B02B10 B11 B12B20 B21 B2231Cannon 算法示例算法示例l 第二輪：計(jì)算第二輪：計(jì)算(1)(1)ADBB1

14、0 B11 B12B20 B21 B22B00 B01 B02A01 A01 A01A12 A12 A12A20 A20 A20l 第三輪：計(jì)算第三輪：計(jì)算(2)(2)ADBB20 B21 B22B00 B01 B02B10 B11 B12A02 A02 A02A10 A10 A10A21 A21 A2132Cannon 算法算法33Cannon 算法算法34Cannon 算法示例算法示例35上機(jī)作業(yè)上機(jī)作業(yè)l 按按行行行行劃分并行計(jì)算矩陣乘積，其中劃分并行計(jì)算矩陣乘積，其中l(wèi) 編寫(xiě)用第二種方式實(shí)現(xiàn)上述矩陣乘積的編寫(xiě)用第二種方式實(shí)現(xiàn)上述矩陣乘積的 Cannon 并行算法并行算法1(), 1n

15、nijijAaaij 1R(), 1n nijijBbbij 1R36主要內(nèi)容主要內(nèi)容n 并行算法基礎(chǔ)知識(shí)并行算法基礎(chǔ)知識(shí)n 矩陣向量乘積的并行算法矩陣向量乘積的并行算法n 矩陣矩陣乘積的并行算法矩陣矩陣乘積的并行算法n 矩陣的矩陣的 LU 分解并行算法分解并行算法n 下三角線性方程組的并行算法下三角線性方程組的并行算法37線性方程組直接解法線性方程組直接解法38線性方程組直接解法線性方程組直接解法39矩陣矩陣 LU 分解分解40矩陣矩陣 LU 分解分解41矩陣矩陣 LU 分解分解42矩陣矩陣 LU 分解分解43上機(jī)作業(yè)上機(jī)作業(yè)l 編寫(xiě)編寫(xiě)LU分解的并行程序，其中分解的并行程序，其中(), 1n nijijAaaij 1R44主要內(nèi)容主要內(nèi)容n 并行算法基礎(chǔ)知識(shí)并行算法基礎(chǔ)知識(shí)n 矩陣向量乘積的并行算法矩陣向量乘積的并行算法n 矩陣矩陣乘積的并行算法矩陣矩陣乘積的并行算法n 矩陣的矩陣的 LU 分解并行算法