Cannon乘法的MPI实现

1、并行算法实践要求学生在KD60实验平台上设计并行算法并实现。实验平台由一块处理板、一块监控板和一块背板等组成。处理板逻辑结构如图1所示。处理板承载4个处理单元，每个处理单元包括一个龙芯3号四核CPU2GBDDR2内存、RTL811阡兆以太网卡芯片、BIOSFlash申口收发芯片以及电源变换电路等。四个龙芯3号处理器通过HT总线实现互连。监控电路检测4个处理单元的状态，并实现对其控制。处埋单元1处理单兀2DDR泌存:HT监控电圈HT:HT1CPU3PCI|干兆以太网RTL8110SCUARTLFCBIOSi电母变换j处理单元3系统服务器图1处理板逻辑结构实验平台的系统软件以开源软件为主（见图2）

2、,具有兼容性强、易维护、易升级、易使用等特点。处理单元操作系统为DebianGNU/Linux无盘系统，采用稳定高效的2.6.27内核。网格文件系统映象远程监控系统要求选修并行算法实践同学在下面表1中选一个题目，（1）阐述基本原理（包括对算法改进和优化方法）；（2）根据KD60实验平台设计实验方法和步骤（包括主要调试过程要求拷屏）。（3）数据及结果分析：根据不同的实验内容，记录具体的实验数据或程序运行结果（要求拷屏）。实验数据量较大时，最好制成表格形式。附上程序功能、模块说明、完整源代码，源代码中尽量多带注释；（4）分析和总结：对程序与算法性能改进结论，总结和体会。表1并行算法实践题目序号题目

3、名称基本方法和内容要求1LU分解的OpenMP实现编写LU分解的OpenMP程序2KMP算法的OpenMP实现编写KMP算法的OpenMP程序3高斯消元法解线性方程组的OpenMP实现编写高斯消元法解线性方程组的OpenMP程序4高斯丫膈法解线性方程组的MPI实现编写高斯丫膈法解线性方程组的MPI程序5局斯-塞德尔迭代解线性方程组的MPI实现编写局斯-塞德尔迭代解线性方程组的MPI程序6Cannon乘法的MPI实现编写Cannon乘法的MPI程序7LU分解的MPI实现编写LU分解的MPI程序8随机串匹配算法的MPI实现编写随机串匹配算法的MPI程序9单源最短路径Dijkstra算法的MPI实现

4、编写单源最短路径Dijkstra算法的MPI程序10快速排序算法的MPI实现编写快速排序算法的MPI程序11KMP串匹配的MPI实现编写KMP串匹配算法的MPI程序图2软件系统结构Cannon乘法的MPI实现及性能分析摘要：cannon算法是矩阵的并行乘法，属于数值并行算法MPI编程实现一篇，其中关于数值并行算法MPI编程由于要处理的数据量巨大，程序循环次数多，对于串行而言，处理时间将非常长，将其并行化非常必要。本文将矩阵数据进行棋盘划分成多个子矩阵，再分别指派给多个处理器，使个处理器并行运算。关键字：cannon乘法并行计算数据划分、Cannon乘法的MPI实现基本原理Cannon乘法属于数

5、值并行算法MPI编程实现一篇，其中关于数值并行算法MPI编程由于要处理的数据量巨大，程序循环次数多，对于串行而言，处理时间将非常长，使其并行化的一般方法有：1）数据相关分析2）数据划分和处理器指派3）循环重构对原有程序并行化，首先要分析计算程序中所有语句间的依赖关系，这称之为相关分析。本项目Cannon乘法的mpi实现，是矩阵运算，阶往往都很高，而且行列之间数据依赖关系也不强，所以就对矩阵进行划分，然后指派给不同的处理器进行处理。最常用的矩阵划分有带状划分和块状划分。1. 带状划分方法带状划分又叫行列划分，就是将矩阵整行或整列地分成若干组，各组指派给一个处理器。也可以将若干行或列指派给一个处理

6、器，而且这些行和列可以是连续的，也可以是等间距的，前者称为块带状的，后者称为循环带状的。2, 块状划分方法块状划分又叫棋盘划分，就是将矩阵划分成若干个子矩阵，每个子矩阵指派给一个处理器，此时任意处理器均不含整行或整列。和带状划分类似，棋盘划分也可分为块棋盘划分和循环棋盘划分。棋盘划分比带状划分可开发更高的并行度，Cannon乘法的mpi实现也正是基于棋盘划分的并行实现。循环重构是指在数据分解之后，相应地将串行程序循环部分进行重构，以实现这种划分所确定的并行计算，主要方法有1）循环交换2）拉伸法3）分裂法4）轮转法5）并列法在三种程序并行化的方法中，数据相关分析和循环重构目的都是挖掘语句间的并行

