數(shù)據(jù)流計算機(jī)結(jié)構(gòu)

1、第八章 數(shù)據(jù)流計算機(jī)結(jié)構(gòu)為了設(shè)計高性能的計算機(jī)系統(tǒng)結(jié)構(gòu)淇中一個方法是突破馮諾依曼型的結(jié)構(gòu)，采用數(shù)據(jù)流執(zhí)行方式而形成的數(shù)據(jù)流計算機(jī)。馮諾依曼型計算機(jī)的基本特點(diǎn)是在程序計數(shù)器的 集中控制下順序地執(zhí)行指令，因此是以控制流(control flow) 方式工作的.美國MIT實(shí)驗(yàn)室的 Jack Dennis 及其助手于1972 年首先提出了數(shù)據(jù)流模型, 并證明由此而設(shè)計的數(shù)據(jù)流計算機(jī) , 其性能價格比高, 較好的跟蹤工藝技術(shù)進(jìn)步的速度, 能較方便地在應(yīng)用領(lǐng)域中進(jìn)行可編程應(yīng)用 .第一節(jié) 數(shù)據(jù)流計算機(jī)的基本原理傳統(tǒng)的馮諾依曼計算機(jī)與數(shù)據(jù)流計算機(jī)的工作原理根本不同，它是在中央控制器控制下順序執(zhí)行的, 而數(shù)據(jù)流

2、計算機(jī)是在數(shù)據(jù)的可用性控制下并行執(zhí)行的. 數(shù)據(jù)流計算機(jī)里沒有指令計數(shù)器, 其指令執(zhí)行靠數(shù)據(jù)記號( 數(shù)據(jù)令牌data token) 的可用性來進(jìn)行, 也就是指令的執(zhí)行由數(shù)據(jù)來驅(qū)動, 把控制流變?yōu)閿?shù)據(jù)流, 數(shù)據(jù)流計算機(jī)里沒有常規(guī)的變量概念, 也就不存在共享數(shù)據(jù)單元的問題, 程序順序性僅是指令部內(nèi)部數(shù)據(jù)相關(guān)性控制, 也就是只要當(dāng)操作所需要的數(shù)據(jù)可用時, 即啟動指令執(zhí)行( 異步性 ) 和所有操作都具有函數(shù)性, 即所有指令都可以任何次序并發(fā)執(zhí)行. 正是這些特性, 數(shù)據(jù)流計算機(jī)可以使許多指令同時異步執(zhí)行, 預(yù)計隱含的并行度是很高的.總之 , 數(shù)據(jù)流計算機(jī)當(dāng)指令所需數(shù)據(jù)可用時, 該指令即可執(zhí)行. 這說明指令

3、的操作不受其他控制的約束. 任何一條指令只要它所需要的數(shù)據(jù)齊全, 且可用時都可以執(zhí)行. 數(shù)據(jù)流計算中沒有變量的概念, 也不設(shè)置狀態(tài), 在指令間直接傳送數(shù)據(jù), 因此操作結(jié)果不產(chǎn)生副作用, 不改變機(jī)器的狀態(tài). 從而具有純函數(shù)的特點(diǎn). 由此可見數(shù)據(jù)流計算機(jī), 第一 , 對指令來說, 擺脫了外界強(qiáng)加于它的控制, 多條指令在數(shù)據(jù)可用性驅(qū)動下同時并行; 第二 , 它可以直接支持函數(shù)語言不僅有利于開發(fā)程序中各級的并發(fā)性, 而且也有利于改善軟件環(huán)境, 提高軟件的生產(chǎn)力.第二節(jié) 數(shù)據(jù)流計算機(jī)的指令一、數(shù)據(jù)流計算機(jī)的指令在數(shù)據(jù)流at算機(jī)中，一條指令包含操作包(operation packet )和數(shù)據(jù)令牌(dat

4、a token)兩部分 , 如圖 8-1 所示 .操作包(或指令包一instruction cell)通常由操作碼、源操作數(shù)、后繼指令地址組成，又可以看成是由操作型和受處理單元影響的部分則包括已經(jīng)接收到的操作數(shù)值、數(shù)據(jù)令牌已到的標(biāo)志、正在等待的數(shù)據(jù)令牌等信息. 數(shù)據(jù)包在存儲器中將占據(jù)一定大小的空間.數(shù)據(jù)令牌通常由結(jié)果值和目標(biāo)地址等組成. 數(shù)據(jù)令牌的實(shí)質(zhì)是一種表示某一操作數(shù)或參數(shù)已準(zhǔn)備就緒的標(biāo)志. 一旦執(zhí)行某一操作的所有操作數(shù)令牌到齊, 則標(biāo)志這一操作是什么操作 , 以及操作結(jié)果所得出的數(shù)據(jù)令牌, 將發(fā)送到哪一些等待此數(shù)據(jù)令牌的操作的第幾個操作數(shù)部位等有關(guān)信息, 都將作為一個消息包(messag

5、e packet), 傳送到處理單元或操作部分予以執(zhí)行 . 這樣的消息包也稱為操作包.二、數(shù)據(jù)流計算機(jī)指令的執(zhí)行在數(shù)據(jù)流計算機(jī)中, 用數(shù)據(jù)令牌傳送并激活指令, 用一種有向圖表示數(shù)據(jù)流程序. 一條指令由一個操作符、一個或幾個操作數(shù)及后繼指令地址組成, 后繼指令地址也可以有幾個, 它的作用是把本指令的執(zhí)行結(jié)果送往需要它的地指令中, 例如 X=(a+ b)*(a-b) 這個函數(shù)中, 其數(shù)據(jù)流程圖如圖8-2 所示 , 為了表示數(shù)據(jù)在程序圖中的流動狀態(tài), 利用圖中實(shí)心的圓點(diǎn)代表令牌沿弧移動. 假設(shè) a=8,b=12, 則圖 8-2 通過令牌沿弧移動的先后過程反映出數(shù)據(jù)流程序圖的執(zhí)行過程. 實(shí)際上 , 實(shí)

