并行處理的擴(kuò)展馮諾依曼結(jié)構(gòu)

1、Evon：并行處理的擴(kuò)展馮諾依曼結(jié)構(gòu)Wai-Mee ChlngIBM T. J. Watson Research CenterP.O. Box 218Yorktown Heights, New York 10598摘要我們?yōu)椴⑿刑幚硖岢隽嗣麨镋von的擴(kuò)展馮諾依曼結(jié)構(gòu)，它是集中控制的，并且可以利 用高級(jí)語(yǔ)言程序固有的并行的指令級(jí)和表示層。利用并行的有效性很大程度上依賴于強(qiáng)大的 原語(yǔ)，我們通過(guò)幾個(gè)簡(jiǎn)短的用APL編程的例子解釋了這一點(diǎn)。然后我們提出了體現(xiàn)Evon 模型的指令集的設(shè)計(jì)的工作，以及針對(duì)并行自動(dòng)提取的指令集的便攜式編譯器。最后，我們 比較了 Evon與其他的為并行處理提出的基于實(shí)際考慮和

2、編程擔(dān)憂的計(jì)算模型和架構(gòu)。1.介紹并行處理的不同方法可以圍繞不同的標(biāo)準(zhǔn)來(lái)討論。第一個(gè)標(biāo)準(zhǔn)是計(jì)算機(jī)的專用性還是通 用性。對(duì)于特殊目的的并行計(jì)算機(jī)，例如約克頓模擬引擎，它的速率是序列機(jī)9、19的 5000倍。另一方面，對(duì)于一般用途的機(jī)器，只有一般的并行已經(jīng)取得了實(shí)際使用，例如Cray X-MP。在對(duì)一般用途的高度并行結(jié)構(gòu)的研究中已經(jīng)提出了許多計(jì)算模型和相應(yīng)的架構(gòu)。在 對(duì)并行處理的討論中構(gòu)成了主要的標(biāo)準(zhǔn)。在計(jì)算模型的競(jìng)爭(zhēng)中，通過(guò)對(duì)并行處理的研究，以 下是最積極:驅(qū)動(dòng)控制或多處理器的馮諾依曼形式，數(shù)據(jù)流以及驅(qū)動(dòng)需求或減少（見(jiàn)114）。 此外，還包括一些混合模型例如Rediflow18以及Eazyflo

3、w16。不同的計(jì)算模式強(qiáng)調(diào)在不 同的粒度級(jí)別的并行開(kāi)發(fā)。一般來(lái)說(shuō)，當(dāng)數(shù)據(jù)流處于表示層的同時(shí)馮諾依曼多處理器的結(jié)構(gòu) 在程序級(jí)并行。在馮諾依曼多處理器模式中，SIMD和MIMD是有區(qū)別的，他們的差別存 在叫喚網(wǎng)絡(luò)互聯(lián)拓?fù)浣Y(jié)構(gòu)，以及是否分組交換和電路交換。Treleaven和Hopkins24指出馮諾依曼的成功與他的通用性有關(guān)。對(duì)比于迄今為止適用 于通用系統(tǒng)中的有限并行，并行處理的競(jìng)爭(zhēng)模型的繁榮顯示確定真正通用的并行計(jì)算模型很 困難。我們相信，馮諾依曼的成功還必須與簡(jiǎn)單概念以及可實(shí)現(xiàn)的硬件執(zhí)行和編程。因此， 另一個(gè)往往在討論中被忽略的標(biāo)準(zhǔn)是并行處理涉及到編程和語(yǔ)言的一系列問(wèn)題。并行應(yīng)該被 明確指定還

4、是在高級(jí)語(yǔ)言編譯器中被暗中編程及提??？我們是否應(yīng)該使用已建立的語(yǔ)言或 一個(gè)新的語(yǔ)言來(lái)實(shí)現(xiàn)并行處理（見(jiàn)212015）？在并行處理中傳統(tǒng)的編譯器總是在硬件項(xiàng) 目后面。兩個(gè)例外是VLIW結(jié)構(gòu)的費(fèi)希爾的ELI-51210，編譯器用于跟蹤調(diào)度，以及伊利 諾伊大學(xué)的Cedar項(xiàng)目11。我們的處理方法也是以編譯器為導(dǎo)向的。我們?yōu)椴⑿刑幚硖岢隽藬U(kuò)展馮諾依曼模型，稱 為Evon。Evon在全球內(nèi)為中央控制，但是功能指令和獨(dú)立數(shù)據(jù)指令可以同時(shí)執(zhí)行，類似于 VLIW結(jié)構(gòu)的費(fèi)ELI-512,它擁有單一指令流，但是不同于傳統(tǒng)的SIMD機(jī)。類似于ELI-S 12 中的超長(zhǎng)指令字，每個(gè)Evon指令有可能命令大量的硬件并行運(yùn)

