第8章 其它計算機(jī)

1、計算機(jī)系統(tǒng)結(jié)構(gòu)計算機(jī)系統(tǒng)結(jié)構(gòu)王若成王若成 教研室：教研室：B-40282022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)2第第1章章 計算機(jī)系統(tǒng)結(jié)構(gòu)基本概念計算機(jī)系統(tǒng)結(jié)構(gòu)基本概念 第第2章章 數(shù)據(jù)表示與指令系統(tǒng)數(shù)據(jù)表示與指令系統(tǒng) 第第3章章 總線、中斷與輸入輸出系統(tǒng)總線、中斷與輸入輸出系統(tǒng) 第第4章章 存儲體系存儲體系 第第5章章 重疊、流水和向量處理機(jī)重疊、流水和向量處理機(jī) 第第6章章 陣列處理機(jī)陣列處理機(jī) 第第7章章 多處理機(jī)多處理機(jī) 第第8章章 其它計算機(jī)結(jié)構(gòu)其它計算機(jī)結(jié)構(gòu) 目 錄2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)38.1 8.1 脈動陣列機(jī)脈動陣列機(jī) 8.2 8.2 大規(guī)模并行處理機(jī)與機(jī)群系統(tǒng)大規(guī)模并行處理機(jī)

2、與機(jī)群系統(tǒng) 8.3 8.3 數(shù)據(jù)流機(jī)數(shù)據(jù)流機(jī) 8.4 8.4 歸約機(jī)歸約機(jī)8.5 8.5 智能機(jī)智能機(jī) 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)48.1 8.1 脈動陣列處理機(jī)脈動陣列處理機(jī) 脈動陣列結(jié)構(gòu)是由一組處理單元脈動陣列結(jié)構(gòu)是由一組處理單元PE構(gòu)成構(gòu)成的陣列。每個的陣列。每個PE的內(nèi)部結(jié)構(gòu)相同，一般由一的內(nèi)部結(jié)構(gòu)相同，一般由一個加法個加法/邏輯運算部件或加法邏輯運算部件或加法/乘法運算部件乘法運算部件再加上若干個鎖存器構(gòu)成，可完成少數(shù)基本再加上若干個鎖存器構(gòu)成，可完成少數(shù)基本的算術(shù)邏輯運算操作。陣列內(nèi)所有處理單元的算術(shù)邏輯運算操作。陣列內(nèi)所有處理單元的數(shù)據(jù)鎖存器都受同一個時鐘控制。運算時的數(shù)據(jù)鎖

3、存器都受同一個時鐘控制。運算時數(shù)據(jù)在陣列結(jié)構(gòu)的各個處理單元間沿各自的數(shù)據(jù)在陣列結(jié)構(gòu)的各個處理單元間沿各自的方向同步向前推進(jìn)。稱其為脈動陣列結(jié)構(gòu)。方向同步向前推進(jìn)。稱其為脈動陣列結(jié)構(gòu)。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)5 為了執(zhí)行多種計算，脈動型系統(tǒng)內(nèi)的輸為了執(zhí)行多種計算，脈動型系統(tǒng)內(nèi)的輸入數(shù)據(jù)流和結(jié)果數(shù)據(jù)流可以在多個不同方向入數(shù)據(jù)流和結(jié)果數(shù)據(jù)流可以在多個不同方向上以不同速度向前搏動。上以不同速度向前搏動。 陣列內(nèi)部的各個單元只接收前一組處理陣列內(nèi)部的各個單元只接收前一組處理單元傳來的數(shù)據(jù)，并向后一組處理單元發(fā)送單元傳來的數(shù)據(jù)，并向后一組處理單元發(fā)送數(shù)據(jù)。數(shù)據(jù)。 只有位于陣列邊緣的處理單元，才與存儲

4、只有位于陣列邊緣的處理單元，才與存儲器或器或I/OI/O端口進(jìn)行數(shù)據(jù)通信。端口進(jìn)行數(shù)據(jù)通信。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)6 主要適用于計算量很大的信號主要適用于計算量很大的信號/ /圖像處理，圖像處理，以及某些特定計算類算法題目的求解，特別以及某些特定計算類算法題目的求解，特別是需要對大量數(shù)據(jù)執(zhí)行重復(fù)計算的運算受限是需要對大量數(shù)據(jù)執(zhí)行重復(fù)計算的運算受限類問題的求解。類問題的求解。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)72022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)8例如給出了在一個脈動式二維陣列結(jié)構(gòu)上進(jìn)例如給出了在一個脈動式二維陣列結(jié)構(gòu)上進(jìn)行兩個行兩個3 33 3矩陣矩陣A A、B B相乘的例子。每個處理相乘的例子

5、。每個處理單元單元PEPE內(nèi)含一個乘法器和一個加法器，可完內(nèi)含一個乘法器和一個加法器，可完成一個內(nèi)積步運算。每經(jīng)一拍，處理單元可成一個內(nèi)積步運算。每經(jīng)一拍，處理單元可把把3 3個輸入端送來的信息沿三個不同方向，即個輸入端送來的信息沿三個不同方向，即由左向右的水平方向、由下向上的垂直方向由左向右的水平方向、由下向上的垂直方向和由左下角到右上角的斜和由左下角到右上角的斜4545方向，同時將方向，同時將結(jié)果傳送到對應(yīng)的結(jié)果傳送到對應(yīng)的3 3個輸出端，使個輸出端，使aa aa ， bb bb ， dab+cdab+c。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)92022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)102022-6-7

6、計算機(jī)系統(tǒng)結(jié)構(gòu)112022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)12給出了給出了t t1 1、t t2 2、t t3 3時刻送入陣列中的數(shù)據(jù)時刻送入陣列中的數(shù)據(jù)情況，到情況，到t t6 6時，從斜時，從斜4545向右上角將同向右上角將同時輸出時輸出c c1313、c c1212、c c1111、c c2121、c c3131的值的值,t,t7 7時時輸出輸出c c2323、c c2222、c c3232的值的值,t,t8 8時輸出時輸出c c3333的值。的值?？梢钥闯?，總共只需要可以看出，總共只需要8 8拍就可以完成兩拍就可以完成兩個個3 33 3的矩陣相乘，比單處理機(jī)上循環(huán)的矩陣相乘，比單處理機(jī)上循環(huán)執(zhí)行