7、性，而数据划分和处理器指派则重在策略，宏观上挖掘并行性。Cannon算法是一种存储有效的算法，设矩阵Ann和Bnn相乘。为了使两矩阵下标满足相乘的要求，和带状的并行分块乘法不同，不是仅仅让B矩阵的各列块循环移动，而是有目的地让A的各行块以及B的各列块皆施行循环移位，从而实现对C的子块的计算。将矩阵A和B分成p个方块Aij和Bij,（0i,jVp1）,每块大小为n/抒n/打，并将它们分配给币*0个处理器（P00,P01，.，P*弁1）。开始时处理器Pj存放块Aij和Bij,并pIpI负责计算块Cij,然后算法开始执行：将块Aj向左循环移动i步；将块Bij向上循环移动j步；Pij执行乘加运算后将块

8、Aij向左循环移动1步，块Bij向上循环移动1步；重复第步，总共执行卬次乘加运算和J?次块Aij和Bij的循环单步移位。二、Cannon乘法的MPI实现内容和步骤实验涉及内容主要有：数据划分和指派处理器最常用的矩阵数据划分有带状划分和块状划分。棋盘划分比带状划分可开发更高的并行度，Cannon乘法的mpi实现也正是基于棋盘划分的并行实现。设有P个处理器，将矩阵A和B分成p个方块Aij和Bij,(0i,j币1),每块大小为n/好n/抒，并将它们分配给m币个处理器(P00,P01,.,p而1jp1)子矩阵的循环移动处理器Pj存放块Aij和Bij,并负责计算块Cj,在使A矩阵的左右循环移动和B矩阵的

9、上下循环移动时，为了避免在通信过程中发生死锁，奇数号及偶数号处理器的收发顺序被错开，使偶数号处理器先发送后接收；而奇数号处理器先将子矩阵块存于缓冲区Buffer中，然后接收编号在其后面的处理器所发送的子矩阵块，最后再将缓冲区中子矩阵块发送给编号在其前面的处理器。基本算法如下：Beginif(j=0)then/*最左端的子块*/将所存的A的子块发送到同行最右端子块所在的处理器中接收其右邻处理器中发来的A的子块endifif(j=sqrt(p)-1)and(jmod2=0)then/*最右端子块处理器且块列号为偶数*/将所存的A的子块发送到其左邻处理器中接收其同行最左端子块所在的处理器发来的A的子

10、块endifif(j=sqrt(p)-1)and(jmod2乒0)then/*最右端子块处理器且块列号为奇数*/将所存的A的子块在缓冲区buffer中做备份接收其同行最左端子块所在的处理器发来的A的子块将在缓冲区buffer中所存的A的子块发送到其左邻处理器中endifif(j乒sqrt(p)-1)and(jmod2=0)and(j乒0)then/*其余的偶数号处理器*/将所存的A的子块发送到其左邻处理器中接收其右邻处理器中发来的A的子块endifif(j乒sqrt(p)-1)and(jmod2=1)and(j乒0)then/*其余的奇数号处理器*/将所存的A的子块在缓冲区buffer中做备份

11、接收其右邻处理器中发来的A的子块将在缓冲区buffer中所存的A的子块发送到其左邻处理器中endifEnd1)登陆KD-60FjEdSWUErnlhDJt!:*实验步骤login&31lABtIwiaiIte4m22;25;1719Ufen：111巨口岳二口=心13二衅=-|4|图KD-60登陆界面2)转至node80节点，上传程序输入命令：sshloongsonnode80和密码进入图界面loongsonfeiodeSDs|.|n|Xloginas:fcdOkd60192.168,150.218+spassword:ILastlogin:ThuJan1322:25:172011from192

