计算机组织与结构-第8章-并行组织课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《计算机组织与结构-第8章-并行组织课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 组织 结构 并行 课件
- 资源描述:
-
1、本章结构18.1 计算机系统并行性28.2 流水线技术38.3 多处理机系统48.4 机群系统8.1 计算机系统的并行性 研究计算机体系结构的目的:提高计算机系统的性能;计算机体系结构的重要研究内容之一:开发计算机系统的并行性。计算机体系结构、计算机组织和计算机实现计算机体系结构、计算机组织和计算机实现三者互不相同但又互相影响计算机组织计算机组织(Computer Organization):所研究的是计算机系统的逻辑实现;计算机实现计算机实现(Computer Implementation):所研究的是计算机系统的物理实现。计算机体系结计算机体系结构构:是程序员所看到的计算机的属性,即概念性
2、结构和功能特性;体系结构中的并行性n现代计算机的一个共同特点是大量采用并行技术,使计算机的性能得以不断提高。n并行性并行性(parallelism):指的是在同一时刻或是同一时间间隔内完成两种或两种以上性质相同或不相同的工作。只要时间上互相重叠,就存在并行性,其包含同时性和并发性两层含义。n同时性同时性(simultaneity):指两个或多个事件在同一时刻发生的并行性;n并发性并发性(concurrency):指两个或多个事件在同一时间间隔内发生的并行性。并行性等级划分:从执行程序角度 指令内部并行指令内部并行:指的是指令内部的微操作之间的并行。指令级并行指令级并行:指的是并行执行两条或多条
3、指令,就是指令之间的并行。线程级并行线程级并行:指的是并发执行多个线程,通常是以一个进程内控制派生的多个线程为调度单位。任务级或过程级并行任务级或过程级并行:指的是并行执行两个或多个过程或任务(程序段)。作业或程序级并行作业或程序级并行:指的是在多个作业或程序间的并行。并行性等级划分:从处理数据的角度 字串位串字串位串:指的是同时只对一个字的一位进行处理。字串位并字串位并:指的是同时对一个字的全部位进行处理,不同字之间是串行的。字并位串字并位串:指的是同时对许多字的同一位(称位片)进行处理。全并行全并行:指的是同时对许多字的全部或部分位进行处理。提高并行性的技术途径提高并行性的技术途径最低耦合
4、1、时间重叠2、资源重复3、资源共享提高并行性的技术途径提高并行性的技术途径1、时间重叠 时间重叠时间重叠:多个处理过程在时间上相互错开,轮流重叠地使用同一套硬件设备的各个部分,以加快硬件周转而赢得速度。实现时间重叠的基础:部件功能专用化。时间重叠的实质:把一件工作按功能分割为若干个相互联系的部分;然后把每一部分指定给专门的部件完成;最后按时间重叠原则把各部分执行过程在时间上重叠起来,使所有部件依次分工完成一组同样的工作。流水线技术流水线技术就是时间重叠的典型应用。时间重叠举例 例:一条指令的执行可以看成是由四个过程组成,即取指令、指令译码、指令执行和写结果。(a)4个子过程的指令流水线4条指
5、令流水的时空图 2、资源重复 资源重复资源重复:根据“以数量取胜”的原则来实现并行,其付出的代价是在空间上通过重复地设置资源,尤其是硬件资源,以提高计算机系统的性能。资源重复的并行举例3、资源共享 资源共享资源共享是一种软件方法的并行,它使多个任务按一定时间顺序轮流使用同一套硬件设备。资源共享的实质就是用单处理机模拟多处理机的功能,形成所谓虚拟机的概念。多机系统的并行性 多机系统:多机系统:包括多处理机系统和多计算机系统。多机系统也遵循时间重叠、资源重复和资源共享这三种基本的技术途径,向着三种不同的多处理机方向发展。多机系统的耦合度 n耦合度耦合度:反映多机系统的各机器之间的物理连接的紧密程度
6、和交互作用能力的强弱。最低耦合最低耦合松散耦合紧密耦合多机系统的耦合度分为最低耦合 n最低耦合最低耦合 耦合度最低的系统。除通过某种中间存储介质之外,各计算机之间没有物理连接,也无共享的联机硬件资源。松散耦合或间接耦合系统 松耦合系统松耦合系统的各处理机间通过共享I/O子系统、通道或通信线路实现处理机间通信和互连,不共享主存,但可共享某些外围设备(例如磁盘、磁带等),机间的相互作用是在文件或数据集一级进行。松散耦合多处理机由多个处理机、一个通道、一个仲裁开关和消息传送系统组成。每个处理机带有一个局部存储器和一组I/O设备。在仲裁开关的通道中有高速通信存储,用来缓冲传送的信息块。紧密耦合系统或直
7、接耦合系统 紧耦合多处理机系统紧耦合多处理机系统,其处理机间物理连接的频带较高,它们往往通过总线或高速开关实现互连,可以共享主存,各处理机之间是通过互连网络共享主存的。一般地,紧耦合系统由P台处理机、m个存储器模块、d个I/O通道和三个互连网络构成。处理机-存储器网络实现处理机与各存储模块的连接;处理机中断信号网络实现多处理机之间的互连;处理机-I/O互连网络实现处理机与外设的连接。每个处理机可自带局部存储器,也可自带Cache存储器模块,可采用流水工作方式。紧耦合系统多用于并行作业中的多任务,一般处理机是同构的。并行计算机体系结构的分类并行计算机体系结构的分类 Flynn(弗林)分类法(弗林
8、)分类法:美国的弗林(Michael Flynn)于1966年提出的分类法这种分类法主要依据指令流和数据流的多倍性关系来对计算机系统进行分类。指令流是指机器执行的指令序列;数据流是指由指令流调用的数据序列,包括输入数据和中间结果;多倍性是指在系统瓶颈部件上处于同一执行阶段的指令或数据的最大可能数。Flynn分类法 按照Flynn分类法,把计算机系统分成四类,分别是:单指令流单数据流(SISD:Single Instruction Stream Single Data Stream)单指令流多数据流(SIMD:Single Instruction Stream Multiple Data Str
9、eam)多指令流单数据流(MISD:Multiple Instruction Stream Single Data Stream)多指令流多数据流(MIMD:Multiple Instruction Stream Multiple Data Stream)SISD计算机 SISD实际上就是传统的单处理器计算机。只要指令部件每次只对一条指令译码,只对一个操作部件分配数据,就属于SISD系统。SISD计算机 SIMD计算机 SIMD中具有代表性的例子是相联处理机和阵列处理机。特殊地,如果“多倍性”中“处于同一执行阶段”被理解成一条指令的操作全过程,那么流水线处理机的不同子过程操作就可以看作是不同子
10、部件处理的是同一条指令的不同阶段的数据,此时流水线处理机也可以算是SIMD。SIMD计算机 MISD计算机 MISD的一般形式是有n个处理单元,按n条不同指令的要求对同一个数据流及其中间结果进行不同的处理,一个处理单元的输出作为另一个处理单元的输入。MISD计算机 MIMD计算机 MIMD系统能实现作业、任务、指令、数组各级的并行,是能实现较为全面的并行处理的多机系统。MIMD一般形式是按n条不同指令的要求在n个控制单元的控制下对n个数据流及其中间结果进行不同的处理。MIMD计算机 知识拓展:数据流机与归约机知识拓展:数据流机与归约机 数据流机的两种驱动方式:种是数据驱动方式,即一条指令当且仅
11、当所需的操作数准备就绪时便开始执行,完全不需要指令计数器的控制。另一种是需求驱动方式,即任何操作都是纯函数操作,只有当某一个函数需要某个自变量时才驱动对该自变量的求值操作,即每一数据流操作都是消耗一组输入值,产生一组输出值而不产生副作用,这就确保任何两个并发操作可以任意次序执行,而不会产生干扰。归约机归约机 归约机:一种面向函数程序设计语言的计算机,指令的执行顺序取决于这些指令产生结果数据的需求,而这种需求又源于函数式程序设计语言对表达式的归约。按其归约模型可分为:串归约机 图归约机两者的主要区别是对函数表达式所使用的存储方式不同,前者以字符串形式存储而后者以图的形式存储。8.2流水线技术 计
12、算机中的流水线技术是一种利用资源重叠技术提高机器性能的并行处理技术,它能在不增加机器硬部件的情况下,通过对某一部件功能进行合理的分解与设计,有效提高部件的处理速度。流水线的分类流水线的分类 1.按照计算机处理的级别来分类按照计算机处理的级别来分类 按照计算机处理的级别来分类流水线可以分为按照计算机处理的级别来分类流水线可以分为部件级、指令级和处理机级流水线机。部件级、指令级和处理机级流水线机。部件级流水指的是构成部件内的各个子部件间的流水,比如运算器内浮点加、减运算的流水。指令级流水指的是构成计算机系统的多个处理机之间的流水,又称为宏流水。处理机级流水指的是构成处理机的各部件之间的流水,比如一
13、条指令分成“取指”、“分析”、“执行”后,这三者之间的流水。流水线的分类流水线的分类2.按照流水线可以完成的动作的数量来分类按照流水线可以完成的动作的数量来分类 按照流水线可以完成的动作的数量来分类,又可按照流水线可以完成的动作的数量来分类,又可以分为单功能流水线和多功能流水线。以分为单功能流水线和多功能流水线。单功能流水线指的是只能实现单一功能的流单功能流水线指的是只能实现单一功能的流水,比如只能实现浮点加减而不能实现浮点水,比如只能实现浮点加减而不能实现浮点乘除的流水线。当然,如果要完成多种功能乘除的流水线。当然,如果要完成多种功能的流水可以将多个单功能的流水线组合起来的流水可以将多个单功
14、能的流水线组合起来实现。实现。多功能流水线指的是在同一流水线的各个段多功能流水线指的是在同一流水线的各个段之间可以有多种不同的连接方式以实现多种之间可以有多种不同的连接方式以实现多种不同的功能或运算。不同的功能或运算。多功能流水线的实现 同一个流水线在不同连接下可以分别实现同一个流水线在不同连接下可以分别实现浮点加、减运算时的连接和定点乘、除法运算时的连接浮点加、减运算时的连接和定点乘、除法运算时的连接流水线的分类流水线的分类3.按照多功能流水线的各个段是否允许同时进行多种不同功能的连接流水来分类按照多功能流水线的各个段是否允许同时进行多种不同功能的连接流水,则可以把流水又分成静态流水线和动态
15、流水线。静态流水线指的是在某一段时间内各功能段只能按照一种功能连接形成流水线,只能等待该流水线上全部任务流空后,才能切换成另一种功能连接进行流水。动态流水线是指在同一时间内,当某些段正在实现某种运算时,另一些段却可以实现另一种运算。静态流水线时空图假设先后有二批任务要完成,第一批是假设先后有二批任务要完成,第一批是n个任务的浮点加、减运算;个任务的浮点加、减运算;第二批任务是第二批任务是AE共共5个任务的定点乘法运算个任务的定点乘法运算按照静态方式形成流水线按照静态方式形成流水线动态流水线时空图假设先后有二批任务要完成,第一批是假设先后有二批任务要完成,第一批是n个任务的浮点加、减运算;个任务
16、的浮点加、减运算;第二批任务是第二批任务是AE共共5个任务的定点乘法运算个任务的定点乘法运算按照动态方式形成流水线按照动态方式形成流水线流水线的分类流水线的分类4.按照流水线内部的功能部件的连接方式(如各功能段之间是否有反馈回路)来分类按照流水线内部的功能部件的连接方式(如各功能段之间是否有反馈回路)来分类,则有线性流水线和非线性流水线。流水线各段之间串行连接,各段只经过一次,且各功能段之间没有反馈回路的,就称为线性流水线。反之,如果流水线除了有串行连接的通路,还有反馈回路,并且往往使得任务流经流水线时需多次经过某个段或越过某些段的,就称之为非线性流水线。非线性流水线举例 流水线的分类流水线的
17、分类5.按照机器可处理的对象来分类 如果按照机器可处理的对象来分类,还可以分为标量流水线和向量流水线。l按照机器可处理的对象来分类实质就是从机器所具有的数据表示来分类,此时一般也意味着针对该机器所具有的这些数据表示会获得相应的硬件支持。所以标量流水机意味着该机器没有向量数据表示,只能用标量循环方式来处理向量和数组。l向量流水机则意味着该机器有向量数据表示,并且硬件上有相应的部件的支持,比如机器上一般都会设置有向量指令和向量运算硬件,能流水地处理向量和数组中的各个元素。显然,向量流水机是向量数据表示和流水技术相结合的产物。流水线的主要性能参数流水线的主要性能参数 衡量一种流水线处理方式的性能的高
18、低的参数主要有吞吐率、加速比吞吐率、加速比和效率效率。吞吐率吞吐率(TP,Thoughput Rate),指的是计算机中的流水线在单位时间内能流出的任务数或结果数。流水线的吞吐率可以进一步分为最大吞吐率和实际吞吐率。在线性流水线中,最大吞吐率Tp max1/T1/max(T1,.,Ti,.,Tm),其中,m是流水线的段数,Ti表示的是第i段的执行时间。最大吞吐率受到了瓶颈段的约束最大吞吐率受到了瓶颈段的约束 例如,某流水线有4个段,其中2号段由于需用时3t,所以2号段是瓶颈段,见图(a);5个任务流经该流水线时的流水效果的实际情况如图(b)所示,显然流水速度受到了2号瓶颈的限制。细分瓶颈段 把
19、瓶颈部分的流水线分拆,以便任务可以充分流水处理 并联瓶颈段 在瓶颈部分设置多条相同流水段,并行处理 流水线的实际效率 分析并计算出流水线的实际效率 分析实际吞吐率的时空图 加速比(Speed Ratio)假设该流水线各子功能段执行时间均为t,流水段有m个段,那么n个任务非流水顺序完成需要nmt的时间;流水完成则需要mt+(n-1)t的时间;因此,流水方式工作的加速比加速比为:nmmtntmtmnSp11)1(所以在流水线各子功能段执行时间均相等的情况下,仅当nm时,其加速比才能趋近于最大值m,即流水线的段数。效率(Efficiency)效率效率(Efficiency):也称流水线设备的时间利用
20、率,又称使用效率,它指的是流水线中各个部件的利用率,也就是设备的实际使用时间占整个运行时间的比值。以前面“分析实际吞吐率的时空图”来看,在T时间里流水线的各段效率都相同,均为0,整个流水线的效率就是,计算如下:TmtnmmmmnmnTtnmm0210211n效率实际上就是n个任务占用的时空区面积与m个段总的时空区面积的比值。显然,只有当nm时,才趋近于1。流水线的相关问题流水线的相关问题 结构相关结构相关:当指令在重叠执行过程中,硬件资源满足不了指令重叠执行的要求,两条或两条以上指令争用同一资源而引起的冲突,因此,结构相关又称为资源相关。数据相关数据相关:当一条指令需要用到前面指令的执行结果,
21、而这些指令均在流水线中重叠执行时,就有可能产生数据相关。控制相关冲突控制相关冲突:是由转移指令引起的。当执行转移指令时,依据转移条件的产生结果,可能为顺序取下条指令;也可能转移到新的目标地址取指令,从而使流水线发生断流。结构相关例如,假设一条指令流水线由5段组成,分别为取指令(IF)、指令译码(ID)、取操作数(MEM)、执行运算(EX)和写寄存器(WR)。若指令I2的取操作数和指令I4的取指令都需要访问存储器。若机器中只有一个单端口存储模块,那么I2的取操作数和指令I4的取指令就产生了访存冲突,两个操作无法同时进行,这就是一种典型的资源冲突。结构相关解决办法n 解决办法:1、在机器中增加存储
22、器模块,如使用双端口存储器,使指令和数据分别存放在不同的存储器模块中,这样,取指令和取操作数就不会发生冲突。2、当发生取指令或取操作数冲突时,将其中一个操作的执行时间推迟,如下图所示。当然,这样的话也就是发生了流水线的断流,流水线的吞吐率就下降了。访存相关引起流水线断流 数据相关 在流水计算机中,指令的处理是重叠进行的,前一条指令还没有结束,第二、三条指令就陆续地开始工作。由于多条指令的重叠处理,当后继指令所需的操作数,刚好是前一指令的运算结果时,便发生数据相关冲突。ADD R1,R2,R3 ;(R2)(R3)R1SUB R4,R1,R5 ;(R1)(R5)R4AND R6,R1,R7 ;(R
23、1)(R7)R6顺序流动和异步流动n 任务在流水线中的流动顺序的安排和控制可以有两种方式。1、任务流入和流出的顺序一致,称为顺序流动方式顺序流动方式或同步流动方式;2、任务流出和流入的顺序可以不同,称为异步流动方式异步流动方式。顺序流动和异步流动 控制相关的解决办法(1)猜测法 顾名思义,猜测法就是当遇见转移指令时,会形成两个分支,+1、+2、,是转移不成功时继续执行的一路分支,另一路分支是转移成功时转向执行指令p、p+1、。流水意味着同时解释多条指令,i进入流水线后,后面到底是执行i+1还是p指令那要等指令i的条件码建立以后才知道,而i的条件码建立一般要等到条件转移指令i快流出流水线时才行,
24、那么在没有建立i的条件码之前,i之后的指令停等下来的话,流水就断流了,性能肯定下降。为了不断流,可采用猜测法猜取i+1和p两个分支中的一个继续向前流动。控制相关的解决办法(2)加快和提前形成条件码 尽快尽早地获得条件码,就可以提前知道流水线将流向哪个分支。其一,加快单条指令内部的条件码的形成,尤其是某些反映运算结果的条件码完全可以不必等到指令执行完就可以提前形成。比如,根据运算规律来看,乘、除运算的结果是正是负的条件码就完全可以在运算前形成。其二,在一段程序内提前形成条件码,比如循环程序,一般是根据循环条件判断是否继续转移。控制相关的解决办法(3)采用延迟转移 采用延迟转移办法是用软件方法进行
25、静态指令调度的技术,就是在编译生成目标指令程序时,将条件转移指令与它前面不相关的一条或多条指令交换位置,让成功转移总是延迟到在这一条或多条指令执行之后再进行。延迟转移方法因为思路简单,而且不必增加硬件,故比较实用。控制相关的解决办法(3)采用延迟转移(续)采用延迟转移办法是用软件方法进行静态指令调度的技术,就是在编译生成目标指令程序时,将条件转移指令与它前面不相关的一条或多条指令交换位置,让成功转移总是延迟到在这一条或多条指令执行之后再进行。延迟转移方法因为思路简单,而且不必增加硬件,故比较实用。控制相关的解决办法(4)加快短循环程序的处理 其一,为避免短循环程序取进了指缓后,由于指令预取导致
展开阅读全文