數據流計算機

根據對數據令牌處理的方式不同，可以把數據流計算機的結構分成靜態和動態兩類。

1．靜態數據流機

靜態數據流機的數據令牌沒加標號。為正確工作，任意給定時刻，當結點操作時，其任何一條輸入弧上只能有一個數據令牌。只有當結點的所有輸入弧上都有數據令牌時，該結點才被激活，執行相應的操作。由於數據令牌沒有加標號，如果給定時間裏允許一條弧上同時出現兩個以上的數據令牌的話，結點對於送達各輸入端的一批數據就無法區分出它們中哪些是屬於同一批的操作數。因此，在靜態數據流機中，為了滿足迭代要求，除要多次重複激活同一操作結點外，還必須另設控制令牌，以識別數據令牌由一個結點傳送到另一個結點的時間關係，從而區分屬於不同迭代層次的各批數據。所以，靜態數據流機不支持遞歸的併發激活，只支持一般的循環。

2．動態數據流機

動態數據流機最主要的特點是讓令牌帶上標記，使得在任意給定時刻，數據流程序圖任何一條弧上允許出現多個帶不同標記的令牌。令牌的標記是令牌附帶的一個能識別該令牌時間先後相對關係的標號，有的機器上也稱其為顏色。所以，動態數據流機不需要像靜態數據流機那樣用控制令牌來對指令間數據令牌的傳送加以認可。對於需要多組(次)數據令牌的指令，可以通過對令牌標記的配對來識別。為此，需要相應硬件將標記附加到數據令牌上，並完成對標記的匹配工作。 ^[2] 

數據流計算機結構中是以“數據驅動”方式啓動指令的執行。按照這種方式，程序中任一條指令只要所需的操作數已經全部齊備，且有可使用的計算資源就可立即啓動執行(稱為點火)。指令的運算結果又可作為下一條指令的操作數驅動該指令的點火執行。這就是“數據驅動”的含義。

在數據流計算機模型中不存在共享數據，一條指令執行後結果數據不送存儲器保存，而是直接流向需要該結果的指令，作為新的操作數供下一條指令使用，每個操作數經過指令的一次使用後便消失。如果若干條指令要求使用相同的數據，那麼就需要事先複製該數據，分別供多條指令使用。

數據流計算機中也不存在指令計數器。指令得以啓動執行的時機取決於操作數具備與否。程序中各條指令的執行順序僅僅由指令間的數據依賴關係決定。因此，數據流計算機中指令的執行是異步併發進行的。在數據流程序中，由於“數據驅動”要求每條指令標明其運算結果的流向，也就是指向將本指令的運算結果作為操作數的那條目標指令。因此數據流程序中只有一條鏈路，即各條指令中指向目標指令的指針。

在數據流計算機中，沒有變量的概念，也不設置狀態，在指令間直接傳送數據，操作數直接以“令牌”(token)或“數值”的記號傳遞而不是作為“地址”變量加以訪問。因此操作結果不產生副作用，也不改變機器狀態，從而具有純函數的特點。所有數據流計算機通常與函數語言有密切的關係。 ^[3] 

數據流計算機的指令主要由數據令牌和操作包(operation packet)兩部分組成。

1．數據令牌

數據令牌用以傳送數據並激活指令，每個數據令牌由兩部分組成：結果數據和目標地址。結果數據就是一條指令執行的結果，是數據令牌攜帶的內容。目標地址即使用該結果的數據。這是數據流計算機工作的一個重要特徵：數據由數據令牌攜帶，在指令問直接傳送。當一條指令的所有數據令牌均到達時，該指令即被激活，可開始執行。因此數據令牌中還應含有各種標誌和特徵等。

2．操作包

操作包由操作碼(operation code)、一個或幾個源操作數(source data)以及零個或多個後繼指令地址(next address)組成。後繼指令地址用於和結果數據組成使用結果數據的後繼指令的數據令牌，如果一條指令的運算結果要送幾個目的地址，則分別形成幾個數據令牌。 ^[4] 

數據流計算機在許多方面的性能優於傳統的馮·諾依曼型計算機。下面就這個領域裏的研究人員們提出的優點進行歸納總結，其中的一部分已得到模擬實驗的驗證。

