第十三章　并行计算机体系结构

本章主要内容

并行计算机系统结构概述
并行计算机系统的设计问题
　　■并行计算机系统的互连网络
　　■并行计算机系统的性能问题
　　■并行计算机系统的软件问题
SIMD计算机简介
MIMD多处理机简介
MIMD多计算机简介

第一个是改变冯.诺依曼机器的串行执行模式
　　■超标量计算机（执行多条指令 ）
　　■多处理机系统（共享集中或分布式存储器）
　　■大规模并行处理机MPP系统
　　■PC或工作站组成的机群系统

第二个是改变冯.诺依曼机器的控制驱动方式
　　■数据驱动方式：操作数到位即可运算，无序执行.数据流计算机是一种数据驱动式系统结构的计算机，只要指令所需的操作数准备好就可以立即启动执行，一条指令的运算结果又流向下一条指令，作为下一条指令的操作数来驱动该条指令的启动执行。程序中各条指令的执行顺序仅由指令间的数据依赖关系决定。
　　■需求驱动方式：驱动方式与数据流相反，无序执行.需求驱动方式是一个操作仅在要用到其输出结果时才开始启动，如果这个操作的操作数没有准备好，那么它就去启动能够得到它的相应输入操作数的其他操作，这样的需求链一直延伸下去，直到遇到常数或者外部已经输入的数据为止，然后再反方向的执行运算。归约机就属于需求驱动式系统结构的使用函数式程序设计语言的计算机。
　　■模式匹配驱动方式：非数值型应用，主要对象为符号.在模式匹配驱动方式中，计算的进行是由谓词模式匹配来驱动的，而谓词是代表客体之间关系的一种字符串模式，主要用来求解非数值的符号演算。面向智能的Lisp机、Prolog机和神经网络等就属于这种模式匹配驱动式系统结构的计算机。
第一个发展方向已经取得了重大进展，取得了一系列的成果。而第二个发展方向，大多数还属于探索、研究阶段，还需要进行大量的工作。

过去曾普遍将计算机系统分为巨、大、中、小、微型机五类。
　　■划分原则：这种方法是按照规模、性能、速度以至价格的一种大致划分。
　　■存在问题：只能对同时期的计算机大致分类，划分的标准是随时间而变化，每５年左右降低一个等级；另外，这种划分方法不能反映机器的系统结构特征。
　　■设计方法：
　　　　◆最高性能 　　　　特殊用途
　　　　◆最佳性能价格比 　一般商用计算机
　　　　◆最低价格 　　　　家用计算机等

计算机系统结构的分类方法

1966年，Michael.J.Flynn提出按指令流和数据流的多倍性对计算机系统结构进行分类。
　　■指令流 是指机器执行的指令序列；
　　■数据流 是由指令流调用的数据序列，包括输入数据和中间结果；
　　■多倍性 是指在系统最受限制的部件上，同时处于同一执行阶段的指令或数据的最大数目。

SISD体系结构

处理器串行执行指令；或者处理器内采用指令流水线，以时间重叠技术实现了一定程度上的指令并行执行；甚至于处理器是超标量处理器，内有几条指令流水线实现了更大程度上的指令并行执行。但它们都是以单一的指令流从存储器取指令，以单一的数据流从存储器取操作数和将结果写回存储器。

SIMD体系结构

有单一的控制部件，但是有多个处理部件。计算机以一个控制单元从存储器取单一的指令流，一条指令同时作用到各个处理单元，控制各个处理单元对来自不同数据流的数据组进行操作。这种体系结构的典型代表是阵列处理机，一些学者认为将向量处理机也划入此类。

多个处理单元，各配有相应的控制单元。各个处理单元接收不同的指令，多条指令同时在一份数据上进行操作。这种计算机体系结构是一种比较奇怪的组合，这已经被证明是不可能至少是不实际的，目前为止还不存在这种类型的计算机。

MIMD体系结构

同时有多个处理单元，并且每个处理单元都配有相应的控制单元。各个处理单元可以接收不同的指令并对不同的数据流进行操作。大多数现代的并行计算机都属于这一类，多处理机系统和多计算机系统都是MIMD型的计算机。

计算机系统结构的分类方法

Flynn分类法的局限
　　■分类的对象主要是控制驱动方式下的串行处理和并行处理计算机。对于非控制驱动方式的计算机，就不适合采用Flynn分类法；
　　■把两个不同等级的功能并列对待，通常，数据流受指令流控制从而造成MISD不存在；
　　■分类太粗，对流水线处理机的划分不明确，标量流水线为SISD，向量流水线为SIMD。
其他的分类方法
　　■美籍华人冯泽云教授在1972年提出了按最大并行度来定量描述各种计算机系统的冯氏分类法。
　　■Wolfgan Handler在冯氏分类法的基础上，于1977年根据并行度和流水线提出了另外一种分类法。
　　■1978年由 D. J. Kuck提出按控制流和执行流分类。

应用的需求永远是并行计算机系统发展的动力。
　　■随着计算机速度的提高，人们对计算机性能的要求也越来越高。例如科学计算、工程和工业设计等都需要高性能计算。
　　■芯片的速度不可能无限地提高，并行计算机可以处理越来越复杂的问题。芯片的速度要受到光速的制约，但芯片的集成度还有发展的空间。
大量商品化的处理器的出现为设计并行计算机系统提供了可能。
并行计算机系统获得快速发展和处理机间通信技术的发展密不可分。

按照Flynn分类法归纳的并行计算机体系结构图谱

