2009并行计算与多核程序设计03-04并行计算基础

1、1陈天洲，施青松，胡威tzchen, zjsqs, 2009年11月27日，玉泉校区曹西101浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 一、程序执行的并行性一、程序执行的并行性p指令内部并行：微操作并行p指令间并行：多条指令并行p任务或进程间并行：任务作并行性分解p作业或程序间并行：资源的并行性分配算法p二、数据处理的并行性二、数据处理的并行性p位串字串：一次只对

2、一个字的一位进行处理无并行无并行 p位并字串：一次对多个字的一位进行处理W=1，B1p位串字并：一次对一个字的多位进行处理W1，B=1p位并字并：一次对许多字的多位进行处理W 1，B 1三、三、操作并行性的层次操作并行性的层次p存储器操作并行：在一个存贮周期内访问多个存贮单元p处理器操作步骤并行：指令执行子操作重叠p处理器操作并行：多处理单元(多核)，在同一控制器控制下按同一条指令对多个数据组同时操作（多SIMD核）并行度增加通信与调度开销增加硬件实现的比例增加浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 江江 大大 学学 软软 硬硬 件件 协

3、协 同同 设设 计计 实实 验验 室室http:/ Degree）：射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。n网络直径（Network Diameter）： 网络中任何两个节点之间的最长距离，即最大路径数。n对剖宽度（Bisection Width） ：对分网络各半所必须移去的最少边数n对剖带宽（ Bisection Bandwidth）:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数n如果从任一节点观看网络都一样，则称为对称的（Symmetry） 浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 江江

4、 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ Linear Arrayn并行机中最简单、最基本的互连方式，n每个节点只与其左、右近邻相连，也叫二近邻连接，nN个节点用N-1条边串接之，内节点度为2，直径为N-1，对剖宽度为1n当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为2，直径或为 （双向环）或为N-1（单向环），对剖宽度为2 浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ Mesh）n每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为4，网络

5、直径为 2N-1，对剖宽度为N n在垂直方向上带环绕，水平方向呈蛇状，就变成Illiac网孔了，节点度恒为4，网络直径为N-1，而对剖宽度为2N n垂直和水平方向均带环绕，则变成了2-D环绕（2-D Torus），节点度恒为4，网络直径为2N/2，对剖宽度为2N(a)2-D网孔(b)Illiac网孔(c)2-D环绕浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ n如果尽量增大节点度为，则直径缩小为2，此时就变成了星形网络，其对剖宽度为n传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。浙浙 江江 大大 学学 软软 硬硬 件

6、件 协协 同同 设设 计计 实实 验验 室室http:/ n一个n-立方由N=2n 个顶点组成，3-立方如图(a)所示；4-立方如图(b)所示，由两个3-立方的对应顶点连接而成。nn-立方的节点度为n，网络直径也是n ，而对剖宽度为N/2。n如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示的3-立方环，此时每个顶点的度为3，而不像超立方那样节点度为n。(b)4-立 方(a)3-立 方(c)顶 点 代 之 以 环(d)3-立 方 环浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ n多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换

7、、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等L MI O C本 地 总 线高 速 缓 存C P UI FI FI F存 储 器 总 线存 储 器 单 元I FI FC P U 板存 储 器 板I / O 板通 信 板系 统 总 线( 底 板 上 )数 据 总 线缓 冲C CI O P数 据 总 线网 络( 以 太 网 等 )磁 盘 和 磁 带部 件打 印 机或 绘 图 仪本 地 外 围 设 备( S C S I 总 线 )M CI F缓 冲浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 江江 大大 学学 软软 硬硬 件件 协协

8、同同 设设 计计 实实 验验 室室http:/ Interconnection Network） 0101010101010101(a)4种可能的开关连接000001010011100101110111输入000001010011100101110111输出第0级第1级第2级(b)一种8输入的Omega网络浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ network）n内存 （memory）内存模块与节点分离内存模块位于节点内部浙浙 江江 大大 学学 软软

9、 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ (Single Instruction Single Data) -UniprocessorspMISD (Multiple Instruction Single Data)n?; multiple processors on a single data streampSIMD (Single Instruction Multiple Data)nExamples: pconnection machine 2：65535个 1bit processors; pIlliac IV： 64个 64bit processors; n

