并行程序設(shè)計 中文課件 10 并行算法及性能分析

ParallelProgrammingInstructor:ZhangWeizhe(張偉哲)ComputerNetworkandInformationSecurityTechniqueResearchCenter,SchoolofComputerScienceandTechnology,HarbinInstituteofTechnologyCommunicationCostsinParallelComputers

并行計算機(jī)中的通信成本OutlineMatrix-VectorMultiplication矩陣向量乘法Matrix-MatrixMultiplication矩陣矩陣乘法MatixAlgorithms:IntroductionDuetotheirregularstructure,parallelcomputationsinvolvingmatricesandvectorsreadilylendthemselvestodata-decomposition.Typicalalgorithmsrelyoninput,output,orintermediatedatadecomposition.Mostalgorithmsuseone-andtwo-dimensionalblock,cyclic,andblock-cyclicpartitioning.MatixAlgorithms:Introduction由于它們的規(guī)則結(jié)構(gòu)，涉及矩陣和向量的并行計算容易使數(shù)據(jù)分解。典型的算法依賴于輸入，輸出或中間數(shù)據(jù)分解。大多數(shù)算法使用一維和二維塊，循環(huán)和塊循環(huán)分區(qū)。Matrix-VectorMultiplication6Matrix-VectorMultiplicationWeaimtomultiplyadensenxnmatrixAwithannx1vectorxtoyieldthenx1resultvectory.我們的目的是將密集的n×n矩陣A與n×1向量x相乘以產(chǎn)生n×1個結(jié)果向量y。Theserialalgorithmrequiresn2multiplications乘法andadditions加法.Matrix-VectorMultiplication:

Rowwise1-DPartitioningThenxnmatrixispartitionedamongnprocessors,witheachprocessorstoringcompleterowofthematrix.nxn矩陣在n個處理器之間分配，每個處理器存儲矩陣的完整行。Thenx1vectorxisdistributedsuchthateachprocessownsoneofitselements.nx1向量x被分布，使得每個進(jìn)程擁有其一個元素。Matrix-VectorMultiplication:

Rowwise1-DPartitioningMultiplicationofannxnmatrixwithannx1vectorusingrowwiseblock1-Dpartitioning.Fortheone-row-per-processcase,p=n.Matrix-VectorMultiplication:

Rowwise1-DPartitioningSinceeachprocessstartswithonlyoneelementofx,anall-to-allbroadcastisrequiredtodistributealltheelementstoalltheprocesses.由于每個進(jìn)程只以x的一個元素開始，因此需要一個全部廣播來將所有元素分發(fā)到所有進(jìn)程。ProcessPinowcomputes.Matrix-VectorMultiplication:

Rowwise1-DPartitioningConsidernowthecasewhenp<nandweuseblock1Dpartitioning.Eachprocessinitiallystoresn=pcompleterowsofthematrixandaportionofthevectorofsizen=p.Theall-to-allbroadcasttakesplaceamongpprocessesandinvolvesmessagesofsizen=p.Thisisfollowedbyn=plocaldotproducts.Thus,theparallelruntimeofthisprocedureisMatrix-VectorMultiplication:

Rowwise1-DPartitioning現(xiàn)在考慮p<n的情況，我們使用塊1D劃分。每個過程最初存儲矩陣的n=p個完整行和大小為n=p的向量的一部分。所有廣播都在p進(jìn)程之間進(jìn)行，并且涉及大小為n=p的消息。其次是n=p個本地點(diǎn)產(chǎn)品。因此，此過程的并行運(yùn)行時間為Matrix-VectorMultiplication:

2-DPartitioningThenxnmatrixispartitionedamongn2processorssuchthateachprocessorownsasingleelement.

n×n矩陣在n2個處理器之間劃分，使得每個處理器擁有單個元素。Thenx1vectorxisdistributedonlyinthelastcolumnofnprocessors.nx1向量x僅分布在n個處理器的最后一列中。Matrix-VectorMultiplication:2-DPartitioningMatrix-VectorMultiplication:

2-DPartitioningWemustfirstalignthevectorwiththematrixappropriately.Thefirstcommunicationstepforthe2-Dpartitioningalignsthevectorxalongtheprincipaldiagonalofthematrix.Thesecondstepcopiesthevectorelementsfromeachdiagonalprocesstoalltheprocessesinthecorrespondingcolumnusingnsimultaneousbroadcastsamongallprocessorsinthecolumn.Finally,theresultvectoriscomputedbyperforminganall-to-onereductionalongthecolumns.Matrix-VectorMultiplication:

2-DPartitioning我們必須首先將向量與矩陣適當(dāng)?shù)貙R。2-D分區(qū)的第一個通信步驟使向量x沿矩陣的主對角線對齊。第二步將向量元素從每個對角線進(jìn)程復(fù)制到相應(yīng)列中的所有進(jìn)程，使用列中所有處理器之間的n個同時廣播。最后，通過沿著列執(zhí)行一對一的減少來計算結(jié)果向量。Matrix-VectorMultiplication:

2-DPartitioningThreebasiccommunicationoperationsareusedinthisalgorithm:one-to-onecommunicationtoalignthevectoralongthemaindiagonal,one-to-allbroadcastofeachvectorelementamongthenprocessesofeachcolumnall-to-onereductionineachrow.Matrix-VectorMultiplication:

2-DPartitioning該算法使用三種基本的通信操作：一對一通信，沿著主對角線對齊向量，每列n個進(jìn)程中的每個向量元素的一對多廣播每行多對一。Matrix-VectorMultiplication:

2-DPartitioningWhenusingfewerthann2processors,eachprocessownsanblockofthematrix.Thevectorisdistributedinportionsofelementsinthelastprocess-columnonly.Inthiscase,themessagesizesforthealignment,broadcast,andreductionareallThecomputationisaproductofansubmatrixwithavectoroflength.Matrix-VectorMultiplication:

2-DPartitioning當(dāng)使用少于n2個處理器時，每個進(jìn)程擁有一個

矩陣塊。向量僅在最后一個進(jìn)程列中

的元素的部分分布。在這種情況下，

對齊，廣播和減少的消息大小都是計算是具有

長度向量的

子矩陣的乘積。Matrix-VectorMultiplication:

2-DPartitioningThefirstalignmentsteptakestimeThebroadcastandreductionstaketimeLocalmatrix-vectorproductstaketimeTotaltimeis

Example:CodeofMVSeeReference22OutlineMatrix-MatrixMultiplicationMatrix-MatrixMultiplication

Matrix-MatrixMultiplicationConsidertheproblemofmultiplyingtwonxndense,squarematricesAandBtoyieldtheproductmatrixC=AxB.TheserialcomplexityisO(n3).Ausefulconceptinthiscaseiscalledblockoperations.Inthisview,annxnmatrixAcanberegardedasaqxqarrayofblocksAi,j(0≤i,j<q)suchthateachblockisan(n/q)x(n/q)submatrix.Inthisview,weperformq3matrixmultiplications,eachinvolving(n/q)x(n/q)matrices.Matrix-MatrixMultiplication考慮將兩個n×n密集矩陣A和B相乘以產(chǎn)生乘積矩陣C=A×B的問題。串行復(fù)雜度為O（n3）。在這種情況下，一個有用的概念稱為塊操作。在該視圖中，n×n矩陣A可以被認(rèn)為是塊Ai，j（0≤i，j<q）的q×q陣列，使得每個塊是（n/q）×（n/q）子矩陣。在這種觀點(diǎn)中，我們執(zhí)行q3矩陣乘法，每個涉及（n/q）x（n/q）個矩陣。Matrix-MatrixMultiplicationConsidertwonxn

matricesAandBpartitionedintopblocksAi,jandBi,j(0≤i,j<

)ofsizeeach.ProcessPi,jinitiallystoresAi,jandBi,jandcomputesblockCi,joftheresultmatrix.ComputingsubmatrixCi,jrequiresallsubmatricesAi,kandBk,jfor0≤k<.All-to-allbroadcastblocksofAalongrowsandBalongcolumns.Performlocalsubmatrixmultiplication.Matrix-MatrixMultiplication考慮兩個n×n矩陣A和B分成p個

塊Ai，j和Bi，j（0≤i，j< ）。過程Pi，j首先存儲Ai，j和Bi，j并計算結(jié)果矩陣的塊Ci，j。計算子矩陣Ci，j要求所有子矩陣Ai，k和Bk，j為0≤k< 。沿著行的A的所有廣播塊，沿列的B。執(zhí)行局部子矩陣乘法。Matrix-MatrixMultiplicationThetwobroadcaststaketime

Thecomputationrequiresmultiplicationsof sizedsubmatrices.Theparallelruntimeisapproximately

Majordrawbackofthealgorithmisthatitisnotmemoryoptimal.算法的主要缺點(diǎn)是它不是內(nèi)存最優(yōu)的。Matrix-MatrixMultiplication:

Cannon'sAlgorithmInthisalgorithm,weschedulethecomputationsofthe processesoftheithrowsuchthat,atanygiventime,eachprocessisusingadifferentblockAi,k.TheseblockscanbesystematicallyrotatedamongtheprocessesaftereverysubmatrixmultiplicationsothateveryprocessgetsafreshAi,kaftereachrotation.Matrix-MatrixMultiplication:

Cannon'sAlgorithm在該算法中，我們調(diào)度第i行的

進(jìn)程的計算，使得在任何給定時間，每個進(jìn)程使用不同的塊Ai，k。在每個子矩陣乘法之后，這些塊可以在進(jìn)程之間系統(tǒng)地旋轉(zhuǎn)，使得每個進(jìn)程在每次旋轉(zhuǎn)之后都獲得新的Ai，k。Matrix-MatrixMultiplication:

Cannon'sAlgorithmMatrix-MatrixMultiplication:

Cannon'sAlgorithmPerformlocalblockmultiplication.EachblockofAmovesonestepleftandeachblockofBmovesonestepup(againwithwraparound).Performnextblockmultiplication,addtopartialresult,repeatuntilallblockshavebeenmultiplied.Matrix-MatrixMultiplication:

Cannon'sAlgorithm執(zhí)行本地塊乘法。A的每個塊移動一步，B的每個塊向上移動一次（再次繞過）。執(zhí)行下一個塊乘法，添加到部分結(jié)果，重復(fù)直到所有的

塊都被乘。Matrix-MatrixMultiplication:

Cannon'sAlgorithmInthealignmentstep,sincethemaximumdistanceoverwhichablockshiftsis,thetwoshiftoperationsrequireatotaloftime.Eachofthesingle-stepshiftsinthecompute-and-shiftphaseofthealgorithmtakestime.Thecomputationtimeformultiplyingmatricesofsize is.Theparalleltimeisapproximately:Matrix-MatrixMultiplication:

DNSAlgorithmUsesa3-Dpartitioning.Visualizethematrixmultiplicationalgorithmasacube.matricesAandBcomeintwoorthogonalfacesandresultCcomesouttheotherorthogonalface.Eachinternalnodeinthecuberepresentsasingleadd-multiplyoperation(andthusthecomplexity).DNSalgorithmpartitionsthiscubeusinga3-Dblockscheme.Matrix-MatrixMultiplication:

DNSAlgorithm使用3-D分區(qū)。將矩陣乘法算法可視化為立方體。矩陣A和B進(jìn)入兩個正交面，結(jié)果C出來另一個正交面。多維數(shù)據(jù)集中的每個內(nèi)部節(jié)點(diǎn)都表示單一的加乘操作（因此是復(fù)雜的）。DNS算法使用3-D塊方案分區(qū)此多維數(shù)據(jù)集。Matrix-MatrixMultiplication:

DNSAlgorithmAssumeannxnxnmeshofprocessors.MovethecolumnsofAandrowsofBandperformbroadcast.Eachprocessorcomputesasingleadd-multiply.ThisisfollowedbyanaccumulationalongtheCdimension.Sinceeachadd-multiplytakesconstanttimeandaccumulationandbroadcasttakeslogntime,thetotalruntimeislogn.Thisisnotcostoptimal.Itcanbemadecostoptimalbyusingn/lognprocessorsalongthedirectionofaccumulation.Matrix-MatrixMultiplication:

DNSAlgorithm假設(shè)一個nxnxn個網(wǎng)格的處理器。移動A列和B列，并執(zhí)行廣播。每個處理器計算單個加法乘法。其次是沿著C維度的積累。由于每個加乘乘以恒定時間，累加和廣播占用時間，因此總運(yùn)行時間為logn。這不是最佳的成本。通過沿著積累的方向使用n/logn個處理器可以使成本最優(yōu)。Matrix-MatrixMultiplication:

DNSAlgorithmMatrix-MatrixMultiplication:

DNSAlgorithm

Usingfewerthann3

processors.Assumethatthenumberofprocessespisequaltoq3forsomeq<n.Thetwomatricesarepartitionedintoblocksofsize(n/q)x(n/q).Eachmatrixcanthusberegardedasaqxqtwo-dimensionalsquarearrayofblocks.Thealgorithmfollowsfromthepreviousone,except,inthiscase,weoperateonblocksratherthanonindividualelements.Matrix-MatrixMultiplication:

DNSAlgorithm使用少于n3個處理器。假設(shè)某些q<n，進(jìn)程數(shù)p等于q3。將兩個矩陣劃分成大?。╪/q）×（n/q）的塊。因此，每個矩陣可以被認(rèn)為是塊的q×q二維正方形陣列。算法遵循前一個算法，除了在這種情況下，我們操作塊而不是單個元素。Matrix-MatrixMultiplication:

DNSAlgorithmUsingfewerthann3

processors.Thefirstone-to-onecommunicationstepisperformedforbothAandB,andtakestimeforeachmatrix.Thetwoone-to-allbroadcaststaketimeforeachmatrix.ThereductiontakestimeMultiplicationofsubmatricestakestime.Theparalleltimeisapproximatedby:

Example:CodeofMMSeeReference43BasicDefinitions基本定義Memory(M)—amountofstoragerequired(e.g.,words)forgivenproblem給定問題所需的存儲空間（例如單詞）Work(W)—numberofoperations(e.g.,flops)requiredforgivenproblem,includingloadsandstores給定問題所需的操作數(shù)（例如，翻牌），包括加載和存儲Velocity(V)—numberofoperationsperunittime(e.g.,flops/sec)performedbyoneprocessor由一個處理器執(zhí)行的每單位時間的操作數(shù)（例如，觸發(fā)器/秒）Time(T)—elapsedwall-clocktime(e.g.,secs)frombeginningtoendofcomputation從開始到結(jié)束計算的經(jīng)過的掛鐘時間（例如秒）Cost(C)—productofnumberofprocessorsandexecutiontime(e.g.,processor-seconds)處理器數(shù)量和執(zhí)行時間的乘積（例如處理器秒數(shù)）44BasicDefinitionsSubscriptindicatesnumberofprocessorsused(e.g.,T1isserialexecutio