第七章 并行计算机结构

第一节 并行计算机结构分类 一、并行性粒度与等级 *并行性粒度G：即计算/通信比，粒度越细、通信量越大 *并行性等级： 作业或程序 第一节 并行计算机结构分类 一、并行性粒度与等级 *并行性粒度G：即计算/通信比，粒度越细、通信量越大 *并行性等级： 作业或程序 子程序、作业步或程序的有关部分 过程、子程序、任务或协同程序 非递归循环或可展开迭代 指令或语句 级1 级2 级3 级4 级5 细粒度 中粒度 粗粒度 并行性程度 通信需求与调度开销 指令数＜20 指令数＜500 指令数＜2000 指令数＜10000 指令数＞10000

二、并行性开发策略 1、开发策略 *时间重叠：侧重时间方面，处理过程相互重叠 *资源重复：侧重空间方面，同时进行处理过程(同时性) *资源共享：侧重软件手段，轮流使用资源(并发性) 2、实现方法 *粗粒度：侧重软件手段，如MIMD方式 要求程序员、编译器相互配合 *细粒度：侧重硬件手段，如流水方式、SIMD方式 借助于流水线、并行化/向量化编译器

三、并行计算机结构分类 *按并行内容分类： SIMD—数据并行，细粒度并行，阵列处理机 MIMD—功能并行，中/粗粒度并行，多处理机/多计算机 *按MEM结构分类： 集中式MEM结构—UMA访存模型，SMP、PVP 分布式MEM结构—NUMA或NORMA访存模型，DSM、MPP、COW 互连网络 ··· P1/C1 P2/C2 Pn/Cn SM1 SM2 SMm SM1或LM1 NIC1 MB 节点1 节点n UMA(Uniform Memory Access),NUMA(Non-Uniform Memory Access),NORMA(No-Remote Memory Access) SMP(Symmetric shared-memory Multi-Processor),PVP(Parallel Vector Processor) DSM(Distributed Shared-Memory),MPP(Massively Parallel Processor),COW(Cluster of Workstation) SIMD的MEM结构两种均有 思考—不同访存模型对编程、性能有哪些影响？

第二节 SIMD处理机 一、基本结构 1、分布式结构 *结构特点：存储模块由每个PE自带，IN是单向的(PE→PE) 主机 标量处理机 阵列控制器 I/O（用户） 大容量存储器 控制存储器 (程序和数据) 标量指令 向量指令 指令 互连网络IN LM0 PEn-1 PE0 LMn-1 数据总线 广播总线 网络控制 CU *结构特点：存储模块由每个PE自带，IN是单向的(PE→PE) 回下页

数据准备—划分后的数据集通过数据总线存放到各PE的LM中 *工作原理： 数据准备—划分后的数据集通过数据总线存放到各PE的LM中 指令执行—通过控制部件控制指令译码、执行， 标量、向量、网络控制指令的执行部件不同 数据寻径—通过网络控制指令控制IN，实现PE间互连 数据通信—通过通信指令实现PE间数据通信 └→属于向量指令，IN已按要求实现了互连 转上页

2、集中式结构 *结构特点： 各个PE共享m个(m≠n)存储模块， IN是双向的(PE←→MEM) 主机 标量处理机 CU I/O（用户） 大容量存储器 标量 指令 互连网络IN SM0 PEn-1 PE0 SMm-1 数据总线 广播总线(向量指令) 网络 控制 控制存储器 阵列控制器 *结构特点： 各个PE共享m个(m≠n)存储模块， IN是双向的(PE←→MEM)

二、主要特点 1、开发并行性中的同时性 所有PE操作相同、数据不同， 比标量/向量流水具有更好的性能和可扩展性 2、IN对系统性能的影响较大 3、并行算法与SIMD计算机结构密切相关 不同结构所对应的并行算法的可行性、实现效率不同 ☆SIMD机研究的重点—IN、并行算法