6、心里圓點(diǎn)代表該輸入數(shù)據(jù)已準(zhǔn)備就緒, 旁邊的數(shù)字代表此數(shù)據(jù)值.(a) 表示初始數(shù)據(jù)就緒,激發(fā)(驅(qū)動)復(fù)制結(jié)點(diǎn)以復(fù)制多操作數(shù);(b) 表示復(fù)制結(jié)點(diǎn)驅(qū)動結(jié)束,激發(fā)數(shù)據(jù)已準(zhǔn)備就緒的+,-結(jié)點(diǎn) ;(c) 表示 +,-結(jié)點(diǎn)驅(qū)動結(jié)束,激發(fā)數(shù)據(jù)已準(zhǔn)備就緒的*結(jié)點(diǎn) ;(d) 表示 *結(jié)點(diǎn)驅(qū)動結(jié)束,輸出計算結(jié)果.總之,數(shù)據(jù)流驅(qū)動的結(jié)果,具有十分明顯的四個特性.:(1)異步性(asynchrony).只要本調(diào)治領(lǐng)所需要的數(shù)據(jù)令牌都到達(dá)，指令即可獨(dú)立執(zhí)行，而不關(guān)心其他指令及數(shù)據(jù)的情況如何.(2) 并行性 (parallelism). 可同時地并行執(zhí)行多條指令,而且這種并行性通常是隱含的.(3) 函數(shù)性 (functi

7、onalism). 由于不使用共享的數(shù)據(jù)存儲單元,所以數(shù)據(jù)流程序不會產(chǎn)生諸如改變存儲字這樣的副作用(side effect), 也可以說數(shù)據(jù)流運(yùn)算是函數(shù)性的.(4)局部性 (locality). 操作數(shù)不是作為地址變量,而是作為數(shù)據(jù)令牌直接傳送,因此數(shù)據(jù)流運(yùn)算沒有產(chǎn)生長遠(yuǎn)影響的后果,運(yùn)算效果具有局部性.綜上所述數(shù)據(jù)流運(yùn)算具有異步性、并行性、函數(shù)性、局部性,所以它很適合采用分布方式的計算實(shí)現(xiàn),從而可以把數(shù)據(jù)流計算機(jī)看作是一種分布或多處理機(jī)系統(tǒng).第三節(jié) 數(shù)據(jù)流計算機(jī)結(jié)構(gòu)數(shù)據(jù)流計算機(jī)根據(jù)對數(shù)據(jù)令牌方式的不同,通常把數(shù)據(jù)流計算機(jī)的結(jié)構(gòu)分為靜態(tài)和動態(tài)兩類。一、靜態(tài)數(shù)據(jù)流計算機(jī)模型及其結(jié)構(gòu)靜態(tài)數(shù)據(jù)流計算機(jī)

8、的最主要特點(diǎn)是數(shù)據(jù)令牌沒有標(biāo)號.為了保證正確無誤的工作,.在任意給定時刻里,當(dāng)數(shù)據(jù)流程序圖中的結(jié)點(diǎn)操作時,其任何一條輸入弧上就只能允許存在一個數(shù)據(jù)令牌 ,.在靜態(tài)數(shù)據(jù)流機(jī)中,數(shù)據(jù)令牌是沿數(shù)據(jù)流程序的弧流向操作結(jié)點(diǎn).當(dāng)所有操作數(shù)據(jù)都出現(xiàn)在輸入弧上時,開始執(zhí)行結(jié)點(diǎn)操作,任何時候只允許一個操作數(shù)呈現(xiàn)在一條弧上,否則后繼指令不能被區(qū)分.操作過程是數(shù)據(jù)令牌出于更新部件的輸入池中,它將數(shù)據(jù)傳遞到存儲部件里的目標(biāo)指令凡已接收到全部所需數(shù)據(jù)令牌的指令都被“取指令部件”取出 , 加入到多條可執(zhí)行指令的隊(duì)列中 , 等待分派程序把他們按先進(jìn)先出方式分配給處理部件中相應(yīng)的空閑處理機(jī)并發(fā)執(zhí)行.各處理器產(chǎn)生的新的數(shù)據(jù)令牌

9、形成結(jié)果的數(shù)據(jù)包( 也稱信息包), 送到“更新部件”的輸入池中 , 再由“更新部件”將這些數(shù)據(jù)令牌按它們的目的地址 , 送入存儲部件指令池內(nèi)相應(yīng)指令有關(guān)部位. 同時 , “更新部件”將已收到全部必需的數(shù)據(jù)令牌的指令地址又“傳送”給“取指令部件”, 實(shí)際上它是以控制令牌的方式把這些已具備激活條件的指令地址送到“取指令部件” . 典型的靜態(tài)數(shù)據(jù)流計算機(jī)結(jié)構(gòu)如圖8-4 所示 .MIT 和 J.B.Dennis 等人是數(shù)據(jù)流計算機(jī)研究的開拓者,他們所提出的數(shù)據(jù)流計算機(jī)系統(tǒng)的主體結(jié)構(gòu)如圖8-5 所示 .(1)存儲部件(Memory Section簡稱MS)由若干個指令單元組成.每個指令單元保存數(shù)據(jù)流程序