5、作。類似于Cedar，Evon使 用強(qiáng)大的（復(fù)合）函數(shù)來(lái)進(jìn)行并行計(jì)算，同時(shí)適用于一定層的數(shù)據(jù)流的原則。在VLIW和 Cedar中，Evon伴隨著一個(gè)復(fù)雜的編譯器，這個(gè)編譯器追蹤用高級(jí)語(yǔ)言編寫(xiě)的程序的并行度， 所以程序員不用考慮并行分解的工作和子同步作業(yè)。Evon不同于VLIW結(jié)構(gòu)和Cedar的是 最有可能或最適合的用于并行機(jī)上的高級(jí)語(yǔ)言隱含的假設(shè)。ELI-512和Cedar假設(shè)程序使用 傳統(tǒng)的標(biāo)量馮諾依曼語(yǔ)言例如Fortune語(yǔ)言來(lái)寫(xiě)，而Evon假定程序使用矢量馮諾依曼例如 APL。我們將看到下面的編程實(shí)例，這種語(yǔ)言的變化對(duì)于前面的假設(shè)沒(méi)有很重要意義，這兩 個(gè)假設(shè)是基于什么是在一個(gè)高級(jí)語(yǔ)言程序

6、并行執(zhí)行的主要障礙。雖然Evon非常想一個(gè)向量 超級(jí)計(jì)算機(jī)，下面的章節(jié)將介紹Evon比傳統(tǒng)的向量處理器負(fù)擔(dān)更高的并行度。我們應(yīng)該報(bào)告我們關(guān)于定義E-code指令集作為Evon模型中特定體現(xiàn)的研究，以及一個(gè) 將現(xiàn)有APL的大量的子集轉(zhuǎn)換成E-code的編譯器（即E-compiler）的工作。E-compiler上 的工作只不過(guò)是我們努力實(shí)現(xiàn)在高級(jí)語(yǔ)言程序固有的并行性的自動(dòng)提取目標(biāo)的第一步。其第 一階段的成功完成為我們提供了一個(gè)學(xué)習(xí)類似于用Fortran語(yǔ)言編寫(xiě)的Parafrase的各種固有 的并行的編程任務(wù)的有效工具。但是我們將能夠覆蓋一個(gè)更廣闊的應(yīng)用領(lǐng)域，包括科學(xué)和工 程計(jì)算，設(shè)計(jì)自動(dòng)化的算法

7、和金融數(shù)據(jù)處理。2. Evon指令和指令級(jí)并行類似于經(jīng)典的馮諾依曼模型，Evon有一個(gè)中央處理單元（CPU），以及通過(guò)一個(gè)足夠的 帶寬總線連接到CPU的線性處理全局內(nèi)存。內(nèi)存是交叉的以提高其有效帶寬。例如，內(nèi)存 分為32個(gè)塊，著名的馮諾依曼瓶頸依然存在，但它的容量以增加了 32倍。顯然，內(nèi)存帶寬 的增加，必須由一個(gè)增加的CPU執(zhí)行的并發(fā)配合才能提高整體性能。在馮諾依曼模型中，每條指令將一個(gè)標(biāo)量基準(zhǔn)從內(nèi)存移到CPU，在CPU執(zhí)行單元中操 作；或者將基準(zhǔn)從CPU存到內(nèi)存中。每個(gè)Evon可以操作沒(méi)給標(biāo)量和矢量數(shù)據(jù)，從CPU移 動(dòng)一段矢量數(shù)據(jù)或者標(biāo)量基準(zhǔn)到內(nèi)存，反之亦然。Evon操作標(biāo)量和矢量中的四個(gè)

8、基本類型 的數(shù)據(jù)，布爾，定點(diǎn)數(shù)字（整數(shù)），浮點(diǎn)數(shù)（實(shí)）和字Evon包含了一些常用的馮諾依曼標(biāo) 量指令，但是大部分Evon為矢量指令。Evon的向量指令集包含典型的向量處理器中的所有 算術(shù)運(yùn)算。但是還需進(jìn)一步包含以下：對(duì)二進(jìn)制算術(shù)運(yùn)算的部分結(jié)果計(jì)算向量，該向量對(duì)應(yīng)于APL中的掃描算子，包含減少 的特殊情況。根據(jù)布爾向量選擇和擴(kuò)大向量集。找到關(guān)于另一個(gè)向量的元素向量的成員和索引。向量的輪換和轉(zhuǎn)變。元素向量的交換（不包含相應(yīng)的APL原語(yǔ)）然而，它不包括像矩陣乘法、倒置或隨機(jī)數(shù)生成等特殊性質(zhì)的功能。我們還注意到，在 基本模式下，向量的長(zhǎng)度不受限制。但是在任何特定的硬件實(shí)現(xiàn)內(nèi)，CPU里的向量長(zhǎng)度要 有一