7、所需的執(zhí)行所需的2727拍，速度提高了兩倍多。拍，速度提高了兩倍多。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)13 兩個兩個n nn n矩陣的相乘，用矩陣的相乘，用3n3n2 2-3n+1-3n+1個個PEPE構(gòu)成的脈動陣列上只需構(gòu)成的脈動陣列上只需3n-13n-1步運算步運算即可全部完成，運算所需要的時間只是即可全部完成，運算所需要的時間只是以近似以近似3n3n的線性關(guān)系增加，比用單處理的線性關(guān)系增加，比用單處理機(jī)的近似機(jī)的近似n n3 3的關(guān)系增加要小得多。當(dāng)?shù)年P(guān)系增加要小得多。當(dāng)n n較較大時，采用脈動陣列進(jìn)行運算的速度提大時，采用脈動陣列進(jìn)行運算的速度提高尤為顯著。高尤為顯著。2022-6-7計

8、算機(jī)系統(tǒng)結(jié)構(gòu)14脈動陣列結(jié)構(gòu)具有如下一些特點：脈動陣列結(jié)構(gòu)具有如下一些特點：(1)(1)結(jié)構(gòu)簡單、規(guī)整，模塊化強(qiáng)，可擴(kuò)充好，非常結(jié)構(gòu)簡單、規(guī)整，模塊化強(qiáng)，可擴(kuò)充好，非常適合用超大規(guī)模集成電路實現(xiàn)。適合用超大規(guī)模集成電路實現(xiàn)。(2)PE(2)PE間數(shù)據(jù)通信距離短、規(guī)則，使數(shù)據(jù)流和控制間數(shù)據(jù)通信距離短、規(guī)則，使數(shù)據(jù)流和控制流的設(shè)計、同步控制等均簡單規(guī)整。流的設(shè)計、同步控制等均簡單規(guī)整。(3)(3)脈動陣列中所有脈動陣列中所有PEPE能同時運算，具有極高的計能同時運算，具有極高的計算并行性，可通過流水獲得很高的運算效率和吞吐算并行性，可通過流水獲得很高的運算效率和吞吐率。率。(4)(4)脈動陣列結(jié)構(gòu)

9、的構(gòu)形與特定計算任務(wù)和算法密脈動陣列結(jié)構(gòu)的構(gòu)形與特定計算任務(wù)和算法密切相關(guān)，具有某種專用性，限制了應(yīng)用范圍，這對切相關(guān)，具有某種專用性，限制了應(yīng)用范圍，這對VLSIVLSI是不利的。是不利的。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)158.1.2 8.1.2 通用脈動陣列結(jié)構(gòu)通用脈動陣列結(jié)構(gòu) 受陣列結(jié)構(gòu)的通用性及受陣列結(jié)構(gòu)的通用性及I/OI/O帶寬約束所限帶寬約束所限制的陣列結(jié)構(gòu)的規(guī)模大小的限制，脈動陣列制的陣列結(jié)構(gòu)的規(guī)模大小的限制，脈動陣列機(jī)應(yīng)用范圍是有限的。不同的算法往往要求機(jī)應(yīng)用范圍是有限的。不同的算法往往要求能有不同的陣列結(jié)構(gòu)，以及大小不同的陣列。能有不同的陣列結(jié)構(gòu)，以及大小不同的陣列。為了克

10、服脈動陣列結(jié)構(gòu)通用性差的弱點，研為了克服脈動陣列結(jié)構(gòu)通用性差的弱點，研究和發(fā)展了一些可有效執(zhí)行多種算法的較為究和發(fā)展了一些可有效執(zhí)行多種算法的較為通用的脈動陣列結(jié)構(gòu)。通用的脈動陣列結(jié)構(gòu)。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)16發(fā)展通用脈動陣列結(jié)構(gòu)的途徑有三種。發(fā)展通用脈動陣列結(jié)構(gòu)的途徑有三種。 第一種途徑是通過增設(shè)附加的硬件，第一種途徑是通過增設(shè)附加的硬件，對陣列的拓?fù)浣Y(jié)構(gòu)和互連方式用可編程對陣列的拓?fù)浣Y(jié)構(gòu)和互連方式用可編程開關(guān)進(jìn)行重構(gòu)，即經(jīng)程序重新配置陣列開關(guān)進(jìn)行重構(gòu)，即經(jīng)程序重新配置陣列的結(jié)構(gòu)。的結(jié)構(gòu)。 美國美國PurduePurdue大學(xué)的可重構(gòu)高度并行大學(xué)的可重構(gòu)高度并行計算機(jī)計算機(jī)CHi

11、PCHiP就是典型的例子。就是典型的例子。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)172022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)18 第二種途徑是用軟件把不同的算法映第二種途徑是用軟件把不同的算法映像到固定的陣列結(jié)構(gòu)上。像到固定的陣列結(jié)構(gòu)上。 這一方法依賴于面向并行運算所采用的這一方法依賴于面向并行運算所采用的程序語言、操作系統(tǒng)、編譯程序和軟件開發(fā)程序語言、操作系統(tǒng)、編譯程序和軟件開發(fā)工具的設(shè)計。工具的設(shè)計。 美國卡內(nèi)基美國卡內(nèi)基- -梅隆大學(xué)用于信號、圖像和梅隆大學(xué)用于信號、圖像和計算機(jī)視覺處理的計算機(jī)視覺處理的WARPWARP機(jī)是一臺由機(jī)是一臺由1010個以上個以上處理單元組成的線形脈動陣列機(jī)。處理單元組成的

12、線形脈動陣列機(jī)。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)19 第三種途徑是探尋與問題大小無關(guān)第三種途徑是探尋與問題大小無關(guān)的脈動處理方法，以及的脈動處理方法，以及VLSIVLSI運算系統(tǒng)的運算系統(tǒng)的分割矩陣算法，使它們可以克服陣列只分割矩陣算法，使它們可以克服陣列只能求解固定大小題目的缺陷，同時探尋能求解固定大小題目的缺陷，同時探尋發(fā)展適合一類計算問題的通用算法和相發(fā)展適合一類計算問題的通用算法和相應(yīng)的設(shè)置方案。應(yīng)的設(shè)置方案。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)208.28.2大規(guī)模并行處理機(jī)與機(jī)群系統(tǒng)大規(guī)模并行處理機(jī)與機(jī)群系統(tǒng)發(fā)展背景：發(fā)展背景： 由于由于VLSIVLSI和微處理技術(shù)的發(fā)展，以及高科和微處