10、中的一條指令,它與數(shù)據(jù)流程序圖中的結(jié)點(diǎn)對應(yīng)且由唯一的地址所指明.(2)處理部件(Processing Section簡稱PS),由對數(shù)據(jù)值進(jìn)行基本運(yùn)算的多個處理單元組成 , 可以并發(fā)執(zhí)行已被激活的指令所要求地操作.(4) 分配網(wǎng)絡(luò)(Distribution Network 簡稱 DN), 它將處理部件產(chǎn)生的多個結(jié)果數(shù)據(jù)令牌依據(jù)其各自的目的地址分別傳送到存儲部件相應(yīng)的指令單元中去.(4)控制網(wǎng)絡(luò)(Control Network簡稱CN)它將控制令牌由處理部件發(fā)送到存儲部件相應(yīng)的指令單元中.(5) 仲裁網(wǎng)絡(luò)(Arbitration Network 簡稱 AN), 它將可執(zhí)行的操作包由存儲部件發(fā)送到

11、處理部件 ,可以同時允許有多個操作包在多個通路上傳送.二、動態(tài)數(shù)據(jù)流計算的模型及其結(jié)構(gòu)動態(tài)數(shù)據(jù)流計算機(jī)最主要特征是讓令牌帶上標(biāo)記,它可以在任意時刻在數(shù)據(jù)流程序圖任一條弧上出現(xiàn)多個帶不同標(biāo)記的令牌.因?yàn)榱钆频臉?biāo)記能識別該令牌時間先后相應(yīng)關(guān)系的標(biāo)號，所以不需要像靜態(tài)數(shù)據(jù)流計算機(jī)那樣用控制令牌來對指令間數(shù)據(jù)令牌的傳送加以認(rèn)可,這種方法能開拓程序中最大并行性.如果程序是循環(huán)的，則標(biāo)記方法允許動態(tài)無拘束地進(jìn)行跌代計算.動態(tài)數(shù)據(jù)流計算機(jī)的同步是由匹配機(jī)構(gòu)來實(shí)現(xiàn)的,數(shù)據(jù)令牌形成匹配部件完成數(shù)據(jù)令牌配對或成組且臨時存儲在某一個存儲空間,直到所有操作數(shù)被比較,之后已匹配的指令組釋放到更新部件,它形成執(zhí)行指令,放

12、入能執(zhí)行隊(duì)列中,然后執(zhí)行.典型的動態(tài)數(shù)據(jù)流計算機(jī)的基本結(jié)構(gòu)如圖8-6 所示 .動態(tài)數(shù)據(jù)流計算機(jī)系統(tǒng)指令中的執(zhí)行與“匹配部件”同步 . 處理部件中各處理單元輸出的數(shù)據(jù)令牌送入到“匹配部件”的輸入池，匹配部件將這些數(shù)據(jù)令牌打上標(biāo)記，并配成對或組，暫時保存起來，直到指令的一對或一組數(shù)據(jù)令牌全部配齊而被激活，送往“更新部 / 取部件”。每組數(shù)據(jù)令牌是執(zhí)行某條指令所需要的，一般對二元操作就需要兩個數(shù)據(jù)令牌。“更新 / 取部件”取出這些激活的指令加入到已配齊的操作數(shù)，然后再送往相應(yīng)的可執(zhí)行的指令隊(duì)列。由“匹配部件”給每對或每組配齊的數(shù)據(jù)令牌加上不同的標(biāo)記，可以區(qū)別處跌代執(zhí)行的不同層次，從而可以將跌代循環(huán)展

13、開，實(shí)現(xiàn)對其并行處理。目前動態(tài)數(shù)據(jù)流計算機(jī)有網(wǎng)絡(luò)型和環(huán)型兩種。這里介紹MIT的動態(tài)數(shù)據(jù)流計算機(jī)的基本結(jié)構(gòu)，如圖8 7 所示，它由N 個處理元件PE（Processing Element） 和一個用于實(shí)現(xiàn)PE間通訊N*N的包交換開關(guān)網(wǎng)絡(luò)組。每一個PE基本上是一臺完整的計算機(jī)，主要包括有自己的程序 / 數(shù)據(jù)存儲器、I 結(jié)構(gòu)存儲器、標(biāo)記匹配部件、算邏部件、打標(biāo)記和對標(biāo)記特征控制的部件及其他硬件，如圖8-7 所示。（ 1）入口有一個寄存器，此寄存器空時可以接收一個其他PE 經(jīng)開關(guān)網(wǎng)絡(luò)送來的令牌，或是接收一個本PE輸出口來的令牌。（ 2）等待匹配部件將已到的令牌暫時保存在其中的緩沖器中，直到帶匹配標(biāo)記的

