并行处理与体系结构课件.ppt
并行处理与体系结构,联系方式：综合楼605房间电话：,课程背景,并行处理技术已经成为现代计算机科研与发展的关键技术；其推动力来自实际应用对高性能、低价格和持续生产力日益增长的要求,计算机原理的概念计算机体系结构的概念(Amdahl)；,并行主要研究：先行方式、流水方式、向量化；并发性、同时性；数据并行性、划分；交叉、重叠、多重性、重复；时间共享、空间共享；多任务处理、多道程序、多线程方式和分布式计算。,第一章 并行计算机模型,1 计算技术的现状2 多处理机和多计算机3 多向量机和SIMD计算机4 并行计算机的抽象模型5 可扩展的范围和设计,1 计算技术的现状,一、并行技术的出现,第六代：超标量，超流水线，超长指令字？第七代：CMP（chip multiprocessor），Kunle Olukotun 博士，斯坦福大学计算机系教授，第一片CMP的设计者，推动了片上多处理器的研究热潮。,二、现代并行计算机的组成,涉及6个问题：1.计算问题 现实生活中对问题要求快速而精确地求解推动了计算机的广泛使用。科学技术中的数值计算问题人工智能(AI)问题事务处理,2.算法和数据结构 并行计算问题中的运算和通信，需要各种专门的算法和数据结构。符号处理科学计算存在的问题?,3.硬件资源 处理机、存储器和外围设备组成了计算机系统的硬件核心外围设备可以直接或通过局域网和广域网与主机相连,4.操作系统 管理用户程序执行过程中的资源分配和再分配。映射是一种算法结构与硬件结构相匹配的双向过程。并行操作系统的映射算法和数据结构到机器结构的映射包括处理机调度、存储器映象、处理器间的通信等。这些问题通常都与系统结构有关。,5.系统软件支持 存在的问题：不能以通用和可移植方式进行并行程序设计开发并行编程环境：一种与系统结构无关的语言、编译器和软件工具。,两个方向：对于开发并行语言，将着眼点放在语言执行的效率、对不同机器的可移植性、与现有的顺序语言的兼容性、并行性的表达和编程的简便性等上面。可以设计一种新的语言，逐步扩展现有的顺序语言。新语言有用显式高级结构描述并行性的优点，但是新语言往往与现有语言不兼容，而需要新的编译器或者通过新的步骤才能利用现有的编译器。大部分系统选用的是语言扩展方式。,6.编译器支持 改进编译器有三种途径：预处理程序;预编译器;并行化编译器。,预处理程序采用顺序编译器和目标计算机的低层程序库实现高级并行结构。预编译器需要程序流分析、相关性检查和有限的优化来检测并行性。联接过程效果取决于预处理程序、预编译器、并行化编译器、加载程序和操作系统支持的功效。由于程序行为的不可预测，现有的编译器在检测所有类型的并行性时都不是完全自动或完全智能进行的。存在一些有效的方法：将编译器命令插入源代码，帮编译器做出较好的结果。这样，用户可与编译器进行交互重构程序，这已被证明对提高并行计算机性能是十分有用的。,7.并行程序的设计环境 隐式并行性伊利诺依大学的David Kuck和Rice大学的KenKennedy以及他们的合作者都已采用这种隐式并行性方法。显式并行性 加州理工学院的CharlesSeitz和麻省理工学院的WilliamDaily在开发多计算机时采用了这种显式方法。,总结：要使一个环境对用户更加友好，必须要有专用软件工具。一些工具是传统高级语言的并行扩展；一些则是集成环境其中包括提供不同级别的程序抽象、验证、测试、查错和调试等各种工具；性能预测和监控；辅助程序开发的可视化支持、性能测量以及计算结果的图形显示及动画表示,三、计算机系统结构向高性能发展历程,主要探讨顺序到并行的过程,1.先行、并行性和流水线技术用先行技术预取指令可使IE(指令读取译码和执行)支持功能并行性的方法有两种：一种是同时使用多个功能部件；另一种是在不同处理级分别实施流水线技术。流水线指令执行、流水线算术计算和存储器存取操作。,2.Flynn分类法MkhealFlynn(1972)根据指令和数据流概念提出了不同计算机系统结构的分类法。,传统的顺序机被称为SISD(单指令流单数据流)计算机。向量计算机-标量和向量硬件装备，或以SIMD(单指令流多数据流)机的形式出现。并行计算机则属MIMD(多指令流多数据流)机,MISD(多指令流单数据流)机在执行不同的指令流时，同一数据流通过处理机线性阵列。这种系统结构也就是所谓流水线执行特定算法的脉动阵列(Systolicarrays)。由卡内基梅隆大学的美籍华人学者HTKung于1978年提出的。这一结构是随着VLSI技术的发展和各种大运算量的信号/图象处理及科学计算的运算要求而建立起来的。,脉动阵列的特点：处理单元简单流水算法专业,例：数据流计算机数据流的计算模型-试图使并行计算的基本方面在机器层显式化，而不利用有可能限制程序并行性的人为约束。它的想法是程序由一个基本数据依赖图来表示；一个指令可能在获得了它的操作数后的任意时刻被执行，不是显式控制线性程序列的固定组合。,3.并行向量计算机 真正的并行计算机是那些以MIMD模式执行程序的计算机。并行计算机有两大类，即共享存储型多处理机和消息传递型多计算机。多处理机和多计算机之间的主要差别就在于存储器共享和处理机间通信机制的不同。多处理机系统中的处理机通过公用存储器的共享变量实现互相通信。多计算机系统的每个计算机结点有一个与其它结点不共享的本地存储器。处理机之间的通信通过结点间的消息传递来实现。,显式向量计算机指令是随向量处理机的问世而出现的。一台向量处理机可以装备有用硬件或固件并发控制的多条向量流水线。,4.开发层次 Lionel Ni的最新分类法(1990)，并行计算机的分层开发可表示于下图,四、性能的系统属性,1.时钟频率和CPI 主频当前数字计算机的CPU(或简称处理机)是由一个恒定周期(，以ns表示)的时钟驱动的。周期的倒数是时钟频率(1/）（以MHz表示）。,程序的规模是由其指令数(Ic)，也就是程序串要执行的机器指令数来决定的。执行不同的机器指令所需要的时钟周期数也是不一样的。一条指令的周期数(CPl)就成为衡量执行每条指令所需时间的重要参数。,2.性能因子执行程序所需的CPU时间：设Ic为已知程序的指令条数。执行程序所需的CPU时间(T，以秒/程序表示)可用三个主要因素的乘积来计算：T Ic CPI,可将上式重写成如下形式：T Ic(p+mk)一种指令类型的CPI可分为完成指令所需的处理机周期数和存储器周期数两部分。完整的指令执行过程可能包含一至四次存储器访问(一次用于取指令，两次用于取操作数，一次用于存储结果)，这与指令的类型有关。,式中的细化：p为指令译码和执行所需的处理机周期数;m为所需的存储器访问次数;k为存储周期与处理机周期之比;Ic为指令条数，为处理机周期。,3.系统属性计算机系统属性可以由五元组表示：(Ic，p，m，k，),五个量可以称为性能因子。与四种系统属性有关：指令系统结构、编译技术、CPU实现和控制技术、高速缓存与存储器层次结构。,推广-并行系统的性能属性机器规模 n处理机个数时钟速率 f工作负载 W-程序中的计算操作数顺序执行时间 T1并行执行时间 Tn速度 Pn=W/Tn加速比 Sn=T1/Tn效率 En=Sn/n 利用率 Un=Pn/n(Ppeak)启动时间 t0 渐进带宽 r,4.Mips速率(其中C是总的周期数),5.吞吐率系统的吞吐率:系统在单位时间内能执行多少个程序，这称为系统的吞吐率(单位为程序数秒)Ws。,在多道程序系统中，系统吞吐率常低于CPU吞吐率Wp。Wp可用下式表示：,或：Wp=(MIPS)106Ic Wp的单位是程序数秒。,CPU吞吐率是根据MIPS速率和程序的平均长度(Ic)来衡量机器每秒钟能执行多少个程序的尺度。WsWp，用多道程序或分时操作在CPU上交叉执行多个程序时，IO、编译器和操作系统产生的额外系统开销所造成的。,总结：并行的产生并行背景下的计算问题串行向并行的演化并行的性能与系统的关系,
