计算机体系结构的发展

第9章 计算机体系结构的发展 内容提要 :在计算机系统结构的发展中，除了建立在传统计算机上的向量机、阵列机、并行多处理机之外，还出现了脉动阵列机、数据流机、归约机以及各种人工智能机等。其中仅脉动阵列机推出较早，技术比较成熟之外，其它尚在研究阶段，有些技术还不成熟，本章仅以作简单介绍，其目的是为读者指出一些新的研究方向，以便在今后的工作中能够从事该领域的研究。第9章 计算机体系结构的发展9.1 脉动阵列机 9.2 数据流计算机 9.3 归约机 9.4 人工智能计算机的研究与发展9.1 脉动阵列机9.1.1 脉动阵列机的组成原理 9.1.2 面向特定算法脉动阵列机的结构形式 9.1.3 通用脉动阵列机的结构9.1.1 脉动阵列机的组成原理1. 脉动阵列机概述阵列机是由主控制器CU将指令广播给各个处理单元，再由其中活跃的处 理单元以同步的方式执行这同一功能的指令。而脉动阵列机（Systolic Array Computer）则是阵列内所有处理单元的数据锁存器受同一时钟脉冲的控制。 当阵列机运算时，数据在各处理单元间沿各自的方向同步向前推进，就象人 体内的血液一样，随着脉搏跳动，一拍一拍地向前涌动。脉动阵列机的基本原理如图9.1 所示。图（a）表示传统的阵列机的 一个处理单元PE的工作过程，数据来自存储器，运算完成后再送入存储器。 若设存储器的带宽为10MB/S ，PE运算一次需要两个单字节的操作数，那么 系统的运算速度不可能超过每秒5M次。而图（b）是由6个处理单元构成一条流水线，存储器读出的数据依次流 过各处理单元，同时运算。因此，整体系统的速度就可能是单一PE单元的6倍 。这样就构成简单的一维线性脉动阵列机。图9.1 脉动阵列结构示意图 A·B =a00·b00 + a01·b10 a00·b01 + a01·b11 a10·b00 + a11·b10 a10·b01+ a11·b11 在脉动阵列机中，各处理单元之间的结构形式与算法紧密相关，可以 是矩形、三角形或六边形等不同的形式。输入数据流和结果数据流可以 多种速度在多个方向上同时流动，而每个处理单元只接收前一组处理单 元送来的数据，并向后一处理单元传送结果。只有边缘上的处理单元才 能作为输入输出端口，与存储器传送数据。2.脉动阵列机的组成原理脉动阵列机与算法紧密相关，下面仅以简单二维数组的运算过程来说 明脉动阵列机的组成原理。设有二维数组A和B，进行乘法运算，其数学 表达式如下：则A =a00 a01 a10 a11B =b00 b01 b10 b11如果每一个处理单元PE能在每一步中执行zz+x入*y入，x出x入，y出y入的操作。那么，就可以构成能进行 2×2的二维矩形脉动阵列机，其示意如图9.2 所示。图9.2 脉动阵列结构示意图 在进行2×2二维矩阵的乘法运算时，每经过一个时钟脉冲，数据向前推动一步，其过程如图9.3所示。在时钟t0时刻，各处理单元PE的累加器赋初值0；时 钟t1，输入a00和b00，进行a00·b00运算，a00和b00向前推进 ；在时钟t2时刻，输入a10、b10、a01和b01，并进行下一步 向量元素的乘法与加法运算，元素继续向前推进；依次类 推。经过4个时钟周期，完成2×2二维数组A和B的乘法运算。 图9.3 二维矩阵在脉动阵列机上的相乘过程 9.1.2面向特定算法脉动阵列机 的结构形式1.面向特定算法脉动阵列机的结构形式脉动阵列机是针对某些特定算法而设计的，适合于特定的领域 。例如，在信号图像处理和模式识别等领域中，用于求解有限冲激响 应（FIR）和无限冲激响应（IIR）滤波，进行一维和二维卷积、离散 傅立叶变换等。在矩阵运算中，用于矩阵-矢量乘法、矩阵-矩阵乘 法、三角形线性方程组求解等。在非数值型领域中，用于堆栈、队列 及类等数据结构的描述。根据求解问题的不同，脉动阵列机可以是一维线性阵列、二维 矩形阵列、二维六边形阵列、二叉树形阵列以及三角形阵列等形式， 如图9.4 所示。图9.4 脉动阵列机结构形式cij = aik·bkj k= 02 其中 ，0i2，0j2。 A =a00 a01 a02 a10 a11 a12 a20 a21 a22B =b00 b01 b02 b10 b11 b12 b20 b21 b22C = A·B = c00 c01 c02 c10 c11 c12 c20 c21 c22则2.脉动阵列机举例对图9.2所示二维阵列结构进行改造，即可得到如图9.5 所示，可 进行3×3矩阵乘法运算的变形脉动阵列机。设有3×3矩阵A和B：图9.5 3×3矩阵乘法运算脉动阵列机工作示意图 为了能够进行两个3×3矩阵的乘法运算，每一个处理单元PE应包含一 个乘法器和加法器，以完成内积和加法运算。在每一个时钟周期，可接收三 个方向输入的数据，即水平方向由左向右，竖直方向由下向上，左下角沿45° 方向到右上角；同时，可将结果传送到三个对应的输出端。即mm，nn ，pm×n+q。这样，在t1t3时钟周期参加运算的矩阵元素开始输入脉动阵列机；t6 时刻，运算结果开始输出，即在45°方向上同时输出c02、c01、c00、c10、c20， t7时刻输出c12、c11、c21，t8时刻输出c22。可以看出，仅需要8个时钟周期就 完成了3×3矩阵的乘法运算，而在单处理机采用循环运算，则至少需要27个 时钟周期，速度提高了近2.4倍。通过对图9.5的结构分析可以看出，若要对n×n矩阵进行乘法运算，则 需要3n2-3n+1个处理单元PE构成脉动阵列机；而且，仅需要3n-1个时钟周期 就可以完成全部运算。运算所需要的时间仅以近似于3n的线性关系在增加。 尤其是n较大时，采用脉动阵列机进行运算，效果更明显。如果矩阵很大，可 用软件拆分为若干小矩阵分别运算，然后求出整体结果。3.脉动阵列机结构的特点对于上述脉动阵列机可归纳出以下特点。（1）脉动阵列机的结构与具体的算法紧密相关（2）结构简单规整，模块化结构明显（3）数据流和控制流简单规整，易于设计（4）各处理单元同时工作，具有很强的系统并行性脉动阵列机是针对某一种或者某些具体的问题而提出来的，因此与算法紧密相联，且由若干个功能相同、结构简单的处理单元构成，采用模块化结构，可扩展性好；通信线路简单规整，易于设计，有利于提高VLSI的集成度；各处理单元同时工作，并行性很强。9.1.3 通用脉动阵列机的结构1.可编程脉动阵列结构可编程脉动阵列结构是增设附加硬件，通过编程对阵列的拓扑结构和互连方式进行重构，以实现不同算法的需求。目前，已 经有可编程脉动阵列芯片，通过编程可重新配置阵列的结构，以 满足不同算法的需求。例如美国普图（Purdue）大学的CHiP（ Configurable Highly Parallel Computer），即可以不同算法构造出相应的阵列机。CHiP结构如图9.6 所示，包含三个部分，即一组功能相同的处 理单元PE、一个控制器和一个开关网络。图中方框表示处理单元，圆圈 表示可编程开关，处理单元通过开关的转接实现互连。每一个开关含有 一个局部存储器，称为开关存储器，存储构成不同阵列时的设置方式。 每一种设置方式可使开关按一定的模式将相应的数据通路连接起来，以 实现各处理单元之间的不同拓扑结构。例如把偶数列上的开关设置成上 下连通，偶数行的开关左右连通，就可以构成如图9.6（a）所示的矩形 脉动阵列结构。按照特定的设置方式，也可构成如图9.6（b）所示的二 叉树阵列结构，其中灰色方框是根处理单元。 2.软件算法映象软件算法映象是用软件的方法把不同的算法映象到固定的阵列结构 中，具有代表性的是美国卡内基梅隆大学研制的WARP计算机，主要 用于图像信号处理和计算机视觉方面。这种方法依赖于面向并行运算的 程序设计语言、操作系统、编译程序和软件开发工具。图9.6 可编程脉动阵列示意图WARP是由10个以上的处理单元组成的一维线性脉动阵列机如图9.7 所示。各处理单元有相同的内部结构，包含乘法器和浮点运算部件，有两 个数据队列x、y和一个地址队列，且有自己的程序存储器和微操作控制器 。数据经x、y通路传送，地址和脉动控制信号经地址线路传送，在同一时 刻，各个处理单元均进行相同的运算。各处理单元按一定的方式连接，组成处理单元阵列，再通过接口部 件与主机连接，构成WARP脉动阵列机。主机负责阵列机与外部的数据信息 传送，经接口部件向处理单元阵列提供地址和控制信号；并且，执行一部 分不适合脉动阵列处理的程序，为用户提供一个通用UNIX操作系统环境。由于WARP机采用的是一维线性结构，因此易于实现和扩充；在内部 处理单元的程序存储器中装有特定的微程序，且有内部数据存储器，可实 现多种运算，从而保证WARP机的通用性和灵活性。但是，一般需要专门的 高级语言和优化编译器。 图9.7 WARP脉动阵列机 为了发展通用型脉动阵列机，人们在不停地探索和研究，比如： 寻求与问题大小无关的脉动阵列处理方法，比如采用矩阵分割算法，对VLSI运算系统进行分割，以克服阵列机只能求解矩阵大小固定的题目。 寻求可以求解一类问题的通用算法及阵列设计方案，以便设计成功后可以求解一类问题。可以预料，随着VLSI技术的进一步提高，脉动阵列机将会有更大的发展，将会在数字信号处理、模式识别、智能数据库等方面有更多的应用。9.2 数据流计算机9.2.1 数据驱动原理 9.2.2 数据流计算机模型 9.2.3 数据流程序图与数据流语言 9.2.4 数据流计算机举例9.2.1 数据驱动原理冯·诺依曼计算机的设计思想是在程序计数器的集中控制下，顺序执行事先存入存储器中的程序，因此是以控制流的方式工作的，难以 最大限度的发展计算的并行性。1.数据驱动为此，人们试图采用数据驱动（Data Driven）的方式来工作。也就是说，当一条或一组指令所需要的操作数完全准备就绪时，即刻执行 。执行的结果并不送往存储器，而是送往需要这一结果的指令，以便驱 动该指令的执行。在这种计算机中指令的执行完全由数据驱动，基本上 是无序的，与指令在程序中的位置无关。2.数据流计算机指令结构在数据流计算机中，信息以操作包（Operation Packet）和数据令牌（Data Token）的形式出现。其中操作包由操作码、操作数和后续指令地址组成。而数据令牌实质上是一种表示某一操作数准备就绪的标志，由结果值、目的地址及数据到达标志组成，一旦执行某一指令的数据令牌到齐，该条指令即刻执行。其结果将送往哪一条指令的第几个操作数位置呢？这样，就产生了数据流计算机的指令，如图9.8 所示。图9.8 数据流计算机指令主要组成 3.数据流驱动过程数据流计算机工作时，众多的操作包和数据“令牌”在各资源部件之 间传递，因而这种数据流计算机可视为信息分组通信的系统结构，具有 分布式多处理机的组织形式。它的操作包与数据令牌在系统中的传送示 意如图9.9 所示，完成的运算是a=(b+2)×(b-c)。每一个操作包所需要的数据到齐时，该操作即刻执行；而结果则 按地址传送到后续指令中的指定位置。图9.9 操作包与数据令牌传送示意图9.2.2 数据流计算机模型按照对数据令牌的不同处理方式，数据流计算机可分为静态数据流计算机和动态数据流计算机。1.静态数据流计算机模型静态数据流计算机模型如图9.10所示，典型代表是由美国麻省理工 学院（MIT）的Jack Dennis和他的实验人员首先提出来的MIT计算机。 图9.10 所示的静态数据流计算机的主要特点是数据令牌不带任何 标号，而且在数据流程序图中的任何一条有向支线上只允许有一个数据令 牌，沿支线的方向流动。一个结点所有支线上的数据令牌都到达，且输出 支线上没有数据令牌时