14、另一個令牌的到來。當(dāng)所需兩個數(shù)據(jù)令牌均已到達(dá)，且標(biāo)記匹配，就將它們轉(zhuǎn)送到取指令部件的緩沖器中。根據(jù)標(biāo)記中的指示說明，從程序/ 數(shù)據(jù)存儲器中取出相應(yīng)指令，然后形成包含操作碼、操作數(shù)和目的地的操作包，送到執(zhí)行部件予以執(zhí)行。執(zhí)行部分有一個浮點(diǎn)算邏部件和一個用于確定一個新的操作名和目的地該用哪個PE的硬件。（ 3） I 結(jié)構(gòu)存儲器是一個帶標(biāo)記的專用存儲器，用于存放類似數(shù)組的數(shù)據(jù)結(jié)構(gòu)。如果操作數(shù)是結(jié)構(gòu)數(shù)據(jù)，則該數(shù)據(jù)從I 結(jié)構(gòu)存儲器中取得。I 結(jié)構(gòu)每一個元素有一位標(biāo)志，當(dāng)讀出時，該元素的標(biāo)志位為0，表示無值，就自動將讀推遲。使用這種I 結(jié)構(gòu)可以避免過多的數(shù)值復(fù)制操作，節(jié)省大量存儲空間和輔助操作開銷。執(zhí)行部

15、分除處理I 結(jié)構(gòu)的讀外，也完成存儲的操作。（4）在AIU或存儲器產(chǎn)生結(jié)果配上新的標(biāo)記和目的地PE號后，送往輸出口。通過輸出口的開關(guān)網(wǎng)絡(luò)送往目標(biāo)PE或不經(jīng)過開關(guān)網(wǎng)絡(luò)就直接送入本PE的輸入口。在PE各部件中為了避免在多個通路傳輸數(shù)據(jù)時發(fā)生沖突、阻塞或死鎖，各個部件都設(shè) 有相應(yīng)的緩沖器。PE中沒有程序計數(shù)器，但有一個存放已激活指令的列表，使已激活指令 的執(zhí)行是無序的。三、靜態(tài)與動態(tài)兩種數(shù)據(jù)流計算機(jī)的比較靜態(tài)數(shù)據(jù)流計算機(jī)與動態(tài)數(shù)據(jù)流計算機(jī)的相同點(diǎn)是：有多個處理部件，可以獨(dú)立、異步地執(zhí)行多條指令，都依靠數(shù)據(jù)令牌來傳送操作數(shù)和激活指令。兩者不同點(diǎn)是在于采用了不同的通信方式和不同的同步方式。在圖 8-4 所

16、示的靜態(tài)數(shù)據(jù)流計算機(jī)中，數(shù)據(jù)令牌開始存放在更新部件的輸入緩沖器內(nèi)，通過該部件傳送給指令、存儲部件。在指令存儲部件中按照數(shù)據(jù)令牌本身攜帶的目的地址，把令牌中的操作數(shù)送目標(biāo)指令。當(dāng)一條指令所需數(shù)據(jù)令牌全部到齊后，該指令開始執(zhí)行。指令由取部件從指令存儲部件中讀出，并送到可執(zhí)行的指令隊(duì)列。一旦處理部件有空閑，該指令可即刻在處理部件中被執(zhí)行。指令執(zhí)行后把產(chǎn)生的結(jié)果與后繼地址一起組成新的數(shù)據(jù)令牌，送入更新部件的輸入緩沖存儲器中，由此完成一條指令執(zhí)行的全過程。比較圖 8-6 與圖 8-4 ，不難發(fā)現(xiàn)動態(tài)數(shù)據(jù)流計算機(jī)比靜態(tài)數(shù)據(jù)流計算機(jī)多一個匹配部件。在圖8-6 中，數(shù)據(jù)令牌首先存入匹配部件的輸入緩沖器內(nèi)，該輸

17、入緩沖器采用相聯(lián)方式訪問。匹配部件把緩沖器內(nèi)的令牌配成對（或配成組），例如，執(zhí)行一個二元運(yùn)算，通常要兩個數(shù)據(jù)令牌相符合，并把配成對的數(shù)據(jù)令牌集送更新/ 取部件。更新/ 取部件將送來的數(shù)據(jù)令牌對與使用該令牌對的指令相符合，并把執(zhí)行指令所需要的操作數(shù)代入指令，形成可執(zhí)行指令，送入可執(zhí)行指令隊(duì)列等待執(zhí)行。只要某個處理部件有空閑，該指令即可執(zhí)行。由于動態(tài)數(shù)據(jù)流計算機(jī)的每個數(shù)據(jù)令牌撒上都有特殊標(biāo)記，因此，可以通過匹配部件把一個循環(huán)程序的不同次循環(huán)同時展開進(jìn)行跌代，從而能大幅度提高程序的指令級并行度，減少程序執(zhí)行時間。從原理上分析，動態(tài)數(shù)據(jù)流計算機(jī)能夠更好地開發(fā)程序中的并行成分，而且，由于中間運(yùn)算結(jié)果直接

18、代入下一條指令，不像控制流計算機(jī)要寫入內(nèi)存或通用寄存器進(jìn)行周轉(zhuǎn)，從而減少了開銷，提高程序執(zhí)行的速度。但是動態(tài)數(shù)據(jù)流計算機(jī)結(jié)構(gòu)復(fù)雜，匹配部件中相聯(lián)存儲器設(shè)計困難，因此，匹配部件通常成為影響并行度提高的一個瓶頸。第四節(jié) 數(shù)據(jù)流程序圖和數(shù)據(jù)流語言一、數(shù)據(jù)流程序圖數(shù)據(jù)流計算機(jī)的程序是用數(shù)據(jù)流語言編寫的，其機(jī)器語言也就是數(shù)據(jù)流程序圖。數(shù)據(jù)流語言主要目標(biāo)是開發(fā)程序內(nèi)隱含的并行性，便于程序設(shè)計，自然表達(dá)程序中的并行性，以及運(yùn)行的高效率。數(shù)據(jù)流語言是函數(shù)語言。在執(zhí)行前需要翻譯成數(shù)據(jù)流圖（機(jī)器語言級程序）。它執(zhí)行的是所謂點(diǎn)火原則：即一個操作可以點(diǎn)火前提是：它的所有輸入值全部到達(dá)，操作開始進(jìn)行，將輸入值吃掉，產(chǎn)生