MIMD体系结构
　　 ■多处理机系统——基于共享存储器
　　　　◆系统中只有唯一的地址空间，所有的处理器共享该地址空间。
　　　　◆唯一的地址空间并不意味着在物理上只有一个存储器。共享地址空间可以通过一个物理上共享的存储器来实现，也可以通过分布式存储器并在硬件和软件的支持下实现。

　　■多计算机系统——基于消息传递
　　　　◆每个处理器有自己的存储器，该存储器只能被该处理器访问而不能被其它处理器直接访问，这种存储器称为局部存储器或私有存储器。
　　　　◆当处理器A需要向处理器B传送数据时，A把数据以消息的形式发送给B。

并行性、可扩展性和可编程性

并行性（Parallelism）的基本概念
　　■并行性是指在同一时刻或同一时间间隔内完成两种或两种以上的工作。
　　■并行性还可以进一步分为同时性和并发性，前者指同一时刻发生的并行性，后者指同一时间间隔内发生的并行性。
并行的粒度问题
　　■粗、中、细三种不同的并行粒度，共享内存的多处理机系统用于细粒度和中粒度并行计算，而消息传递型多计算机系统用于中粒度和粗粒度并行计算。

硬件资源的可扩展性（Scalability）
　　■是指通过增加处理器数目、投入更多的存储器部件（高速缓存、主存、磁盘等），从而使系统具有更高的性能或功能。
　　■由于多处理机和多计算机主要是以资源重复手段实现并行处理的，因此它们是可扩展系统。而且，松散耦合的多计算机系统的可扩展性要好于紧密耦合的多处理机系统。
并行计算机系统可编程性（Programmability）
　　■涉及到操作系统、编译器、语言支持等多个方面的问题。到目前为止，可以说对并行计算机系统编程仍然是非常困难和费力的事情，这主要是因为人们原来所熟悉的顺序编程不适合并行程序的设计特征。
　　■从体系结构的角度来看，多处理机有统一编址的全局共享存储器，其可编程性要好于多计算机系统。

本章主要内容

并行计算机系统结构概述
并行计算机系统的设计问题
　　■并行计算机系统的互连网络
　　■并行计算机系统的性能问题
　　■并行计算机系统的软件问题
SIMD计算机简介
MIMD多处理机简介
MIMD多计算机简介

互连网络概述

并行计算机的通信体系结构是系统的核心
　　■两个层次：底层的互连网络；上层的语言、软件工具包、编译器、操作系统等提供的通信支持。
互连网络是并行计算机系统内部的互连网络
　　■定义：由开关元件按一定拓扑结构和控制方式构成的网络以实现计算机系统内部多个处理机或多个功能部件间的相互连接。
　　■与计算机网络在工作原理、概念以及术语上有许多相同或相似之处；并且某些并行计算机系统中的互连网络就是高速以太网和ATM网络。
互连网络一般由以下五个部分组成
　　■CPU、内存模块、接口、链路和交换结点

接口、链路和交换结点

接口：是从CPU和内存取得信息并向另外的CPU和内存发送信息的设备。典型设备如网络接口卡。
链路：是传送数据位的物理信道。链路可以是电缆、双绞线或者光纤；可以是串行的也可以是并行的，每种链路都有其最大带宽；链路可以是单工的（单方向传送）、半双工的（某个时刻只能传送一个方向的数据）和全双工的（同时两个方向传送）；链路使用的时钟机制可以是同步或是异步的。
交换结点：是互连网络的信息交换和控制站点，它是具有多个输入端口和多个输出端口的设备。能够进行数据缓冲存储和路径选择。

设计和分析互连网络的几个重要问题

互连网络的拓扑结构
　　■互连网络的拓扑结构描述了链路和交换结点是如何组织安排的。拓扑结构可以用图来表示，链路用边表示，交换结点用结点表示。
互连网络的寻径方式
　　■交换结点所做的工作就是接收到达输入端口的分组然后把分组发送到正确的输出端口，具有多种不同的工作方式。
互连网络的寻径算法
　　■寻径算法：决定一个分组从源结点到达目的结点的过程中经过的结点序列的算法。

互连网络的分类

静态网络
　　■静态网络(Static Networks)是指结点间有着固定连接通路且在程序执行期间，这种连接保持不变的网络。
动态网络
　　■动态网络(Dynamic Networks)由开关单元构成，可按应用程序的要求动态地改变连接状态。如总线、交叉开关，多级交换网络等。

互连网络的参数

结点度：与结点相连接的边数，表示节点所需要的端口数，根据链路到结点的方向，结点度可以进一步表示为：结点度 = 入度 + 出度，其中入度是进入结点的链路数，出度是从结点出来的链路数。
链路的长度：链路中包含的边数
距离：与两个结点之间相连的最少边数。
网络直径：网络中任意两个结点间距离的最大值。
网络规模：网络中结点数，表示该网络功能连结部件的多少。
等分宽度：某一网络被切成相等的两半时，沿切口的最小边数称为该网络的等分宽度。
对称性：从任何结点看，拓扑结构都一样，这种网络实现和编程都很容易。

静态互连网络

线性阵列
　　■对N个结点的线性阵列，有N-1条链路，直径为N-1（任意两点之间距离的最大值）度为2不对称，等分宽度为1。N很大时，通信效率很低。

环形 　　■对N个结点的环，考虑相邻结点数据传送方向： 　　▲双向环：链路数为N，直径N/2，度为2，对称，等分宽度为2。 　　▲单向环：链路数为N，直径N-1，度为2，对称，等分宽度为2。

带弦环 　　■对图中12个结点的带弦双向环 　　▲结点度为3：链路数为18，直径4（比如红色结点），度为3，不对称，等分宽度为2。 　　▲结点度为4：链路数为24，直径3（比如红色结点），度为4，对称，等分宽度为8。