10、Ad: Simple programming model; Low overhead;Flexibility;All custom integrated circuitsn(Phrase reused by Intel marketing for media instructions vector)pMIMD (Multiple Instruction Multiple Data)nExamples: Sun Enterprise 5000, Cray T3D, SGI OriginnAd: Flexible; Use off-the-shelf micros; nMultiprocessor

11、s, MulticomputerspMIMD current winner: Concentrate on major design emphasis = 128 processor MIMD machines浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ on organization of main memorynShared vs. DistributedpAppearance of memory to hardwarenQ1: Memory acce

12、ss latency uniform?nShared (UMA): yes, doesnt matter where data goesnDistributed (NUMA): no, makes a big differencepAppearance of memory to softwarenQ2: Can processors communicate directly via memory?nShared (shared memory): yes, communicate via load/storenDistributed (message passing): no, communic

13、ate via messagespDimensions are orthogonalne.g. DSM: (physically) distributed, (logically) shared memory浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ Centralized Shared-Memory Architecture Main memoryI/O 系统ProcessorOne ormore levelsof cacheProcessorOne ormore levelsof cacheProcessorOne ormore leve

14、lsof cacheProcessorOne ormore levelsof cache总线结构总线结构SMP浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ of distributed-memory multiprocessor互连网络互连网络浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ Core Micro-architecture CPU1Memory CPU2Cache LineFront Side Bus (FSB)L2 is shared:No need to ship cache l

15、ine浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 架构核心的3.2 GHz Cell处理器，包括8个协同处理器(SPE)，除1个SPE保留用做其它用途，其余7个SPE均以3.2 GHz频率运做，内建512 KB二级缓存，浮点性能最高可达218 GFLOPS 浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ shared memory（DSM or scalable shared memory)n统一的逻辑地址空间，但物理空间是分布的统一的逻辑地址空间，但物理空间是分布的n每个处理器可以通过逻辑每个

16、处理器可以通过逻辑nShared memory means sharing the address space, which is different from centralized shared memory.pmultiple computers n Address space consists of multiple private address spaces。逻辑上不连续，远程处理器无法访问。n每一结点（processor-memory）模块是一单独的计算机，故称为多计算机结构。nNOW计划，每一结点实质上是一工作站或PC，由LAN连接而成。浙浙 江江 大大 学学 软软 硬硬 件件

17、 协协 同同 设设 计计 实实 验验 室室http:/ 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ UnitInterconnection NetworkPLMPLMPLMPLMShared Memory浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ （Exclusive-Read and Exclusive-Write），不允许同时读和同时写nPRAM-CREW （Concurrent-Read and Exc