9、定的邏輯值限制（我們?cè)O(shè)想不是特定科學(xué)應(yīng)用的計(jì)算機(jī)的邏輯值為128到1024）。話句 話說(shuō)，當(dāng)內(nèi)存中的向量長(zhǎng)于CPU設(shè)定的邏輯值限制時(shí)，向量必須存在于一個(gè)真正的CPU向 量寄存器中。為了利用Evon模型來(lái)實(shí)現(xiàn)我們對(duì)并行處理的研究，以及使我們的情況更加具體，我們 為簡(jiǎn)化的Evon計(jì)算機(jī)設(shè)計(jì)了一個(gè)指令集和E-code。圖1給出了 Evon計(jì)算機(jī)的邏輯結(jié)構(gòu)。 這個(gè)計(jì)算機(jī)有4個(gè)最大長(zhǎng)度的向量累加器：BV、CV、IV和EV，它們對(duì)應(yīng)的數(shù)據(jù)類型為布 爾、字符、整數(shù)、浮點(diǎn)數(shù)。一個(gè)向量累加器里的一個(gè)向量的有效長(zhǎng)度根據(jù)其類型由內(nèi)部長(zhǎng)度 寄存器BL、CL、IL、EL控制。在370系統(tǒng)中它還包括標(biāo)量寄存器R0-R15

10、，以及F0、F2、 F4和F6。E-code比如370是雙地址代碼，即一個(gè)目標(biāo)操作數(shù)可以是標(biāo)量寄存器、向量累加 器或者存儲(chǔ)操作的內(nèi)存位置。4中對(duì)E-code有進(jìn)一步說(shuō)明。370系統(tǒng)上E-code 一個(gè)基本執(zhí) 行已經(jīng)完成。我們注意到，這里介紹的E-code只作為討論一些編程實(shí)例機(jī)器代碼的方便的 工具。其基本機(jī)組織并不代表一個(gè)Evon模型的理想實(shí)現(xiàn)。一個(gè)Evon的CPU包含三個(gè)部分：（1）負(fù)責(zé)指令解碼、調(diào)度和糾錯(cuò)的I-box。（2）負(fù)責(zé) 內(nèi)存地址計(jì)算、寄存器文件和內(nèi)存訪問(wèn)與數(shù)據(jù)傳輸?shù)腗-box。（3）負(fù)責(zé)算術(shù)和邏輯運(yùn)算功能 的E-box。E-box是操作單元如+、*、=等的功能集合。對(duì)于每個(gè)算術(shù)功

11、能都有獨(dú)立的標(biāo)量和 向量執(zhí)行內(nèi)容。對(duì)每一個(gè)向量運(yùn)算的功能元素，重復(fù)的硬件執(zhí)行單元執(zhí)行向量部分中實(shí)際計(jì) 算。例如32位的浮點(diǎn)乘法器。然而在功能元素中重復(fù)的次數(shù)不同。這與相對(duì)擴(kuò)散或不同功 能執(zhí)行單元的管線級(jí)數(shù)相關(guān)，例如，定點(diǎn)加法器多余乘法器。復(fù)制硬件設(shè)備將克服傳統(tǒng)向量 處理的管線級(jí)的有效并行的限制。眾所周知，典型的向量指令可以節(jié)省一個(gè)傳統(tǒng)機(jī)器上的向量環(huán)的重復(fù)的指令存取和解碼。 但是Evon包含以下所有向量機(jī)中沒(méi)有的并行特點(diǎn)：首先，Evon硬件支持上面1）到4）中舉出的重要的復(fù)合操作的并行執(zhí)行。尤其的，操 作數(shù)寄存器和功能元素上的執(zhí)行單元數(shù)組可以硬件實(shí)現(xiàn)計(jì)算一個(gè)向量上的特殊二進(jìn)制運(yùn)算 的所有部分結(jié)果

12、的n倍。圖2解釋了 8要素向量的基本思想。我們同時(shí)說(shuō)明了特定功能元素。 第一行中，向量V中的8個(gè)元素V0-V7被分配8個(gè)寄存器R0-R7中。經(jīng)過(guò)第一輪的4個(gè)加 法器的并行運(yùn)算，偶數(shù)寄存器的內(nèi)容沒(méi)有改變，但是奇數(shù)寄存器包含了原有內(nèi)容的總和。我 們注意到，圖2中兩行的集合代表了一個(gè)操作單元，像一個(gè)功能元素的加法器。第三輪的操 作中，結(jié)果存儲(chǔ)在r7中。在第4（1+log8）輪的操作中部分值被計(jì)算并存于r0-r7中（詳細(xì) 見(jiàn)56）。第4組中的指令可以通過(guò)在與另一個(gè)相連的向量寄存器上進(jìn)行并行相關(guān)的研究的 電路執(zhí)行（然而，Evon并不是關(guān)聯(lián)處理器，因?yàn)樗徊捎孟嚓P(guān)內(nèi)存）。第二，Evon期望每個(gè)指令的基本塊

13、（下節(jié)中介紹）組成的編譯器的流。V型流（指令） 是一個(gè)指令序列，例如1）包括所有的相同長(zhǎng)度的向量（或者所有的標(biāo)量），2）一條指令的 結(jié)果作為下一次操作。一個(gè)編譯器中的V流的指令組是靜態(tài)鏈接。Cray-I的鏈接技術(shù)允許 繼承（向量）操作可以作為一個(gè)眾所周知的操作數(shù)。我們注意到，Cray-I中的鏈接在運(yùn)行時(shí) 間完成，然而Evon要在編譯時(shí)完成。靜態(tài)鏈接的作用是閉環(huán)控制微融合。例如，下面的 APL里的代碼行。E+D+A+CxB翻譯成E-code為：LIA R1,lOOLDI RI,aBMPI Rl,aCST1 Rl,aAAD1 Rl,aDAD1 Rl,aER1是向量長(zhǎng)度寄存器，它利用隱式向量累加器記

