并行处理与体系结构课件.ppt

1、并行处理与体系结构并行处理与体系结构联系方式：综合楼联系方式：综合楼605房间房间电话：电话：课程背景课程背景n并行处理技术已经成为现代计并行处理技术已经成为现代计算机科研与发展的关键技术；算机科研与发展的关键技术；q其推动力来自实际应用对高性其推动力来自实际应用对高性能、低价格和持续生产力日益能、低价格和持续生产力日益增长的要求增长的要求 n计算机原理的概念计算机原理的概念n计算机体系结构的概念计算机体系结构的概念(Amdahl)；n并行主要研究：并行主要研究：q先行方式、流水方式、向量化；先行方式、流水方式、向量化；q并发性、同时性；并发性、同时性；q数据并行性、划分；数据并行性、划分；q

2、交叉、重叠、多重性、重复；交叉、重叠、多重性、重复；q时间共享、空间共享；时间共享、空间共享；q多任务处理、多道程序、多线程方多任务处理、多道程序、多线程方式和分布式计算。式和分布式计算。q第一章第一章 并行计算机模型并行计算机模型n 1 1 计算技术的现状计算技术的现状n 2 2 多处理机和多计算机多处理机和多计算机n 3 3 多向量机和多向量机和SIMDSIMD计算机计算机n 4 4 并行计算机的抽象模型并行计算机的抽象模型n 5 5 可扩展的范围和设计可扩展的范围和设计 1 1 计算技术的现状计算技术的现状n一、并行技术的出现一、并行技术的出现n第六代：超标量，超流水线，超长指令字？n第

3、七代：CMP（chip multiprocessor），Kunle Olukotun 博士，斯坦福大学计算机系教授，第一片CMP的设计者，推动了片上多处理器的研究热潮。n二、现代并行计算机的组成二、现代并行计算机的组成n涉及涉及6 6个问题：个问题：n1.1.计算问题计算问题 q现实生活中对问题要求快速而精确地现实生活中对问题要求快速而精确地求解推动了计算机的广泛使用。求解推动了计算机的广泛使用。n科学技术中的数值计算问题科学技术中的数值计算问题n人工智能人工智能(AI)(AI)问题问题n事务处理事务处理n2.2.算法和数据结构算法和数据结构 n并行计算问题中的并行计算问题中的运算和通信运算和

4、通信，需要，需要各种专门的算法和数据结构。各种专门的算法和数据结构。n符号处理符号处理n科学计算科学计算n存在的问题存在的问题? ?n3.3.硬件资源硬件资源 n处理机、存储器和外围设备组成了计处理机、存储器和外围设备组成了计算机系统的硬件核心算机系统的硬件核心n外围设备可以直接或通过局域网和广外围设备可以直接或通过局域网和广域网与主机相连域网与主机相连n4.4.操作系统操作系统 n管理用户程序执行过程中的管理用户程序执行过程中的资源分配资源分配和再分配和再分配。n映射是一种算法结构与硬件结构相匹映射是一种算法结构与硬件结构相匹配的双向过程。配的双向过程。n并行操作系统的映射并行操作系统的映射

5、q算法和数据结构到机器结构的映射包括处算法和数据结构到机器结构的映射包括处理机调度、存储器映象、处理器间的通信理机调度、存储器映象、处理器间的通信等。等。q这些问题通常都与系统结构有关。这些问题通常都与系统结构有关。n5.系统软件支持系统软件支持 n存在的问题：不能以通用和可存在的问题：不能以通用和可移植方式进行并行程序设计移植方式进行并行程序设计n开发并行编程环境：开发并行编程环境：q一种与系统结构无关的语言、编译器一种与系统结构无关的语言、编译器和软件工具。和软件工具。n两个方向：两个方向：q对于开发并行语言，对于开发并行语言，n将着眼点放在语言执行的效率、对不同机将着眼点放在语言执行的效

