并行处理的扩展冯诺依曼结构.docx

Evon：并行处理的扩展冯诺依曼结构Wai-Mee Chlng IBM T. J. Watson Research Center P.O. Box 218 Yorktown Heights, New York 10598 摘要我们为并行处理提出了名为Evon的扩展冯诺依曼结构，它是集中控制的，并且可以利 用高级语言程序固有的并行的指令级和表示层利用并行的有效性很大程度上依赖于强大的 原语，我们通过几个简短的用 APL 编程的例子解释了这一点然后我们提出了体现 Evon 模型的指令集的设计的工作，以及针对并行自动提取的指令集的便携式编译器最后，我们 比较了 Evon 与其他的为并行处理提出的基于实际考虑和编程担忧的计算模型和架构 1. 介绍并行处理的不同方法可以围绕不同的标准来讨论第一个标准是计算机的专用性还是通 用性对于特殊目的的并行计算机，例如约克顿模拟引擎，它的速率是序列机 ［9］、［19］的 5000倍另一方面，对于一般用途的机器，只有一般的并行已经取得了实际使用，例如Cray X-MP在对一般用途的高度并行结构的研究中已经提出了许多计算模型和相应的架构在 对并行处理的讨论中构成了主要的标准。

在计算模型的竞争中，通过对并行处理的研究，以 下是最积极：驱动控制或多处理器的冯诺依曼形式，数据流以及驱动需求或减少（见［1］［14］） 此外，还包括一些混合模型例如Rediflow［18］以及Eazyflow［16］不同的计算模式强调在不 同的粒度级别的并行开发一般来说，当数据流处于表示层的同时冯诺依曼多处理器的结构 在程序级并行在冯诺依曼多处理器模式中， SIMD 和 MIMD 是有区别的，他们的差别存 在叫唤网络互联拓扑结构，以及是否分组交换和电路交换Treleaven和Hopkins［24］指出冯诺依曼的成功与他的通用性有关对比于迄今为止适用 于通用系统中的有限并行，并行处理的竞争模型的繁荣显示确定真正通用的并行计算模型很 困难我们相信，冯诺依曼的成功还必须与简单概念以及可实现的硬件执行和编程因此， 另一个往往在讨论中被忽略的标准是并行处理涉及到编程和语言的一系列问题并行应该被 明确指定还是在高级语言编译器中被暗中编程及提取？我们是否应该使用已建立的语言或 一个新的语言来实现并行处理（见［21］［20］［15］）？在并行处理中传统的编译器总是在硬件项 目后面两个例外是VLIW结构的费希尔的ELI-512［10］，编译器用于跟踪调度，以及伊利 诺伊大学的 Cedar 项目［11］。

我们的处理方法也是以编译器为导向的我们为并行处理提出了扩展冯诺依曼模型，称 为 Evon Evon 在全球内为中央控制，但是功能指令和独立数据指令可以同时执行，类似于 VLIW结构的费ELI-512,它拥有单一指令流，但是不同于传统的SIMD机类似于ELI-S 12 中的超长指令字，每个Evon指令有可能命令大量的硬件并行运作类似于Cedar，Evon使 用强大的（复合）函数来进行并行计算，同时适用于一定层的数据流的原则在 VLIW 和 Cedar 中， Evon 伴随着一个复杂的编译器，这个编译器追踪用高级语言编写的程序的并行度， 所以程序员不用考虑并行分解的工作和子同步作业 Evon 不同于 VLIW 结构和 Cedar 的是 最有可能或最适合的用于并行机上的高级语言隐含的假设 ELI-512 和 Cedar 假设程序使用 传统的标量冯诺依曼语言例如 Fortune 语言来写，而 Evon 假定程序使用矢量冯诺依曼例如 APL我们将看到下面的编程实例，这种语言的变化对于前面的假设没有很重要意义，这两 个假设是基于什么是在一个高级语言程序并行执行的主要障碍虽然Evon非常想一个向量 超级计算机，下面的章节将介绍Evon比传统的向量处理器负担更高的并行度。