14、錄向量長(zhǎng)度。這些指令的特別意義并 不重要。我們想要說(shuō)明的一點(diǎn)是，剛才的5個(gè)指令可以被鏈接在一起，它們負(fù)責(zé)整數(shù)向量累 加器和內(nèi)存之間的數(shù)據(jù)傳遞以及在整數(shù)向量累加器上操作。也就是說(shuō)，這5個(gè)指令將與微指 令共享相同的控制結(jié)構(gòu)。一個(gè)在指令的向量元素進(jìn)行操作將被進(jìn)行一旦該元素上的以前的操 作已經(jīng)完成。在微代碼級(jí)，5個(gè)循環(huán)中只有一個(gè)長(zhǎng)度檢查。上述第一點(diǎn)的另一個(gè)例子如下：當(dāng)B作為基本人口，以及A0，A1.A99作為1到 99歲的死亡率時(shí)，計(jì)算人口分布律。PASCAL語(yǔ)言為：P0:= B;FOR I=0 TO 99 DOPI+l:= PI*（l-AI）END;但是在APL中為：P+Bxxl-A翻譯成E-cod

15、e為：LIA Rl,lOOLDE Rl,aASBEM 0ADEM 1MPEPMPEM aBMPEP計(jì)算向量元素中的部分，可以通過(guò)以（n/logn）速度增長(zhǎng)的（n/2）個(gè)執(zhí)行單元來(lái) 執(zhí)行。我們注意到，這個(gè)例子與馮諾依曼結(jié)構(gòu)中程序同步的多處理器的15的第3節(jié)中的例 子一模一樣?；旧嫌袃煞N循環(huán)（在標(biāo)量馮諾依曼語(yǔ)言中編寫(xiě)的程序），獨(dú)立循環(huán)，即一個(gè) 迭代的數(shù)據(jù)獨(dú)立于以前的迭代數(shù)據(jù)；依賴循環(huán)，即一個(gè)迭代的數(shù)據(jù)在本質(zhì)上是依賴以往的迭 代（這意味著依賴不能被重命名刪除）。上面給出的第一個(gè)例子中的鏈接向量指令是第一種 循環(huán)。一個(gè)向量機(jī)可以很容易的通過(guò)流水線處理第一類循環(huán)加速，陣列結(jié)構(gòu)也可以處理這類 循環(huán)。數(shù)據(jù)

16、依賴循環(huán)列出了并行的困難，即使它可以被一個(gè)向量化程序識(shí)別。一般情況下， 除了加快探測(cè)某些將在一個(gè)重疊的方式執(zhí)行獨(dú)立部分的循環(huán)什么也不能做。Evon的這種方 法是使用APL的掃描操作為核心來(lái)表達(dá)這種依賴，并提供一臺(tái)原始機(jī)器，即1）的指令， 它控制的大量硬件并行的理論上的最佳時(shí)機(jī)執(zhí)行。令人吃驚的是，本質(zhì)上相似的大量順序代 碼有一個(gè)（n/logn）的增長(zhǎng)速度，其中功能元素中可實(shí)現(xiàn)的執(zhí)行單元的數(shù)量為n/2。例如， 一階線性遞推方程：XOl:= x0;FOR I=0 TO 99 DOXI+1:= XI*AI+DIEND;可以在一個(gè)APL序列中被編碼為：I*睥/ （0,3） +（3如F并且可以得益于支持快

