Download presentation
Presentation is loading. Please wait.
1
第七章 并行计算机结构
2
第一节 并行计算机结构分类 一、并行性粒度与等级 *并行性粒度G:即计算/通信比,粒度越细、通信量越大 *并行性等级: 作业或程序
第一节 并行计算机结构分类 一、并行性粒度与等级 *并行性粒度G:即计算/通信比,粒度越细、通信量越大 *并行性等级: 作业或程序 子程序、作业步或程序的有关部分 过程、子程序、任务或协同程序 非递归循环或可展开迭代 指令或语句 级1 级2 级3 级4 级5 细粒度 中粒度 粗粒度 并行性程度 通信需求与调度开销 指令数<20 指令数<500 指令数<2000 指令数<10000 指令数>10000
3
二、并行性开发策略 1、开发策略 *时间重叠:侧重时间方面,处理过程相互重叠 *资源重复:侧重空间方面,同时进行处理过程(同时性)
*资源共享:侧重软件手段,轮流使用资源(并发性) 2、实现方法 *粗粒度:侧重软件手段,如MIMD方式 要求程序员、编译器相互配合 *细粒度:侧重硬件手段,如流水方式、SIMD方式 借助于流水线、并行化/向量化编译器
4
三、并行计算机结构分类 *按并行内容分类: 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结构两种均有 思考—不同访存模型对编程、性能有哪些影响?
5
第二节 SIMD处理机 一、基本结构 1、分布式结构 *结构特点:存储模块由每个PE自带,IN是单向的(PE→PE) 主机 标量处理机
阵列控制器 I/O(用户) 大容量存储器 控制存储器 (程序和数据) 标量指令 向量指令 指令 互连网络IN LM0 PEn-1 PE0 LMn-1 数据总线 广播总线 网络控制 CU *结构特点:存储模块由每个PE自带,IN是单向的(PE→PE) 回下页
6
数据准备—划分后的数据集通过数据总线存放到各PE的LM中
*工作原理: 数据准备—划分后的数据集通过数据总线存放到各PE的LM中 指令执行—通过控制部件控制指令译码、执行, 标量、向量、网络控制指令的执行部件不同 数据寻径—通过网络控制指令控制IN,实现PE间互连 数据通信—通过通信指令实现PE间数据通信 └→属于向量指令,IN已按要求实现了互连 转上页
7
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)
8
二、主要特点 1、开发并行性中的同时性 所有PE操作相同、数据不同, 比标量/向量流水具有更好的性能和可扩展性 2、IN对系统性能的影响较大
3、并行算法与SIMD计算机结构密切相关 不同结构所对应的并行算法的可行性、实现效率不同 ☆SIMD机研究的重点—IN、并行算法
9
三、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页
10
由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组成:如右图 各部件受控制部件控制; 控制部件受指令控制总线控制 转上页
11
组成—由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页
12
*功能:所有指令译码与控制、标量指令执行、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页
13
*实现:每个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页
14
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分组求解
15
四、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
16
2、MMX数据类型与寄存器 *MMX数据类型:共4种类型,不同数据类型的运算方法不同 紧缩字节类型--8个字节打包成64位数据 紧缩字类型-- 4个字打包成64位数据 紧缩双字类型--2个双字打包成64位数据 四字类型 个64位数据 *MMX寄存器:8个64位寄存器MM0-MM7 Pentium--借用8个浮点寄存器,别名方法实现, 浮点运算与MMX运算互斥; PII--增设8个MMX寄存器,MMX运算和浮点运算可并行
17
3、MMX指令集 *MMX指令类型:共7组,为算术、比较、转换、逻辑、移位、数据传送、清除MMX状态(EMMS)指令 *MMX指令的特征: SIMD结构—可并行处理多个短数据(无相关性) 饱和运算方式—溢出时不做异常处理,保持为极限值 积和运算方式—点积功能,即 , 适于矩阵、离散余弦变换、滤波等操作 比较指令—比较结果(各段)放在MM-REG中,用作屏蔽字, 后跟一条逻辑运算指令,可避免转移猜测 转换指令—完成不同精度的数据转换(紧缩或解紧缩),用于像点间插值、矩阵转置、色彩空间转换等
18
五、并行存储器的无冲突访问 1、访问需求 并行存取分量,不同分量步长不一致(如按行/列/对角线) 2、存在问题
存储器宽度<向量长度,易产生访存冲突(分量步长不同) 3、解决方法 ⑴采用多体交叉存储器:存储体数>PE数,使PE可并行访问 ⑵对向量进行分组操作:使MEM宽度>向量长度 ⑶选择适当存储体数(m):使访问无冲突 对一维向量—顺序存放,访问步长与m不成比例 m=质数,便于与PE数(常为偶数)互质
19
对多维向量—错位存放,行/列/对角线数据在不同体中
例1:设m=22P+1,对矩阵A,不同列错开距离为σ1=1, 不同行错开距离为σ2=2P a00 a01 a02 a03 a a10 a11 a12 a21 a22 a a20 a30 a31 a32 a33 体号 4×4矩阵的错位存放(m=5) a00 a10 a20 a30 a01 a11 a31 a02 a12 a22 a a21 a23 a33 a04 a a03 a13 a24 a34 体号 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为质数,程序根据向量进行相应处理
20
第三节 多处理机 一、SIMD与MIMD比较 *多处理机:MIMD结构、NUMA访存模型(MEM单地址空间)、共享变量通信机制
1、结构与通用性 *SIMD:数据并行,一个CU,IN集中控制,通用性较差; *MIMD:功能/数据并行,多个CU,IN分布控制,通用性较强 2、程序并行性 *SIMD:操作级并行,识别靠向量指令, 支持靠编译程序和硬件 *MIMD:任务级并行,识别靠显式并行指令、OS, 支持靠程序员、编译程序、OS对任务的调度
21
*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:软件手段(排队器、触发等)分配及调度
22
二、多处理机结构 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,分布式控制
23
*节点结构:完整的处理机系统(可为多处理机系统),
2、分布式共享存储多处理机 IN ··· M1 NIC1 P1 /C1 MB 节点1 节点n Bridge1 IOB *节点结构:完整的处理机系统(可为多处理机系统), *互连网络:节点间互连,非对称网络,分布式控制 *节点通信:MEM为单地址空间、NUMA访存模型, 共享变量通信机制 3、机间互连形式 P较少时—总线、交叉开关,多端口存储器 P较多时—多级网络,静态网络
24
三、多处理机的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等
25
四、多处理机实例 1、Intel SHV SMP系统 节点互连—总线结构,可通过OEM桥扩展
MEM总线 PCI桥 存储器控制器 L2$ APIC P6处理器 总线控制器 Pentium Pro 处理器组件 PCI总线 DRAM阵列 L3$,机群 OEM桥 节点互连—总线结构,可通过OEM桥扩展 MEM总线—拆分总线(总线事务采用流水方式处理) Cache一致性—基于总线监听的MESI协议
26
结点结构—包含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实际上是一个交换机 回下页
27
*互连网络—胖立方体结构: *路由器结构: 8个结点 16个结点 32个结点 路由表 LLP SSD/SSR 路由器 本地部件 路由器 结点
6×6 交叉开关 路由表 发送器 接收器 LLP SSD/SSR 路由器 本地部件 转上页
28
第四节 集群系统 一、大规模并行处理机MPP *多计算机:MIMD结构、NORMA访存模型(MEM多地址空间)、消息传递通信机制
*系统结构:紧耦合(连接MB)互连、NORMA模型、 计算节点(无HD/仅驻留部分OS) IN ··· M1 NIC1 P1 /C1 MB 节点1 节点n *互连与通信:专用IN,消息传递通信机制
29
二、集群Cluster(工作站集群COW)
1、系统结构 *结构:松耦合(连接IOB)互连、NORMA模型 完整节点(驻留全部OS) IN ··· 节点n M1 NIC1 P1 /C1 MB 节点1 Bridge1 IOB *互连与通信:商用IN,消息传递通信机制
30
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接口 回下页
31
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等 转上页
32
*Torque作业管理原理:管理进程与各守护进程
33
第五节 多处理机中并行性开发 一、并行程序设计语言 *并行性开发途径:语言、编译、算法、OS等方面 1、主要并行程序编程模型
*共享变量模型:通过进程实现并行性,通过共享变量实现进程间通信与同步。数据一致性由编译程序及硬件系统保证 *消息传递模型:通过进程实现并行性,通过消息传递实现进程间通信与自然同步。数据一致性由程序员保证 *数据并行模型:通过处理单元并行操作实现并行性,通过软件指令实现数据交换,SI或SP实现数据自然同步和一致性
34
2、并行程序设计语言开发方式 *设计并行程序设计语言方法: ⑴重新设计新语言 ⑵扩充现有语言功能 ⑶不改变现有语言,提供函数库或并行化编译系统 *并行程序编译器实现方法: ⑴设计新语言的编译器 ⑵利用通用编译器,加入预编译(并行成分用传统语言) ⑶利用通用编译器,链接时提供并行函数库 ⑷设计新的编译器,将现有语言串行程序自动并行化
35
3、并行程序设计语言的关键技术 (1)进程管理 ①进程创建与消亡:显式、隐式 显式如FORK-JOIN,隐式如cobegin-coend、parfor等 ②进程激活:创建时激活、收到消息时激活 一般采用创建时激活 ③进程粒度:一般提供中粒度(2K~10K指令)进程描述手段 (因进程创建代价较大) (2)进程通信与同步 *通信方式:同步、异步互锁、异步非互锁 通信—进程间数据传递,一般采用异步方式(提高性能) 同步—进程间协同,一般采用同步方式(提高可靠性)
36
①显式创建--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列*/ 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次
37
例: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
38
二、串行算法到并行算法转换 1、相关类型 数据相关—RAW相关,数据反相关—WAR相关, 数据输出相关—WAW相关,控制相关—条件语句
2、并行性检测 --伯恩斯坦准则 *P1、P2可并行条件:Ii—读单元集,Oi—写单元集 I1∩O2=φ,并且I2∩O1=φ,并且O1∩O2=φ
39
主要解决反相关和输出相关,由编译程序自动完成
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; 存在数据相关、反相关、输出相关、控制相关 消除数据反相关、输出相关
40
三、并行算法 1、同步并行算法 进程的某些段要等待其它进程,以保持同步的并行算法 *应用:只适用于进程速度波动较小的情况 2、异步并行算法
进程间直接通信(共享变量或传递消息),无需等待/触发 *种类:简单异步迭代算法、自适应算法 *实现:通过进程交替进行,可并行处理
41
四、MPI并行程序设计举例 *要求:计算 *公式转换: *并行算法: 共M个进程(0#~M-1#);
第i#进程计算i、i+M、i+2M…i+(n/M-1)M个块; 0#进程兼管理进程
42
#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= ; 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);
43
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);
44
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();
Similar presentations