并行程序设计 中文课件 10 并行算法及性能分析

ParallelProgrammingInstructor:ZhangWeizhe(张伟哲)ComputerNetworkandInformationSecurityTechniqueResearchCenter,SchoolofComputerScienceandTechnology,HarbinInstituteofTechnologyCommunicationCostsinParallelComputers

并行计算机中的通信成本OutlineMatrix-VectorMultiplication矩阵向量乘法Matrix-MatrixMultiplication矩阵矩阵乘法MatixAlgorithms:IntroductionDuetotheirregularstructure,parallelcomputationsinvolvingmatricesandvectorsreadilylendthemselvestodata-decomposition.Typicalalgorithmsrelyoninput,output,orintermediatedatadecomposition.Mostalgorithmsuseone-andtwo-dimensionalblock,cyclic,andblock-cyclicpartitioning.MatixAlgorithms:Introduction由于它们的规则结构，涉及矩阵和向量的并行计算容易使数据分解。典型的算法依赖于输入，输出或中间数据分解。大多数算法使用一维和二维块，循环和块循环分区。Matrix-VectorMultiplication6Matrix-VectorMultiplicationWeaimtomultiplyadensenxnmatrixAwithannx1vectorxtoyieldthenx1resultvectory.我们的目的是将密集的n×n矩阵A与n×1向量x相乘以产生n×1个结果向量y。Theserialalgorithmrequiresn2multiplications乘法andadditions加法.Matrix-VectorMultiplication:

Rowwise1-DPartitioningThenxnmatrixispartitionedamongnprocessors,witheachprocessorstoringcompleterowofthematrix.nxn矩阵在n个处理器之间分配，每个处理器存储矩阵的完整行。Thenx1vectorxisdistributedsuchthateachprocessownsoneofitselements.nx1向量x被分布，使得每个进程拥有其一个元素。Matrix-VectorMultiplication:

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

Rowwise1-DPartitioningSinceeachprocessstartswithonlyoneelementofx,anall-to-allbroadcastisrequiredtodistributealltheelementstoalltheprocesses.由于每个进程只以x的一个元素开始，因此需要一个全部广播来将所有元素分发到所有进程。ProcessPinowcomputes.Matrix-VectorMultiplication:

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

Rowwise1-DPartitioning现在考虑p<n的情况，我们使用块1D划分。每个过程最初存储矩阵的n=p个完整行和大小为n=p的向量的一部分。所有广播都在p进程之间进行，并且涉及大小为n=p的消息。其次是n=p个本地点产品。因此，此过程的并行运行时间为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我们必须首先将向量与矩阵适当地对齐。2-D分区的第一个通信步骤使向量x沿矩阵的主对角线对齐。第二步将向量元素从每个对角线进程复制到相应列中的所有进程，使用列中所有处理器之间的n个同时广播。最后，通过沿着列执行一对一的减少来计算结果向量。Matrix-VectorMultiplication:

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

2-DPartitioning该算法使用三种基本的通信操作：一对一通信，沿着主对角线对齐向量，每列n个进程中的每个向量元素的一对多广播每行多对一。Matrix-VectorMultiplication:

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

2-DPartitioning当使用少于n2个处理器时，每个进程拥有一个

矩阵块。向量仅在最后一个进程列中

的元素的部分分布。在这种情况下，

对齐，广播和减少的消息大小都是计算是具有

长度向量的

子矩阵的乘积。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相乘以产生乘积矩阵C=A×B的问题。串行复杂度为O（n3）。在这种情况下，一个有用的概念称为块操作。在该视图中，n×n矩阵A可以被认为是块Ai，j（0≤i，j<q）的q×q阵列，使得每个块是（n/q）×（n/q）子矩阵。在这种观点中，我们执行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并计算结果矩阵的块Ci，j。计算子矩阵Ci，j要求所有子矩阵Ai，k和Bk，j为0≤k< 。沿着行的A的所有广播块，沿列的B。执行局部子矩阵乘法。Matrix-MatrixMultiplicationThetwobroadcaststaketime

Thecomputationrequiresmultiplicationsof sizedsubmatrices.Theparallelruntimeisapproximately

Majordrawbackofthealgorithmisthatitisnotmemoryoptimal.算法的主要缺点是它不是内存最优的。Matrix-MatrixMultiplication:

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

Cannon'sAlgorithm在该算法中，我们调度第i行的

进程的计算，使得在任何给定时间，每个进程使用不同的块Ai，k。在每个子矩阵乘法之后，这些块可以在进程之间系统地旋转，使得每个进程在每次旋转之后都获得新的Ai，k。Matrix-MatrixMultiplication:

Cannon'sAlgorithmMatrix-MatrixMultiplication:

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

Cannon'sAlgorithm执行本地块乘法。A的每个块移动一步，B的每个块向上移动一次（再次绕过）。执行下一个块乘法，添加到部分结果，重复直到所有的

块都被乘。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分区。将矩阵乘法算法可视化为立方体。矩阵A和B进入两个正交面，结果C出来另一个正交面。多维数据集中的每个内部节点都表示单一的加乘操作（因此是复杂的）。DNS算法使用3-D块方案分区此多维数据集。Matrix-MatrixMultiplication:

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

DNSAlgorithm假设一个nxnxn个网格的处理器。移动A列和B列，并执行广播。每个处理器计算单个加法乘法。其次是沿着C维度的积累。由于每个加乘乘以恒定时间，累加和广播占用时间，因此总运行时间为logn。这不是最佳的成本。通过沿着积累的方向使用n/logn个处理器可以使成本最优。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个处理器。假设某些q<n，进程数p等于q3。将两个矩阵划分成大小（n/q）×（n/q）的块。因此，每个矩阵可以被认为是块的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给定问题所需的操作数（例如，翻牌），包括加载和存储Velocity(V)—numberofoperationsperunittime(e.g.,flops/sec)performedbyoneprocessor由一个处理器执行的每单位时间的操作数（例如，触发器/秒）Time(T)—elapsedwall-clocktime(e.g.,secs)frombeginningtoendofcomputation从开始到结束计算的经过的挂钟时间（例如秒）Cost(C)—productofnumberofprocessorsandexecutiontime(e.g.,processor-seconds)处理器数量和执行时间的乘积（例如处理器秒数）44BasicDefinitionsSubscriptindicatesnumberofprocessorsused(e.g.,T1isserialexecutio