17、速執(zhí)行原語(yǔ)的硬件支持。我們要說(shuō)明的單行編碼并不是很好。相反，如果一種語(yǔ)言（或機(jī)器）包含足夠的高層原 語(yǔ)，那么我們可以加速存儲(chǔ)處理一些重要的數(shù)據(jù)依賴循環(huán)的類。APL單行代碼是功能程序， 即計(jì)算中沒(méi)有狀態(tài)的變化。高級(jí)原語(yǔ)在相應(yīng)的PASCAL版本上吸收原先的控制結(jié)構(gòu)，并把 一個(gè)數(shù)據(jù)依賴循環(huán)轉(zhuǎn)換為表達(dá)式樹(shù)。此外，并行利用每個(gè)Evon指令的相應(yīng)的執(zhí)行節(jié)點(diǎn)，樹(shù) 的許多分支可以并行處理，我們將在下節(jié)中介紹。從標(biāo)量馮諾依曼語(yǔ)言的角度來(lái)看，指令集并行中很少能夠得到并行。但在擴(kuò)展的馮諾依 曼模型Evon中，許多硬件支持高級(jí)原語(yǔ)，情況就變得完全不同。我們可以利用指令集并行 來(lái)大大加速計(jì)算?；究煺{(diào)度和局部數(shù)據(jù)流編譯

18、程序每次最多執(zhí)行一個(gè)基本塊。一個(gè)基本快是一組除了第一個(gè)和最后一個(gè)分支指令 之外沒(méi)有其他分支指令的指令群組。我們使用”基本塊”來(lái)表示“最大塊”。如果我們采取APL 那樣的高級(jí)語(yǔ)言作為源語(yǔ)言，那么一個(gè)基本塊由編譯器的解釋程序產(chǎn)生的表達(dá)式樹(shù)組成。每 個(gè)表達(dá)式樹(shù)可以在數(shù)據(jù)依賴限制和硬件單元限制下并行的執(zhí)行。另外，基本塊中的表達(dá)式樹(shù)， 可以不按照源代碼中的相應(yīng)序列來(lái)順序執(zhí)行。換句話說(shuō)，Evon是由中央控制的，每次根據(jù) 程序流程圖執(zhí)行一個(gè)基本塊，但是根據(jù)數(shù)據(jù)流原則在本地執(zhí)行它的代碼塊。在我們討論指令調(diào)度計(jì)劃前，先描述一下Evon的指令處理單元，I-box，一般術(shù)語(yǔ)I-box 擁有一個(gè)指令緩沖區(qū)，大的足以容

19、納每個(gè)平均大小的基本塊的所有機(jī)器指令。I-box的前端 部分是指令的編碼單元，可以把指令編碼為幾個(gè)并行指令。為了具體描述，我們假定每個(gè)指 令32bit寬。每次可以編碼4到8個(gè)指令。Evon的這部分很像ELI-512的超長(zhǎng)指令字。指令 編碼單元有自己的加法器可以計(jì)算地址。還有一個(gè)基本功用寄存器叫做f-register,用來(lái)指示 任意機(jī)器周期的功能碼元是空閑和執(zhí)行狀態(tài)。I-box的末端部分是一個(gè)獨(dú)立的指令棧。我們 假定在Evon中有3到8個(gè)指令棧。每個(gè)棧的頂端保存著一個(gè)在硬件單元可用時(shí)即將發(fā)出的 指令。我們?cè)谇懊嬉呀?jīng)介紹了 v-streams的概念。一個(gè)表達(dá)式樹(shù)可以被分解為指令v-streams組

20、。 但是，編譯器首先計(jì)算內(nèi)部數(shù)據(jù)依賴。這些依賴來(lái)自我們所關(guān)心的基本塊中的指令分配變量 和使用這些變量作為操作數(shù)的指令。我們之所以忽略塊間數(shù)據(jù)依賴，一個(gè)很簡(jiǎn)單的原因是編 譯器程序每次僅執(zhí)行一個(gè)基本塊。當(dāng)一個(gè)基本塊中的代碼塊被裝載進(jìn)指令緩沖區(qū)時(shí)，所有的 變量實(shí)體被假定安排在基本塊外，而且已經(jīng)有正確的值。V-stream然后被大碎成塊，這些碎 片被稱為i-sequences，i-sequences的頭部指令盡可能和同一塊中的其他指令有依賴?；緣K的指令調(diào)度計(jì)劃可以如下描述：一個(gè)基本塊中的指令的獨(dú)立i-sequences被編碼裝 載進(jìn)各自的指令棧，然后靜靜地等待被執(zhí)行。在每組i-sequences的開(kāi)

21、始執(zhí)行階段，這個(gè)階 段中的指令是內(nèi)部相互獨(dú)立的，而且在不相關(guān)的功能項(xiàng)中執(zhí)行，他們被裝進(jìn)指令棧和 i-sequences同時(shí)并行執(zhí)行。如果有競(jìng)爭(zhēng)，由于指令棧數(shù)量的限制，編譯器將選擇擁有最多 i-sequences數(shù)據(jù)依賴的指令。每個(gè)指令會(huì)將即將執(zhí)行的功能位置位，每個(gè)即將被分配的指令 會(huì)將相應(yīng)位寫(xiě)進(jìn)指令。編碼和啟動(dòng)指令然后檢查f-register看看所需的功能項(xiàng)是否空閑。如 果是，指令棧中的最頂端的將被發(fā)布執(zhí)行。假設(shè)一個(gè)i-sequences向量，如果不是所有的功 能項(xiàng)可以在一個(gè)時(shí)間被保護(hù)，機(jī)器將打亂指令流。那就是說(shuō)，Evon機(jī)器不會(huì)堅(jiān)持按照向量 循環(huán)形狀來(lái)執(zhí)行。它可以分別執(zhí)行每個(gè)循環(huán)來(lái)利用可用的