13、理技術(shù)的發(fā)展，以及高科技應(yīng)用領(lǐng)域?qū)τ嬎銠C(jī)和通信網(wǎng)絡(luò)在計算、處技應(yīng)用領(lǐng)域?qū)τ嬎銠C(jī)和通信網(wǎng)絡(luò)在計算、處理和通信性能上不斷提出理和通信性能上不斷提出更高的要求更高的要求( (極大的極大的處理數(shù)據(jù)量、異常復(fù)雜的運算、很不規(guī)則的處理數(shù)據(jù)量、異常復(fù)雜的運算、很不規(guī)則的數(shù)據(jù)結(jié)構(gòu)、極高的處理速度數(shù)據(jù)結(jié)構(gòu)、極高的處理速度),),使發(fā)展大規(guī)模使發(fā)展大規(guī)模的并行處理成了的并行處理成了2020世紀(jì)世紀(jì)8080年代中期計算機(jī)發(fā)年代中期計算機(jī)發(fā)展的熱點。展的熱點。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)21大規(guī)模并行處理機(jī)：大規(guī)模并行處理機(jī)： 通過新的計算方法、存儲技術(shù)、處理手通過新的計算方法、存儲技術(shù)、處理手段和結(jié)構(gòu)組織方式，

14、將數(shù)百至數(shù)萬個高性能、段和結(jié)構(gòu)組織方式，將數(shù)百至數(shù)萬個高性能、低成本的低成本的RISCRISC微處理器用專門的互連網(wǎng)絡(luò)互微處理器用專門的互連網(wǎng)絡(luò)互連，組成大規(guī)模并行處理機(jī)連，組成大規(guī)模并行處理機(jī)MPPMPP。這種處理機(jī)。這種處理機(jī)可進(jìn)行中粒度和細(xì)粒度大規(guī)模并行處理，構(gòu)可進(jìn)行中粒度和細(xì)粒度大規(guī)模并行處理，構(gòu)成成SIMDSIMD或或MIMDMIMD系統(tǒng)。系統(tǒng)。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)22優(yōu)點：它具有性能價格比高和可擴(kuò)展性好的優(yōu)點。優(yōu)點：它具有性能價格比高和可擴(kuò)展性好的優(yōu)點。如果一個如果一個RISCRISC微處理器的性能為微處理器的性能為100MFLOPS100MFLOPS，則，則102410

15、24個這樣的微處理器組搭成的個這樣的微處理器組搭成的MPPMPP系統(tǒng)，其最高系統(tǒng)，其最高性能就可達(dá)性能就可達(dá)100GFLOPS100GFLOPS。這比用單一主處理機(jī)構(gòu)成。這比用單一主處理機(jī)構(gòu)成的巨型機(jī)的性能要高出許多倍，而造價可能只是它的巨型機(jī)的性能要高出許多倍，而造價可能只是它的的1/51/5。可擴(kuò)展性好表現(xiàn)在能比較方便地增減結(jié)點?？蓴U(kuò)展性好表現(xiàn)在能比較方便地增減結(jié)點處理器數(shù)，來使系統(tǒng)的規(guī)模、處理速度、系統(tǒng)價格處理器數(shù)，來使系統(tǒng)的規(guī)模、處理速度、系統(tǒng)價格滿足應(yīng)用的需要。采用分布式存儲器來減少訪存沖滿足應(yīng)用的需要。采用分布式存儲器來減少訪存沖突。突。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)23MPPM

16、PP的系統(tǒng)軟件：操作系統(tǒng)采用微內(nèi)核和大外殼。的系統(tǒng)軟件：操作系統(tǒng)采用微內(nèi)核和大外殼。內(nèi)核只提供中斷處理、進(jìn)程調(diào)度、進(jìn)程間簡單內(nèi)核只提供中斷處理、進(jìn)程調(diào)度、進(jìn)程間簡單通信及其他最基本的功能，將大量的服務(wù)功能搬移通信及其他最基本的功能，將大量的服務(wù)功能搬移到內(nèi)核之外。內(nèi)核基本功能是同構(gòu)的，對不同用戶到內(nèi)核之外。內(nèi)核基本功能是同構(gòu)的，對不同用戶的不同服務(wù)需要，允許進(jìn)行異構(gòu)服務(wù)。的不同服務(wù)需要，允許進(jìn)行異構(gòu)服務(wù)。為適應(yīng)系統(tǒng)的開放性，采用客戶為適應(yīng)系統(tǒng)的開放性，采用客戶/ /服務(wù)器模式。服務(wù)器模式。在進(jìn)程通信上，由內(nèi)核提供基本的通信，由服務(wù)層在進(jìn)程通信上，由內(nèi)核提供基本的通信，由服務(wù)層提供網(wǎng)絡(luò)的通信。負(fù)

17、荷平衡調(diào)度可有分配型、調(diào)整提供網(wǎng)絡(luò)的通信。負(fù)荷平衡調(diào)度可有分配型、調(diào)整型和復(fù)合型等多種。型和復(fù)合型等多種。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)248.2.2 8.2.2 機(jī)群系統(tǒng)機(jī)群系統(tǒng) 將多個高性能的工作站或高檔微型計算機(jī)，使將多個高性能的工作站或高檔微型計算機(jī)，使用高速的通信網(wǎng)絡(luò)加以互連組成的系統(tǒng)。在并行程用高速的通信網(wǎng)絡(luò)加以互連組成的系統(tǒng)。在并行程序設(shè)計和集成開發(fā)環(huán)境的支持下，進(jìn)行統(tǒng)一調(diào)度和序設(shè)計和集成開發(fā)環(huán)境的支持下，進(jìn)行統(tǒng)一調(diào)度和協(xié)調(diào)處理，以實現(xiàn)對中、粗粒度并行進(jìn)程的高效并協(xié)調(diào)處理，以實現(xiàn)對中、粗粒度并行進(jìn)程的高效并行處理。行處理。 機(jī)群系統(tǒng)中的主機(jī)和網(wǎng)絡(luò)可以是同構(gòu)的，也可機(jī)群系統(tǒng)中的主機(jī)

