高性能矩陣乘法課件

2023/3/311

矩陣乘法

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

在工程科學(xué)計(jì)算中，矩陣乘積是最基本的運(yùn)算 典型的n階稠密方陣乘積算法的時(shí)間復(fù)雜度是O(n3)。 目前對(duì)大型矩陣乘積運(yùn)算的處理主要是采用分治思想，將矩陣分布在多個(gè)節(jié)點(diǎn)上，但每個(gè)結(jié)點(diǎn)上的小矩陣仍要立方級(jí)乘法次數(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?指派一個(gè)緩沖區(qū)，使用MPI_Irecv/MPI_Isend非阻塞式通訊函數(shù)，MPI_wait.MPI_Sendrecv.

2023/3/3122Cannon-bug

死鎖的問題 問題來源于main_shift()這個(gè)函數(shù)中MPI函數(shù)的使用。在Cannon-mpi代碼的main_shift()模塊中，文獻(xiàn)中算法使用的是MPI的阻塞通信函數(shù):MPI_Send/MPI_Recv,這就使得Cannon算法在執(zhí)行循環(huán)左移和循環(huán)上移時(shí)，矩陣規(guī)模超過共享buff的容量時(shí)出現(xiàn)循環(huán)等待的死鎖狀況。 在曙光4000集群系統(tǒng)上，該算法的發(fā)生死鎖的矩陣下限規(guī)模是200×200的浮點(diǎn)型矩陣。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僅僅初始化接受操作,在與之對(duì)應(yīng)的MPI_Wait函數(shù)的調(diào)用返回之前，將不能訪問bufferMPI_Irecv函數(shù)返回時(shí)，handle指向一個(gè)MPI_Request對(duì)象，它代表了一個(gè)已近初始化了的通信操作。這個(gè)函數(shù)并不返回一個(gè)指向MPI_Status對(duì)象的指針，因?yàn)閷?shí)際的接受操作并未完成。MPI_Wait會(huì)一直阻塞，直至參數(shù)handle所關(guān)聯(lián)的操作完成，對(duì)發(fā)送來說，此時(shí)就可以向緩沖區(qū)寫入新的值。而對(duì)接收來 說，便可以從緩沖區(qū)讀取消息，而status所指向的MPI_Status對(duì)象包含了所接收消息的信息。新增加buf的目的就是防止在a還未發(fā)送出去的時(shí)候就recv內(nèi)容至a中導(dǎo)致信息的錯(cuò)誤，只有在MPI_Wait返回以后，再調(diào)用mencpy將buf的內(nèi)容寫回a中，完成更新。2023/3/3126Cannon乘法mpi代碼主要模塊intget_index(introw,intcol,intsp)//處理器邏輯陣列坐標(biāo)至rank號(hào)的轉(zhuǎn)換

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

Voidmain_shift