22、功能單元。因此他很像一個(gè)加法器， 一個(gè)累加器，或者一個(gè)向量，在一個(gè)運(yùn)行的編譯程序中同時(shí)執(zhí)行。我們注意到這種類型的并 行在CDC Cyber系列和CRAY-1中已經(jīng)可用。因此，這些運(yùn)行時(shí)間檢測(cè)在傳統(tǒng)矢量機(jī)器中 的使用被認(rèn)為更加復(fù)雜。我們將簡(jiǎn)要闡述調(diào)度和基于編譯時(shí)間依賴的塊內(nèi)并行策略，用下面的例子：找出2到N 的所有素?cái)?shù)。不像FORTRAN和PASCAL那樣，我們有如下N; V+ 2（洲1）岳2它的分析樹(shù)如圖3所示。基本上，他設(shè)置了一個(gè)乘法表，而且奇數(shù)矢量要被檢查。沒(méi)有在表 中的數(shù)字是主要的數(shù)字。這個(gè)指令流對(duì)應(yīng)于右子樹(shù)，V的計(jì)算是互相獨(dú)立的。簡(jiǎn)言之，這兩 個(gè)被兩個(gè)打點(diǎn)的半圓環(huán)描繪的子樹(shù)，是數(shù)據(jù)獨(dú)立

23、的。他們是計(jì)算的主要部分，可以被分別獨(dú) 立執(zhí)行。這個(gè)例子顯示了 Evon可以成功的支持表達(dá)式級(jí)的并行。我們注意到在我們接近表達(dá)式式級(jí)的并行的開(kāi)發(fā)和表達(dá)式處理器，還有塊驅(qū)動(dòng)數(shù)據(jù)流處 理器和并行順序程序執(zhí)行工作都有著很多的相似。我們的調(diào)度更加特殊和不同。我們的功 能項(xiàng)僅僅有執(zhí)行特殊功能的能力。多數(shù)并行工作的程序并非我們假定的那樣已經(jīng)序列化。并 且我們僅僅限制在一個(gè)基本塊。但是他們?cè)诤芏嗖糠质遣煌?。尤其是每個(gè)指令沒(méi)有被假定 為等量的時(shí)間，我們還考慮了硬件執(zhí)行時(shí)間的限制。無(wú)論是Evon還是典型的矢量機(jī)器，他們的目標(biāo)都是使矢量指令更快的運(yùn)行。但是Evon 來(lái)自于復(fù)制硬件執(zhí)行單元，不是簡(jiǎn)單的流水線技術(shù)，

24、在數(shù)據(jù)的執(zhí)行上加速，支持一些混合操 作例如掃描，而大多數(shù)向量機(jī)僅支持縮小。更重要的是，Evon模型依靠基本塊中的數(shù)據(jù)依 賴編譯時(shí)間檢測(cè)，并且依靠相應(yīng)的硬件支持，盡可能的達(dá)到表達(dá)級(jí)的并行，而這些在向量機(jī) 中是很難解決的。語(yǔ)言和編譯器對(duì)多處理器的并行計(jì)算的研究多是用的fortran或者pascal。數(shù)據(jù)流需要需要新的數(shù)據(jù)流 語(yǔ)言，比如val和id。我們也能夠設(shè)計(jì)一個(gè)新的語(yǔ)言。新語(yǔ)言的問(wèn)題是在編寫(xiě)實(shí)時(shí)程序時(shí)的 不足。我們也能夠使用老的語(yǔ)言，比如Fortran。幸運(yùn)的是，有一個(gè)叫做APL的語(yǔ)言適合我 們的要求，這種語(yǔ)言滿足我們并行計(jì)算的要求，不像Fortran是串行。事實(shí)上，APL語(yǔ)言強(qiáng) 調(diào)了并行計(jì)算

25、的重要性。雖然APL不像Fortran應(yīng)用那么廣泛，但是它也在很多地方用了很 長(zhǎng)時(shí)間，不如科學(xué)計(jì)算、設(shè)計(jì)自動(dòng)算法、金融計(jì)算。它對(duì)并行計(jì)算很重要。我們還寫(xiě)了 APL 機(jī)，APL是解釋執(zhí)行的，我們的目標(biāo)是使APL機(jī)解釋執(zhí)行更快。它有快速的語(yǔ)法單元。過(guò) 去在這個(gè)方向的努力是微程序。APL的問(wèn)題是沒(méi)有一個(gè)可用的編譯器。這個(gè)阻礙了我們的研究，我們沒(méi)有現(xiàn)成的代碼 去學(xué)習(xí)，去安排實(shí)驗(yàn)。因此我們?cè)O(shè)計(jì)了 E-code。他包括了95的語(yǔ)言特征，工程和科學(xué)中 的APL程序都能夠編譯，不需要特別改變。特別是它不需要聲明變量和類型。編譯器的前 期已經(jīng)基本完成。他包含了組件來(lái)分析類型，變量和數(shù)據(jù)流分析。本地?cái)?shù)據(jù)能夠很容易