18、和網(wǎng)絡(luò)可以是同構(gòu)的，也可以是異構(gòu)的。主機(jī)間的通信主要采用消息傳遞。從以是異構(gòu)的。主機(jī)間的通信主要采用消息傳遞。從結(jié)構(gòu)和結(jié)點間的通信來看，是一種分布式存儲方式，結(jié)構(gòu)和結(jié)點間的通信來看，是一種分布式存儲方式，而從用戶來看，表示出的是一個完整的并行系統(tǒng)。而從用戶來看，表示出的是一個完整的并行系統(tǒng)。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)25機(jī)群系統(tǒng)比起傳統(tǒng)的并行處理系統(tǒng)有幾個明機(jī)群系統(tǒng)比起傳統(tǒng)的并行處理系統(tǒng)有幾個明顯優(yōu)點。顯優(yōu)點。 (1) (1)系統(tǒng)有高的性能價格比。系統(tǒng)有高的性能價格比。 (2) (2)系統(tǒng)的開發(fā)周期短。系統(tǒng)的開發(fā)周期短。 (3) (3)系統(tǒng)的可擴(kuò)展性好。系統(tǒng)的可擴(kuò)展性好。 (4)(4)系

19、統(tǒng)的資源利用率高。系統(tǒng)的資源利用率高。 (5) (5)用戶投資風(fēng)險小。用戶投資風(fēng)險小。 (6)(6)用戶編程方便。用戶編程方便。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)268.3 8.3 數(shù)據(jù)流計算機(jī)數(shù)據(jù)流計算機(jī)8.3.18.3.1數(shù)據(jù)驅(qū)動的概念數(shù)據(jù)驅(qū)動的概念計數(shù)器控制驅(qū)動的控制流方式：計數(shù)器控制驅(qū)動的控制流方式： VonNeumann VonNeumann型計算機(jī)的基本特型計算機(jī)的基本特點是在程序計數(shù)器集中控制下，順次點是在程序計數(shù)器集中控制下，順次地執(zhí)行指令，因此，它是以控制流方地執(zhí)行指令，因此，它是以控制流方式工作的。式工作的。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)27特點：通過訪問共享存儲單元讓數(shù)據(jù)在指

20、令特點：通過訪問共享存儲單元讓數(shù)據(jù)在指令之間傳遞；指令執(zhí)行的順序性隱含于控制流之間傳遞；指令執(zhí)行的順序性隱含于控制流中，但卻可以顯示使用專門的控制操作符來中，但卻可以顯示使用專門的控制操作符來實現(xiàn)并行處理；指令執(zhí)行的順序受程序計數(shù)實現(xiàn)并行處理；指令執(zhí)行的順序受程序計數(shù)器控制，即是受控制令牌所支配。器控制，即是受控制令牌所支配。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)28數(shù)據(jù)驅(qū)動的數(shù)據(jù)流方式：數(shù)據(jù)驅(qū)動的數(shù)據(jù)流方式：指的是只要一條或一組指令所要求的操作數(shù)全指的是只要一條或一組指令所要求的操作數(shù)全部準(zhǔn)備就緒，就可立即激發(fā)相應(yīng)的指令或指令組部準(zhǔn)備就緒，就可立即激發(fā)相應(yīng)的指令或指令組執(zhí)行。執(zhí)行結(jié)果的輸出將送往等待

21、這一數(shù)據(jù)的下執(zhí)行。執(zhí)行結(jié)果的輸出將送往等待這一數(shù)據(jù)的下一條或下一組指令。如果其中一些指令因此而使一條或下一組指令。如果其中一些指令因此而使所需用到的數(shù)據(jù)全部準(zhǔn)備就緒，就可被激發(fā)執(zhí)行。所需用到的數(shù)據(jù)全部準(zhǔn)備就緒，就可被激發(fā)執(zhí)行。在這種機(jī)器上不需要程序計數(shù)器，指令的執(zhí)行基在這種機(jī)器上不需要程序計數(shù)器，指令的執(zhí)行基本上是無序的，完全受數(shù)據(jù)流的驅(qū)動，與指令在本上是無序的，完全受數(shù)據(jù)流的驅(qū)動，與指令在程序中出現(xiàn)的先后順序無關(guān)。程序中出現(xiàn)的先后順序無關(guān)。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)29特點：數(shù)據(jù)驅(qū)動的數(shù)據(jù)流方式?jīng)]有通常的特點：數(shù)據(jù)驅(qū)動的數(shù)據(jù)流方式?jīng)]有通常的共享變量的概念，即沒有共享存儲數(shù)據(jù)的共享變量的概

22、念，即沒有共享存儲數(shù)據(jù)的概念；指令執(zhí)行順序只受指令中數(shù)據(jù)相關(guān)概念；指令執(zhí)行順序只受指令中數(shù)據(jù)相關(guān)性的制約；數(shù)據(jù)是以數(shù)據(jù)令牌方式直接在性的制約；數(shù)據(jù)是以數(shù)據(jù)令牌方式直接在指令之間傳遞的。指令之間傳遞的。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)30數(shù)據(jù)令牌：實質(zhì)上是一種表示某一操作數(shù)或數(shù)據(jù)令牌：實質(zhì)上是一種表示某一操作數(shù)或參數(shù)已準(zhǔn)備就緒的標(biāo)志。一旦執(zhí)行某一操作參數(shù)已準(zhǔn)備就緒的標(biāo)志。一旦執(zhí)行某一操作的所有操作數(shù)令牌都到齊，則標(biāo)志著這一操的所有操作數(shù)令牌都到齊，則標(biāo)志著這一操作是什么操作，以及操作結(jié)果所得出的數(shù)據(jù)作是什么操作，以及操作結(jié)果所得出的數(shù)據(jù)令牌應(yīng)發(fā)送到哪些等待此數(shù)據(jù)令牌的操作的令牌應(yīng)發(fā)送到哪些等待此數(shù)