19、輸出數(shù)據(jù)。數(shù)據(jù)流是有向圖，節(jié)點(diǎn)對應(yīng)操作符，弧是數(shù)據(jù)令牌遷移的指針。J.B.Dennis 和 J.E.Rumbaugh 等提出用于數(shù)據(jù)流程序圖的各種符號（即節(jié)點(diǎn)），并規(guī)定相應(yīng)操作執(zhí)行規(guī)則。現(xiàn)分別介紹如下：（ 1）復(fù)制節(jié)點(diǎn)圖 8-9 給出兩種最常用的復(fù)制節(jié)點(diǎn)及其操作規(guī)則。其中，圖8-9（a） 是數(shù)據(jù)復(fù)制結(jié)點(diǎn)，數(shù)據(jù)令牌x經(jīng)過復(fù)制節(jié)點(diǎn)時執(zhí)行操作，產(chǎn)生兩個相同的數(shù)據(jù)令牌X1和X2。圖8-9（b）是邏輯復(fù)制點(diǎn)，其復(fù)制結(jié)點(diǎn)為空心圓點(diǎn)，（數(shù)據(jù)復(fù)制結(jié)點(diǎn)為實(shí)心結(jié)點(diǎn)），控制令牌x 經(jīng)復(fù)制產(chǎn)生兩個相同的控制令牌x1 和 x2 。（ 2）運(yùn)算結(jié)點(diǎn)根據(jù)操作功能可分為算術(shù)運(yùn)算結(jié)點(diǎn)和邏輯運(yùn)算結(jié)點(diǎn)。算術(shù)運(yùn)算符有+、-、*、-+

20、 1、 1等。邏輯運(yùn)算結(jié)點(diǎn)有A（與）、V（或）、N（非）、（異或）等。按照輸入端個數(shù)可把結(jié)點(diǎn)分為單輸入結(jié)點(diǎn)和多輸入結(jié)點(diǎn)兩種。如圖8-10 所示。圖8-10 是 n 個例子。算術(shù)運(yùn)算結(jié)點(diǎn)的箭頭為實(shí)心，邏輯運(yùn)算箭頭為空心。（3） 常數(shù)發(fā)生器結(jié)點(diǎn)此類結(jié)點(diǎn)無輸入線，只有一條輸出線，其功能產(chǎn)生一個常數(shù)。圖8-11（a） 是該類節(jié)點(diǎn)示意圖，（b） 是常數(shù) 2 的結(jié)點(diǎn)及其執(zhí)行操作后產(chǎn)生數(shù)據(jù)令牌的情況，此令牌帶有常數(shù)2。（ 4）條件分支節(jié)點(diǎn)此類結(jié)點(diǎn)用于控制數(shù)據(jù)令牌傳送時刻，通過空心箭頭表示輸入分支線輸入的是控制令 牌。常用分支結(jié)點(diǎn)有四種：if ture then XfXtif false then XfXfi

21、f true then XfXt else X f Kif false then XfXf else Xf Xt這四種條件分支結(jié)點(diǎn)如圖8-12 至圖 8-15 所示。圖8-12是T（true）的分支結(jié)點(diǎn)及其操作規(guī)則示意圖，當(dāng)輸入分支線上的數(shù)據(jù)令牌X和帶有其值的控制令牌T 都到達(dá)該節(jié)點(diǎn)，且輸出線上沒有數(shù)據(jù)令牌時，該分支結(jié)點(diǎn)操作立即進(jìn)行，將輸入分支線上的數(shù)據(jù)令牌原樣傳送到輸出線上。圖8-13 是 F（false） 的分支結(jié)點(diǎn)及其操作規(guī)則示意圖。其工作過程與T 的類似，所不同的只是輸入分支線上的數(shù)據(jù)令牌X和帶有假值(false) 的控制令牌F 都到達(dá)該節(jié)點(diǎn)，且輸出線上無數(shù)據(jù)令牌時，該分支結(jié)點(diǎn)才執(zhí)行操

22、作。開關(guān)分支結(jié)點(diǎn)用橢圓表示，如圖8-14 所示。開關(guān)分支解帶你操作執(zhí)行規(guī)則是：當(dāng)輸入分支線上出現(xiàn)數(shù)據(jù)令牌 X時，若控制輸入分支線上令牌是真值(true)，且T輸出線上無數(shù)據(jù)令牌時，該結(jié)點(diǎn)執(zhí)行結(jié)果是把X送到T輸出線上。如圖8-14(a)所示。相反，如控制令牌是假值(false),且F輸出線上無數(shù)據(jù)令牌，該結(jié)點(diǎn)執(zhí)行結(jié)果是把 X送到F輸出線上，如 圖 8-14(b) 所示。圖 8-15 是合并結(jié)點(diǎn)及其操作執(zhí)行規(guī)則示意圖。它根據(jù)到達(dá)的控制令牌帶的是真值T還是假值F決定把T輸入線上X還是把F輸入線上X送到輸出線上。因此，其作用正好和 開關(guān)結(jié)點(diǎn)相反。(五)條件操作結(jié)點(diǎn)該結(jié)點(diǎn)用菱形表示，它有一條或數(shù)條數(shù)據(jù)令