我们应该报告我们关于定义E-code指令集作为Evon模型中特定体现的研究，以及一个 将现有APL的大量的子集转换成E-code的编译器（即E-compiler）的工作E-compiler上 的工作只不过是我们努力实现在高级语言程序固有的并行性的自动提取目标的第一步其第 一阶段的成功完成为我们提供了一个学习类似于用Fortran语言编写的Parafrase的各种固有 的并行的编程任务的有效工具但是我们将能够覆盖一个更广阔的应用领域，包括科学和工 程计算，设计自动化的算法和金融数据处理2. Evon 指令和指令级并行类似于经典的冯诺依曼模型，Evon有一个中央处理单元（CPU），以及通过一个足够的 带宽总线连接到 CPU 的线性处理全局内存内存是交叉的以提高其有效带宽例如，内存 分为 32 个块，著名的冯诺依曼瓶颈依然存在，但它的容量以增加了 32 倍显然，内存带宽 的增加，必须由一个增加的CPU执行的并发配合才能提高整体性能在冯诺依曼模型中，每条指令将一个标量基准从内存移到CPU,在CPU执行单元中操 作；或者将基准从CPU存到内存中每个Evon可以操作没给标量和矢量数据，从CPU移 动一段矢量数据或者标量基准到内存，反之亦然。

Evon操作标量和矢量中的四个基本类型 的数据，布尔，定点数字（整数），浮点数（实）和字oEvon包含了一些常用的冯诺依曼标 量指令，但是大部分Evon为矢量指令Evon的向量指令集包含典型的向量处理器中的所有 算术运算但是还需进一步包含以下：1. 对二进制算术运算的部分结果计算向量，该向量对应于 APL 中的扫描算子，包含减少 的特殊情况2. 根据布尔向量选择和扩大向量集3. 找到关于另一个向量的元素向量的成员和索引4. 向量的轮换和转变5. 元素向量的交换（不包含相应的APL原语）然而，它不包括像矩阵乘法、倒置或随机数生成等特殊性质的功能我们还注意到，在 基本模式下，向量的长度不受限制但是在任何特定的硬件实现内， CPU 里的向量长度要 有一定的逻辑值限制（我们设想不是特定科学应用的计算机的逻辑值为128到1024）话句 话说，当内存中的向量长于CPU设定的逻辑值限制时，向量必须存在于一个真正的CPU向 量寄存器中为了利用Evon模型来实现我们对并行处理的研究，以及使我们的情况更加具体，我们 为简化的Evon计算机设计了一个指令集和E-code图1给出了 Evon计算机的逻辑结构 这个计算机有4个最大长度的向量累加器：BV、CV、IV和EV,它们对应的数据类型为布 尔、字符、整数、浮点数。

一个向量累加器里的一个向量的有效长度根据其类型由内部长度 寄存器BL、CL、IL、EL控制在370系统中它还包括标量寄存器R0-R15，以及F0、F2、 F4和F6E-code比如370是双地址代码，即一个目标操作数可以是标量寄存器、向量累加 器或者存储操作的内存位置［4］中对E-code有进一步说明370系统上E-code 一个基本执 行已经完成我们注意到，这里介绍的 E-code 只作为讨论一些编程实例机器代码的方便的 工具其基本机组织并不代表一个Evon模型的理想实现一个Evon的CPU包含三个部分：（1）负责指令解码、调度和纠错的I-box2）负责 内存地址计算、寄存器文件和内存访问与数据传输的M-boxo （3）负责算术和逻辑运算功能 的 E-box E-box 是操作单元如+、 *、 =等的功能集合对于每个算术功能都有独立的标量和 向量执行内容对每一个向量运算的功能元素，重复的硬件执行单元执行向量部分中实际计 算例如 32 位的浮点乘法器然而在功能元素中重复的次数不同这与相对扩散或不同功 能执行单元的管线级数相关，例如，定点加法器多余乘法器复制硬件设备将克服传统向量 处理的管线级的有效并行的限制。