6、率、对不同机器的可移植性、与现有的顺序语言的兼容器的可移植性、与现有的顺序语言的兼容性、并行性的表达和编程的简便性等上面。性、并行性的表达和编程的简便性等上面。可以设计一种新的语言，可以设计一种新的语言，q逐步扩展现有的顺序语言。逐步扩展现有的顺序语言。n新语言有用显式高级结构描述并行性的优新语言有用显式高级结构描述并行性的优点，但是新语言往往与现有语言不兼容，点，但是新语言往往与现有语言不兼容，而需要新的编译器或者通过新的步骤才能而需要新的编译器或者通过新的步骤才能利用现有的编译器。大部分系统选用的是利用现有的编译器。大部分系统选用的是语言扩展方式。语言扩展方式。n6.编译器支持编译器支持

7、n改进编译器有三种途径：改进编译器有三种途径：q预处理程序预处理程序; ;q预编译器预编译器; ;q并行化编译器。并行化编译器。n预处理程序采用顺序编译器和目标计算机的低预处理程序采用顺序编译器和目标计算机的低层程序库实现高级并行结构。层程序库实现高级并行结构。q预编译器需要程序流分析、相关性检查和有限的优预编译器需要程序流分析、相关性检查和有限的优化来检测并行性。化来检测并行性。n联接过程联接过程q效果取决于预处理程序、预编译器、并行化编译器、效果取决于预处理程序、预编译器、并行化编译器、加载程序和操作系统支持的功效。由于程序行为的加载程序和操作系统支持的功效。由于程序行为的不可预测，现有的

8、编译器在检测所有类型的并行性不可预测，现有的编译器在检测所有类型的并行性时都不是完全自动或完全智能进行的。时都不是完全自动或完全智能进行的。n存在一些有效的方法：存在一些有效的方法：q将编译器命令插入源代码，帮编译器做出较好的结将编译器命令插入源代码，帮编译器做出较好的结果。这样，用户可与编译器进行交互重构程序，这果。这样，用户可与编译器进行交互重构程序，这已被证明对提高并行计算机性能是十分有用的。已被证明对提高并行计算机性能是十分有用的。n7.7.并行程序的设计环境并行程序的设计环境n 隐式并行性隐式并行性q伊利诺依大学的伊利诺依大学的David KuckDavid Kuck和和RiceRi

9、ce大学大学的的KenKennedyKenKennedy以及他们的合作者都已采以及他们的合作者都已采用这种隐式并行性方法。用这种隐式并行性方法。n 显式并行性显式并行性 q加州理工学院的加州理工学院的CharlesSeitzCharlesSeitz和麻省理和麻省理工学院的工学院的WilliamDailyWilliamDaily在开发多计算机在开发多计算机时采用了这种显式方法。时采用了这种显式方法。 n总结：总结：n要使一个环境对用户更加友好，必须要使一个环境对用户更加友好，必须要有专用软件工具。要有专用软件工具。n一些工具是传统高级语言的并行扩展；一些工具是传统高级语言的并行扩展；n一些则是集

10、成环境一些则是集成环境q其中包括提供不同级别的程序抽象、验证、其中包括提供不同级别的程序抽象、验证、测试、查错和调试等各种工具；性能预测和测试、查错和调试等各种工具；性能预测和监控；辅助程序开发的可视化支持、性能测监控；辅助程序开发的可视化支持、性能测量以及计算结果的图形显示及动画表示量以及计算结果的图形显示及动画表示n三、计算机系统结构向高性能三、计算机系统结构向高性能发展历程发展历程n主要探讨顺序到并行的过程主要探讨顺序到并行的过程n1.1.先行、并行性和流水线技术先行、并行性和流水线技术n用先行技术预取指令可使用先行技术预取指令可使I IE(E(指令指令读取译码和执行读取译码和执行) )

