高性能矩陣乘法課件

2023/3/311

矩陣乘法

2023/3/312并行算法優(yōu)化研究相對于傳統(tǒng)面向?qū)ο蟠兴惴ǖ?個挑戰(zhàn)：同步：兩個或者多個線程協(xié)調(diào)其行為的過程通信：與線程之間交換數(shù)據(jù)相關的帶寬和延遲問題負載均衡：多個線程之間工作量分布的情況，給各個線程（執(zhí)行核）分配均勻的工作可擴展性：衡量在性能更加強勁的系統(tǒng)上運行軟件時能否有效利用更多線程的指標， 觀察應用程序在更高級的平臺上運行 4核到8核線性增長2023/3/313多線程（核）設計主要分解模式任務分解： 對程序根據(jù)其執(zhí)行的功能進行分解的過程數(shù)據(jù)分解： 將應用程序根據(jù)各任務所處理的數(shù)據(jù)而非按任務的天然特性來進行分解數(shù)據(jù)流分解： 研究數(shù)據(jù)在諸任務之間如何流動，根據(jù)任務之間的數(shù)據(jù)流關系對問題 進行分解模式分解方式任務級并行模式任務分解DivideandConquer任務/數(shù)據(jù)分解幾何分解模式數(shù)據(jù)分解流水線模式數(shù)據(jù)流分解波峰（wavefront）模式數(shù)據(jù)流分解2023/3/315矩陣乘法算法探討

在工程科學計算中，矩陣乘積是最基本的運算 典型的n階稠密方陣乘積算法的時間復雜度是O(n3)。 目前對大型矩陣乘積運算的處理主要是采用分治思想，將矩陣分布在多個節(jié)點上，但每個結(jié)點上的小矩陣仍要立方級乘法次數(shù)。 基于分之思想的兩種劃分策略：條形劃分和塊狀（棋盤）劃分的6種常見分布式矩陣乘法并行算法。

2023/3/316基于不同劃分策略的矩陣乘法算法探討

1、條形（stripedpartitioning）劃分的矩陣乘法并行算法

行條劃分 列條劃分兩兩組合：行列、行行、列列、列行2023/3/317基于不同劃分策略的矩陣乘法算法探討

2、塊狀劃分(checkerboardpartitioning)的矩陣乘法并行算法

稱為棋盤劃分Cannon

Objective

Computingthematrix-matrixmultiplicationonSMPSystem.UseblockcheckerboardpartitioningofthematricesandCannon'sAlgorithm.

AssumptionSizeofthesquarematricesp=q2andthesizeofsquarematricesAandBisevenlydivisiblebyq.

Itisassumedthatthenumberofblocksareequaltothenumberofprocessors.2023/3/319Cannon

Cannon'salgorithmisbasedoncartesianvirtualtopologyAandBaresquarematricesofsizenandCbetheoutput

matrix.Thesematricesaredivedintoblocksorsubmatricestoperformmatrix-matrixoperationsinparallelnxnmatrixAcanberegardedasqxqarrayofblocksAi,j(0<=i<q,0<=j<q)suchthateachblockisan(n/q)x(n/q)submatrixWeusep

processorstoimplementtheblockversionofmatrixmultiplicationinparallelbychoosingqasasquarerootof

p

andcomputeadistinctblockCi,joneachprocessor.2023/3/3110傳統(tǒng)并行

2023/3/3111傳統(tǒng)并行

ProcessPi,jinitiallystoreblockmatricesAi,jandBi,jandcomputesblockCi,jofresultmatrix.TocomputesubmatrixCi,j,weneedallsubmatrices,Ai,kand

Bk,j(0

<=k<q).Toacquirealltherequiredblocks,anall-to-allbroadcastofmatrixAi,j's

isperformedineachrowandsimilarlyineachcolumnofmatrixBi,j's.MPIcollectivecommunicationisusedtoperformthisoperations.2023/3/3113傳統(tǒng)并行

AfterPi,jacquires,Ai,0,Ai,1,Ai,2

,Ai,q-1andB0,j

,B1,j

,B2,j

,Bq-1,j

,itperformstheserialblockmatrixtomatrixmultiplicationandaccumulatesthepartialblock