三、Illiac Ⅳ阵列处理机 控制描述字 控制器CDC 总线控制器 B6700外围设备 译码器 闭合螺旋线阵列 PEM0 PE0 模式位 总线 闭合螺旋线阵列 PEM0 PE0 阵列控制器CU PE63 … PE1 PEM1 PEM63 公共数据总线 CDB 指令控制 标量执行部件 控制器 缓冲器 CU总线 I/O总线 B6700 RAM I/O缓冲存储 器BIOM 磁盘文件系统DFS IO开关 实时 装置 B6700多路开关 CPU 1024 256 128 48 激光存储器 64×8 64 取指令 回下页 回11页 回12页 回13页

由64个PE、64个PEM(含MEM逻辑部件)组成 1、Illiac Ⅳ阵列 由64个PE、64个PEM(含MEM逻辑部件)组成 *PE阵列结构：闭合螺旋线拓扑结构 驱动/接收器 操作数选择门 REGR 通用REG 算术单元 AU 逻辑单元 LU REGA 地址加法 器ADA REGM 移位单元 SU REGX MAR 来自PEM 来自CDB(来自CU) 东 南 西 北 CU 存储器逻辑部件MLU REGR—被乘数和互连REG；REGM—模式REG； REGX—变址REG；MAR—存储器地址REG PE0 PE1 PE7 … PE8 PE9 PE15 PE56 PE57 PE63 *PE组成：如右图 各部件受控制部件控制； 控制部件受指令控制总线控制 转上页

组成—由64个双重编址的PEM组成，存放数据和指令 PEM容量：为2048×64位(一维空间) 双重编址：公共编址(行序)、PE编址(列序) *阵列存储器： 组成—由64个双重编址的PEM组成，存放数据和指令 PEM容量：为2048×64位(一维空间) 双重编址：公共编址(行序)、PE编址(列序) … PEM0 PEM1 PEM63 00000[000] 00040[001] 1FFC0[7FF] 00001[000] 00041[001] 1FFC1[7FF] 0003F[000] 0007F[001] 1FFFF[7FF] 公共 [PE] 访问—各PE只能访问自己的PEM(按PE编址)，存取数据； CU可通过CU总线访问阵列存储器(按公共编址)， 取指令和数据(如标量指令操作数)； B6700可通过I/O总线访问阵列存储器(按公共编址) 转9页

*功能：所有指令译码与控制、标量指令执行、PE执行控制 2、阵列控制器 *功能：所有指令译码与控制、标量指令执行、PE执行控制 *CU与PE通信途径： CU总线—传送指令(CU用)和公共数据(标量部件用) CDB—广播公共数据(64个PE用) 模式位总线—传递各PE状态(CU中拼成一个模式字) 指令控制线—控制各PE执行的向量指令操作 3、I/O系统 *组成：DFS、I/O分系统(IOS、CDC和BIOM)、B6700 *IOS：实现DFS或实时装置与阵列存储器的连接； *CDC：管理CU的I/O请求，使B6700产生中断， B6700通过CDC返回响应给CU； *BIOM：匹配B6700与DFS的带宽，容量为4个PEM容量 转9页

*实现：每个PE计算一个坐标点，多次迭代，直到误差达标 4、常用并行算法 (1)有限差分 *原理： *实现：每个PE计算一个坐标点，多次迭代，直到误差达标 数据通信—由4条IN控制及PE通信指令实现 (2)矩阵加 *原理：每个PE计算矩阵中一个元素 *实现：对C=A+B，A、B、C不同地址的分量放在各PE的LM中的相同位置，用三条指令完成(设PE的运算基于累加器)： LDA α ADD α+1 STA α+2 C(0,0) A(0,0) B(0,0) α α+1 α+2 … C(0,1) A(0,1) B(0,1) C(7,7) A(7,7) B(7,7) 转9页

PE活跃问题—使用专用指令实现(操作数为2k-1)； (3)累加求和 *算法： k=0； while ( 2k ＜ N ) //每轮步距为2k，共log2N轮 { 置PE0至PE2k-1不活跃 PEi+2k += PEi ； //0≤i≤N-2k k++； } /*最终结果在PEN-1中*/ *实现： PE活跃问题—使用专用指令实现(操作数为2k-1)； 通信步距问题—编译程序生成不同的IN控制指令、通信指令对(串)； N＞PE数问题—将N分组求解