23、牌輸入分支線和一條控制令牌輸入分支線。根據(jù)數(shù)據(jù)令牌所帶數(shù)值的某個特征(或若干輸入數(shù)據(jù)令牌所帶數(shù)值的某個關(guān)系)作出判斷，最終在輸入線上產(chǎn)生一個控制令牌。特征和關(guān)系同常包括：X>0, X=0,X<0 , 及 X>Y,X=Y,X<Y等。圖8-16是此節(jié)點(diǎn)及操作規(guī)則示意圖。圖8-16(a)是單輸入線條件操作節(jié)點(diǎn)。圖中P是判真、假使用條件。圖8-16(b)是多輸入線條件操作節(jié)點(diǎn)。圖8-17是條件操作節(jié)點(diǎn)及其執(zhí)行規(guī)則舉例。圖8-17(a)是單輸入線，當(dāng)輸入線上出現(xiàn)X且輸入線上無數(shù)令牌，若X>0 條件滿足，輸出線產(chǎn)生T 控制令牌，否則，在輸出線上產(chǎn)生一個F控制令牌。圖8-17(

24、b)是一個雙輸入線，其操作執(zhí)行規(guī)則類同于單輸入線，所不同的是判斷條件該為X>Y 。根據(jù)數(shù)據(jù)流程序圖的需要，可以利用上述這幾種單功能的操作節(jié)點(diǎn)組合成功能復(fù)雜的多功能節(jié)點(diǎn)。下面舉例說明這些單功能操作節(jié)點(diǎn)的使用方法。例 1 利用上述單功能操作節(jié)點(diǎn)實(shí)現(xiàn)一般高級語言中的條件語句：if true then G1 else G2畫出數(shù)據(jù)流程序圖，其中的G1 和 G2 都是各自獨(dú)立的數(shù)據(jù)流程序圖。如圖 8-18 所示，利用一個復(fù)雜節(jié)點(diǎn)，一個T 門分支節(jié)點(diǎn)和一個F 門分支節(jié)點(diǎn)實(shí)現(xiàn)起始數(shù)據(jù)令牌的兩路傳送，它根據(jù)起始控制令牌所攜帶的是真值還是假值把起始數(shù)據(jù)令牌分別送往 G1 數(shù)據(jù)流程序圖或G2 數(shù)據(jù)流程序圖。

25、并利用一個合并條件分支節(jié)點(diǎn)選擇G1 或 G2數(shù)據(jù)流程序圖中的一個結(jié)果作為輸出，選擇的依據(jù)仍然是起始控制令牌攜帶的是真值還是假值。例 2 利用上述單功能操作節(jié)點(diǎn)實(shí)現(xiàn)一般高級語言中的循環(huán)與句： while P do G 或 until P do G畫出數(shù)據(jù)流程圖，其中P 是循環(huán)條件，G 是循環(huán)體。如圖 8-19 所示，為了使數(shù)據(jù)流程序圖中的循環(huán)體G 能夠開始執(zhí)行，在一開始要輸入一個起始數(shù)據(jù)令牌和一個起始控制令牌，并用一個合并的分支節(jié)點(diǎn)取得循環(huán)體G 的輸入數(shù)據(jù)令牌。在第一次循環(huán)開始時從外部輸入數(shù)據(jù)令牌，而在以后的各次循環(huán)中都從循環(huán)體本身的輸出端取得所需要的輸入數(shù)據(jù)令牌。在第一次循環(huán)時，由一個T 門分

26、支節(jié)點(diǎn)控制起始數(shù)據(jù)令牌是否輸入給循環(huán)體G,這就是while和until語句的區(qū)別，控制方法是起始控制令牌攜帶真值還是攜帶假值。另外，用一個單輸入條件操作節(jié)點(diǎn)根據(jù)循環(huán)結(jié)束條件P產(chǎn)生的控制令牌來控制循環(huán)的執(zhí)行。最后用一個條件分支節(jié)點(diǎn)分配每次循環(huán)產(chǎn)生的結(jié)果數(shù)據(jù)令牌，如果循環(huán)還沒有結(jié)束，則條件操作節(jié)點(diǎn)P 輸出為真值，通過條件分支節(jié)點(diǎn)把結(jié)果數(shù)據(jù)令牌分配給循環(huán)體 G,繼續(xù)進(jìn)行下一次循環(huán)；如果循環(huán)結(jié)束，則條件操作節(jié)點(diǎn)P輸出為假值,通過條件分支節(jié)點(diǎn)把結(jié)果數(shù)據(jù)令牌輸出到外部。例 3 給定一個自然數(shù)x ，求它的階乘x！ 。畫出數(shù)據(jù)流程序圖。如果 C 語言來實(shí)現(xiàn)x! ，可以描述如下：main ( )int x ,