12、.168.31.1B4HIrdGOlocalliQstJSloongsonQnodeBOHSB戒护姓C湍簸惧娘IkdOlocaliiQa-$aih1oQQ3DnuodeG0HloongsonSncKleBOspass-word:.diskless-files:Copyriqlit(Cl1999BrianMa/.HCopyrigh-t(C)1993-19SoftwareinthePublicInteiestftfosCofpEoycaosincludedwihGHU/LinuxsyHfreelyredlatributable;theexactdiatributicnteimjforeHarede

13、scribedinrhemdivj_dualfilesm/usr/doc/*/c0pyr3_HDebianGNU/LlnuxcoinervithABSOLUTELYKOWARRANTY,tothelperaittidbyapplicableLaw.H图转到节点80的界面再命令vim,进入vim编辑器加入程序，保存为1) 编译程序输入命令:mpiccpcannonTm在目录中查看，已成功。如下图.16S.iSO.SlSpassword:Last;loginjTliuJan1322:25:172Q11from192,10.31,10locaIhoat$loongsonfinodeB0ss戒护sic

14、g惧垠ykd60localhost$ashIc-ongsoiiSnodeSOloongsanfinodefiO1spaasword:disklesa-iJiiage-5ingLefiles:Copyright(C)1999ErianMay.CopyrightC)1993-1999SoftwareinEli蛙PublicInterestTaMostofthprogramsincludedwiththeDebianGNU/Linuxsyfreelyredistrlbutable;tb.eexactdiscriburicnTermsforearedescribedIntlieIndivldualfi

15、leaIn/list/doe/*/coprl.DebianGNU/LLullkcorneawithABSOLUTELYHOWARRANTYrtothepennittedtoyapplicablelaw.loongsonnodeSO:vimloongsonSnodeflO:*$Iscamiondataln.tJttgen_ped.cch_reul匚cannon.c-gausshost;pattern-datcc-gauss.cIhTlPwhocic,ugenpedkmp.cwhQ.c1oongison0nodes0:图将程序保存并编译后界面2) 运行程序输入：mpirunnp4cannon4，其

16、中第一个4是指定的处理器个数，第二个4是产生随机矩阵的维数，这两个参数在实验过程中可以调整，但要求第一个参数即处理器的个数必须是一个数的平方数。输出:13回区IlGQngBonnLOdLeSO:nszruz:-np./cannon4randminaxnxA:马q用何m每ttsnBO69?33S4?039?3iaoa191036070432111S731弓春日7732=1再SI&7172SCI31562264与g1?#与SCIfit1弓7西951571371101056D234012S株HEW445吞10A1506608649251904zaLndozLE:1076240640519902304

17、1993S132O21247&3702310T436402042fiS1922016/78374413C6042752237992962S4DbH4H11309187341773194301B2D254O3&e?0249tiMat:riwc=n*B:9n0170B,7a4A4703fil31iR43323527534565993-161767069903094-152305929631S13G5GD337G7G174O39449C83332i6?3l92.l&H-1bU.21-SOCMKoKIauais立冲(&)(根也查若0此通恒)隹蛤1.脚本信)工且心帮肌1凶盘辨GXJ日匾|0唱金|新痣V1

18、粉6192.1S615D|E3r9026059OT2240987932719&4404044823147136650!26590?200023406W9742S88S462G?8240127041509C7449907222712319GG468CMEM694421773354326745031511042471754303032999316!5221092TD49699330：66668P1SfiSI(53326361390082354DQS015567933530022078643845704S170496打?nRF38233011404823484D2377536a65027522245

19、82022964ST510016023962089671899CI60633S22550404619835031552226S467e8ti710S96SflT0421011825S36473759744024637772312711594003222001258434963492044822O0S9G7G0!671812S6704 224007638090B2017760220218246032105622520207154260099016095256223331220n32F5n773192867M002330754952027705111289E24536901273fid232082

20、2D5194072399213923432793330&2252124SO1735 961357228823SS45125502112033280233S50425d.3-d8S15424224358918fl1459816448203517045054409303042156529800742038152277G35S74C3191377317fl2303441148053O49Sr3E452SMdGggSSadTlDBTd1702JfllnflOSTl29227CB72102 247805718G1823692S228flQ751T344302Bilfl94fil2039690826547

21、72428800-i?1M-JjrTd-2328om751(18720200214077938881217S91A71F：TR口775431307958412342DT1346S1224857S21831Q732i9fiS421.5DSfc4758I8268777084217919263975520250181215317370595012441S210953881-40032901243 22240lB233483gOC2528D21230547420145079430423A56548S10232093(1418199710410fi2t58a4381184212172!G32508184

22、53501209-4BB434GT11421B80821341977800?111211135T5fi8222441EH1nFST2Tl3?RRn41537S1?n5O4T53fi435853232848WTid1e*rurirLinain1.7DE344ffecrorids11臼邙1|蛙jSurL命LuJid/B1:|5tXSsth?AB5-35e4.2024iJ*日。如l_inuM数字图四个处理器并行执行结果图史怦世J编辑查看世)选项也)佳输脚本工具Q帮助凹陌粕名I宅Q石每昼解，:ef，.品ILj1P?F168.)60,2184一SqcufoCRT:；|回胸|211385235723014