11、q支持功能并行性的方法有两种：支持功能并行性的方法有两种：q一种是同时使用多个功能部件；一种是同时使用多个功能部件；q另一种是在不同处理级分别实施流水线另一种是在不同处理级分别实施流水线技术。技术。 n流水线指令执行、流水线算术计算和存储流水线指令执行、流水线算术计算和存储器存取操作。器存取操作。n2.Flynn2.Flynn分类法分类法qMkhealFlynn(1972)MkhealFlynn(1972)根据指令和数据流概根据指令和数据流概念提出了不同计算机系统结构的分类法。念提出了不同计算机系统结构的分类法。n传统的顺序机被称为传统的顺序机被称为SISD(SISD(单指令流单指令流单数据流

12、单数据流) )计算机。计算机。n向量计算机向量计算机-标量和向量硬件装备，标量和向量硬件装备，或以或以SIMD(SIMD(单指令流多数据流单指令流多数据流) )机的形机的形式出现。式出现。n并行计算机则属并行计算机则属MIMD(MIMD(多指令流多数多指令流多数据流据流) )机机nMISD(MISD(多指令流单数据流多指令流单数据流) )机机q在执行不同的指令流时，同一数据流通在执行不同的指令流时，同一数据流通过处理机线性阵列。这种系统结构也就过处理机线性阵列。这种系统结构也就是所谓流水线执行特定算法的脉动阵列是所谓流水线执行特定算法的脉动阵列(Systolicarrays)(Systolic

13、arrays)。q由卡内基由卡内基梅隆大学的美籍华人学者梅隆大学的美籍华人学者H HT TKungKung于于19781978年提出的。年提出的。n这一结构是随着这一结构是随着VLSIVLSI技术的发展和各技术的发展和各种大运算量的信号种大运算量的信号/ /图象处理及科学图象处理及科学计算的运算要求而建立起来的。计算的运算要求而建立起来的。n脉动阵列的特点：脉动阵列的特点：q处理单元简单处理单元简单q流水流水q算法专业算法专业n例：数据流计算机例：数据流计算机n数据流的计算模型数据流的计算模型-试图使并行计算的试图使并行计算的基本方面在机器层显式化，而不利用有基本方面在机器层显式化，而不利用有

14、可能限制程序并行性的人为约束。可能限制程序并行性的人为约束。q它的想法是程序由一个基本数据依赖图来表它的想法是程序由一个基本数据依赖图来表示；示；q一个指令可能在获得了它的操作数后的任意一个指令可能在获得了它的操作数后的任意时刻被执行，不是显式控制线性程序列的固时刻被执行，不是显式控制线性程序列的固定组合。定组合。n3.3.并行向量计算机并行向量计算机 n真正的并行计算机是那些以真正的并行计算机是那些以MIMDMIMD模式执行程序的模式执行程序的计算机。计算机。n并行计算机有两大类，即共享存储型多处理机和并行计算机有两大类，即共享存储型多处理机和消息传递型多计算机。消息传递型多计算机。n多处理

15、机和多计算机之间的主要差别就在多处理机和多计算机之间的主要差别就在于存储器共享和处理机间通信机制的不同。于存储器共享和处理机间通信机制的不同。n多处理机系统中的处理机通过公用存储器多处理机系统中的处理机通过公用存储器的共享变量实现互相通信。的共享变量实现互相通信。n多计算机系统的每个计算机结点有一个与多计算机系统的每个计算机结点有一个与其它结点不共享的本地存储器。处理机之其它结点不共享的本地存储器。处理机之间的通信通过结点间的消息传递来实现。间的通信通过结点间的消息传递来实现。n显式向量计算机显式向量计算机q指令是随向量处理机的问世而出现的。指令是随向量处理机的问世而出现的。一台向量处理机可以