26、的插 入局部，我們也能偶增加其他的組件。后期工作的主要部分也實(shí)現(xiàn)了，事實(shí)上，我們已經(jīng)能 夠編譯的函數(shù)在370系統(tǒng)上。編譯器證實(shí)了 APL語(yǔ)言確實(shí)有功能強(qiáng)大。我們編譯了三個(gè)程序。i)SIMPLE模擬打印機(jī) ii)CUT包含大量的布爾計(jì)算和算法。iii)GRAFSTAT用于靜態(tài)分析和繪圖。下面的表寫(xiě)出了 函數(shù)的數(shù)量，代碼的行數(shù)，節(jié)點(diǎn)數(shù)。一個(gè)典型的Fortran程序的節(jié)點(diǎn)數(shù)是10。APL的節(jié)點(diǎn)數(shù) 比Fortran少。記載了大塊的平均數(shù)量，控制計(jì)算時(shí)間?；緣K的平均大小很重要。最終，這三個(gè)程序沒(méi)有Fortran和Pascal版本。這意味著APL比Fortran更適合并行計(jì)算。從這些程序我們能夠看出指令

27、級(jí)的并行。我們希望學(xué)習(xí)各個(gè)領(lǐng)域的現(xiàn)存的 程序。我們也希望在一些計(jì)算量大的地方用APL編程，以前只能用Fortran的地方。和其他的并行結(jié)構(gòu)比較Neumann模型和數(shù)據(jù)流模型是并行計(jì)算模型中兩個(gè)最熱的方向。他們的擁護(hù)者都寫(xiě)了 很多文章。我們應(yīng)該比較一下Neumann模型、數(shù)據(jù)流模型和VLIW結(jié)構(gòu)。我不是說(shuō)我們要 批評(píng)這兩種流行的方法和VLIW的創(chuàng)新。我們只是想說(shuō)明Evon對(duì)一般的并行計(jì)算應(yīng)用來(lái)說(shuō) 是一種更務(wù)實(shí)有效的方法，是一個(gè)應(yīng)該研究的方向。Evon和數(shù)據(jù)流模型都試圖發(fā)現(xiàn)表現(xiàn)層次的并行，兩種方法的并行都是毫無(wú)疑問(wèn)的。數(shù)據(jù)流 模型是指令級(jí)的并行，這和Neumann恰好相反。然而，指令可能浪費(fèi)時(shí)間去

28、等待不需要的 爭(zhēng)論。穿過(guò)數(shù)據(jù)流圖的都是變量，既然不允許使用單任務(wù)的數(shù)據(jù)流語(yǔ)言副作用的出現(xiàn)，兩個(gè) 另外的可靠的操作都可以保證執(zhí)行的順序。沒(méi)有什么能夠阻止數(shù)據(jù)循環(huán)。這些都表現(xiàn)在數(shù)據(jù) 流圖上，因此我們需要標(biāo)記不同的鄰近的計(jì)算。結(jié)構(gòu)復(fù)雜的內(nèi)部控制模式被發(fā)明用來(lái)解決這 個(gè)問(wèn)題。管理輸入輸出隊(duì)列的困難時(shí)因?yàn)樗麄冊(cè)谝粋€(gè)低層次的抽象，換句話說(shuō)，就是并行的 粒度太小。對(duì)比來(lái)看，Evon利用了矢量操作，能夠高水平的處理矢量循環(huán)和頻繁的數(shù)據(jù)依賴循環(huán)。 總體控制是集中的，計(jì)算是分布式的。換句話說(shuō)，把一個(gè)大的計(jì)算分成很多小的計(jì)算，然后 把結(jié)果組織起來(lái)，這樣更容易實(shí)現(xiàn)。我們可以把Neumann并行模型看成是經(jīng)典Neuma

29、nn模型的水平擴(kuò)展，而Evon是垂直。 嚴(yán)格的說(shuō)，Evon既不是SIMD也不是MIMD，但是它有點(diǎn)像SIMD機(jī)器。在SIMD機(jī)器中， 每個(gè)進(jìn)程都有指令處理能力。在Evon中功能處理模塊只能夠執(zhí)行特定的操作。中心指令處 理和行程安排依賴硬件電路。即便是在MIMD機(jī)器就像Neumann機(jī)器，在一個(gè)進(jìn)程中同時(shí) 處理加法和乘法也是不可能。從硬件的角度來(lái)看，Evon更有效。從另一個(gè)角度看，Neumann 在處理陣列上有兩個(gè)有點(diǎn)。第一，微處理器廣泛引用，第二，規(guī)模不大。例如，我們能夠把 成百上千的處理器連接起來(lái)。在Evon中，平均有1.5到4個(gè)功能單元工作，每個(gè)功能單元 的64個(gè)執(zhí)行單元能加速大約100。

30、管道技術(shù)能夠大大增加速度，但這不是Evon獨(dú)有的。理論上，MIDM機(jī)器也能夠開(kāi)發(fā)表現(xiàn)層并行。就像Gottlieb和Schwartz在“網(wǎng)絡(luò)和大規(guī)模 并行算法”中指出的那樣，超計(jì)算機(jī)能夠模擬數(shù)據(jù)流機(jī)器。如果用數(shù)據(jù)流模型來(lái)進(jìn)行表現(xiàn)層 并行那將是一個(gè)不可能完成的工作。MIMD機(jī)器上網(wǎng)絡(luò)傳輸是繁忙的，一次一個(gè)多處理器 的Neumann MIMD機(jī)器能夠有效的解決這個(gè)問(wèn)題。它需要制定一個(gè)工作規(guī)則，程序員必須 寫(xiě)出并行執(zhí)行的程序。從另一個(gè)角度來(lái)看，Evon做這個(gè)事情就簡(jiǎn)單多了。但是類超計(jì)算 MIMD做起來(lái)比Evon更簡(jiǎn)單。感覺(jué)來(lái)說(shuō)，Evon有更大的潛力。VLIW結(jié)構(gòu)比Neumann機(jī)器需要更少的規(guī)則，因?yàn)?/p>