四、IA32中的SIMD应用--MMX技术 1、实现要求 *对硬件的要求： 64位特殊ALU能够同时处理多个8位、16位、32位等数据 └→不同数据间无关联(如进位) *对OS的要求： OS向下兼容，不引进新的状态、控制REG和条件码 *对指令系统的要求： 增加4种数据表示； 使用8个64位MMX寄存器(借用/增加)； 增加MMX新指令(57条) MMX(Multi Media Extension)，SSE(Streaming SIMD Extensions)，AVX(Advanced Vector Extensions) 1996年，MMX，64bit； 1999年，SSE，128bit，2001、2004、2007年，SSE2、SSE3、SSE4； 2010年，AVX,256bit，2013年，AVX2

2、MMX数据类型与寄存器 *MMX数据类型：共4种类型，不同数据类型的运算方法不同 紧缩字节类型--8个字节打包成64位数据 紧缩字类型-- 4个字打包成64位数据 紧缩双字类型--2个双字打包成64位数据 四字类型-- 1个64位数据 *MMX寄存器：8个64位寄存器MM0-MM7 Pentium--借用8个浮点寄存器，别名方法实现， 浮点运算与MMX运算互斥； PII--增设8个MMX寄存器，MMX运算和浮点运算可并行

3、MMX指令集 *MMX指令类型：共7组，为算术、比较、转换、逻辑、移位、数据传送、清除MMX状态(EMMS)指令 *MMX指令的特征： SIMD结构—可并行处理多个短数据(无相关性) 饱和运算方式—溢出时不做异常处理，保持为极限值 积和运算方式—点积功能，即 ， 适于矩阵、离散余弦变换、滤波等操作 比较指令—比较结果(各段)放在MM-REG中，用作屏蔽字， 后跟一条逻辑运算指令，可避免转移猜测 转换指令—完成不同精度的数据转换(紧缩或解紧缩)，用于像点间插值、矩阵转置、色彩空间转换等

五、并行存储器的无冲突访问 1、访问需求 并行存取分量，不同分量步长不一致(如按行/列/对角线) 2、存在问题 存储器宽度＜向量长度，易产生访存冲突(分量步长不同) 3、解决方法 ⑴采用多体交叉存储器：存储体数＞PE数，使PE可并行访问 ⑵对向量进行分组操作：使MEM宽度＞向量长度 ⑶选择适当存储体数(m)：使访问无冲突 对一维向量—顺序存放，访问步长与m不成比例 m＝质数，便于与PE数(常为偶数)互质

对多维向量—错位存放，行/列/对角线数据在不同体中 例1：设m=22P+1，对矩阵A，不同列错开距离为σ1=1， 不同行错开距离为σ2=2P a00 a01 a02 a03 a13 a10 a11 a12 a21 a22 a23 a20 a30 a31 a32 a33 体号 0 1 2 3 4 4×4矩阵的错位存放(m=5) a00 a10 a20 a30 a01 a11 a31 a02 a12 a22 a32 a21 a23 a33 a04 a14 a03 a13 a24 a34 体号 0 1 2 3 4 5 6 4×5二维数组的错位存放(m=7，n=6) 例1中，Aab的体号：j=(aσ2+bσ1+C) mod m，体内序号：i=a 例2中，S(a)的体号：j=a mod m，体内序号：i= [a/n]下界 例2：元素不固定(或非n×n)时，先变换成一维数组S，再处理（如体号j=a mod m，体内序号i= a/n ） 常用方法—m为质数，程序根据向量进行相应处理

第三节 多处理机 一、SIMD与MIMD比较 *多处理机：MIMD结构、NUMA访存模型(MEM单地址空间)、共享变量通信机制 1、结构与通用性 *SIMD：数据并行，一个CU，IN集中控制，通用性较差； *MIMD：功能/数据并行，多个CU，IN分布控制，通用性较强 2、程序并行性 *SIMD：操作级并行，识别靠向量指令， 支持靠编译程序和硬件 *MIMD：任务级并行，识别靠显式并行指令、OS， 支持靠程序员、编译程序、OS对任务的调度