23、據(jù)令牌的操作的第幾個操作數(shù)部件等有關(guān)信息，都將作為一第幾個操作數(shù)部件等有關(guān)信息，都將作為一個消息包，傳送到處理單元或操作部件并予個消息包，傳送到處理單元或操作部件并予以執(zhí)行。以執(zhí)行。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)31需求驅(qū)動的數(shù)據(jù)流方式：而需求驅(qū)動是按需求值，需求驅(qū)動的數(shù)據(jù)流方式：而需求驅(qū)動是按需求值，只有當(dāng)某一函數(shù)需要用到某一自變量時，才驅(qū)動對只有當(dāng)某一函數(shù)需要用到某一自變量時，才驅(qū)動對該自變量的求值操作，是一種滯后求值的策略。需該自變量的求值操作，是一種滯后求值的策略。需求驅(qū)動計算，其操作則按數(shù)據(jù)需求所決定的次序進(jìn)求驅(qū)動計算，其操作則按數(shù)據(jù)需求所決定的次序進(jìn)行。行。 數(shù)據(jù)驅(qū)動計算，其操作是

24、按輸入數(shù)據(jù)可用性決數(shù)據(jù)驅(qū)動計算，其操作是按輸入數(shù)據(jù)可用性決定的次序進(jìn)行；數(shù)據(jù)驅(qū)動計算只要所要求的輸入數(shù)定的次序進(jìn)行；數(shù)據(jù)驅(qū)動計算只要所要求的輸入數(shù)據(jù)全部就緒，即可驅(qū)動操作執(zhí)行，是一種提前求值據(jù)全部就緒，即可驅(qū)動操作執(zhí)行，是一種提前求值的策略；的策略；2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)32 顯然后者較之前者可以減少許多不必顯然后者較之前者可以減少許多不必要的求值，輔助開銷少，有助于提高系統(tǒng)要的求值，輔助開銷少，有助于提高系統(tǒng)的效率。作為本節(jié)討論的數(shù)據(jù)流機(jī)來說，的效率。作為本節(jié)討論的數(shù)據(jù)流機(jī)來說，一般是指數(shù)據(jù)驅(qū)動計算，需求驅(qū)動更適合一般是指數(shù)據(jù)驅(qū)動計算，需求驅(qū)動更適合面向函數(shù)程序設(shè)計的計算機(jī)。面向函數(shù)

25、程序設(shè)計的計算機(jī)。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)338.1.28.1.2數(shù)據(jù)流程序圖和語言數(shù)據(jù)流程序圖和語言 有向圖來表示指令級的數(shù)據(jù)流程序，它可看成有向圖來表示指令級的數(shù)據(jù)流程序，它可看成是數(shù)據(jù)流機(jī)器的機(jī)器語言。它有多個結(jié)點，并用一是數(shù)據(jù)流機(jī)器的機(jī)器語言。它有多個結(jié)點，并用一些弧把它們連接而成。每一個結(jié)點用圓圈或三角形些弧把它們連接而成。每一個結(jié)點用圓圈或三角形或其他特殊符號表示，認(rèn)為是一種處理部件，結(jié)點或其他特殊符號表示，認(rèn)為是一種處理部件，結(jié)點內(nèi)的符號或字母表示一種操作?；〈頂?shù)據(jù)令牌在內(nèi)的符號或字母表示一種操作?；〈頂?shù)據(jù)令牌在結(jié)點間的流向。在數(shù)據(jù)流機(jī)中，根據(jù)這樣的數(shù)據(jù)流結(jié)點間的流向

26、。在數(shù)據(jù)流機(jī)中，根據(jù)這樣的數(shù)據(jù)流程序圖，通過一個分配器或分配程序，不斷分配適程序圖，通過一個分配器或分配程序，不斷分配適當(dāng)?shù)奶幚聿考韺崿F(xiàn)操作符的操作。當(dāng)?shù)奶幚聿考韺崿F(xiàn)操作符的操作。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)34計算計算z z=(=(a a+ +b b) )* *( (a a- -b b) )數(shù)據(jù)流程序圖數(shù)據(jù)流程序圖 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)352022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)362022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)372022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)38例如：是具有條件分支結(jié)構(gòu)的數(shù)據(jù)流程序例如：是具有條件分支結(jié)構(gòu)的數(shù)據(jù)流程序圖的例子，以實現(xiàn)當(dāng)圖的例子，以實現(xiàn)當(dāng)x x0 0時，讓時，讓x x

27、加加y y，否，否則，就讓則，就讓x x減減y y的功能。為具有循環(huán)結(jié)構(gòu)的的功能。為具有循環(huán)結(jié)構(gòu)的數(shù)據(jù)流程序圖的例子，以實現(xiàn)對數(shù)據(jù)流程序圖的例子，以實現(xiàn)對x x循環(huán)累加，循環(huán)累加，直到直到x x的值超過的值超過10001000為止，所得結(jié)果為為止，所得結(jié)果為z z的的功能。功能。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)392022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)402022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)41 活動模片表示法活動模片表示法 數(shù)據(jù)流實際上可以被看成是一組活動數(shù)據(jù)流實際上可以被看成是一組活動模片組成的集合體。每一個活動模片相應(yīng)于模片組成的集合體。每一個活動模片相應(yīng)于數(shù)據(jù)流程序圖中一個或多個操作結(jié)點，且由數(shù)據(jù)流

28、程序圖中一個或多個操作結(jié)點，且由4 4個域組成。它們是一個操作碼域，兩個操作個域組成。它們是一個操作碼域，兩個操作數(shù)域和一個目的域。數(shù)域和一個目的域。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)42計算計算z=(a+b)z=(a+b)* *(a-b)(a-b)活動模片活動模片2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)432022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)44 活動模片就是結(jié)點在數(shù)據(jù)流機(jī)器內(nèi)部具活動模片就是結(jié)點在數(shù)據(jù)流機(jī)器內(nèi)部具體實現(xiàn)時的存儲器映像。所以，活動模片表體實現(xiàn)時的存儲器映像。所以，活動模片表示的數(shù)據(jù)流程序圖也可認(rèn)為就是數(shù)據(jù)流機(jī)的示的數(shù)據(jù)流程序圖也可認(rèn)為就是數(shù)據(jù)流機(jī)的可執(zhí)行的機(jī)器代碼程序，可由數(shù)據(jù)流機(jī)硬件可執(zhí)行的機(jī)

