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

《并行处理的扩展冯诺依曼结构》由会员分享，可在线阅读，更多相关《并行处理的扩展冯诺依曼结构（9页珍藏版）》请在金锄头文库上搜索。

1、Evon：并行处理的扩展冯诺依曼结构Wai-Mee Chlng IBM T. J. Watson Research Center P.O. Box 218 Yorktown Heights, New York 10598 摘要我们为并行处理提出了名为Evon的扩展冯诺依曼结构，它是集中控制的，并且可以利 用高级语言程序固有的并行的指令级和表示层。利用并行的有效性很大程度上依赖于强大的 原语，我们通过几个简短的用 APL 编程的例子解释了这一点。然后我们提出了体现 Evon 模型的指令集的设计的工作，以及针对并行自动提取的指令集的便携式编译器。最后，我们 比较了 Evon 与其他的为并行处理提出

2、的基于实际考虑和编程担忧的计算模型和架构。 1. 介绍并行处理的不同方法可以围绕不同的标准来讨论。第一个标准是计算机的专用性还是通 用性。对于特殊目的的并行计算机，例如约克顿模拟引擎，它的速率是序列机 9、19的 5000倍。另一方面，对于一般用途的机器，只有一般的并行已经取得了实际使用，例如Cray X-MP。在对一般用途的高度并行结构的研究中已经提出了许多计算模型和相应的架构。在 对并行处理的讨论中构成了主要的标准。在计算模型的竞争中，通过对并行处理的研究，以 下是最积极：驱动控制或多处理器的冯诺依曼形式，数据流以及驱动需求或减少（见114）。 此外，还包括一些混合模型例如Rediflow

3、18以及Eazyflow16。不同的计算模式强调在不 同的粒度级别的并行开发。一般来说，当数据流处于表示层的同时冯诺依曼多处理器的结构 在程序级并行。在冯诺依曼多处理器模式中， SIMD 和 MIMD 是有区别的，他们的差别存 在叫唤网络互联拓扑结构，以及是否分组交换和电路交换。Treleaven和Hopkins24指出冯诺依曼的成功与他的通用性有关。对比于迄今为止适用 于通用系统中的有限并行，并行处理的竞争模型的繁荣显示确定真正通用的并行计算模型很 困难。我们相信，冯诺依曼的成功还必须与简单概念以及可实现的硬件执行和编程。因此， 另一个往往在讨论中被忽略的标准是并行处理涉及到编程和语言的一系

4、列问题。并行应该被 明确指定还是在高级语言编译器中被暗中编程及提取？我们是否应该使用已建立的语言或 一个新的语言来实现并行处理（见212015）？在并行处理中传统的编译器总是在硬件项 目后面。两个例外是VLIW结构的费希尔的ELI-51210，编译器用于跟踪调度，以及伊利 诺伊大学的 Cedar 项目11。我们的处理方法也是以编译器为导向的。我们为并行处理提出了扩展冯诺依曼模型，称 为 Evon。 Evon 在全球内为中央控制，但是功能指令和独立数据指令可以同时执行，类似于 VLIW结构的费ELI-512,它拥有单一指令流，但是不同于传统的SIMD机。类似于ELI-S 12 中的超长指令字，每

5、个Evon指令有可能命令大量的硬件并行运作。类似于Cedar，Evon使 用强大的（复合）函数来进行并行计算，同时适用于一定层的数据流的原则。在 VLIW 和 Cedar 中， Evon 伴随着一个复杂的编译器，这个编译器追踪用高级语言编写的程序的并行度， 所以程序员不用考虑并行分解的工作和子同步作业。 Evon 不同于 VLIW 结构和 Cedar 的是 最有可能或最适合的用于并行机上的高级语言隐含的假设。 ELI-512 和 Cedar 假设程序使用 传统的标量冯诺依曼语言例如 Fortune 语言来写，而 Evon 假定程序使用矢量冯诺依曼例如 APL。我们将看到下面的编程实例，这种语言

6、的变化对于前面的假设没有很重要意义，这两 个假设是基于什么是在一个高级语言程序并行执行的主要障碍。虽然Evon非常想一个向量 超级计算机，下面的章节将介绍Evon比传统的向量处理器负担更高的并行度。我们应该报告我们关于定义E-code指令集作为Evon模型中特定体现的研究，以及一个 将现有APL的大量的子集转换成E-code的编译器（即E-compiler）的工作。E-compiler上 的工作只不过是我们努力实现在高级语言程序固有的并行性的自动提取目标的第一步。其第 一阶段的成功完成为我们提供了一个学习类似于用Fortran语言编写的Parafrase的各种固有 的并行的编程任务的有效工具。

7、但是我们将能够覆盖一个更广阔的应用领域，包括科学和工 程计算，设计自动化的算法和金融数据处理。2. Evon 指令和指令级并行类似于经典的冯诺依曼模型，Evon有一个中央处理单元（CPU），以及通过一个足够的 带宽总线连接到 CPU 的线性处理全局内存。内存是交叉的以提高其有效带宽。例如，内存 分为 32 个块，著名的冯诺依曼瓶颈依然存在，但它的容量以增加了 32 倍。显然，内存带宽 的增加，必须由一个增加的CPU执行的并发配合才能提高整体性能。在冯诺依曼模型中，每条指令将一个标量基准从内存移到CPU,在CPU执行单元中操 作；或者将基准从CPU存到内存中。每个Evon可以操作没给标量和矢量数