*SIMD：向量指令表示及控制，隐式并行、效率低 3、任务派生 *SIMD：向量指令表示及控制，隐式并行、效率低 I1 I2 I3 I4 I5 I7 I6 P0 P1 P2 P3 P标量 屏蔽 空闲 I1 I2 I3 I4 I5 I7 I6 P0 P1 P2 P3 *MIMD：专用指令表示及控制，显式并行、效率高 4、进程同步 *SIMD：单一CU控制，自然同步 *MIMD：多个CU控制，需用特殊措施同步(锁、信号灯等) 5、资源分配和任务调度 *SIMD：屏蔽手段，无需调度 *MIMD：软件手段(排队器、触发等)分配及调度

二、多处理机结构 1、集中式共享存储多处理机 *节点结构：同构/异构—PE类型相同/不同 对称/非对称—每个PE连接的I/O通道是/否相同 PM-IN ··· P1/C1/M1 SM1 SMm Pn/Cn/Mn PP-IN PIO-IN D0 Dn *节点结构：同构/异构—PE类型相同/不同 对称/非对称—每个PE连接的I/O通道是/否相同 SMP为同构对称式 常见结构：同构对称式、异构非对称式、 *互连网络：PM-IN、PP-IN、PIO-IN，分布式控制

*节点结构：完整的处理机系统(可为多处理机系统)， 2、分布式共享存储多处理机 IN ··· M1 NIC1 P1 /C1 MB 节点1 节点n Bridge1 IOB *节点结构：完整的处理机系统(可为多处理机系统)， *互连网络：节点间互连，非对称网络，分布式控制 *节点通信：MEM为单地址空间、NUMA访存模型， 共享变量通信机制 3、机间互连形式 P较少时—总线、交叉开关，多端口存储器 P较多时—多级网络，静态网络

三、多处理机的Cache一致性 *应用需求：各P共享MEM，各P自带私有Cache(写回法) *处理方案： 系统不支持(APP实现)、系统支持 (硬件及OS实现) *Cache一致性实现方法：基于监听法、目录法的一致性协议 主存 CPU Cache DMA I/On I/O1 … (a)总线互连[监听法] 互连网络 ··· (b)网络互连[目录法] SM NIC Cache一致性（Cache Coherence） *Cache一致性协议：VI、MSI、MESI、Dragon等

四、多处理机实例 1、Intel SHV SMP系统 节点互连—总线结构，可通过OEM桥扩展 MEM总线 PCI桥 存储器控制器 L2$ APIC P6处理器 总线控制器 Pentium Pro 处理器组件 PCI总线 DRAM阵列 L3$,机群 OEM桥 节点互连—总线结构，可通过OEM桥扩展 MEM总线—拆分总线(总线事务采用流水方式处理) Cache一致性—基于总线监听的MESI协议

结点结构—包含2个MIPS R10000 CPU，通过HUB互连 节点互连—胖立方体拓扑结构，可达512个节点 2、SGI Origin 2000系统 互连网络 P L2$(1~4M) SysAD总线 HUB* 目录 主存(1~4G) Xbow 结点结构—包含2个MIPS R10000 CPU，通过HUB互连 节点互连—胖立方体拓扑结构，可达512个节点 Cache一致性—基于目录表的MESI协议 该HUB实际上是一个交换机 回下页

*互连网络—胖立方体结构： *路由器结构： 8个结点 16个结点 32个结点 路由表 LLP SSD/SSR 路由器 本地部件 路由器 结点 6×6 交叉开关 路由表 发送器 接收器 LLP SSD/SSR 路由器 本地部件 转上页

第四节 集群系统 一、大规模并行处理机MPP *多计算机：MIMD结构、NORMA访存模型(MEM多地址空间)、消息传递通信机制 *系统结构：紧耦合(连接MB)互连、NORMA模型、 计算节点(无HD/仅驻留部分OS) IN ··· M1 NIC1 P1 /C1 MB 节点1 节点n *互连与通信：专用IN，消息传递通信机制