29、器代碼程序，可由數(shù)據(jù)流機(jī)硬件直接解釋執(zhí)行。直接解釋執(zhí)行。 優(yōu)點直觀易懂，但編程效率低，難以為優(yōu)點直觀易懂，但編程效率低，難以為一般用戶所接受。一般用戶所接受。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)45 目前數(shù)據(jù)流控制機(jī)的高級語言主要目前數(shù)據(jù)流控制機(jī)的高級語言主要有單賦值語言和函數(shù)程序設(shè)計語言。另有單賦值語言和函數(shù)程序設(shè)計語言。另外，邏輯程序設(shè)計語言外，邏輯程序設(shè)計語言PROLOGPROLOG這樣一類這樣一類的描述式語言，也可作為數(shù)據(jù)流機(jī)的高的描述式語言，也可作為數(shù)據(jù)流機(jī)的高級語言。級語言。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)468.3.38.3.3數(shù)據(jù)流計算機(jī)的結(jié)構(gòu)數(shù)據(jù)流計算機(jī)的結(jié)構(gòu) 根據(jù)對數(shù)據(jù)令牌處理的

30、方式不同，可以把數(shù)根據(jù)對數(shù)據(jù)令牌處理的方式不同，可以把數(shù)據(jù)流計算機(jī)的結(jié)構(gòu)分成靜態(tài)和動態(tài)兩類。據(jù)流計算機(jī)的結(jié)構(gòu)分成靜態(tài)和動態(tài)兩類。 靜態(tài)數(shù)據(jù)流機(jī)：靜態(tài)數(shù)據(jù)流機(jī)的數(shù)據(jù)令靜態(tài)數(shù)據(jù)流機(jī)：靜態(tài)數(shù)據(jù)流機(jī)的數(shù)據(jù)令牌沒加標(biāo)號。為正確工作，任意給定時刻，牌沒加標(biāo)號。為正確工作，任意給定時刻，當(dāng)結(jié)點操作時，其任何一條輸入弧上只能有當(dāng)結(jié)點操作時，其任何一條輸入弧上只能有一個數(shù)據(jù)令牌。只有當(dāng)結(jié)點的所有輸入弧上一個數(shù)據(jù)令牌。只有當(dāng)結(jié)點的所有輸入弧上都有數(shù)據(jù)令牌時，該結(jié)點才被激活執(zhí)行相應(yīng)都有數(shù)據(jù)令牌時，該結(jié)點才被激活執(zhí)行相應(yīng)的操作。的操作。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)47由于數(shù)據(jù)令牌沒有加標(biāo)號，如果給定時間里允許一由于

31、數(shù)據(jù)令牌沒有加標(biāo)號，如果給定時間里允許一條弧上同時出現(xiàn)兩個以上的數(shù)據(jù)令牌的話，結(jié)點對條弧上同時出現(xiàn)兩個以上的數(shù)據(jù)令牌的話，結(jié)點對于送達(dá)各輸入端的一批數(shù)據(jù)就無法區(qū)分出它們中哪于送達(dá)各輸入端的一批數(shù)據(jù)就無法區(qū)分出它們中哪些是屬于同一批的操作數(shù)。因此，為了滿足迭代要些是屬于同一批的操作數(shù)。因此，為了滿足迭代要求，除要多次重復(fù)激活同一操作結(jié)點外，還必須另求，除要多次重復(fù)激活同一操作結(jié)點外，還必須另設(shè)控制令牌，以識別數(shù)據(jù)令牌由一個結(jié)點傳送到另設(shè)控制令牌，以識別數(shù)據(jù)令牌由一個結(jié)點傳送到另一個結(jié)點的時間關(guān)系，從而區(qū)分屬于不同迭代層次一個結(jié)點的時間關(guān)系，從而區(qū)分屬于不同迭代層次的各批數(shù)據(jù)。所以，靜態(tài)數(shù)據(jù)流機(jī)不

32、支持遞歸的并的各批數(shù)據(jù)。所以，靜態(tài)數(shù)據(jù)流機(jī)不支持遞歸的并發(fā)激活，只支持一般的循環(huán)。發(fā)激活，只支持一般的循環(huán)。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)48 動態(tài)數(shù)據(jù)流機(jī)：最主要的特點是讓令牌帶上動態(tài)數(shù)據(jù)流機(jī)：最主要的特點是讓令牌帶上標(biāo)記，使得在任意給定時刻，數(shù)據(jù)流程序圖任何一標(biāo)記，使得在任意給定時刻，數(shù)據(jù)流程序圖任何一條弧上允許出現(xiàn)多個帶不同標(biāo)記的令牌。令牌的標(biāo)條弧上允許出現(xiàn)多個帶不同標(biāo)記的令牌。令牌的標(biāo)記是令牌附帶的一個能識別該令牌時間先后相對關(guān)記是令牌附帶的一個能識別該令牌時間先后相對關(guān)系的標(biāo)號。對于需要多組系的標(biāo)號。對于需要多組( (次次) )數(shù)據(jù)令牌的指令，則數(shù)據(jù)令牌的指令，則是通過對令牌標(biāo)記的配

