计算机体系结构第13章要点

计算机组成与系统结构王诚宋佳兴清华大学计算机系第13章并行计算机体系结构3本章主要内容并行计算机系统结构概述并行计算机系统的互连网络SIMD计算机简介MIMD多处理机简介MIMD多计算机简介计算机系统结构的发展历程硬件技术和系统结构软件和应用第一代（1945～1954）电子管和继电器。单CPU，以程序计数器PC和累加器顺序完成定点运算。机器语言或汇编语言。单用户。用CPU程序控制I/O。第二代（1955～1964）晶体管和磁芯存储器。用印制电路互连。变址寄存器，浮点运算；多路存储器，I/O处理机。有编译程序支持的高级语言，子程序库，批处理监控程序。第三代（1965～1974）中小规模集成电路。多层印制电路。微程序设计，流水线，高速缓存，先行处理机。多道程序设计，分时操作系统，多用户应用。第四代（1975～1990）大规模集成电路。半导体存储器。多处理机，多计算机，向量超级计算机。用于并行处理的多处理机操作系统、专用语言和编译器；并行处理或分布计算的软件工具和环境。第五代（1991～现在）超大规模集成电路。高密度高速度处理器和存储器芯片，可扩展体系结构，因特网。大规模并行处理，Java语言，分布式操作系统，万维网，网格。计算机系统结构的发展方向第一个是改变冯.诺依曼机器的串行执行模式超标量计算机（并行执行多条指令）多处理机系统（共享集中或分布式存储器）大规模并行处理机MPP系统PC或工作站组成的集群系统第二个是改变冯.诺依曼机器的控制驱动方式数据驱动方式：操作数到位即可运算，无序执行需求驱动方式：驱动方式与数据流相反，无序执行模式匹配驱动方式：非数值型应用，主要对象为符号第一个发展方向已经取得了重大进展，取得了一系列的成果。而第二个发展方向，大多数还属于探索、研究阶段，还需要进行大量的工作。计算机系统结构的分类方法过去曾普遍将计算机系统分为巨、大、中、小、微型机五类。划分原则：这种方法是按照规模、性能、速度以至价格的一种大致划分。存在问题：只能对同时期的计算机大致分类，划分的标准是随时间而变化，每５年左右降低一个等级；另外，这种划分方法不能反映机器的系统结构特征。设计方法：最高性能特殊用途计算机最佳性能价格比一般商用计算机最低价格家庭用计算机等计算机系统结构的分类方法计算机系统结构的分类方法1966年，Michael.J.Flynn提出按指令流和数据流的多倍性对计算机系统结构进行分类。指令流是指机器执行的指令序列；数据流是由指令流调用的数据序列，包括输入数据和中间结果；多倍性是指在系统最受限制的部件上，同时处于同一执行阶段的指令或数据的最大数目。指令流数据流名称举例1个1个SISD传统的冯.诺依曼计算机1个多个SIMD向量计算机，阵列处理机多个1个MISD？？？？？？多个多个MIMD多处理机，多计算机SISD体系结构单一的指令流从存储器取指令，以单一的数据流从存储器取操作数和将结果写回存储器。单功能部件处理机：IBM1401，VAX-11多功能部件处理机：IBM360/370，CDC6600流水线处理机：指标量流水线处理机ISDSCUPUMMSISDSIMD体系结构单一的控制部件，多个处理部件。计算机以一个控制单元从存储器取单一的指令流，一条指令同时作用到各个处理单元，控制各个处理单元对来自不同数据流的数据组进行操作。这种体系结构的典型代表是阵列处理机和向量流水处理机。ISDS1PUMMDS2CUPU…DSnMMPUSIMDMISD体系结构多个处理单元，各配有相应的控制单元。各个处理单元接收不同的指令，多条指令同时在一份数据上进行操作。这种计算机体系结构已经被证明是不可能至少是不实际的，目前为止还不存在这种类型的计算机。DSIS1CU1PU1MMIS2IS2CU2PU2……MMCUnPUnISnMISDMIMD体系结构同时有多个处理单元，并且每个处理单元都配有相应的控制单元。各个处理单元可以接收不同的指令并对不同的数据流进行操作。大多数现代的并行计算机都属于这一类，多处理机系统和多计算机系统都是MIMD型的计算机。例如IBM3081、IBM3084、UNIVAC-1100/80、CRAY-2IS1DS1CU1PU1MMIS2DS2CU2PU2………MMISnDSnCUnPUnMIMD计算机系统结构的分类方法Flynn分类法的局限分类的对象主要是控制驱动方式下的串行处理和并行处理计算机。对于非控制驱动方式的计算机，就不适合采用Flynn分类法；把两个不同等级的功能并列对待，通常，数据流受指令流控制从而造成MISD不存在；分类太粗，对流水线处理机的划分不明确，标量流水处理机为SISD，向量流水处理机为SIMD。其他的分类方法美籍华人冯泽云教授在1972年提出了按最大并行度来定量描述各种计算机系统的冯氏分类法。WolfganHandler在冯氏分类法的基础上，于1977年根据并行度和流水线提出了另外一种分类法。1978年由D.J.Kuck提出按控制流和执行流分类。并行计算机系统的分类图13.4并行计算机的分类消息传递计算机系统结构SISDMIMD向量计算机阵列计算机多处理机UMA多计算机COMASIMDMISDNUMAMPPCOW总线交换结构CC-NUMA网格超立方体NC-NUMA共享内存?冯.诺依曼按照Flynn分类法归纳的并行计算机体系结构图谱SIMD体系结构向量计算机可以在一个向量的每个元素上执行相同的操作，一般来说向量处理机是以流水线式ALU为核心，实现向量各个元素的并行计算采用的是时间重叠技术。阵列计算机这类计算机采用资源重复方法引入空间因素，即在系统中设置多个相同的处理单元来开发并行性。此外，它是利用并行性中的同时性，所有处理单元必须同时进行相同操作。MIMD体系结构多处理机系统——基于共享存储器系统中只有唯一的地址空间，所有的处理器共享该地址空间。共享地址空间可以通过一个物理上共享的存储器来实现，也可以通过分布式存储器并在硬件和软件的支持下实现。多计算机系统——基于消息传递每个处理器有自己的存储器，该存储器只能被该处理器访问而不能被其它处理器直接访问，这种存储器称为局部存储器或私有存储器。当处理器A需要向处理器B传送数据时，A把数据以消息的形式发送给B。并行计算机系统发展的原因应用的需求永远是并行计算机系统发展的动力随着计算机速度的提高，人们对计算机性能的要求也越来越高。例如科学计算、工程和工业设计等都需要高性能计算。芯片的速度不可能无限地提高，并行计算机可以处理越来越复杂的问题。芯片的速度要受到光速的制约，但芯片的集成度还有发展的空间。大量商品化的处理器的出现为设计并行计算机系统提供了可能并行计算机系统获得快速发展和处理机间通信技术的发展密不可分18本章主要内容并行计算机系统结构概述并行计算机系统的互连网络SIMD计算机简介MIMD多处理机简介MIMD多计算机简介互连网络概述并行计算机的通信体系结构是系统的核心两个层次：底层的互连网络；上层的语言、软件工具包、编译器、操作系统等提供的通信支持。互连网络是并行计算机系统内部的互连网络由开关元件按一定拓扑结构和控制方式构成的网络以实现计算机系统内部多个处理机或多个功能部件间的相互连接。与计算机网络在工作原理、概念以及术语上有许多相同或相似之处；并且某些并行计算机系统中的互连网络就是高速以太网和ATM网络。互连网络一般由以下五个部分组成CPU、内存模块、接口、链路和交换结点接口、链路和交换结点接口：是从CPU和内存取得信息并向另外的CPU和内存发送信息的设备。典型设备如网络接口卡。链路：是传送数据位的物理信道。链路可以是电缆、双绞线或者光纤；可以是串行的也可以是并行的，每种链路都有其最大带宽；链路可以是单工的（单方向传送）、半双工的（某个时刻只能传送一个方向的数据）和全双工的（同时两个方向传送）；链路的时钟机制可以是同步或是异步的。交换结点：是互连网络的信息交换和控制站点，它是具有多个输入端口和多个输出端口的设备。能够进行数据缓冲存储和路径选择。设计和分析互连网络的几个重要问题互连网络的拓扑结构互连网络的拓扑结构描述了链路和交换结点是如何组织安排的。拓扑结构可以用图来表示，链路用边表示，交换结点用结点表示。互连网络的寻径方式交换结点所做的工作就是接收到达输入端口的分组然后把分组发送到正确的输出端口，具有多种不同的工作方式。互连网络的寻径算法寻径算法：决定一个分组从源结点到达目的结点的过程中经过的结点序列的算法。互连网络的分类静态网络静态网络(StaticNetworks)是指结点间有着固定连接通路且在程序执行期间，这种连接保持不变的网络。动态网络动态网络(DynamicNetworks)由开关单元构成，可按应用程序的要求动态地改变连接状态。如总线、交叉开关，多级交换网络等。互连网络的参数结点度：与结点相连接的边数，表示节点所需要的端口数，根据链路到结点的方向，结点度可以进一步表示为：结点度=入度+出度，其中入度是进入结点的链路数，出度是从结点出来的链路数。链路的长度：链路中包含的边数距离：与两个结点之间相连的最少边数。网络直径：网络中任意两个结点间距离的最大值。网络规模：网络中结点数，表示该网络功能连结部件的多少。等分宽度：某一网络被切成相等的两半时，沿切口的最小边数称为该网络的等分宽度。对称性：从任何结点看，拓扑结构都一样，这种网络实现和编程都很容易。静态互连网络线性阵列对N个结点的线性阵列，有N-1条链路，直径为N-1（任意两点之间距离的最大值）度为2不对称，等分宽度为1。N很大时，通信效率很低。环形对N个结点的环，考虑相邻结点数据传送方向：双向环：链路数为N，直径N/2，度为2，对称，等分宽度为2。单向环：链路数为N，直径N-1，度为2，对称，等分宽度为2。静态互连网络静态互连网络全链接全链接是带弦环的一种特殊情形。链接中的每个结点和其他结点之间都有单一的直接链路。如下图中8个结点的全链接：有28条链路，直径为1，度为7，对称，等分宽度为16。4层的二叉树静态互连网络树形一棵K层完全二叉树应有N=2K-1个结点，最大结点度为3，直径为2（K-1）（即右边任意一个叶子结点到左边任意一个叶子结点）。不对称，等分宽度为1。带环树二叉胖树树形的扩展这两种结构都可以缓解根结点的瓶颈问题静态互连网络星形星形实际上是一种二层树（如右图）。有N个结点的星形网络，有N-1条链路，直径为2，最大结点度为N-1，非对称，等分宽度为1。静态互连网络网格形有N个结点的rr网，有2N-2r条链路，直径为2(r-1)，结点度为4，非对称，等分宽度为r。其中Nr静态互连网络二维环网形有N个结点的rr网，有2N条链路，直径为2r/2，结点度为4，对称。其中Nr静态互连网络超立方体一个n-立方体由N=2n个结点构成，它们分布在n维上，每维有两个结点。直径为n，结点度为n，对称。3-立方体4-立方体带环3-立方体静态互连网络带环立方体一个带环n-立方体由N=2n个结点环构成，每个结点环是一个有n个结点的环，所以结点总数为n2n个，结点度为3，对称。静态互连网络特性一览表动态互连网络网络特点动态互连网络中的连接不固定，在程序执行过程中可根据需要改变。网络的开关元件有源，链路可通过设置这些开关的状态来重构。只有在互连网络边界上的开关元件才能与处理机相连。动态互连网络主要有总线、交叉开关、多级交换网络。动态互连网络总线（Bus）总线实际上是连接处理器、存储器和I/O等外围设备的一组导线和插座它在某一时刻只能用于一对源和目的之间传输数据当有多对源和目的请求使用总线时，要进行总线仲裁。当CPU数目较多时对总线争用严重（=32个）I/O总线I/O总线C局部总线CAIFPMCPU板…存储器总线IFC存储器存储器板C局部总线CAIFPMCPU板存储器总线IFC存储器存储器板…系统总线（在底板上）IF局部总线缓存器IFIOPI/O板磁盘打印机C局部总线缓存器IFIF