二、集群Cluster（工作站集群COW） 1、系统结构 *结构：松耦合(连接IOB)互连、NORMA模型 完整节点(驻留全部OS) IN ··· 节点n M1 NIC1 P1 /C1 MB 节点1 Bridge1 IOB *互连与通信：商用IN，消息传递通信机制

2、集群实例—IBM Cluster 1350 (1)结点--HS20刀片服务器 (2)结点组--刀片服务器中心 L2$(1M) P4(3.0G) MEM(4G) HD(73G) ×2 系统管理 处理器 以太网卡 (1G)×2 InfiniBand 网卡(10G) (2)结点组--刀片服务器中心 InfiniBand 交换机(18口) 以太网交换 机(18口) RS-485 接口 以太网 …… 刀片1 管理 模块 刀片14 用户接口卡/USB开关 CD、FDD、USB USB接口 KVM接口 回下页

InfiniBand网络为数据网络；以太网络为管理/控制网络 (3)整机—机群系统 光纤接口 中心1 中心3 中心2 以太网交换机(24口) InfiniBand交换机(24口) 管理计算机 KVM交换机 K、V、M RAID(5T) 远程管理计算机 远程应用网络 InfiniBand网络为数据网络；以太网络为管理/控制网络 (4)软件系统 *操作系统：RedHat Linux 9.0 *COW管理 ：CSM(核心Director) *作业管理：Torque for Linux *编程环境：MPI、PVM，Gun C/C++、Fortran等 转上页

*Torque作业管理原理：管理进程与各守护进程

第五节 多处理机中并行性开发 一、并行程序设计语言 *并行性开发途径：语言、编译、算法、OS等方面 1、主要并行程序编程模型 *共享变量模型：通过进程实现并行性，通过共享变量实现进程间通信与同步。数据一致性由编译程序及硬件系统保证 *消息传递模型：通过进程实现并行性，通过消息传递实现进程间通信与自然同步。数据一致性由程序员保证 *数据并行模型：通过处理单元并行操作实现并行性，通过软件指令实现数据交换，SI或SP实现数据自然同步和一致性

2、并行程序设计语言开发方式 *设计并行程序设计语言方法： ⑴重新设计新语言 ⑵扩充现有语言功能 ⑶不改变现有语言，提供函数库或并行化编译系统 *并行程序编译器实现方法： ⑴设计新语言的编译器 ⑵利用通用编译器，加入预编译(并行成分用传统语言) ⑶利用通用编译器，链接时提供并行函数库 ⑷设计新的编译器，将现有语言串行程序自动并行化

3、并行程序设计语言的关键技术 (1)进程管理 ①进程创建与消亡：显式、隐式 显式如FORK-JOIN，隐式如cobegin-coend、parfor等 ②进程激活：创建时激活、收到消息时激活 一般采用创建时激活 ③进程粒度：一般提供中粒度(2K~10K指令)进程描述手段 (因进程创建代价较大) (2)进程通信与同步 *通信方式：同步、异步互锁、异步非互锁 通信—进程间数据传递，一般采用异步方式(提高性能) 同步—进程间协同，一般采用同步方式(提高可靠性)

①显式创建--FORK-JOIN(不同语言有不同形式) FORK A,J：派生一进程，本进程继续，地址J处计数器+1 (3)进程创建示例 ①显式创建--FORK-JOIN(不同语言有不同形式) FORK A,J：派生一进程，本进程继续，地址J处计数器+1 JOIN J： 地址J处计数器减1；当计数器值为零时，启动地址J+1处进程，否则，结束该进程 例：3个PE并行处理8×8矩阵乘法 DO 10 J=0，6 10 FORK 20，60 /*派生处理第0~6列进程*/ J=7 /*当前进程处理第7列*/ 20 DO 40 I=0，7 /*处理0~7行*/ C(I,J)=0 DO 30 K=0,7 /*处理C(I,J)*/ 30 C(I,J)=C(I,J)+A(I,K)*B(K,J) 40 CONTINUE JOIN 60 60 … PE t J=0 J=1 J=2 J=3 J=7 J=4 J=5 J=6 7次