33、對來識別。為此，需要相應(yīng)是通過對令牌標(biāo)記的配對來識別。為此，需要相應(yīng)硬件將標(biāo)記附加到數(shù)據(jù)令牌上，并完成對標(biāo)記的匹硬件將標(biāo)記附加到數(shù)據(jù)令牌上，并完成對標(biāo)記的匹配工作。配工作。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)498.3.4 8.3.4 數(shù)據(jù)流機(jī)器存在的問題數(shù)據(jù)流機(jī)器存在的問題 (1)(1)數(shù)據(jù)流機(jī)主要目的是為了提高操作級并行的開數(shù)據(jù)流機(jī)主要目的是為了提高操作級并行的開發(fā)水平，但如果題目本身數(shù)據(jù)相關(guān)性很強(qiáng)，內(nèi)涵并發(fā)水平，但如果題目本身數(shù)據(jù)相關(guān)性很強(qiáng)，內(nèi)涵并行性成分不多時，就會使效率反而比傳統(tǒng)的行性成分不多時，就會使效率反而比傳統(tǒng)的VonNeumannVonNeumann型機(jī)的還要低。型機(jī)的還要低。(

34、2)(2)在數(shù)據(jù)流機(jī)器中為給數(shù)據(jù)建立、識別、處理標(biāo)在數(shù)據(jù)流機(jī)器中為給數(shù)據(jù)建立、識別、處理標(biāo)記，需要花費較多的輔助開銷和較大的存儲空間。記，需要花費較多的輔助開銷和較大的存儲空間。(3)(3)數(shù)據(jù)流機(jī)不保存數(shù)組。數(shù)據(jù)流機(jī)器對標(biāo)量運算數(shù)據(jù)流機(jī)不保存數(shù)組。數(shù)據(jù)流機(jī)器對標(biāo)量運算有利，而對數(shù)組、遞歸及其他高級操作較難管理。有利，而對數(shù)組、遞歸及其他高級操作較難管理。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)50(4)(4)數(shù)據(jù)流語言的變量代表數(shù)值而不是存儲單數(shù)據(jù)流語言的變量代表數(shù)值而不是存儲單元位置，使程序員無法控制存儲分配。元位置，使程序員無法控制存儲分配。 (5)(5)數(shù)據(jù)流機(jī)互連網(wǎng)絡(luò)設(shè)計困難，輸入數(shù)據(jù)流機(jī)互

35、連網(wǎng)絡(luò)設(shè)計困難，輸入/ /輸出輸出系統(tǒng)仍不夠完善。系統(tǒng)仍不夠完善。(6)(6)數(shù)據(jù)流機(jī)沒有程序計數(shù)器，給診斷和維護(hù)數(shù)據(jù)流機(jī)沒有程序計數(shù)器，給診斷和維護(hù)帶來了困難。帶來了困難。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)518.4 8.4 歸約機(jī)歸約機(jī) 歸約機(jī)和數(shù)據(jù)流機(jī)，都是基于數(shù)據(jù)流的歸約機(jī)和數(shù)據(jù)流機(jī)，都是基于數(shù)據(jù)流的計算模型，只是其采用的驅(qū)動方式不同。數(shù)計算模型，只是其采用的驅(qū)動方式不同。數(shù)據(jù)流機(jī)是采用數(shù)據(jù)驅(qū)動，執(zhí)行的操作序列取據(jù)流機(jī)是采用數(shù)據(jù)驅(qū)動，執(zhí)行的操作序列取決于輸入數(shù)據(jù)的可用性；歸約機(jī)則是需求驅(qū)決于輸入數(shù)據(jù)的可用性；歸約機(jī)則是需求驅(qū)動，執(zhí)行的操作序列取決于對數(shù)據(jù)的需求，動，執(zhí)行的操作序列取決于對

36、數(shù)據(jù)的需求，對數(shù)據(jù)的需求又來源于函數(shù)式程序設(shè)計語言對數(shù)據(jù)的需求又來源于函數(shù)式程序設(shè)計語言對表達(dá)式的歸約。對表達(dá)式的歸約。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)52 函數(shù)式語言：是由所有函數(shù)表達(dá)式的集合、函數(shù)式語言：是由所有函數(shù)表達(dá)式的集合、所有目標(biāo)所有目標(biāo)( (也是表達(dá)式也是表達(dá)式) )的集合及所有由函數(shù)的集合及所有由函數(shù)表達(dá)式到目標(biāo)的函數(shù)集合三部分組成的。表達(dá)式到目標(biāo)的函數(shù)集合三部分組成的。 函數(shù)是其基本成分，是從一批目標(biāo)到另一函數(shù)是其基本成分，是從一批目標(biāo)到另一批目標(biāo)的映射。批目標(biāo)的映射。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)53 從函數(shù)程序設(shè)計的角度看，一個程序就是一個從函數(shù)程序設(shè)計的角度看，一個程序

37、就是一個函數(shù)的表達(dá)式。通過定義一組函數(shù)的表達(dá)式。通過定義一組“程序形成算符程序形成算符”，可以用簡單函數(shù)可以用簡單函數(shù)( (即簡單程序即簡單程序) )構(gòu)成任意復(fù)雜的程序，構(gòu)成任意復(fù)雜的程序，也就是構(gòu)成任意復(fù)雜函數(shù)的表達(dá)式。反過來，如果也就是構(gòu)成任意復(fù)雜函數(shù)的表達(dá)式。反過來，如果給出了一個屬函數(shù)表達(dá)式集合中的復(fù)雜函數(shù)的表達(dá)給出了一個屬函數(shù)表達(dá)式集合中的復(fù)雜函數(shù)的表達(dá)式，利用提供的函數(shù)集合中的子函數(shù)經(jīng)過有限次歸式，利用提供的函數(shù)集合中的子函數(shù)經(jīng)過有限次歸約代換之后，總可以得到所希望的結(jié)果，即由常量約代換之后，總可以得到所希望的結(jié)果，即由常量構(gòu)成的目標(biāo)。函數(shù)表達(dá)式的每一次歸約，就是一次構(gòu)成的目標(biāo)。函

38、數(shù)表達(dá)式的每一次歸約，就是一次函數(shù)的應(yīng)用，或是一個子表達(dá)式函數(shù)的應(yīng)用，或是一個子表達(dá)式( (子函數(shù)式子函數(shù)式) )的代換的代換( (還原還原) )。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)54 例如：表達(dá)式例如：表達(dá)式z=(y-1)z=(y-1)* *(y+x)(y+x)，可以理，可以理解成解成z=f(u),z=f(u),而而f(u)f(u)等價于等價于g(v)g(v)* *h(w)h(w)，其，其中中g(shù)(v)=y-1,h(w)=y+x,g(v)=y-1,h(w)=y+x,也就是說，函數(shù)也就是說，函數(shù)z=f(u)z=f(u)的求解可歸約成求兩個子函數(shù)的求解可歸約成求兩個子函數(shù)g(v)g(v)和和h(w)