1)高度並行運算

數據流方法本身就體現了操作的高度並行性。它不僅能開發程序中有規則的並行性，還能開發程序中任意的並行性。

在數據流方法中，由於沒有指令執行順序的限制。從理論上來講，只要硬件資源充分就能獲得最大的並行性。已經通過程序驗證，許多問題的加速倍數隨處理機數目的增加

而線性的增長。

2)流水線異步操作

由於在指令中直接使用數值本身，而不是使用存放數值的地址，從而能實現無副作用的純函數型程序設計方法，可以在過程級及指令級充分開發異步並行性，可以把實際串行的問題用簡單的辦法展開成並行問題計算。例如，把一個循環程序的幾個相鄰循環體同時展開，把體內、體間本來相關的操作數直接互相替代，形成一條異步流水線，使不同次的循環體能並行執行。

數據流方法已廣泛的應用於流水線處理、數組處理及多重循環處理中。

3)與VI。SI技術相適應

雖然數據流計算機的結構比較複雜，但是它的基本組成具有模塊性和均勻性，其中的指令存儲器、數據令牌緩衝器及可執行指令隊列緩衝器等存儲部件，可以用VLSI存儲陣列均勻的構成。處理部件及信息包開關網絡也可以分別用模塊化的標準單元有規則的連接而成。因此，有可能研製出具有更高性能價格比的計算機系統。

4)有利於提高軟件生產能力

在傳統語言如FORTRAN，Pascal等語言中，由於大量使用全局變量和同義名變量而產生副作用，給軟件的生產和調試帶來很多困難。而在數據流計算機中，執行的是純函數操作，使用函數程序設計語言來編程，從含義上取消了“變量”，取消了變量賦值機制。因而消除了巴科斯所説的馮·諾依曼賦值操作的瓶頸。

用函數語言編寫的程序符合程序設計方法學的要求，易讀易懂。它良好的程序結構為程序的調試和驗證提供了很好的基礎。總之，數據流技術改善了軟件研製環境，有可能提高軟件的生產能力和可靠性。

數據流技術的反對者們指出的數據流計算機在指令級並行性上有許多潛在問題。確切的來説，上述這些數據流技術的優點實際上只是理論化的數據流計算機模型才具備的。實際的數據流計算機為獲得這些優點往往要付出巨大的代價，從而使得實際的數據流計算機具有許多明顯的不足之處。

1)操作開銷過大

與傳統的計算機相比，數據流計算機中各種操作的開銷要大得多，以至於使所獲得的並行度在相當廣泛的實際應用領域裏得不到補償。

數據流計算機中的每條指令除了包含操作碼之外，還要提供兩個操作數存儲單元及存放多個後繼指令地址的存儲單元。所以，數據流計算機的每條指令都很長。這不僅要佔用較多的存儲單元，還使指令的存取複雜且費時間。

數據流計算機中有大量中間結果形成的數據令牌在系統中流動，使信息的流動相當頻繁，衝突增加。為減小衝突，要設置許多局部緩衝器，這樣不僅增加了開銷，也延長了通信途徑。

數據流計算機操作開銷大的根本原因是把並行性完全放在指令級上。在一個實際的計算機系統中，並行可分為多級，如任務級、作業級、進程級、過程級、函數級和指令級等。

如果不適當地把高一級的並行性都依賴低級的並行性實現，往往要付出過高的代價。如已經相當成熟的數組運算就是一例。

操作開銷大的另一個原因是完全採用異步操作，沒有集中控制。為解決這些異步操作和隨即調度引起的混亂，需要花費大量的操作開銷。

2)不能有效利用傳統計算機的研究成果

數據流計算機完全放棄了傳統計算機的結構，獨樹一幟，這樣做一方面擺脱了傳統結構的束縛，具有活躍的生命力；另一方面它不能吸取傳統計算機已經證明行之有效的許多研究成果。

另外，數據流計算機企圖擺脱困擾多機系統的許多問題，如存儲器按模塊訪問引起的衝突、複雜昂貴的互連網絡、多進程之間的同步與通信等，但是在實際中往往又以新的形式回到這些老問題上。所以在數據流計算機的設計中認真吸取傳統計算機的研究成果是非常有益的。

