并行处理课件

2.14 点对点通信本节借助图形/图象变换中的实例程序，引入点对点通信机制实现并行。例2.14.1在分辨率为SIZE*SIZE(SIZE为2的幂)的黑白带灰度的显示屏幕上：左上角为坐标原点，轴向下，轴向右；为白，为黑。用NUMNODES(亦为2的幂，且SIZE/16)个并行节点把现有的图象(位图表示)map0:SIZE-1,0:SIZE-1加以变换。主进程：for (I=0,row=0;INUMNODES;I+,row+=SIZE/NUMNODES)send(row,Pi);/*消息发送语句1，把开始行号告诉第i台处理机*/for (I=0;ISIZE*2;I+) recv(oldrow,oldcol,newvalue,Pany);/*消息接收语句2，从处理机接收变换后的新值*/temp_mapoldrowoldcol = newvalue;/*开辟临时存储，暂存变换后的值*/for (I=0;ISIZE;I+)for (j=0;jSIZE;j+)mapIj=temp_mapIj; /*快速更新画面*/从进程：recv(row,Pmaster); /*消息接收语句1，接收开始行号*/for (oldrow=row;oldrow(row+SIZE/NUMNODES);oldrow+)for (oldcol=0;oldcolSIZE;oldcol+)newrow=oldrow16*16;newcol=oldcol16*16; /* 是整除运算符*/newvalue=mapnewrownewcol;send (oldrow,oldcol,newvalue,Pmaster); /*消息发送语句2，把一个象素点的变换结果返回主进程*/程序中包含两个消息发送语句和两个消息接收语句，它们配成两对。第一对，主进程里的消息发送语句1 “send(row,Pi)”，把一个行号row发送給第i个子进程（或称“从进程”）pi。通过循环语句：for (I=0,row=0;INUMNODES;I+,row+=SIZE/NUMNODES)从0号进程起，一直到NUMNODES-1号进程止，NUMNODES个进程无一遗漏。而交給它们的row并不相同：每当i上调1，row皆要跳过SIZE/NUMNODES，实为分摊給一个进程的工作量。结合子进程里的循环语句：for (oldrow=row;oldrow(row+SIZE/NUMNODES);oldrow+)我们得知：屏幕被横向均分成NUMNODES份，每个进程承担由SIZE/NUMNODES个连行构成的一等份。而子进程里的消息接收语句1 “recv(row,Pmaster)”，则从主进程Pmaster那里获取一个行号作为起始行，计算它包含SIZE/NUMNODES个连行的那一份。第二对，子进程里的消息发送语句2 “send (oldrow,oldcol,newvalue, Pmaster);”，把一个由平面直角坐标标记的象素点，连带计算出的新图像值newvalue，向主进程Pmaster报告。通过双重循环语句：for (oldrow=row;oldrow(row+SIZE/NUMNODES);oldrow+)for (oldcol=0;oldcolSIZE;oldcol+)遍历该子进程的那一份。至于新值如何算出，则由双重循环体内的newrow=oldrow16*16;newcol=oldcol16*16; /* 是整除运算符*/newvalue=mapnewrownewcol;决定：把全屏等分为(SIZE/16)(SIZE/16)个1616的小正方形，任何一个象素点，无论其原来的图像值如何，都向它所在的小正方形左上角看齐，即以左上角原来的图像值mapoldrow16*16oldcol16*16作为它的新值newvalue。此即所谓的“马赛克”效应。程序中的临时存储temp_map，用来逐点收集新的图像值；待全屏新值到齐，集中地向显示缓冲区转移，以免变换过程的“不堪入目”。 设map的初值：mapij=(i+j)/(2*(SIZE-1)； 0i,jSIZE。于是全白点0与全黑点1，原图各拥有一个。变换后：全白点，16*16-1个；全黑点消失。 例2.14.2在分辨率为SIZE*SIZE(SIZE为2的幂)的显示屏幕上，用NUMNODES(亦为2的幂，且SIZE)个并行节点把现有的图象(位图表示)map0:SIZE-1,0:SIZE-1位移。主进程：for (I=0;ISIZE;I+)for (j=0;jSIZE;j+)temp_mapIj=1;/*start values are all black*/for (I=0;ISIZE*2;I+)/*for each pixel*/ recv(oldrow,oldcol,newrow,newcol,Pany)/*old point moves to new one */if !(newrow=SIZE).OR. (newcol=SIZE)temp_mapnewrownewcol=mapoldrowoldcol;for (I=0;ISIZE;I+)for (j=0;jSIZE;j+)mapIj=temp_mapIj; /*update bitmap after finishing the whole calculation*/从进程：for (oldrow=m_get_myid();oldrowSIZE;oldrow+= NUMNODES)for (oldcol=0;oldcolSIZE;oldcol+)newrow=oldrow+delta_x; /*shift in x direction*/newcol=oldcol+delta_y; /*shift in y direction*/send (oldrow,oldcol,newrow,newcol,Pmaster);跟前例不同，其中仅含一个“发送接收”对。为什么？因为无论申请了多少个子进程，实际又分配到多少个子进程，均约定第i个子进程就从第i行开始，然后每次跳过子进程总数NUMNODES。所以，尽管本例依然按行分割，但每个子进程加工的行不再连片。每当一个老的点计算出它的新位置后，立即借助发送语句：send (oldrow,oldcol,newrow,newcol,Pmaster);向主进程汇报，而主进程则借助接收语句：recv(oldrow,oldcol,newrow,newcol,Pany)；登记计算结果。由于本例的图形/图像变换是位移，产生出界问题。仅在新位置不出界，即：(newrow=SIZE).OR.(newcol=SIZE)为“假”的条件下，才会真正登记进“草稿纸”：temp_mapnewrownewcol=mapoldrowoldcol;跟前例一样，计算全部完成后从“草稿纸”集中写入显示缓存；跟前例又不一样，本例的“草稿纸”即temp_map，不仅避免画面杂乱无章，而且保护原始数据：一个点未被移走之前，不让别的点移入，以免该点的原信息丢失。因此，它对前例是可省的，对本例却是不可或缺的。2.15 并行程序设计从1945年起，当各类串行计算机和各种串行程序设计语言涌现在人们面前时，人们面临过串行程序设计的挑战。串行程序设计的困难携手应用领域的膨胀，导致软件危机如火山般喷发，逼迫人们耗费大量人力物力去探索程序设计的自动化。对此，人们记忆犹新。“前车之鉴，乃后车之师。”如今，当各类并行计算机和各种并行程序设计语言涌现在我们面前时，我们该如何去走跟串行相应的旅程呢？为了避免并行时代的软件危机，让我们借助对比法揭示并行与串行的实质差异。如图2.17所示，假定我们在用也许淡忘了的框图法编写串行的1280项A(1:1280)求和程序。例2.15.1 A(1:1280)串行求和 和数S清零 否 还有未加项吗？ 出口S=A(i)是 取下一项 加进S里 图2.17 串行求和框图其中最上面的那一框，实现为赋值语句：S = 0其余各框实现为循环语句：DO I = 1 , 1280S = S + A(I)ENDDO 不难想象，上述步骤本质上是翻译：从汉语翻译成FORTRAN语言。跟英语专家把莎士芘亚全集译成中文，或者汉语专家把中国四大名著译成英文雋然而异，此翻译过程基本不含创造性，分工为程序员的“简单”劳动。下面，让我们把它并行化。例2.15.2 A(1:1280) 在“银河-1”上并行求和S = 0DO I = 1 , 1280S = S + A(I) /* 忽略循环开关门的开销，共1+1280次运算 */ENDDO依据加法的结合律：( a + b ) + c = a + ( b + c )硬件的向量长度，乃系统一次运算的最大并行度。我们可以按照“银河-1”硬件的向量长度128，把这1280个加法运算切成10等份：先加A(1+128*0:128+128*0) 共128个再加A(1+128*1:128+128*1) 共128个 . . .再加A(1+128*8:128+128*8) 共128个再加A(1+128*9:128+128*9) 共128个 10排，每排128个，从而转换为二重循环：S = 0DO I = 0 , 9DO J = 1 , 128S = S + A(128*I+J) /* 仍然1+128*10次 */ENDDOENDDO再依据加法的交换律：( a + b ) + c = ( a + c ) + b颠倒循环次序:S = 0DO J = 1 , 128DO I = 0, 9S = S + A(128*I+J) /* 先竖加，后横加，次数未变 */ENDDOENDDO外层循环能够改造成向量并行形式：S = 0B(1:128) = 0DO I = 0, 9B(1:128) = B(1:128) + A(1+128*I:128+128*I)ENDDODO J = 1 , 128S = S + B(J) /* 12+128 = 140次 */ENDDO在向量长度128的“银河-1”上，速度提高9倍多。 为了展示并行中的智力，我们尚可深入地挖掘其并行的潜力。例2.15.3 A(1:1280)求和的并行效益最大化。以上我们取机器向量寄存器的长度128分排，由向量长度的最大化推测并行效益也会最大化。其实不然：由于最后的那个串行次数会随并行长度同时达到极值，一涨一消，效益有某种程度的相抵。于是，效益或许还有提高的空间：在缩小最后的那个串行次数，因而同时又减小了并行长度的情况下，程序的表现如何呢？记最后的那个串行次数亦即向量运算的长度为x , 1 x 128。于是，等分排数等于：y = (1280/x)“”为“向上取整”函数。程序变成：S = 0B(1:x) = 0DO I = 0, y-1B(1:x) = B(1:x) + A(1+x*I:x+x*I)ENDDODO J = 1 , xS = S + B(J)ENDDO 忽略循环开关门的开销，总的运算次数n等于：2+y+x = 2+x+(1280/x)不是一个解析函数，微积分的极值学说对它无用武之地。让我们回避非整除的诸多麻烦（比如扩张A、难求极值），令x递减地取2的幂：x = 128, n = 140x = 64, n = 86x = 32, n = 74x = 16, n = 98.推得A(1:1280)在分段无零头的限制下，在“银河-1”（对于硬件向量长度不小于32的机器，尽然）上最优的并行求和程序：S = 0B(1:32) = 0DO I = 0, 39B(1:32) = B(1:32) + A(1+32*I:32+32*I)ENDDODO J = 1 , 32S = S + B(J) ENDDO 较之串行，加快17倍多。 人是宇宙中最复杂的并行体（之一？）：当我们上班从事各行各业的活动时，我们的呼吸系统、消化系统、血液循环系统、排泄系统、，都在并行不悖地工作着。人体生理学