27、i ;scanf ( “x = %d”, x);for ( i = x, i>l; i- )x = x * i;printf ( “ x ! = %d n “, x )圖 8-20 是計算自然數(shù)x 階乘的數(shù)據(jù)流程序圖，從圖中可以明顯看出它有兩個并行執(zhí)行的迭代循環(huán)，一個是乘法操作循環(huán)，另一個是減“1 ”操作循環(huán)。為了使這個數(shù)據(jù)流程序圖能夠開始執(zhí)行，首先要從外部輸入一個帶有原始數(shù)值x 的數(shù)據(jù)令牌和一個帶有假值的起始控制令牌。通過復(fù)制節(jié)點(diǎn)把從外部輸入的原始數(shù)據(jù)令牌復(fù)制成完全相同的兩個數(shù)據(jù)令牌分別送往乘法操作循環(huán)和減“1 ”操作循環(huán)；然后在起始控制令牌的控制下，兩個迭代循環(huán)分別同時開始執(zhí)行。每執(zhí)

28、行一次循環(huán)，“>1 ”條件操作節(jié)點(diǎn)就產(chǎn)生一個帶有真值的控制令牌，在這個控制令牌的控制下并行執(zhí)行一次乘法循環(huán)和一次減“1 ”循環(huán)。當(dāng)“-1 ”操作節(jié)點(diǎn)輸出帶有數(shù)值“1 ”的數(shù)據(jù)令牌時，“ 1 ”條件操作就產(chǎn)生一個帶有假值的控制令牌，在這個控制令牌的控制下停止乘法操作循環(huán)和減“1”操作循環(huán)，并把乘法操作節(jié)點(diǎn)產(chǎn)生的最后一個數(shù)據(jù)令牌作為最終運(yùn)算結(jié)果輸出到外部，在這個數(shù)據(jù)令牌中攜帶的數(shù)值就是最終運(yùn)算結(jié)果 x! 。從圖 8-20 所示的計算x 階乘的數(shù)據(jù)流程序圖中可以很明顯地看到，在數(shù)據(jù)流計算機(jī)中操作執(zhí)行過程的異步性和充分的并行性。數(shù)據(jù)流程序圖相當(dāng)于數(shù)據(jù)流計算機(jī)中的機(jī)器語言。對于一般用戶，如果直接用

29、數(shù)據(jù)流程序圖編寫程序是很不方便的。數(shù)據(jù)流程序圖與傳統(tǒng)計算機(jī)中的高級語言和超高級語言相比，不易被用戶接受。因此，必須研制適合于數(shù)據(jù)流計算機(jī)的高級語言，這種高級語言應(yīng)該能夠用近似于自然語言的方式最大限度地描述隱含的并行性，并具有易讀，易于理解和調(diào)試，維護(hù)方便等優(yōu)點(diǎn)。二 數(shù)據(jù)流語言及其性質(zhì)目前，數(shù)據(jù)流語言的研究還很不成熟，還沒有形成象傳統(tǒng)高級語言那樣的規(guī)范版本。就已經(jīng)出現(xiàn)的數(shù)據(jù)流語言而言，大致可以分為如下三類：(1)單賦值預(yù)言(single assignment language):包括美國加州大學(xué)Irvine分校研制的ID語言 ( Irvine Data Flow Language ) 和美國 M

30、IT 科學(xué)試驗(yàn)室的Dennis 教授于 1979 年提出的VAL 語言 ( Value Algorithmic Language ) 。(2)函數(shù)類語言(Functional Language ):比較著名的有美國猶他大學(xué)研制的FP語言( Functional Programming Language ).(3) 命令類語言(Command Language )：目前，美國依阿華州立大學(xué)正在研制此類語言，并研制了把命令類語言轉(zhuǎn)換成數(shù)據(jù)流語言的編譯器。一般來所，不論采用哪種高級語言編寫的程序，都可通過相應(yīng)的編譯程序處理后，變換成數(shù)據(jù)流圖。但是，傳統(tǒng)機(jī)器上廣泛使用的面向過程的命令或語言缺乏并行性描

31、述，很難表達(dá)出數(shù)據(jù)流控制機(jī)制的并行性。雖然有些高級語言也擴(kuò)充了并行描述部分，如：FORTRAN 的 FORK 和 JOIN ，以及并行PASCAL ,Ada 等語言。由命令是語言程序轉(zhuǎn)換成數(shù)據(jù)流的過程也還是復(fù)雜，低效的，所以仍需要研究和發(fā)展新的、適合于數(shù)據(jù)控制機(jī)制的高級語言，希望能以“自然”方式，最充分地表達(dá)出計算的并行性，并使用戶編程方便，程序有較強(qiáng)的可讀性核可維護(hù)性。在這方面有美國的VAL 語言 ( Value AlgorithmicLanguage )、 ID 語言 ( Irvine Data Flow Language ) ，法國的LAU 語言，英國曼徹斯特大學(xué)的SISAL 語言等都具

32、有可操作性。MIT 所研制的VAL 語言是面向值的應(yīng)用式數(shù)據(jù)流語言。用它書寫的程序是一組獨(dú)立翻譯的模塊集合，每一個模塊包括一個外部函數(shù)定義，該函數(shù)對于程序中的其他模塊都可以訪問。模塊還可以包括內(nèi)部函數(shù)定義，它僅能在模塊中使用，對其他模塊則是不可訪問的?？傊?， VAL 語言具有易于開發(fā)程序中隱含和顯式的并行性，語句結(jié)構(gòu)表達(dá)了算法的并行成分；沒有變量的概念，僅有值的名稱，提供的數(shù)據(jù)類型有整型、實(shí)型、布爾型和字符型等；編制的源程序具有模塊化結(jié)構(gòu)，源程序中不規(guī)定語句的執(zhí)行順序，語句的執(zhí)行順序不影響最終計算結(jié)果；它能對任何函數(shù)的自變量和計算結(jié)果的數(shù)據(jù)類型都在函數(shù)的首部加以定義。編譯程序在編譯過程中能方便