8、据，从CPU移 动一段矢量数据或者标量基准到内存，反之亦然。Evon操作标量和矢量中的四个基本类型 的数据，布尔，定点数字（整数），浮点数（实）和字oEvon包含了一些常用的冯诺依曼标 量指令，但是大部分Evon为矢量指令。Evon的向量指令集包含典型的向量处理器中的所有 算术运算。但是还需进一步包含以下：1. 对二进制算术运算的部分结果计算向量，该向量对应于 APL 中的扫描算子，包含减少 的特殊情况。2. 根据布尔向量选择和扩大向量集。3. 找到关于另一个向量的元素向量的成员和索引。4. 向量的轮换和转变。5. 元素向量的交换（不包含相应的APL原语）然而，它不包括像矩阵乘法、倒置或随机数

9、生成等特殊性质的功能。我们还注意到，在 基本模式下，向量的长度不受限制。但是在任何特定的硬件实现内， CPU 里的向量长度要 有一定的逻辑值限制（我们设想不是特定科学应用的计算机的逻辑值为128到1024）。话句 话说，当内存中的向量长于CPU设定的逻辑值限制时，向量必须存在于一个真正的CPU向 量寄存器中。为了利用Evon模型来实现我们对并行处理的研究，以及使我们的情况更加具体，我们 为简化的Evon计算机设计了一个指令集和E-code。图1给出了 Evon计算机的逻辑结构。 这个计算机有4个最大长度的向量累加器：BV、CV、IV和EV,它们对应的数据类型为布 尔、字符、整数、浮点数。一个向

10、量累加器里的一个向量的有效长度根据其类型由内部长度 寄存器BL、CL、IL、EL控制。在370系统中它还包括标量寄存器R0-R15，以及F0、F2、 F4和F6。E-code比如370是双地址代码，即一个目标操作数可以是标量寄存器、向量累加 器或者存储操作的内存位置。4中对E-code有进一步说明。370系统上E-code 一个基本执 行已经完成。我们注意到，这里介绍的 E-code 只作为讨论一些编程实例机器代码的方便的 工具。其基本机组织并不代表一个Evon模型的理想实现。一个Evon的CPU包含三个部分：（1）负责指令解码、调度和纠错的I-box。（2）负责 内存地址计算、寄存器文件和内

11、存访问与数据传输的M-boxo （3）负责算术和逻辑运算功能 的 E-box。 E-box 是操作单元如+、 *、 =等的功能集合。对于每个算术功能都有独立的标量和 向量执行内容。对每一个向量运算的功能元素，重复的硬件执行单元执行向量部分中实际计 算。例如 32 位的浮点乘法器。然而在功能元素中重复的次数不同。这与相对扩散或不同功 能执行单元的管线级数相关，例如，定点加法器多余乘法器。复制硬件设备将克服传统向量 处理的管线级的有效并行的限制。众所周知，典型的向量指令可以节省一个传统机器上的向量环的重复的指令存取和解码 但是 Evon 包含以下所有向量机中没有的并行特点：首先，Evon硬件支持上

12、面1）到4）中举出的重要的复合操作的并行执行。尤其的，操 作数寄存器和功能元素上的执行单元数组可以硬件实现计算一个向量上的特殊二进制运算 的所有部分结果的n倍。图2解释了 8要素向量的基本思想。我们同时说明了特定功能元素。 第一行中，向量V中的8个元素V0-V7被分配8个寄存器R0-R7中。经过第一轮的4个加 法器的并行运算，偶数寄存器的内容没有改变，但是奇数寄存器包含了原有内容的总和。我 们注意到，图 2中两行的集合代表了一个操作单元，像一个功能元素的加法器。第三轮的操 作中，结果存储在r7中。在第4 （1+log8）轮的操作中部分值被计算并存于r0-r7中（详细 见56）。第4组中的指令可

13、以通过在与另一个相连的向量寄存器上进行并行相关的研究的 电路执行（然而，Evon并不是关联处理器，因为它不采用相关内存）。第二，Evon期望每个指令的基本块（下节中介绍）组成的编译器的流。V型流（指令） 是一个指令序列，例如1）包括所有的相同长度的向量（或者所有的标量）， 2）一条指令的 结果作为下一次操作。一个编译器中的 V 流的指令组是静态链接。 Cray-I 的链接技术允许 继承（向量）操作可以作为一个众所周知的操作数。我们注意到,Cray-I中的链接在运行时 间完成，然而 Evon 要在编译时完成。静态链接的作用是闭环控制微融合。例如，下面的 APL 里的代码行。E+D+A+CxB翻译

14、成 E-code 为：LIA R1,lOOLDI RI,aBMPI Rl,aCST1 Rl,aAAD1 Rl,aDAD1 Rl,aER1 是向量长度寄存器，它利用隐式向量累加器记录向量长度。这些指令的特别意义并 不重要。我们想要说明的一点是，刚才的5个指令可以被链接在一起，它们负责整数向量累 加器和内存之间的数据传递以及在整数向量累加器上操作。也就是说，这5个指令将与微指 令共享相同的控制结构。一个在指令的向量元素进行操作将被进行一旦该元素上的以前的操 作已经完成。在微代码级，5 个循环中只有一个长度检查。上述第一点的另一个例子如下：当B作为基本人口，以及A0, A1.A99作为1到 99岁的

15、死亡率时，计算人口分布律。PASCAL语言为：P0:= B;FOR I=0 TO 99 DOPI+l:= PI*（l-AI）END;但是在APL中为：P+Bxxl-A翻译成 E-code 为：LIA Rl,lOOLDE Rl,aASBEM 0ADEM 1MPEPMPEM aBMPEP计算向量元素中的部分，可以通过以（n/logn）速度增长的（n/2）个执行单元来 执行。我们注意到，这个例子与冯诺依曼结构中程序同步的多处理器的15的第3 节中的例 子一模一样。基本上有两种循环（在标量冯诺依曼语言中编写的程序），独立循环，即一个 迭代的数据独立于以前的迭代数据；依赖循环，即一个迭代的数据在本质上是

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