18、lusive-Write） ，允许同时读但不允许同时写nPRAM-CRCW （Concurrent-Read and Concurrent-Write） ，允许同时读和同时写浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ CRCWCREWEREWTTT)log()log(pTOpTOTCRCWCREWEREW浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ Barrier）p需在并行程序中显式地加入同步路栅栏同步

19、各进程n一条指令可在非确定但有限的时间内完成。pAPRAM模型中有四类指令:n全局读：将全局存储单元中的内容读入本地存储器单元中n局部操作：对本地存储器中的数执行操作，其结果存入本地存储器中n全局写：将本地存储器单元中的内容写入全本地存储器单元中n同步：在程序的某一个逻辑点进程同步，在该点各处理器均需等待别的处理器到达后才能继续执行其局部程序浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 设局部操作为单位时间；全局读/写平均时间为d，d随着处理器数目的增加而

20、增加；同步路障时间为B=B(p)满足关系 ； 或 设tph 为全局各处理器执行时间最长者，则APRAM上的计算时间为 优缺点n易编程和分析算法的复杂度，但与现实相差较远n其上并行算法非常有限，也不适合MIMD-DM模型。)log()(pdOpBB)log/log(dpdO同步障次数BtTphpBd2浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ p模型参数np：处理器数(带有存储器)nl：同步障时间(Barrier synchronization time)ng：带宽因子(time steps/packet)=1/bandwidth 浙浙 江江

21、大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 强调了计算和通讯的分离， 提供了一个编程环境，易于 程序复杂性分析。但需要显 式同步机制，限制至多h条 消息的传递等。浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ Overheadng: GapnP:ProcessorpC3（Computation, Communication, Congestion）模型是一个与体系结构无关的粗粒度的并行计算模型，旨在能反映计算复杂度，通信模式和通信期间潜在的拥挤等因素对粗粒度网络算法的影响。浙浙 江江 大大 学学 软软 硬硬

22、 件件 协协 同同 设设 计计 实实 验验 室室http:/ 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ PVMOpenMPHPF可移植性所有主流并行计算机SMP, DSMSMP, DSM, MPP并行粒度进程级大粒度线程级细粒度进程级细粒度并行操作方式异步异步松散同步数据存储模式分布式存储共享存储共享存储数据分配方式显式隐式半隐式学习入门难度较难容易偏易可扩展性好较差一般浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室htt

23、p:/ Collector)，程序员可不对变量范围的开放负责任等05 package main07 import fmt “fmt” / Package implementing formatted I/O.09 func main() 10 fmt.Printf(”Hello, world; or ; or 世界n”);11 浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ Studio 2008nC#语法n面向角色（actor）和域（domain）n支持隔离、actor和消息传递n非面向对象p拥有对象概念，但不能自定义类p主要元素是域n域是一个

24、资源仓库n是数据、代理和函数的集合n域与域之间是相互隔离n域中的代理可以共享域中的数据n代理之间通过信道（Channel）来交换消息domain A int i;int func(int k)writer agent X: Channel1 reader agent Y: Channel2domain B int j;agent Z: Channel1 浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ Building Blocks 2.0 (TBB)模板库，开源n在程序员和处理器之间插入一个稳定的硬件抽象层n核的数量可以变化n自动向量化过程n自动

25、线程最优化n有编译器的影子，可以认为是Intel的多核编译器p各种专业库n多媒体IPP库，数学MKL库等p各种调优工具以及parallel studio浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ pjava.util.concurrent包n提供了大量线程和锁之上的并发抽象，比如线程池、闭锁、信号量、关卡等浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 与目标机无关的优化，通常是在中间代码上进行的优化。p与机器有关的优化：多核优化 充分利用系统资源（指令系统，寄存器资源浙浙 江江 大大 学学 软

26、软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 间进行均匀的分配，使得达到高的加速系数nNP完全性问题，只有近似算法p动态负载平衡n在程序的运行过程中来进行任务的分配达到负载平衡n操作系统的调度策略浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ Vectorization）: 把标量程序中的由一种可向量化循环完成的操作变换成向量操作。n代码并行化（Code Parallelization）:并行代码的优化是将一个程序展开成多线程以同时供

27、多台处理机并行执行，其目的是要减少总的执行时间。p代码生成n并行代码生成（Code Generation）涉及到将优化后的中间形式的代码转换程可执行的具体的机器目标代码。包括执行次序、指令选择、寄存器分配、负载平衡、并行粒度、代码调度以及后优化（Postoptimization）等问题。浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ studio浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ p事务内存技术浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/

28、 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ mod p表示i对i取模运算。p通常采用的是矩阵在处理机阵列按卷帘方式存放。设分块矩阵是88，处理机阵列是32，则矩阵的存放方式如下：00010203040506071011121314151617202122232425262730313233343536374041424344454647505152535455565760616263646566677071727374757677aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