33、的檢查出函數(shù)和表達(dá)式中數(shù)據(jù)類型發(fā)生的錯誤。但是VAL 語言也存在著沒有輸入輸出手段，程序的表達(dá)形式還不夠自然和方便，運(yùn)行的效率還很低。傳統(tǒng)的程序設(shè)計語言是建立在Von Neumann 系統(tǒng)結(jié)構(gòu)基礎(chǔ)上的，共享存儲單元，順序控制方式執(zhí)行語句或指令。因此，控制流語言不能充分表達(dá)程序中的并行性。雖然已開發(fā)出并行Pascal,并發(fā)Prolog,向量Fortran等，但是，這些語言是以順序執(zhí)行和多賦值為基礎(chǔ)的，所以不能用到數(shù)據(jù)流計算機(jī)中來。數(shù)據(jù)流語言應(yīng)具有如下性質(zhì)：(1) 并行性好：指令的執(zhí)行順序僅受程序中數(shù)據(jù)相關(guān)性的約束，而與指令在存儲器中存放的位置(即地址)無關(guān)，因此，數(shù)據(jù)流語言能夠以自然的方式最大限

34、度地表達(dá)程序中的并行性。(2) 單賦值規(guī)則：根據(jù)單賦值規(guī)則，在所有語句的左邊，同一變量名只能出現(xiàn)一處，即要為任何一個重新賦值的變量選擇一個從未用過的新名字，而且在以后所有引用中都使用這個新名字。例如下列兩個程序段：程序甲： x= a - b程序乙：x = a -bx= x + yx1 =x +yz= x -yz = x1 -y程序甲語句序列不滿足單賦值規(guī)則，而程序乙卻滿足單賦值規(guī)則。單賦值規(guī)則使程序清晰，易于理解，為程序的并行執(zhí)行提供了一種新方法。該規(guī)則由 Tesler和Enea于1969年提出，被法國LAU 機(jī)和英國的Manchester 機(jī)采用(注：均為數(shù)據(jù)流計算機(jī)) 。(3) 不產(chǎn)生副作

35、用：副作用是指使用了不當(dāng)變量而產(chǎn)生數(shù)據(jù)相關(guān)，從而導(dǎo)致程序不能順序執(zhí)行。在數(shù)據(jù)流語言中不使用全局變量和公共變量，嚴(yán)格控制變量使用范圍，采用賦值調(diào)用 ( Call by Value ) ， 而不是傳統(tǒng)機(jī)中的引用調(diào)用，這就是根本上解決了變量的同一名問題。賦值調(diào)用過程只復(fù)制變量，而不修改變量。因此，在子程序中決不修改調(diào)用程序傳送來的變量，即各程序模塊之間的輸入和輸出是完全隔離的。(4) 結(jié)果的局部性：傳統(tǒng)的過程式語言大量使用局部變量，并只允許在本過程內(nèi)部定義、賦值和引用，保證了操作結(jié)果具有局部性，不對其他過程產(chǎn)生影響，即使在不同過程中使用了相同的變量也仍然能夠保證操作結(jié)果具有局部性。但是，過程式語言也

36、允許使用全局變量，并規(guī)定任何一個過程都可對全局變量賦值，因此，全局賦值可能會對其他過程產(chǎn)生影響。在數(shù)據(jù)流計算機(jī)的指令中，沒有長遠(yuǎn)起作用的數(shù)據(jù)依賴關(guān)系，數(shù)據(jù)流語言完全采用模塊化結(jié)構(gòu)，不是用全局變量，不允許全局賦值，對形式參量的賦值也有嚴(yán)格限制，因此，在數(shù)據(jù)流語言中每一個操作產(chǎn)生的結(jié)果都具有局部性。(5) 循環(huán)程序迭代展開：從圖8-19 可見，一個循環(huán)程序可以用一個環(huán)行結(jié)構(gòu)的數(shù)據(jù)流程序圖表示，數(shù)據(jù)流計算機(jī)本身就是一種環(huán)行結(jié)構(gòu)。因此，如果要把循環(huán)程序的不同次循環(huán)展開，進(jìn)行并行計算，則必須在數(shù)據(jù)令牌中增加一種特殊的標(biāo)記，這就引出了所謂的動態(tài)數(shù)據(jù)流計算的概念(見前述)?，F(xiàn)在通過例子說明如何把循環(huán)程序展開

37、進(jìn)行并行計算。有一個用 C 語言編寫的循環(huán)程序如下：for ( i =1 ; i <= n ; i +)xi = a i + b i;yi = x i + c i;zi = x i + y i;在每個循環(huán)體中存在三個“先寫后獨(dú)”數(shù)據(jù)相關(guān)，因此，每個循環(huán)體只能串行執(zhí)行。按照常規(guī)計算方法，循環(huán)體部分只能用一個加法器運(yùn)算，共需要3n 個機(jī)器周期才能執(zhí)行完。如果把相鄰的三個循環(huán)體同時展開，并按照流水線原理重新進(jìn)行調(diào)度，可以得到語義上完全等效的新循環(huán)程序。x1 = a 1 + b 1;y1 = x 1 + c 1;x2 = a 2 + b 2;for ( i =1 ; i <= n ; i +)zi = x i + y i;yi+1 = x i+1 + c i+1;xi+2