1、1,第七章 并行计算机结构,2,第一节 并行计算机结构分类,一、并行性粒度与等级,*并行性粒度G：即计算/通信比，粒度越细、通信量越大,*并行性等级：,3,二、并行性开发策略,1、开发策略,*时间重叠：侧重时间方面，处理过程相互重叠*资源重复：侧重空间方面，同时进行处理过程(同时性)*资源共享：侧重软件手段，轮流使用资源(并发性),2、实现方法,*粗粒度：侧重软件手段，如MIMD方式要求程序员、编译器相互配合,*细粒度：侧重硬件手段，如流水方式、SIMD方式借助于流水线、并行化/向量化编译器,4,三、并行计算机结构分类,*按并行内容分类：SIMD数据并行，细粒度并行，阵列处理机MIMD功能并行
2、，中/粗粒度并行，多处理机/多计算机,*按MEM结构分类：集中式MEM结构UMA访存模型，SMP、PVP分布式MEM结构NUMA或NORMA访存模型，DSM、MPP、COW,思考不同访存模型对编程、性能有哪些影响？,5,第二节 SIMD处理机,一、基本结构,1、分布式结构,回下页,*结构特点：存储模块由每个PE自带，IN是单向的(PEPE),6,*工作原理：数据准备划分后的数据集通过数据总线存放到各PE的LM中,指令执行通过控制部件控制指令译码、执行，标量、向量、网络控制指令的执行部件不同,数据寻径通过网络控制指令控制IN，实现PE间互连,数据通信通过通信指令实现PE间数据通信属于向量指令，I
3、N已按要求实现了互连,转上页,7,2、集中式结构,*结构特点：各个PE共享m个(mn)存储模块，IN是双向的(PEMEM),8,二、主要特点,1、开发并行性中的同时性所有PE操作相同、数据不同，比标量/向量流水具有更好的性能和可扩展性,2、IN对系统性能的影响较大IN直接影响数据通信/存取带宽，IN影响并行算法的实现效率,3、并行算法与SIMD计算机结构密切相关不同结构所对应的并行算法的可行性、实现效率不同,SIMD机研究的重点IN、并行算法,9,三、Illiac 阵列处理机,回下页,回11页,回12页,回13页,10,1、Illiac 阵列由64个PE、64个PEM(含MEM逻辑部件)组成,
4、*PE阵列结构：闭合螺旋线拓扑结构,转上页,*PE组成：如右图各部件受控制部件控制；控制部件受指令控制总线控制,11,*阵列存储器：组成由64个双重编址的PEM组成，存放数据和指令PEM容量：为204864位(一维空间)双重编址：公共编址(行序)、PE编址(列序),访问各PE只能访问自己的PEM(按PE编址)，存取数据；CU可通过CU总线访问阵列存储器(按公共编址)，取指令和数据(如标量指令操作数)；B6700可通过I/O总线访问阵列存储器(按公共编址),转9页,12,2、阵列控制器*功能：所有指令译码与控制、标量指令执行、PE执行控制,*CU与PE通信途径：CU总线传送指令(CU用)和公共数
5、据(标量部件用)CDB广播公共数据(64个PE用)模式位总线传递各PE状态(CU中拼成一个模式字)指令控制线控制各PE执行的向量指令操作,转9页,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容量,13,4、常用并行算法,(1)有限差分*原理：,*实现：每个PE计算一个坐标点，多次迭代，直到误差达标,数据通信由4条IN控制及PE通信指令实现,(2)矩阵加*原理：
6、每个PE计算矩阵中一个元素,*实现：对C=A+B，A、B、C不同地址的分量放在各PE的LM中的相同位置，用三条指令完成(设PE的运算基于累加器)：LDA ADD +1STA +2,转9页,14,(3)累加求和*算法：,k=0； while ( 2k N ) /每轮步距为2k，共log2N轮 置PE0至PE2k-1不活跃PEi+2k += PEi ； /0iN-2kk+； /*最终结果在PEN-1中*/,*实现：PE活跃问题使用专用指令实现(操作数为2k-1)；,通信步距问题编译程序生成不同的IN控制指令、通信指令对(串)；,NPE数问题将N分组求解,15,四、IA32中的SIMD应用-MMX技
7、术,1、实现要求*对硬件的要求：64位特殊ALU能够同时处理多个8位、16位、32位等数据不同数据间无关联(如进位),*对OS的要求：OS向下兼容，不引进新的状态、控制REG和条件码,*对指令系统的要求：增加4种数据表示；使用8个64位MMX寄存器(借用/增加)；增加MMX新指令(57条),16,2、MMX数据类型与寄存器,*MMX数据类型：共4种类型，不同数据类型的运算方法不同紧缩字节类型-8个字节打包成64位数据紧缩字类型- 4个字打包成64位数据紧缩双字类型-2个双字打包成64位数据四字类型- 1个64位数据,*MMX寄存器：8个64位寄存器MM0-MM7Pentium-借用8个浮点寄存
8、器，别名方法实现，浮点运算与MMX运算互斥；PII-增设8个MMX寄存器，MMX运算和浮点运算可并行,17,3、MMX指令集,*MMX指令类型：共7组，为算术、比较、转换、逻辑、移位、数据传送、清除MMX状态(EMMS)指令,*MMX指令的特征：SIMD结构可并行处理多个短数据(无相关性),饱和运算方式溢出时不做异常处理，保持为极限值,积和运算方式点积功能，即 ，适于矩阵、离散余弦变换、滤波等操作,比较指令比较结果(各段)放在MM-REG中，用作屏蔽字， 后跟一条逻辑运算指令，可避免转移猜测,转换指令完成不同精度的数据转换(紧缩或解紧缩)，用于像点间插值、矩阵转置、色彩空间转换等,18,五、并
9、行存储器的无冲突访问,1、访问需求并行存取分量，不同分量步长不一致(如按行/列/对角线),2、存在问题存储器宽度向量长度，易产生访存冲突(分量步长不同),3、解决方法,采用多体交叉存储器：存储体数PE数，使PE可并行访问,对向量进行分组操作：使MEM宽度向量长度,选择适当存储体数(m)：使访问无冲突,对一维向量顺序存放，访问步长与m不成比例,m质数，便于与PE数(常为偶数)互质,19,对多维向量错位存放，行/列/对角线数据在不同体中,例1：设m=22P+1，对矩阵A，不同列错开距离为1=1，不同行错开距离为2=2P,常用方法m为质数，程序根据向量进行相应处理,20,第三节 多处理机,一、SIM
10、D与MIMD比较,1、结构与通用性*SIMD：数据并行，一个CU，IN集中控制，通用性较差；*MIMD：功能/数据并行，多个CU，IN分布控制，通用性较强,2、程序并行性*SIMD：操作级并行，识别靠向量指令，支持靠编译程序和硬件 *MIMD：任务级并行，识别靠显式并行指令、OS，支持靠程序员、编译程序、OS对任务的调度,*多处理机：MIMD结构、NUMA访存模型(MEM单地址空间)、共享变量通信机制,21,3、任务派生*SIMD：向量指令表示及控制，隐式并行、效率低,*MIMD：专用指令表示及控制，显式并行、效率高,4、进程同步*SIMD：单一CU控制，自然同步*MIMD：多个CU控制，需用
11、特殊措施同步(锁、信号灯等),5、资源分配和任务调度*SIMD：屏蔽手段，无需调度*MIMD：软件手段(排队器、触发等)分配及调度,22,二、多处理机结构,1、集中式共享存储多处理机,*节点结构：同构/异构PE类型相同/不同对称/非对称每个PE连接的I/O通道是/否相同,常见结构：同构对称式、异构非对称式、,*互连网络：PM-IN、PP-IN、PIO-IN，分布式控制,23,2、分布式共享存储多处理机,*节点结构：完整的处理机系统(可为多处理机系统)，,*互连网络：节点间互连，非对称网络，分布式控制,*节点通信：MEM为单地址空间、NUMA访存模型，共享变量通信机制,3、机间互连形式P较少时总
12、线、交叉开关，多端口存储器P较多时多级网络，静态网络,24,三、多处理机的Cache一致性,*应用需求：各P共享MEM，各P自带私有Cache(写回法),*处理方案：系统不支持(APP实现)、系统支持 (硬件及OS实现),*Cache一致性实现方法：基于监听法、目录法的一致性协议,*Cache一致性协议：VI、MSI、MESI、Dragon等,25,四、多处理机实例,1、Intel SHV SMP系统,节点互连总线结构，可通过OEM桥扩展MEM总线拆分总线(总线事务采用流水方式处理)Cache一致性基于总线监听的MESI协议,26,2、SGI Origin 2000系统,结点结构包含2个MIP
13、S R10000 CPU，通过HUB互连节点互连胖立方体拓扑结构，可达512个节点Cache一致性基于目录表的MESI协议,回下页,27,*互连网络胖立方体结构：,*路由器结构：,转上页,28,第四节 集群系统,*多计算机：MIMD结构、NORMA访存模型(MEM多地址空间)、消息传递通信机制,一、大规模并行处理机MPP,*系统结构：紧耦合(连接MB)互连、NORMA模型、计算节点(无HD/仅驻留部分OS),*互连与通信：专用IN，消息传递通信机制,29,二、集群Cluster（工作站集群COW）,1、系统结构*结构：松耦合(连接IOB)互连、NORMA模型完整节点(驻留全部OS),*互连与通
14、信：商用IN，消息传递通信机制,30,2、集群实例IBM Cluster 1350,(1)结点-HS20刀片服务器,(2)结点组-刀片服务器中心,回下页,31,(3)整机机群系统,InfiniBand网络为数据网络；以太网络为管理/控制网络,(4)软件系统,*操作系统：RedHat Linux 9.0*COW管理 ：CSM(核心Director)*作业管理：Torque for Linux*编程环境：MPI、PVM，Gun C/C+、Fortran等,转上页,32,*Torque作业管理原理：管理进程与各守护进程,33,第五节 多处理机中并行性开发,*并行性开发途径：语言、编译、算法、OS等方
15、面,一、并行程序设计语言,1、主要并行程序编程模型,*共享变量模型：通过进程实现并行性，通过共享变量实现进程间通信与同步。数据一致性由编译程序及硬件系统保证,*消息传递模型：通过进程实现并行性，通过消息传递实现进程间通信与自然同步。数据一致性由程序员保证,*数据并行模型：通过处理单元并行操作实现并行性，通过软件指令实现数据交换，SI或SP实现数据自然同步和一致性,34,2、并行程序设计语言开发方式,*设计并行程序设计语言方法：重新设计新语言扩充现有语言功能不改变现有语言，提供函数库或并行化编译系统,*并行程序编译器实现方法：设计新语言的编译器利用通用编译器，加入预编译(并行成分用传统语言)利用
16、通用编译器，链接时提供并行函数库设计新的编译器，将现有语言串行程序自动并行化,35,3、并行程序设计语言的关键技术,(1)进程管理进程创建与消亡：显式、隐式显式如FORK-JOIN，隐式如cobegin-coend、parfor等,进程激活：创建时激活、收到消息时激活一般采用创建时激活,进程粒度：一般提供中粒度(2K10K指令)进程描述手段(因进程创建代价较大),(2)进程通信与同步*通信方式：同步、异步互锁、异步非互锁通信进程间数据传递，一般采用异步方式(提高性能)同步进程间协同，一般采用同步方式(提高可靠性),36,(3)进程创建示例显式创建-FORK-JOIN(不同语言有不同形式)FOR
17、K A,J：派生一进程，本进程继续，地址J处计数器+1JOIN J： 地址J处计数器减1；当计数器值为零时，启动地址J+1处进程，否则，结束该进程,例：3个PE并行处理88矩阵乘法,DO 10 J=0，610 FORK 20，60 /*派生处理第06列进程*/J=7 /*当前进程处理第7列*/20 DO 40 I=0，7 /*处理07行*/C(I,J)=0DO 30 K=0,7 /*处理C(I,J)*/30 C(I,J)=C(I,J)+A(I,K)*B(K,J)40 CONTINUEJOIN 6060 ,37,隐式创建parforparfor i=k,n原语：,例：C(n1)=A(nn)B(n
18、1),parfor i=1, p for j=(i-1)*s+1, s*i / s=n/p/ P1:1s;P2:s+12s;Pp:n-snc(j)=0for k=1, nc(j)=c(j)+A(j,k)*B(j),38,二、串行算法到并行算法转换,1、相关类型,数据相关RAW相关，数据反相关WAR相关，数据输出相关WAW相关，控制相关条件语句,2、并行性检测 -伯恩斯坦准则,*P1、P2可并行条件：Ii读单元集，Oi写单元集I1O2=，并且I2O1=，并且O1O2=,39,3、数据相关避免主要解决反相关和输出相关，由编译程序自动完成,*重命名方法：,S：A=B+CT：D=A+EU：A=A+DV
19、：IF X0 THEN G=F+A,U：AA=A+D V：IF X0 THEN G=F+AA,*标量扩充方法：,for i=1 to n doif A(i)0 then X=B(i);else X=C(i);D(i)=X+1;,for i=1 to n dob(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、同步并行算法进程的某些段要等待其它进程，以保持同步的并行算法,*应用：只适用于进程速度波动
20、较小的情况,2、异步并行算法进程间直接通信(共享变量或传递消息)，无需等待/触发,*种类：简单异步迭代算法、自适应算法,*实现：通过进程交替进行，可并行处理,41,四、MPI并行程序设计举例,*公式转换：,*并行算法：共M个进程(0#M-1#)；第i#进程计算i、i+M、i+2Mi+(n/M-1)M个块；0#进程兼管理进程,*要求：计算,42,#include “mpi.h” #include #include double f(double x);/*定义函数f(x) */ return(4.0/(1.0+x*x); int main (int argc,char * argv) int d
21、one=0,n=0,myid,numprocs,i，namelen;double PI25DT=3.141592653589793238462643;double mypi,pi,h,sum=0,x，startwtime=0.0,endwtime;char processor_nameMPI_MAXPROCESSOR_NAME; MPI_Status status; MPI_Init(,43,if (myid=0) printf(“Please give N=”); scanf( /*各进程并行计算得到的部分和*/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;jnumprocs;j+) MPI_Recv( ,