在軟件方面，由於採用全新的函數語言，人類已經長期積累的大量軟件成果不能繼承。這一基本問題如果不解決，數據流計算機將無法進入市場，無法與傳統的計算機競爭。

3)數據流語言尚不完善

已經見到的數據流語言，如VAL及ID等都不完善，輸入輸出操作因為不是函數運算至今未被引入到數據流語言中來。另外，數據流語言以隱含的方式描述並行性，而由編譯器開發這種並行成分，但這種方式並非總是有效。因此，數據流語言還需要進一步不斷地改進和完善。

在數據流程序中由於引入了大量隱含的並行性，使得程序的調試工作變得非常困難。還沒有一種好的解決辦法。另外，對數據流計算機操作系統的研究還很少，在這一方面的研究還很不成熟。 ^[3] 

數據流計算機在提高並行處理效能上有着非常顯著的長處，但也存在一些問題。

(1)數據流機的主要目的是為了提高操作級並行的開發水平，但如果題目本身數據相關性很強，內涵並行性成分不多，就會使效率反而比傳統的Von Neumann型機還要低。

(2)在數據流機中為給數據建立、識別、處理標記，需要花費較多的輔助開銷和較大的存儲空間(可能比Neumann型的要大出2～3倍)，但如果不用標記則無法遞歸併會降低並行能力。

(3)數據流機不保存數組。在處理大型數組時，數據流機會因複製數組造成存儲空間的大量浪費，增加額外數據傳輸開銷。數據流機對標量運算有利，而對數組、遞歸及其他高級操作較難管理。

(4)數據流語言的變量代表數值而不是存儲單元位置，使程序員無法控制存儲分配。為有效回收不用的存儲單元，編譯程序的難度將增大。

(5)數據流機互連網絡設計困難，輸入/輸出系統仍不夠完善。

(6)數據流機沒有程序計數器，給診斷和維護帶來了困難。

因此，數據流機尚難批量生產，仍需進一步改進。就發展來看，數據流機是有很大潛力的，在並行度低的小型機及需要高度並行的超級機上有潛在的發展餘地，但在中型的並行機上可能較難使用。 ^[2] 

隨着數據流機研製的深人開展，已提出若干新的數據流機器，它們既繼承了傳統計算機採用的並行處理技術，又彌補了經典數據流機的一些缺陷。

1．採用提高並行度等級的數據流機

由於經典的數據流機將數據流級的並行性放在指令級上，致使機器的操作開銷大；將並行性級別提高到函數或複合函數一級上，用數據來直接驅動函數或複合函數，就可以較大地減少總的操作開銷。1981年Motooka等人及1982年Gajks等人提出複合函數級驅動方式，在全操作循環、流水線循環、賦值語句、複合條件語句、數組向量運算及線性遞歸計算上採用複合函數級的並行。這樣，就可以用傳統高級語言來編寫程序，只是需要研製專門的程序轉換軟件，實現將傳統高級語言編制的程序轉換成複合函數級的數據流程圖，並生成相應的機器碼。

2．採用同步、異步結合的數據流機

由於數據流機採用完全的異步操作，尤其是指令級的異步會造成系統操作開銷的增大。所以，在指令級上適當採用同步操作，而在函數級及函數級之上採用異步操作，就可以減少機器的操作開銷。

指令級同步操作可以使中間結果不必存回存儲器，直接被下一操作所用，指令中就不需要目標地址了，這樣可縮短指令字長。指令級同步操作不需要回答信號，減少了系統的通信量，系統採用總線互連即可，簡化了結構。雖然函數級並行異步的開銷較大，例如取函數標題、取程序要多花費些時間，互連標題也還要多佔用存儲空間，但這些開銷分攤到函數中的每條指令就少得多了。

3．採用控制流與數據流相結合的數據流機

控制流與數據流相結合，可以繼承傳統控制流計算機的優點。例如，Cedar數據流機就實現了函數級宏流水線，其指令級上仍採用控制流方式，如控制流計算機中的向量處理技術，用FORTRAN語言，經編譯開發程序的並行性技術，照樣可以使用。 ^[2]