16、装备有用硬件或固一台向量处理机可以装备有用硬件或固件并发控制的多条向量流水线。件并发控制的多条向量流水线。n4.开发层次 nLionel NiLionel Ni的最新分类法的最新分类法(1990)(1990)，n并行计算机的分层开发可表示于下图并行计算机的分层开发可表示于下图n四、性能的系统属性四、性能的系统属性n1 1 . .时钟频率和时钟频率和CPICPI n主频主频q当前数字计算机的当前数字计算机的CPU(CPU(或简称处理或简称处理机机) )是由一个恒定周期是由一个恒定周期( (，以，以nsns表表示示) )的时钟驱动的。的时钟驱动的。q周期的倒数是时钟频率周期的倒数是时钟频率n( (

17、1/1/ ）（以）（以MHzMHz表示）。表示）。n程序的规模程序的规模q是由其指令数是由其指令数(Ic)(Ic)，也就是程序串要执，也就是程序串要执行的机器指令数来决定的。执行不同的行的机器指令数来决定的。执行不同的机器指令所需要的时钟周期数也是不一机器指令所需要的时钟周期数也是不一样的。样的。q一条指令的周期数一条指令的周期数(CPl)(CPl)就成为衡量执就成为衡量执行每条指令所需时间的重要参数。行每条指令所需时间的重要参数。n2.2.性能因子性能因子n执行程序所需的执行程序所需的CPUCPU时间：时间：n设设IcIc为已知程序的指令条数。执为已知程序的指令条数。执行程序所需的行程序所需

18、的CPUCPU时间时间(T(T，以秒，以秒/ /程序表示程序表示) )可用三个主要因素的乘可用三个主要因素的乘积来计算：积来计算：n T T IcIc CPI CPI n可将上式重写成如下形式：可将上式重写成如下形式： n T T IcIc (p+m (p+mk) k) q一种指令类型的一种指令类型的CPICPI可分为完成指令可分为完成指令所需的处理机周期数和存储器周期数所需的处理机周期数和存储器周期数两部分。两部分。q完整的指令执行过程可能包含一至四完整的指令执行过程可能包含一至四次存储器访问次存储器访问( (一次用于取指令，两一次用于取指令，两次用于取操作数，一次用于存储结次用于取操作数，

19、一次用于存储结果果) )，这与指令的类型有关。，这与指令的类型有关。n式中的细化：式中的细化：qp p为指令译码和执行所需的处理机周为指令译码和执行所需的处理机周期数期数; ;qm m为所需的存储器访问次数为所需的存储器访问次数; ;qk k为存储周期与处理机周期之比为存储周期与处理机周期之比; ;qIcIc为指令条数，为处理机周期。为指令条数，为处理机周期。n3.3.系统属性系统属性n计算机系统属性可以由五元组表计算机系统属性可以由五元组表示：示：n(Ic(Ic，p p，m m，k k，),),n五个量可以称为性能因子。五个量可以称为性能因子。q与四种系统属性有关：指令系统结构、与四种系统属

20、性有关：指令系统结构、编译技术、编译技术、CPUCPU实现和控制技术、高速缓实现和控制技术、高速缓存与存储器层次结构。存与存储器层次结构。n推广推广-并行系统的性能属性并行系统的性能属性q机器规模机器规模 n n处理机个数处理机个数q时钟速率时钟速率 f fq工作负载工作负载 W-W-程序中的计算操作数程序中的计算操作数q顺序执行时间顺序执行时间 T1T1q并行执行时间并行执行时间 TnTnq速度速度 Pn=W/TnPn=W/Tnq加速比加速比 Sn=T1/TnSn=T1/Tnq效率效率 En=Sn/n En=Sn/n q利用率利用率 Un=Pn/n(Ppeak)Un=Pn/n(Ppeak)q

21、启动时间启动时间 t0 t0 q渐进带宽渐进带宽 rrn4.Mips4.Mips速率速率( (其中其中C C是总的周期数是总的周期数) )n5.5.吞吐率吞吐率n系统的吞吐率系统的吞吐率: :n系统在单位时间内能执行多少个系统在单位时间内能执行多少个程序，这称为系统的吞吐率程序，这称为系统的吞吐率( (单位单位为程序数秒为程序数秒) ) Ws 。n在多道程序系统中，系统吞吐率常低在多道程序系统中，系统吞吐率常低于于CPUCPU吞吐率吞吐率WpWp。WpWp可用下式表示：可用下式表示： n或：或： Wp=(MIPS)Wp=(MIPS)10106 6IcIc nWpWp的单位是程序数秒。的单位是程序数秒。nCPUCPU吞吐率是根据吞吐率是根据MIPSMIPS速率和程序的速率和程序的平均长度平均长度(Ic)(Ic)来衡量机器每秒钟能执来衡量机器每秒钟能执行多少个程序的尺度。行多少个程序的尺度。nWsWpWsWp，q用多道程序或分时操作在用多道程序或分时操作在CPUCPU上交叉执上交叉执行多个程序时，行多个程序时，I IO O、编译器和操作系、编译器和操作系统产生的额外系统开销所造成的。统产生的额外系统开销所造成的。n总结：一并行的产生二并行背景下的计算问题三串行向并行的演化四并行的性能与系统的关系