matrixCi,jofmatrixC.ToobtaintheresultantproductmatrixC,processeswithrank0gathersalltheblockmatricesbyusingMPI_Gather

collectivecommunicationoperation.2023/3/3114Cannon

pprocessorsarrangedinqxqsquaregridofprocessorsandtheinputmatrices.AandBaredistributedamongtheprocessesincheckerboardfashion.ItresultsinconstructingpblockmatricesofAandB.Itusesonlypoint-to-pointcommunication

forcircularlyshiftingblocksofmatrixAandmatrixBamongpprocesses.

2023/3/3115Cannon-inital2023/3/3117Cannon-runningThealgorithmperformsthefollowingstepsineachstage:

1.MultiplytheblockofmatrixAandmatrixBandaddtheresultantmatrixtogettheblockmatrixC,whichisinitiallysettozero.

2.CircularlyshifttheblocksofmatrixAtoleftintherowsoftheprocessesandtheblocksofmatrixBupwardsinthecolumnsofthesquaregridofprocessesinawraparoundmanner.

2023/3/3118Cannon-running2023/3/3119書中Cannon-bug2023/3/3121

MPI_SendandMPI_Recvisnotusedforpoint-to-pointcommunicationbecauseifalltheprocessescallMPI_SendorMPI_Recv

indifferentorderthedeadlockedsituationmayarise.

Howtofix?指派一個緩沖區(qū)，使用MPI_Irecv/MPI_Isend非阻塞式通訊函數(shù)，MPI_wait.MPI_Sendrecv.

2023/3/3122Cannon-bug

死鎖的問題 問題來源于main_shift()這個函數(shù)中MPI函數(shù)的使用。在Cannon-mpi代碼的main_shift()模塊中，文獻中算法使用的是MPI的阻塞通信函數(shù):MPI_Send/MPI_Recv,這就使得Cannon算法在執(zhí)行循環(huán)左移和循環(huán)上移時，矩陣規(guī)模超過共享buff的容量時出現(xiàn)循環(huán)等待的死鎖狀況。 在曙光4000集群系統(tǒng)上，該算法的發(fā)生死鎖的矩陣下限規(guī)模是200×200的浮點型矩陣。2023/3/3123Cannon-bug原始（阻塞式）的main_shift模塊：

voidmain_shift() { … /*將分塊b左移位*/

MPI_Send(a,dl2,MPI_FLOAT,get_index(my_row,my_col-1, sp),1, MPI_COMM_WORLD);

MPI_Recv(a,dl2,MPI_FLOAT,get_index(my_row, my_col+1,sp),1, MPI_COMM_WORLD,&status); /*將分塊b上移位*/

MPI_Send(b,dl2,MPI_FLOAT,get_index(my_row-1,my_col, sp),1, MPI_COMM_WORLD);

MPI_Recv(b,dl2,MPI_FLOAT,get_index(my_row+1, my_col,sp),1, MPI_COMM_WORLD,&status);

}2023/3/3125Cannon-bugMPI_Irecv僅僅初始化接受操作,在與之對應的MPI_Wait函數(shù)的調(diào)用返回之前，將不能訪問bufferMPI_Irecv函數(shù)返回時，handle指向一個MPI_Request對象，它代表了一個已近初始化了的通信操作。這個函數(shù)并不返回一個指向MPI_Status對象的指針，因為實際的接受操作并未完成。MPI_Wait會一直阻塞，直至參數(shù)handle所關聯(lián)的操作完成，對發(fā)送來說，此時就可以向緩沖區(qū)寫入新的值。而對接收來 說，便可以從緩沖區(qū)讀取消息，而status所指向的MPI_Status對象包含了所接收消息的信息。新增加buf的目的就是防止在a還未發(fā)送出去的時候就recv內(nèi)容至a中導致信息的錯誤，只有在MPI_Wait返回以后，再調(diào)用mencpy將buf的內(nèi)容寫回a中，完成更新。2023/3/3126Cannon乘法mpi代碼主要模塊intget_index(introw,intcol,intsp)//處理器邏輯陣列坐標至rank號的轉(zhuǎn)換

voidrandom_A_B()//隨機生成矩陣A/Bvoidscatter_A_B() //rank=0的處理器向外分發(fā)A,B的相關塊voidinit_alignment()//矩陣A/B初始對齊

Voidmain_shift