众所周知，典型的向量指令可以节省一个传统机器上的向量环的重复的指令存取和解码 但是 Evon 包含以下所有向量机中没有的并行特点：首先，Evon硬件支持上面1）到4）中举出的重要的复合操作的并行执行尤其的，操 作数寄存器和功能元素上的执行单元数组可以硬件实现计算一个向量上的特殊二进制运算 的所有部分结果的n倍图2解释了 8要素向量的基本思想我们同时说明了特定功能元素 第一行中，向量V中的8个元素V0-V7被分配8个寄存器R0-R7中经过第一轮的4个加 法器的并行运算，偶数寄存器的内容没有改变，但是奇数寄存器包含了原有内容的总和我 们注意到，图 2中两行的集合代表了一个操作单元，像一个功能元素的加法器第三轮的操 作中，结果存储在r7中在第4 （1+log8）轮的操作中部分值被计算并存于r0-r7中（详细 见[5][6]）第4组中的指令可以通过在与另一个相连的向量寄存器上进行并行相关的研究的 电路执行（然而，Evon并不是关联处理器，因为它不采用相关内存）第二，Evon期望每个指令的基本块（下节中介绍）组成的编译器的流V型流（指令） 是一个指令序列，例如1）包括所有的相同长度的向量（或者所有的标量）， 2）一条指令的 结果作为下一次操作。

一个编译器中的 V 流的指令组是静态链接 Cray-I 的链接技术允许 继承（向量）操作可以作为一个众所周知的操作数我们注意到,Cray-I中的链接在运行时 间完成，然而 Evon 要在编译时完成静态链接的作用是闭环控制微融合例如，下面的 APL 里的代码行E+D+A+CxB翻译成 E-code 为：LIA R1,lOOLDI RI,aBMPI Rl,aCST1 Rl,aAAD1 Rl,aDAD1 Rl,aER1 是向量长度寄存器，它利用隐式向量累加器记录向量长度这些指令的特别意义并 不重要我们想要说明的一点是，刚才的5个指令可以被链接在一起，它们负责整数向量累 加器和内存之间的数据传递以及在整数向量累加器上操作也就是说，这5个指令将与微指 令共享相同的控制结构一个在指令的向量元素进行操作将被进行一旦该元素上的以前的操 作已经完成在微代码级，5 个循环中只有一个长度检查上述第一点的另一个例子如下：当B作为基本人口，以及A[0], A[1]・・・.A[99]作为1到 99岁的死亡率时，计算人口分布律PASCAL语言为：P[0]:= B;FOR I=0 TO 99 DOP[I+l]:= P[I]*（l-A[I]）END;但是在APL中为：P+Bxx\l-A翻译成 E-code 为：LIA Rl,lOOLDE Rl,aASBEM 0ADEM 1MPEPMPEM aBMPEP计算向量元素中的部分，可以通过以（n/logn）速度增长的（n/2）个执行单元来 执行。

我们注意到，这个例子与冯诺依曼结构中程序同步的多处理器的[15]的第3 节中的例 子一模一样基本上有两种循环（在标量冯诺依曼语言中编写的程序），独立循环，即一个 迭代的数据独立于以前的迭代数据；依赖循环，即一个迭代的数据在本质上是依赖以往的迭 代（这意味着依赖不能被重命名删除）上面给出的第一个例子中的链接向量指令是第一种 循环一个向量机可以很容易的通过流水线处理第一类循环加速，阵列结构也可以处理这类 循环数据依赖循环列出了并行的困难，即使它可以被一个向量化程序识别一般情况下， 除了加快探测某些将在一个重叠的方式执行独立部分的循环什么也不能做Evon的这种方 法是使用 APL 的扫描操作为核心来表达这种依赖，并提供一台原始机器，即 1）的指令， 它控制的大量硬件并行的理论上的最佳时机执行令人吃惊的是，本质上相似的大量顺序代 码有一个（n/logn）的增长速度，其中功能元素中可实现的执行单元的数量为n/2例如， 一阶线性递推方程：X[Ol:= x0;FOR I=0 TO 99 DOX[I+1]:= X[I]*A[I]+。