31、VLIW經(jīng)過(guò)這么多年的發(fā)展已經(jīng)很成熟， 確實(shí)，很多例子都說(shuō)明VLIW方法的分支方向是矢量循環(huán)。Evon能夠在更廣泛的并行計(jì)算 領(lǐng)域里面應(yīng)用，因?yàn)楫?dāng)程序用Neumann語(yǔ)言來(lái)寫(xiě)，編譯器能夠做更有效的工作。結(jié)束以上我們介紹了并行計(jì)算的模型。它是由分布全球的控制中心和本地分布式計(jì)算組織起 來(lái)的一個(gè)多功能的系統(tǒng)。它能夠有效的執(zhí)行矢量命令，并且有硬件支持混合的大規(guī)模循環(huán)計(jì) 算。不僅可以并行執(zhí)行制冷，不同的硬件功能單元還可以并行執(zhí)行無(wú)關(guān)的數(shù)據(jù)。它沒(méi)有清晰 的流程，而是從高級(jí)語(yǔ)言編譯器中自動(dòng)提煉來(lái)的。我們?yōu)樗x了指令系統(tǒng)，并實(shí)現(xiàn)了一個(gè) 編譯器。我相信在很多科學(xué)或者工程即使是商業(yè)應(yīng)用，循環(huán)操作都要占用一大部

32、分時(shí)間，如 果我們能夠發(fā)現(xiàn)更有效的節(jié)省的方法去做這種計(jì)算，那我們就使并行計(jì)算在實(shí)際工程中前進(jìn) 了一大步。從何其他的并行計(jì)算模型的比較中，我們看出了我們的優(yōu)點(diǎn)，但是不同的模型被設(shè)計(jì)用 在并行計(jì)算的不同層次何以互補(bǔ)。我們需要測(cè)試現(xiàn)有的模型，用不同類型語(yǔ)言實(shí)現(xiàn)，讓我們 更好的理解各種各樣的方法。致謝我要感謝George Almasi在這個(gè)研究上對(duì)我的支持和鼓勵(lì)。參考文獻(xiàn)T. Agerwala and Arvind, ed., Data Flow System, IEEE Computer, Feb., 1982.Arvind and R.A. Iannucci, A Critique of Mult

33、iprocessing von Neumann Style, Proc. 10hAnnual Intl Symposium on Computer Architecture, 426-436,1983.T.L.Chang and F.D. Fisher, A Block-driven Data- flow Processor, Proc. Infl Conf, on Parallel Processing, 151-155, 1982.W.M. Ching, A Portable Compiler for Parallel Machines, Proc. IEEE Intl Conf, on

34、ComputerDesign, 592-596, 1984.W.M. Ching and D. L. Ostapko, Hardware and an Algorithm for Performing Parallel Prefix Calculation, IBM Technical Disclosure Bulletin, No.Y0884-0007. May, 1984.W.M. Ching and D. L. Ostapko. Regular and Fast Hardware Interconnection for a Group of Execution Units to Calc

35、ulate All Partial Results of an Associative Operation, IBM Technical Disclosure Bulletin, No.Y0884-0694. February, 1985.M.Denneau, The Yorktown Simulation Engine, Proc. ACM-IEEE 19th Design Automation Conf., 55-59, 1982.J. Fisher, Very Long Instruction Word Architectures and the ELI-512, Proc. 10th

36、Annual IntlSymposium on Computer Architecture, 140-150, 1983.D. Gajski, D. Kuck, D. Lawrie, and A. Sameh, Cedar-A Large Scale Multiprocessor, Proc. Infl Conf. on Parallel Processing, 524-529, 1983.A. Gottlieb, R. Grishman, C. Kruskal, K. McAuliffe, L.Rodulph and M.Snir, The NW Ultracomputer- Designi

37、ng a MIMD Shared Memory Parallel Computer, IEEE Trans.onComputers,01.32,175-189, 1983.A.Hassitt, J. Lageshulte and L.Lyon, Implementation of a High Level Language Machine, ACM Connn., 16(1973), 199-212.L Haynes, ed., Highly Parallel Computing, IEEE Computer, Jan., 1982.H.A.Hartung, FORTRAN: “for the

38、 bids”，11, Physics Today, September, 1984.R. Jaganathan and E.A. Ashcroft, Eazyflow: A Hybrid Model for Parallel Processing, Proc. Intl Conf, on Parallel Processing, 514-523, 1984.A. Kapauan, K.Y. Wang, D. Cannon, J. Cuny and L. Snyder, The Pringle: An Experimental System for Parallel Algorithm and Software Testing, Proc. 19