39、h(w)的積，而的積，而g(v)g(v)和和h(w)h(w)又可以分別繼又可以分別繼續(xù)向下歸約。續(xù)向下歸約。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)55歸約機(jī)歸約機(jī) 函數(shù)式程序本質(zhì)上是屬于解釋執(zhí)行方式，從函數(shù)函數(shù)式程序本質(zhì)上是屬于解釋執(zhí)行方式，從函數(shù)式程序的歸約來看，機(jī)器內(nèi)部通常采用鏈表的存儲式程序的歸約來看，機(jī)器內(nèi)部通常采用鏈表的存儲結(jié)構(gòu)，且依賴于動態(tài)存儲分配，存儲空間的大小無結(jié)構(gòu)，且依賴于動態(tài)存儲分配，存儲空間的大小無法預(yù)測，需要頻繁地進(jìn)行空白單元的回收，使空間、法預(yù)測，需要頻繁地進(jìn)行空白單元的回收，使空間、時間開銷都較大，頻繁的函數(shù)應(yīng)用和參數(shù)傳遞，加時間開銷都較大，頻繁的函數(shù)應(yīng)用和參數(shù)傳遞，加上

40、自變量動態(tài)取值，同樣的計算往往要重復(fù)多次。上自變量動態(tài)取值，同樣的計算往往要重復(fù)多次。所以，必須針對函數(shù)程序設(shè)計語言的特點和問題來所以，必須針對函數(shù)程序設(shè)計語言的特點和問題來設(shè)計支持函數(shù)式程序運行的新計算機(jī)（歸約機(jī)）。設(shè)計支持函數(shù)式程序運行的新計算機(jī)（歸約機(jī)）。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)56 歸約機(jī)一般有如下一些結(jié)構(gòu)特點：歸約機(jī)一般有如下一些結(jié)構(gòu)特點：(1)(1)歸約機(jī)應(yīng)當(dāng)是面向函數(shù)式語言，或以函數(shù)式語歸約機(jī)應(yīng)當(dāng)是面向函數(shù)式語言，或以函數(shù)式語言為機(jī)器語言的非言為機(jī)器語言的非NeumannNeumann型機(jī)器。型機(jī)器。 (2)(2)具有大容量物理存儲器并采用大虛存容量的虛具有大容量物理存儲

41、器并采用大虛存容量的虛擬存儲器，具備高效的動態(tài)存儲分配和管理的軟、擬存儲器，具備高效的動態(tài)存儲分配和管理的軟、硬件支持，滿足歸約機(jī)對動態(tài)存儲分配及所需存儲硬件支持，滿足歸約機(jī)對動態(tài)存儲分配及所需存儲空間大的要求。空間大的要求。(3)(3)處理部分應(yīng)當(dāng)是一種有多個處理器或多個處理處理部分應(yīng)當(dāng)是一種有多個處理器或多個處理機(jī)并行的結(jié)構(gòu)形式，以發(fā)揮函數(shù)式程序并行處理特機(jī)并行的結(jié)構(gòu)形式，以發(fā)揮函數(shù)式程序并行處理特長長. .2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)57(4)(4)采用適合于函數(shù)式程序運行的多處理器采用適合于函數(shù)式程序運行的多處理器( (機(jī)機(jī)) )互連的結(jié)構(gòu)，最好采用樹形方式的互連互連的結(jié)構(gòu)，最好采用

42、樹形方式的互連結(jié)構(gòu)或多層次復(fù)合的互連結(jié)構(gòu)形式。結(jié)構(gòu)或多層次復(fù)合的互連結(jié)構(gòu)形式。 (5)(5)為減少進(jìn)程調(diào)度及進(jìn)程間通信開銷，盡量為減少進(jìn)程調(diào)度及進(jìn)程間通信開銷，盡量把運行進(jìn)程的結(jié)點機(jī)安排成緊靠該進(jìn)程所需把運行進(jìn)程的結(jié)點機(jī)安排成緊靠該進(jìn)程所需用的數(shù)據(jù)，并使運行時需相互通信的進(jìn)程所用的數(shù)據(jù)，并使運行時需相互通信的進(jìn)程所占用的處理機(jī)也靠近，讓各處理機(jī)的負(fù)荷平占用的處理機(jī)也靠近，讓各處理機(jī)的負(fù)荷平衡。衡。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)58根據(jù)機(jī)器內(nèi)部對函數(shù)表達(dá)式所用存儲方式的根據(jù)機(jī)器內(nèi)部對函數(shù)表達(dá)式所用存儲方式的不同，將歸約方式分成串歸約和圖歸約兩類。不同，將歸約方式分成串歸約和圖歸約兩類。 以表達(dá)式

43、以表達(dá)式z=(y-1)z=(y-1)* *(y+x)(y+x)為例，假定為例，假定x x和和y y分別分別賦予賦予2 2和和5 5。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)59串歸約方式串歸約方式 當(dāng)提出求函數(shù)當(dāng)提出求函數(shù)z=f(u)的請求后，立即轉(zhuǎn)的請求后，立即轉(zhuǎn)化成執(zhí)行由操作符化成執(zhí)行由操作符*和兩個子函數(shù)和兩個子函數(shù)g和和h的作的作用所組成的用所組成的“指令指令”。g和和h的作用又引起的作用又引起“指令指令”(-y,1)和和(+y,x)的執(zhí)行。于是，從的執(zhí)行。于是，從存儲單元中分別取出存儲單元中分別取出y和和x的值，算出的值，算出y-1和和y+x的結(jié)果，然后將返回值再各自取代的結(jié)果，然后將返回值再各自取代g和和h，最后求最后求(*4,7)，得結(jié)果，得結(jié)果28。2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)60 串歸約方式是一種不斷地在定義表達(dá)串歸約方式是一種不斷地在定義表達(dá)式集合中去查找和復(fù)制的過程，而且對每式集合中去查找和復(fù)制的過程，而且對每次函數(shù)作用都要重復(fù)執(zhí)行，因而時間和空次函數(shù)作用都要重復(fù)執(zhí)行，因而時間和空間的輔助開銷都比較大。間的輔助開銷都比較大。 2022-6-7計算機(jī)系統(tǒng)結(jié)構(gòu)61圖歸約方