例：C(n×1)=A(n×n)×B(n×1) ②隐式创建—parfor parfor i=k,n原语： 例：C(n×1)=A(n×n)×B(n×1) parfor i=1, p { for j=(i-1)*s+1, s*i // s=n/p // P1:1~s;P2:s+1~2s;Pp:n-s~n c(j)=0 for k=1, n c(j)=c(j)+A(j,k)*B(j) } i=k, 计数器为1 i=i+1 i>n FORK A5,A6 循环体S JOIN A1 A2 A3 A4 A5 A6

二、串行算法到并行算法转换 1、相关类型 数据相关—RAW相关，数据反相关—WAR相关， 数据输出相关—WAW相关，控制相关—条件语句 2、并行性检测 --伯恩斯坦准则 *P1、P2可并行条件：Ii—读单元集，Oi—写单元集 I1∩O2=φ，并且I2∩O1=φ，并且O1∩O2=φ

主要解决反相关和输出相关，由编译程序自动完成 3、数据相关避免 主要解决反相关和输出相关，由编译程序自动完成 *重命名方法： S：A=B+C T：D=A+E U：A=A+D V：IF X>0 THEN G=F+A 消除反相关、输出相关 U’：AA=A+D V’：IF X>0 THEN G=F+AA *标量扩充方法： for i=1 to n do if A(i)<0 then X=B(i); else X=C(i); D(i)=X+1; for i=1 to n do b(i)=A(i)<0; X(i)=B(i) when b(i); X(i)=C(i) when not b(i); D(i)=X(i)+1; 存在数据相关、反相关、输出相关、控制相关 消除数据反相关、输出相关

三、并行算法 1、同步并行算法 进程的某些段要等待其它进程，以保持同步的并行算法 *应用：只适用于进程速度波动较小的情况 2、异步并行算法 进程间直接通信(共享变量或传递消息)，无需等待/触发 *种类：简单异步迭代算法、自适应算法 *实现：通过进程交替进行，可并行处理

四、MPI并行程序设计举例 *要求：计算 *公式转换： *并行算法： 共M个进程(0#~M-1#)； 第i#进程计算i、i+M、i+2M…i+(n/M-1)M个块； 0#进程兼管理进程

#include “mpi.h” #include <stdio.h> #include <math.h> double f(double x);/*定义函数f(x) */ { return(4.0/(1.0+x*x)); } int main (int argc,char * argv[]) { int done=0,n=0,myid,numprocs,i，namelen; double PI25DT=3.141592653589793238462643; double mypi,pi,h,sum=0,x，startwtime=0.0,endwtime; char processor_name[MPI_MAXPROCESSOR_NAME]; MPI_Status status; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&numprocs); MPI_Comm_rank(MPI_COMM_WORLD,&myid); MPI_Get_processor_name(processor_name,&namelen); fprint(stdout,”Process %d of %d on % s\n”, myid,numprocs, processor_name);

if (myid==0) { printf(“Please give N=”); scanf(&n); startwtime=MPI_Wtime(); for (j=1;j<numprocs;j++) MPI_Send(&n,1,MPI_INT,j,99,MPI_COMM_WORLD); } else { MPI_Recv(&n,1,MPI_INT,MPI_ANY_SOURCE,99, MPI_COMM_WORLD,&status); h=1.0/(double)n; for (i=myid+1;i<=n;i+=numprocs) { x=h*((double)i-0.5); sum+=f(x); mypi=h*sum; /*各进程并行计算得到的部分和*/ if (myid != 0) MPI_Send(&mypi,1,MPI_DOUBLE,0,myid, MPI_COMM_WORLD)；

else { pi=0.0; pi=pi+mypi; for (j=1;j<numprocs;j++) { MPI_Recv(&mypi,1,MPI_DOUBLE,MPI_ANY_SOURCE, MPI_ANY_TAG,MPI_COMM_WORLD,&status); } printf(“pi is approximately %.16f,Error is %.16f\n”, pi,fabs(pi-PI25DT)); endwtime=MPI_Wtime(); printf(“wall clock time=% f\n”, endwtime-startwtime); fflush(stdout); MPI_Finalize();