《计算机组织与结构 第8章 并行组织》由会员分享，可在线阅读，更多相关《计算机组织与结构 第8章 并行组织（115页珍藏版）》请在金锄头文库上搜索。
1、第8章 并行组织,本章结构,8.1 计算机系统的并行性,研究计算机体系结构的目的：提高计算机系统的性能；计算机体系结构的重要研究内容之一：开发计算机系统的并行性。,计算机体系结构、计算机组织和计算机实现,计算机体系结构、计算机组织和计算机实现三者互不相同但又互相影响,计算机组织（Computer Organization）：所研究的是计算机系统的逻辑实现；,计算机实现（Computer Implementation）：所研究的是计算机系统的物理实现。,计算机体系结构：是程序员所看到的计算机的属性，即概念性结构和功能特性；,体系结构中的并行性,现代计算机的一个共同特点是大量采用并行技术，使计算机
2、的性能得以不断提高。并行性（parallelism）：指的是在同一时刻或是同一时间间隔内完成两种或两种以上性质相同或不相同的工作。只要时间上互相重叠，就存在并行性，其包含同时性和并发性两层含义。同时性（simultaneity）：指两个或多个事件在同一时刻发生的并行性；并发性(concurrency)：指两个或多个事件在同一时间间隔内发生的并行性。,并行性等级划分：从执行程序角度,指令内部并行：指的是指令内部的微操作之间的并行。 指令级并行：指的是并行执行两条或多条指令，就是指令之间的并行。 线程级并行：指的是并发执行多个线程，通常是以一个进程内控制派生的多个线程为调度单位。任务级或过程级并行
3、：指的是并行执行两个或多个过程或任务(程序段)。 作业或程序级并行：指的是在多个作业或程序间的并行。,并行性等级划分：从处理数据的角度,字串位串: 指的是同时只对一个字的一位进行处理。 字串位并：指的是同时对一个字的全部位进行处理，不同字之间是串行的。字并位串：指的是同时对许多字的同一位(称位片)进行处理。全并行：指的是同时对许多字的全部或部分位进行处理。,提高并行性的技术途径,最低耦合,1、时间重叠,2、资源重复,3、资源共享,提高并行性的技术途径,1、时间重叠,时间重叠：多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。实现时间重叠的基础：部件
4、功能专用化。时间重叠的实质：把一件工作按功能分割为若干个相互联系的部分；然后把每一部分指定给专门的部件完成；最后按时间重叠原则把各部分执行过程在时间上重叠起来，使所有部件依次分工完成一组同样的工作。流水线技术就是时间重叠的典型应用。,时间重叠举例,例：一条指令的执行可以看成是由四个过程组成，即取指令、指令译码、指令执行和写结果。,（a）4个子过程的指令流水线,4条指令流水的时空图,2、资源重复,资源重复：根据“以数量取胜”的原则来实现并行，其付出的代价是在空间上通过重复地设置资源，尤其是硬件资源，以提高计算机系统的性能。,资源重复的并行举例,3、资源共享,资源共享是一种软件方法的并行，它使多个
5、任务按一定时间顺序轮流使用同一套硬件设备。资源共享的实质就是用单处理机模拟多处理机的功能，形成所谓虚拟机的概念。,多机系统的并行性,多机系统：包括多处理机系统和多计算机系统。多机系统也遵循时间重叠、资源重复和资源共享这三种基本的技术途径，向着三种不同的多处理机方向发展。,多机系统的耦合度,耦合度：反映多机系统的各机器之间的物理连接的紧密程度和交互作用能力的强弱。,最低耦合,最低耦合,松散耦合,紧密耦合,多机系统的耦合度分为,最低耦合,最低耦合 耦合度最低的系统。除通过某种中间存储介质之外，各计算机之间没有物理连接，也无共享的联机硬件资源。,松散耦合或间接耦合系统,松耦合系统的各处理机间通过共享
6、I/O子系统、通道或通信线路实现处理机间通信和互连，不共享主存，但可共享某些外围设备(例如磁盘、磁带等)，机间的相互作用是在文件或数据集一级进行。松散耦合多处理机由多个处理机、一个通道、一个仲裁开关和消息传送系统组成。每个处理机带有一个局部存储器和一组I/O设备。在仲裁开关的通道中有高速通信存储，用来缓冲传送的信息块。,紧密耦合系统或直接耦合系统,紧耦合多处理机系统，其处理机间物理连接的频带较高，它们往往通过总线或高速开关实现互连，可以共享主存，各处理机之间是通过互连网络共享主存的。一般地，紧耦合系统由P台处理机、m个存储器模块、d个I/O通道和三个互连网络构成。处理机-存储器网络实现处理机与
7、各存储模块的连接；处理机中断信号网络实现多处理机之间的互连；处理机-I/O互连网络实现处理机与外设的连接。每个处理机可自带局部存储器，也可自带Cache存储器模块，可采用流水工作方式。紧耦合系统多用于并行作业中的多任务，一般处理机是同构的。,并行计算机体系结构的分类,Flynn（弗林）分类法：美国的弗林（Michael Flynn）于1966年提出的分类法这种分类法主要依据指令流和数据流的多倍性关系来对计算机系统进行分类。指令流是指机器执行的指令序列；数据流是指由指令流调用的数据序列，包括输入数据和中间结果；多倍性是指在系统瓶颈部件上处于同一执行阶段的指令或数据的最大可能数。,Flynn分类法
8、,按照Flynn分类法，把计算机系统分成四类，分别是：单指令流单数据流（SISD：Single Instruction Stream Single Data Stream）单指令流多数据流（SIMD：Single Instruction Stream Multiple Data Stream）多指令流单数据流（MISD：Multiple Instruction Stream Single Data Stream）多指令流多数据流（MIMD：Multiple Instruction Stream Multiple Data Stream）,SISD计算机,SISD实际上就是传统的单处理器计算机。
9、只要指令部件每次只对一条指令译码，只对一个操作部件分配数据，就属于SISD系统。,SISD计算机,SIMD计算机,SIMD中具有代表性的例子是相联处理机和阵列处理机。特殊地，如果“多倍性”中“处于同一执行阶段”被理解成一条指令的操作全过程，那么流水线处理机的不同子过程操作就可以看作是不同子部件处理的是同一条指令的不同阶段的数据，此时流水线处理机也可以算是SIMD。,SIMD计算机,MISD计算机,MISD的一般形式是有n个处理单元，按n条不同指令的要求对同一个数据流及其中间结果进行不同的处理，一个处理单元的输出作为另一个处理单元的输入。,MISD计算机,MIMD计算机,MIMD系统能实现作业、
10、任务、指令、数组各级的并行，是能实现较为全面的并行处理的多机系统。MIMD一般形式是按n条不同指令的要求在n个控制单元的控制下对n个数据流及其中间结果进行不同的处理。,MIMD计算机,知识拓展：数据流机与归约机,数据流机的两种驱动方式：种是数据驱动方式，即一条指令当且仅当所需的操作数准备就绪时便开始执行，完全不需要指令计数器的控制。另一种是需求驱动方式，即任何操作都是纯函数操作，只有当某一个函数需要某个自变量时才驱动对该自变量的求值操作，即每一数据流操作都是消耗一组输入值，产生一组输出值而不产生副作用，这就确保任何两个并发操作可以任意次序执行，而不会产生干扰。,归约机,归约机：一种面向函数程序
11、设计语言的计算机，指令的执行顺序取决于这些指令产生结果数据的需求，而这种需求又源于函数式程序设计语言对表达式的归约。按其归约模型可分为：串归约机图归约机两者的主要区别是对函数表达式所使用的存储方式不同，前者以字符串形式存储而后者以图的形式存储。,8.2流水线技术,计算机中的流水线技术是一种利用资源重叠技术提高机器性能的并行处理技术，它能在不增加机器硬部件的情况下，通过对某一部件功能进行合理的分解与设计，有效提高部件的处理速度。,流水线的分类,1.按照计算机处理的级别来分类,流水线的分类,2.按照流水线可以完成的动作的数量来分类,多功能流水线的实现,同一个流水线在不同连接下可以分别实现浮点加、减
12、运算时的连接和定点乘、除法运算时的连接,流水线的分类,3.按照多功能流水线的各个段是否允许同时进行多种不同功能的连接流水来分类,静态流水线时空图,假设先后有二批任务要完成，第一批是n个任务的浮点加、减运算；第二批任务是AE共5个任务的定点乘法运算,按照静态方式形成流水线,动态流水线时空图,假设先后有二批任务要完成，第一批是n个任务的浮点加、减运算；第二批任务是AE共5个任务的定点乘法运算,按照动态方式形成流水线,流水线的分类,4.按照流水线内部的功能部件的连接方式（如各功能段之间是否有反馈回路）来分类,非线性流水线举例,流水线的分类,5.按照机器可处理的对象来分类,流水线的主要性能参数,衡量一
13、种流水线处理方式的性能的高低的参数主要有吞吐率、加速比和效率。吞吐率（TP, Thoughput Rate），指的是计算机中的流水线在单位时间内能流出的任务数或结果数。流水线的吞吐率可以进一步分为最大吞吐率和实际吞吐率。在线性流水线中，最大吞吐率Tp max1/T1/max（T1 ，.，Ti ，.，Tm），其中，m是流水线的段数，Ti表示的是第i段的执行时间。,最大吞吐率受到了瓶颈段的约束,例如，某流水线有4个段，其中2号段由于需用时3t，所以2号段是瓶颈段，见图（a）；5个任务流经该流水线时的流水效果的实际情况如图（b）所示，显然流水速度受到了2号瓶颈的限制。,细分瓶颈段,把瓶颈部分的流水线
14、分拆，以便任务可以充分流水处理,并联瓶颈段,在瓶颈部分设置多条相同流水段，并行处理,流水线的实际效率,分析并计算出流水线的实际效率,分析实际吞吐率的时空图,加速比（Speed Ratio）,假设该流水线各子功能段执行时间均为t，流水段有m个段，那么n个任务非流水顺序完成需要nmt的时间；流水完成则需要mt+(n-1)t的时间；因此，流水方式工作的加速比为：,所以在流水线各子功能段执行时间均相等的情况下，仅当nm时，其加速比才能趋近于最大值m，即流水线的段数。,效率（Efficiency）,效率（Efficiency）：也称流水线设备的时间利用率，又称使用效率，它指的是流水线中各个部件的利用率，
15、也就是设备的实际使用时间占整个运行时间的比值。以前面“分析实际吞吐率的时空图 ”来看，在T时间里流水线的各段效率都相同，均为0，整个流水线的效率就是 ，计算如下：,效率实际上就是n个任务占用的时空区面积与m个段总的时空区面积的比值。显然，只有当nm时，才趋近于1。,流水线的相关问题,结构相关：当指令在重叠执行过程中，硬件资源满足不了指令重叠执行的要求，两条或两条以上指令争用同一资源而引起的冲突，因此，结构相关又称为资源相关。数据相关：当一条指令需要用到前面指令的执行结果，而这些指令均在流水线中重叠执行时，就有可能产生数据相关。控制相关冲突：是由转移指令引起的。当执行转移指令时，依据转移条件的产
16、生结果，可能为顺序取下条指令；也可能转移到新的目标地址取指令，从而使流水线发生断流。,结构相关,例如，假设一条指令流水线由5段组成，分别为取指令（IF）、指令译码（ID）、取操作数（MEM）、执行运算（EX）和写寄存器（WR）。若指令I2的取操作数和指令I4的取指令都需要访问存储器。若机器中只有一个单端口存储模块，那么I2的取操作数和指令I4的取指令就产生了访存冲突，两个操作无法同时进行，这就是一种典型的资源冲突。,结构相关解决办法,解决办法：1、在机器中增加存储器模块，如使用双端口存储器，使指令和数据分别存放在不同的存储器模块中，这样，取指令和取操作数就不会发生冲突。2、当发生取指令或取操作数冲突时，将其中一个操作的执行时间推迟，如下图所示。当然，这样的话也就是发生了流水线的断流，流水线的吞吐率就下降了。,访存相关引起流水线断流,数据相关,在流水计算机中，指令的处理是重叠进行的，前一条指令还没有结束，第二、三条指令就陆续地开始工作。由于多条指令的重叠处理，当后继指令所需的操作数，刚好是前一指令的运算结果时，便发生数据相关冲突。,