29、aaaaa浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 11 , 10, 11, 11 , 10, 11, 01 , 00, 01, 11 , 10, 11, 11 , 10, 11, 01 , 00, 01, 11 , 10, 11, 11 , 10, 11, 01 , 00, 0,)()()(nnnnnnnnnnnnnnnnnnnnijnnijnnijbbbbbbbbbaaaaaaaaacccccccccBACcCbBaA设jiABC10nkkjikijbac浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室

30、http:/ I = 1, MDO J = 1, LDO K = 1, NC（I,J） = C（I,J） + A（I,K） * B（K,J）ENDDOENDDOENDDO串行矩阵乘积子程序（j-k-i形式）DO J = 1, LDO K = 1, NDO I = 1, MC（I,J） = C（I,J） + A（I,K） * B（K,J）ENDDOENDDOENDDO浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 江江 大大 学学 软软 硬硬 件件 协协 同同

31、 设设 计计 实实 验验 室室http:/ ,Bj存放在Pi中(j=0,1,2,p-1) Ci,j的计算是按对角线进行的 p个处理机，一维结构,每次每个处理机计算出一个Ci,j计算C需要p次来完成。011011,TTTTppAAAABBBB,()()i jijCCABTT浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ P1P2.Pp-1Ci.j = Ci.j =Ai BjAB子阵对应元素相乘Ci,j的计算是按对角线进行的BjAiaaaaaaaaaaaaaaaapppppppp1, 12, 11 , 10, 11,22,21 ,20,21, 12,

32、 11 , 10, 11,02,01 ,00,0.bbbbbbbbbbbbbbbbpppppppp1, 12, 11 , 10, 11,22,21 ,20,21, 12, 11 , 10, 11,02,01 ,00,0.cacccccccccccccccccppppppppp2, 11 , 10, 11, 11 ,20,20, 11, 11,04,23,22,23, 12, 11 , 12, 12,01 ,00,0.浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ mod p; mml=(myid-1) mod p;For i=0 to p-1 d

33、ol=(i+myid) mod pCi,l=Ai,lBi,j if (i!=p-1) then send(B,mml) recv(B,mpl)Endfor设：l为列下标Ci.j = Cmyid.l =Amyid BlP0a00a01a02 a03b00b10b20b30P1a10a11a12 a13b01b11b21b31P2a20a21a22 a23b02b12b22b32P3a30a31a32 a33b03b13b23b33浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 11 ,33,00,32,33,22,22,22, 11 ,22,00,

34、21 ,33, 11 ,22, 11 , 11 , 11 ,00, 10,33,00,22,00, 11 ,00,00,0P0a00a01a02 a03b00b10b20b30P1a10a11a12 a13b01b11b21b31P2a20a21a22 a23b02b12b22b32P3a30a31a32 a33b03b13b23b33v对应行列子块元素相乘求和vCi.j呈对角线位置v子矩阵B垂直循环传送给相邻P,垂直滚动v发送地址：mml=myid-1 mod pv接收地址：mpl=myid+1 mod pcccc3,32,21 , 10,0浙浙 江江 大大 学学 软软 硬硬 件件 协协 同

35、同 设设 计计 实实 验验 室室http:/ a03b01b11b21b31P1a10a11a12 a13b02b12b22b32P2a20a21a22 a23b03b13b23b33P3a30a31a32 a33b00b10b20b30babababababababababababababababa0,33,30,22,30, 11 ,30,00,33,33,23,22,23, 11 ,23,00,22,33, 12,22, 12, 11 , 12,00, 11 ,33,01 ,22,01 , 11 ,01 ,00,0cccccccc0,33,33,22,22, 11 , 11 ,00,0v

36、对应行列子块元素相乘求和vCi.j呈对角线位置v子矩阵B垂直循环传送给相邻P,垂直滚动v发送地址：mml=myid-1 mod pv接收地址：mpl=myid+1 mod p浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ a03b02b12b22b32P1a10a11a12 a13b03b13b23b33P2a20a21a22 a23b00b10b20b30P3a30a31a32 a33b01b11b21b31babababababababababababababababa1 ,33,31 ,22,31 , 11 ,31 ,00,30,33,20

37、,22,20, 11 ,20,00,23,33, 13,22, 13, 11 , 13,00, 12,33,02,22,02, 11 ,02,00,0cccccccccccc1 ,30,33,30,23,22,23, 12, 11 , 12,01 ,00,0v对应行列子块元素相乘求和vCi.j呈对角线位置v子矩阵B垂直循环传送给相邻P,垂直滚动v发送地址：mml=myid-1 mod pv接收地址：mpl=myid+1 mod p浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ a03b03b13b23b33P1a10a11a12 a13b00b1

38、0b20b30P2a20a21a22 a23b01b11b21b31P3a30a31a32 a33b02b12b22b32babababababababababababababababa2,33,32,22,32, 11 ,32,00,31 ,33,21 ,22,21 , 11 ,21 ,00,20,33, 10,22, 10, 11 , 10,00, 13,33,03,22,03, 11 ,03,00,0cccccccccccccccc2,31 ,30,33,31 ,20,23,22,20, 13, 12, 11 , 13,02,01 ,00,0cccccccccccccccc3,32,31

39、 ,30,33,22,21 ,20,23, 12, 11 , 10, 13,02,01 ,00,0v对应行列子块元素相乘求和vCi.j呈对角线位置v子矩阵B垂直循环传送给相邻P,垂直滚动v发送地址：mml=myid-1 mod pv接收地址：mpl=myid+1 mod p浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ jjjCABA BTTTTTTpTTBBBB110.TTpTTAAAA110.数据结构：Ci,j和Ai ,Bj存放在Pi中(j=0,1,2,p-1) Ci,j的计算是按对角线进行的 p个处理机，一维结构, 每次每个处理机计算出Ci

40、的部分积,采用乘累加 计算C需要p次来完成。浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 12, 11 , 10, 11,22,21 ,20,21, 12, 11 , 10, 11,02,01 ,00,0.bbbbbbbbbbbbbbbbpppppppp1, 12, 11 , 10, 11,22,21 ,20,21, 12, 11 , 10, 11,02,01 ,00,0.1,01 ,00,01, 11,1, 11 ,1,00,1 , 11,1 , 11 ,1 ,00,0, 11,0, 11 ,0,00,1, 11 , 10, 11,1, 11

41、 , 10, 11 ,1,01 ,00,00,11,11 ,00,1101,1 ,0,10,.,.,.,.ppppipipippiiippiiipppppipipippiiippiiipjjjiiicccbabababababababababbbabbbabbbaBaBaBaBBBaaaBABAC浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ P1P2.Pp-1BjAiaaaaaaaaaaaaaaaapppppppp1, 12, 11 , 10, 11,22,21 ,20,21, 12, 11 , 10, 11,02,01 ,00,0.bbbbb

42、bbbbbbbbbbbpppppppp1, 12, 11 , 10, 11,22,21 ,20,21, 12, 11 , 10, 11,02,01 ,00,0.ccccccccccccccccppppppp1, 12, 11 , 10, 14,22,21 ,20,21, 12, 11 , 10, 12, 12,01 ,00,0.P0a00a01a02 a03b00b01b01b03P1a10a11a12 a13b10b11b12b13P2a20a21a22 a23b20b21b22b23P3a30a31a32 a33b30b31b32b33浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同

43、设设 计计 实实 验验 室室http:/ (myid+1) mod p; mm1= (myid1) mod p;for i = 0 to p-1 dol = （i + myid） mod pC=C+Amyid ,lBlif (i != p-1) then send(B,mm1) recv(B,mp1)endfor设：l为行下标Ci.j = Cmyid.l =Amyid,lBl,jj=0,1,2.p-1P0a00a01a02 a03b00b01b02b03P1a10a11a12 a13b10b11b12b13P2a20a21a22 a23b20b21b22b23P3a30a31a32 a33b3

44、0b31b32b33浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ mod pv接收地址：mpl=myid+1 mod pbabababababababababababababababa3,30,32,30,31 ,30,30,30,33,20,22,20,21 ,20,20,20,23,10,12,10,11 ,10,10,10,13,00,02,00,01 ,00,00,00,0cccccccccccccccc33,332,331 ,330,323,222,221 ,220,213, 112, 111 , 110, 103,002,001 ,

45、000,0P0a00a01a02 a03b00b01b02b03P1a10a11a12 a13b10b11b12b13P2a20a21a22 a23b20b21b22b23P3a30a31a32 a33b30b31b32b33浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ mod pv接收地址：mpl=myid+1 mod pbacbacbacbacbacbacbacbacbacbacbacbacbacbacbacbac3,033,31 ,32,032,31 ,31 ,031 ,31 ,30,030,31 ,33,323,21 ,22,322,2

46、1 ,21 ,321 ,21 ,20,320,21 ,23,213,11 ,12,212,11 ,11 ,211 ,11 ,10,210,11 ,13,103,01 ,02,102,01 ,01 ,101 ,01 ,00,100,01 ,0P0a00a01a02 a03b10b11b12b13P1a10a11a12 a13b20b21b22b23P2a20a21a22 a23b30b31b32b33P3a30a31a32 a33b00b01b02b03cccccccccccccccc033,3032,3031,3030,3323,2322,2321,2320,2213,1212,1211,12

47、10,1103,0102,0101,0100,0浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ mod pv接收地址：mpl=myid+1 mod pbacbacbacbacbacbacbacbacbacbacbacbacbacbacbacbac3,1033,32,32,1032,32,31 ,1031 ,32,30,1030,32,33,0323,22,22,0322,22,21 ,0321 ,22,20,0320,22,23,3213,12,12,3212,12,11 ,3211 ,12,10,3210,12,13,2103,02,02,21

48、02,02,01 ,2102,02,00,2100,02,0P0a00a01a02a03b20b21b22b23P1a10a11a12 a13b30b31b32b33P2a20a21a22 a23b00b01b02b03P3a30a31a32 a33b10b11b12b13cccccccccccccccc1033,31032,31031,31030,30323,20322,20321,20320,23213,13212,13211,13210,12103,02102,02101,02100,0浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ mod

49、 pv接收地址：mpl=myid+1 mod pbacbacbacbacbacbacbacbacbacbacbacbacbacbacbacbac3,21033,33,32,21032,33,31 ,21031 ,33,30,21030,33,33, 10323,23,22, 10322,23,21 , 10321 ,23,20, 10320,23,23,03213, 13, 12,03212, 13, 11 ,03211 , 13, 10,03210, 13, 13,32103,03,02,32102,03,01 ,32102,03,00,32100,03,0P0a00a01a02a03b30

50、b31b32b33P1a10a11a12 a13b00b01b02b03P2a20a21a22 a23b10b11b12b13P3a30a31a32 a33b20b21b22b23cccccccccccccccccccccccccccccccc3,32,31,30,33,22,21,20,23,12,11,10,13,02,01,00,021033,321032,321031,321030,310323,210322,210321,210320,203213,103212,103211,103210,132103,032102,032101,032100,0浙浙 江江 大大 学学 软软 硬硬

51、件件 协协 同同 设设 计计 实实 验验 室室http:/ 的方块阵Ai,j、Bi,j和Ci,j , 其中Ai,j、Bi,j和Ci,j均为nn的方阵。 Ai,j、Bi,j和Ci,j 存放在Pi,j 设处理器数P= mm，二维结构 每次每个处理机计算出Ci的部分积,采用乘累加 计算C需要p次来完成。()ijm mAA()ijm mBB()ijm mCC广播滚动浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 12, 11 , 10, 11,22,21 ,20,21, 12, 11 , 10, 11,02,01 ,00,0.bbbbbbbbbbbbbb

52、bbpppppppp1, 12, 11 , 10, 11,22,21 ,20,21, 12, 11 , 10, 11,02,01 ,00,0.其它mlijIQnljimod, 0,设：块置换矩阵Ql=(Qi,j) ccccccccccccccccppppppp1,11,21 ,10,14,22,21 ,20,21,12,11 ,10,12,12,01 ,00,0.Ci,jnnnnIIIIQ.000.0.000.000.0000.00.0.0000.000.001nnnnIIIIQ0.00.0000.0000.002nnnnnIIIIIQ0.00.0.000.00.0001nnnnlIIIIQ浙

53、浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ mod m) 1, 12,21, 1,0.000.0.000.000.00lmllllAAAAADlQmllADIIIIAAAAIIIIIAAAAIIIIAAAAAAAAAAAAAAAAAAAAAAAAnnnnmmmnnnnnmnnnnmmmmmmmmmmmmmm10)(0.000.0.0000.00.000.000.0.000.000.00.0.00.0.0000.000.00.000.0.000.000.00.000.0.000.000.00.000.0.000.000.000.000.0.000

54、.00.00000.0000.0.00.0000.000.0.00.0.0000.000.00.000.0.000.000.002, 11 ,20, 11,00, 13,22, 11 ,0,2,21 , 10,02, 12, 31 ,20, 11,03, 11 , 30,21, 12,00, 12,23,22, 11 ,0,2,21 , 10,0浙浙 江江 大大 学学 软软 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ 1() 1(.) 1 () 1 () 0() 0(mBmADBADBADBBBBBBBBBBBBBBBBBBBBmADBBBBBBBBBBBBBBBBBBB

55、BADBBBBBBBBBBBBBBBBADBBBBBBBBBBBBBBBBIIIIImADBBBBBBBBBBBBBBBBIIIIIADBBBBBBBBBBBBBBBBIIIIADmmmmmmmmmmpmmmmmmmmmmmmpppmmmmmpppmmmmmmmmnnnnnmmmmmmmmnnnnnmmmmmmmmnnnn1,22,21 ,20,21,32,31 ,30,31,12,11 ,10,11,02,01 ,00,01,12,11 ,10,11,02,01 ,00,01,12,11 ,10,11,32,31 ,30,31,22,21 ,20,21,12,11 ,10,11,12,11

56、,10,11,22,21 ,20,21,12,11 ,10,11,02,01 ,00,01,12,11 ,10,11,22,21 ,20,21,12,11 ,10,11,02,01 ,00,01,12,11 ,10,11,22,21 ,20,21,12,11 ,10,11,02,01 ,00,01,12,11 ,10,11,22,21 ,20,21,12,11 ,10,11,02,01 ,00,0.) 1(.) 1 (.)0(.0.0000.0.000.00.000) 1(.0.00.0.0000.000.00) 1 (.000.0.000.000.00)0(浙浙 江江 大大 学学 软软 硬硬

57、 件件 协协 同同 设设 计计 实实 验验 室室http:/ 1() 1(.) 1 () 1 ()0()0()(10)(mBmADBADBADlBmllADBABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABBBBBBBBBBBBBBBBBBBBAAAABBBBBBBBBBBBBBBBBBBBAAAABBBBBBBBBBBBBBBBAAAAmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmpm

58、mmmmmmmmmmmmmmmmmmmmmmmmmmmm,0,21,02,12 .02,11,02,10,01,21,11,22,11,21,11,20,10,11,000,12,00,11,0,10,01,01,11,02,11,01,11,00,1,0,11,00,12 .00,11,00,10,03,21,33,22,33,21,33,20,32,11,22,12,22,11,22,10,21,01,11,02,11,01,11,00,1,11,1,12,1,11,1,10,12,21,22,22,22,21,22,20,21,11,11,12,11,11,11,10,10,01,00,

59、02,00,01,00,00,01,22,21,20,21,32,31,30,31,12,11,10,11,02,01,00,01,12,11,10,12,11,20,11,01,02,01,00,01,22,21,20,21,32,31,30,31,22,21,20,21,12,11,10,10,13,22,11,01,12,11,10,11,22,21,20,21,12,11,10,11,02,01,00,01,12,21,10,0.,.,.,.,.,.,.,.000.0.000.000.00.000.0.000.000.00.000.0.000.000.00,浙浙 江江 大大 学学 软软

60、 硬硬 件件 协协 同同 设设 计计 实实 验验 室室http:/ ，每个处理器做对应子块乘累加，一次完成Ci,i的部分积。循环m次完成C的全部乘法P0,0P1,0P2,0Pm-1,0P0,1P1,1P2,1Pm-1,1P0,2P1,2P2,2Pm-1,2P0,m-1P1,m-1P2,m-1Pm-1,m-1A0,0B0,0A0,1B0,1A0,2B0,2A0, m-1B0, m-1A1,0B1,0A1,1B1,1A1,2B1,2A1, m-1B1，m-1A2,0B2,0A2,1B2,1A2,2B2,2A2, m-1B2, m-1Am-1,0Bm-1,0Am-1,1Bm-1,1Am-1,2Bm-