23、63112珈洲口23895Q84SS369308&9T2&25474S0953J002finfi324?343716E717O4PC|fi27M823M73Tfi3G4323722?37cn-jqnsciri5f5A337Q7l56223910fl33TlZl1715379220S94T240(300022546462191X95630775652915S4256SE95S22217OE10131223825180975676211223482607SG43S404?97224261tiDiyitjytjlDbdJbM4Z4&2&762&t；4IbeiUK1J1224413i54073bbiy

24、13rr?tiC2429UGbIl5SS7L9aS9SS42331150S037&5B152304022633S1101020079411&23S30SS95343400LiyiS4M2HJ13LI96LI48f2Ly621S：&y2822082J101ZJa2LeyJiKE546yy42124B223GSG01774Ei2S090444624428229B25B17961385623040405727714(3302336228734095530706075&482369398021579d0736DOO2521(328587312640163642217A4Y54(3O0L83S7353t

25、5?45477flS7B2040SJ64160?402T7T00?8495B87Ti3&(5243S9U35998481021096212103208&70210069-102lOB4372643487a6242502312480716D301122dlb647U63S921?S912Z41678D5S5B623D435712Z4g卵建副即驼8243eSD5527017a7S256562233407607012077024228T226T8SC196324EJC642hfi235fi7lfiR9nnH747?2M71nh32SR5RM3PMSS9R4臼5&6日日11%!53气9日2200895

26、4159903475072255146303130350549702034244445030091391262EE1113939-d8PS33filS3e2323657S1lSH72E528E7e22E?33AS32321TR1Q4.320251OdSSPl015193625145635533591091532a2133497022149B57501&2Z3T64B3654399697059S1223001273415157877632260032603330?5GS38E2fi234046202263407891942JJ4MZBZ4ti?M4iylcik)thenLeftmoveonest

27、ep(a)endif/*a循环左移至同行相邻处理器中*/if(jk)thenUpmoveonestep(b)endif/*b循环上移至同列相邻处理器中*/endforfori=0tom-1doforj=0tom-1doci,j=0endforendforfork=0top-1dofori=0tom-1doforj=0tom-1dofork1=0tom-1doci,j=ci,j+ai,k1*bk1,jendforendforendforLeftmoveonestep(a)/*子块a循环左移至同行相邻的处理器中*/Upmoveonestep(b)/*子块b循环上移至同列相邻的处理器中*/endfo

28、rEndLeftmoveonestep(a)见实验内容处附2.程序源码#include#include#include#include#include#include/*全局变量声明*/float*A,*B,*C;/*总矩阵,C=A*B*/float*a,*b,*c,*tmp_a,*tmp_b;/*a、b、c表分块，tmp_a、tmp_b表缓冲区*/intdg,dl,dl2,p,sp;/*dg:总矩阵维数;dl:矩阵块维数;dl2=dl*dl;p:处理器个数;sp=sqrt(p)*/intmy_rank,my_row,my_col;/*my_rank:处理器ID;(my_row,my_col)

29、:处理器逻辑阵列坐标*/MPI_Statusstatus;floatstarttime;floattimel;/* 函数名：get_index*功能：处理器逻辑阵列坐标至rank号的转换*输入：坐标、逻辑阵列维数*输出：rank号*/intget_index(introw,intcol,intsp)(return(row+sp)%sp)*sp+(col+sp)%sp;)/* 函数名：random_A_B*功能：随机生成矩阵A和B*/voidrandom_A_B()(inti,j;/*设随机数种子*/srand(unsignedint)time(NULL);/*随机生成A,B,并初始化C*/fo

30、r(i=0;idg;i+)for(j=0;jdg;j+)Aij=rand();Bij=rand();Cij=;/*函数名：scatter_A_B*功能：rank为0的处理器向其他处理器发送A、B矩阵的相关块*/voidscatter_A_B()inti,j,k,l;intp_imin,p_imax,p_jmin,p_jmax;for(k=0;kp;k+)/*计算相应处理器所分得的矩阵块在总矩阵中的坐标范围*/p_jmin=(k%sp)*dl;p_jmax=(k%sp+1)*dl-1;p_imin=(k-(k%sp)/sp*dl;p_imax=(k-(k%sp)/sp+1)*dl-1;l=0;/

31、*rank=0的处理器将A,B中的相应块拷至tmp_a,tmp_b，准备向其他处理器发送*/for(i=p_imin;i=p_imax;i+)for(j=p_jmin;j=p_jmax;j+)tmp_al=Aij;tmp_bl=Bij;l+;/*rank=0的处理器直接将自己对应的矩阵块从tmp_a,tmp_b拷至a,b*/if(k=0)memcpy(a,tmp_a,dl2*sizeof(float);memcpy(b,tmp_b,dl2*sizeof(float);)else/*rank=0的处理器向其他处理器发送tmp_a,tmp_b中相关的矩阵块*/MPI_Send(tmp_a,dl2,

32、MPI_FLOAT,k,1,MPI_COMM_WORLD);MPI_Send(tmp_b,dl2,MPI_FLOAT,k,2,MPI_COMM_WORLD);)/* 函数名：init_alignment*功能：矩阵A和B初始对准*/voidinit_alignment()/*将A中坐标为(i,j)的分块A(i,j)向左循环移动i步*/MPI_Sendrecv(a,dl2,MPI_FLOAT,get_index(my_row,my_col-my_row,sp),1,tmp_a,dl2,MPI_FLOAT,get_index(my_row,my_col+my_row,sp),1,MPI_COMM_

33、WORLD,&status);memcpy(a,tmp_a,dl2*sizeof(float);/*将B中坐标为(i,j)的分块B(i,j)向上循环移动j步*/MPI_Sendrecv(b,dl2,MPI_FLOAT,get_index(my_row-my_col,my_col,sp),1,tmp_b,dl2,MPI_FLOAT,get_index(my_row+my_col,my_col,sp),1,MPI_COMM_WORLD,&status);memcpy(b,tmp_b,dl2*sizeof(float);)/* 函数名：main_shift*功能：分块矩阵左移和上移，并计算分块c*/

34、voidmain_shift()inti,j,k,l;for(l=0;lsp;l+)/*矩阵块相乘，c+=a*b*/for(i=0;idl;i+)for(j=0;jdl;j+)for(k=0;kdl;k+)ci*dl+j+=ai*dl+k*bk*dl+j;/*将分块a左移1位*/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

35、上移1位*/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);/*函数名：collect_c*功能：rank为0的处理器从其余处理器收集分块矩阵c*/voidcollect_C()inti,j,i2,j2,k;intp_imin,p_imax,p_jmin,p_jmax;/*分块矩阵在总矩阵中顶点边界值*/*将rank为0的处理器中分块矩阵

36、c结果赋给总矩阵C对应位置*/for(i=0;idl;i+)for(j=0;jdl;j+)Cij=ci*dl+j;for(k=1;kp;k+)/*将rank为0的处理器从其他处理器接收相应的分块c*/MPI_Recv(c,dl2,MPI_FLOAT,k,1,MPI_COMM_WORLD,&status);p_jmin=(k%sp)*dl;p_jmax=(k%sp+1)*dl-1;p_imin=(k-(k%sp)/sp*dl;p_imax=(k-(k%sp)/sp+1)*dl-1;i2=0;/*将接收到的c拷至C中的相应位置，从而构造出C*/for(i=p_imin;i=p_imax;i+)j2

37、=0;for(j=p_jmin;j=p_jmax;j+)Cij=ci2*dl+j2;j2+;i2+;)/*函数名：print*功能：打印矩阵*输入：指向矩阵指针的指针，字符串*/voidprint(float*m,char*str)(inti,j；printf(%s,str);/*打印矩阵m*/for(i=0;idg;i+)(for(j=0;jdg;j+)printf(%15.0f,mij);printf(n);)printf(n);)/*函数名：main*功能：主过程，Cannon算法，矩阵相乘*输入：argc为命令行参数个数，argv为每个命令行参数组成的字符串数组*/intmain(in

38、targc,char*argv)(inti;MPI_Init(&argc,&argv);/*启动MPI计算*/MPI_Comm_size(MPI_COMM_WORLD,&p);/*确定处理器个数*/MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);/*确定各自的处理器标识符*/sp=sqrt(p);/*确保处理器个数是完全平方数，否则打印错误信息，程序退出*/if(sp*sp!=p)(if(my_rank=0)printf(Numberofprocessorsisnotaquadraticnumber!n);MPI_Finalize();exit(1);if(arg

39、c!=2)(if(my_rank=0)printf(usage:mpirun-npProcNumcannonMatrixDimensionn);MPI_Finalize();exit(1);)dg=atoi(argv1);/*总矩阵维数*/dl=dg/sp;/*计算分块矩阵维数*/dl2=dl*dl;/*计算处理器在逻辑阵列中的坐标*/my_col=my_rank%sp;my_row=(my_rank-my_col)/sp;/*为a、b、c分配空间*/a=(float*)malloc(dl2*sizeof(float);b=(float*)malloc(dl2*sizeof(float);c=

40、(float*)malloc(dl2*sizeof(float);/*初始化c*/for(i=0;idl2;i+)ci=;/*为tmp_a、tmp_b分配空间*/tmp_a=(float*)malloc(dl2*sizeof(float);tmp_b=(float*)malloc(dl2*sizeof(float);if(my_rank=0)(/*rank为。的处理器为A、B、C分配空间*/starttime=MPI_Wtime();A=(float*)malloc(dg*sizeof(float*);B=(float*)malloc(dg*sizeof(float*);C=(float*)m

41、alloc(dg*sizeof(float*);for(i=0;idg;i+)(Ai=(float*)malloc(dg*sizeof(float);Bi=(float*)malloc(dg*sizeof(float);Ci=(float*)malloc(dg*sizeof(float);)random_A_B();/*rank为0的处理器随机化生成A、B矩阵*/scatter_A_B();/*rank为0的处理器向其他处理器发送A、B矩阵的相关块*/)else/*rank不为0的处理器接收来自rank为0的处理器的相应矩阵分块*/(MPI_Recv(a,dl2,MPI_FLOAT,0,1,M

42、PI_COMM_WORLD,&status);MPI_Recv(b,dl2,MPI_FLOAT,0,2,MPI_COMM_WORLD,&status);)init_alignment();/*A、B矩阵的初始对准*/main_shift();/*分块矩阵左移、上移，cannon算法的主过程*/if(my_rank=0)(collect_C();/*rank为0的处理器从其余处理器收集分块矩阵c*/print(A,randommatrixA:n);/*打印矩阵A*/print(B,randommatrixB:n);/*打印矩阵B*/print(C,MatrixC=A*B:n);/*打印矩阵C*/

43、)else(MPI_Send(c,dl2,MPI_FLOAT,0,1,MPI_COMM_WORLD);/*rank不为。的处理器向rank为。的处理器发送矩阵块c*/)MPI_Barrier(MPI_COMM_WORLD);/*同步所有处理器*/if(my_rank=0)(time1=MPI_Wtime();printf(%s”,time1-starttime);/*运行时间*/)MPI_Finalize();/*结束MPI计算*/return0;)四、结果分析和总结由第三部分数据结果可以看出，多个处理器并行算法比单个处理器串行程序在计算大量数据时要快得多。分析如下：设Ann，Bnn相乘，结果

44、矩阵：G,jA,l*Bl,j,其中，i(1,2,.,n),j(1,2,.,n),ll(1,2,.,n)，记一次乘法和加法为一个运算时间单位，则这种情况下串行运行时间为Tn3个时间单位。在简单的带状划分中，A按行分为P块，则每块Ai是u*n大小，其中u=ceil(n/p);(i=0,P-1),B按列分为P块，则则每块Bj是n*v,其中v=ceil(n/p);(j=0,P-1);结果矩阵C进行行、列划分，得到P*P个大小为u*v的子矩阵。Ci,jABj,开始，各处理器存储内容如图(a)所示。此时各处理器并行计算处理器编号存储内容0AB01AiB12A2B2P-1AD-1Bp-1处理器编号存储内容0

45、A0B11A1B22AB3.P-1Ap-1Bq(a)(b)图矩阵相乘并行算法中的数据交换Ci,jABi,此后，第i号处理器将其所存储的B的列块送至第i-1号处理器(第0号送至第P-1号，形成循环传送)。它们再次执行Ci,jABj,其中j(i1)modP,B的列块在个处理器中以这样的方式循环传送P-1次，并做P次子矩阵相乘运算，就生成了结果矩阵C的所有子矩阵。编号为i的处理器存储了子矩阵Ci,0,Ci,1,.Ci,P1,为避免在通信过程发生死锁，奇数号及偶数号处理器的收发顺序被错开。偶数号处理器：先发送后接收；奇数号处理器：先将B的列块存于buffer中，再接收编号在其后面的处理器所发送的B的列块，最后将buffer中原矩阵B的列块发送给编号在其前面的处理器。处理时间