1、1,6.1 引言,現(xiàn)代計(jì)算機(jī)自問世以來已歷經(jīng)50余年的歷史，基本結(jié)構(gòu)形式始終是馮諾依曼機(jī)結(jié)構(gòu)。 馮諾依曼機(jī)的基本特征: “程序存儲(chǔ)、順序執(zhí)行、二進(jìn)制、五大部件組成、共享數(shù)據(jù)”,第六章 數(shù)據(jù)流計(jì)算機(jī),2,相關(guān)性是并行處理的關(guān)鍵問題 并行處理計(jì)算的發(fā)展，兩條路線： 對(duì)馮諾依曼機(jī)結(jié)構(gòu)改進(jìn)，適應(yīng)并行處理，解決相關(guān)性問題 提出非馮諾依曼結(jié)構(gòu),3,四種驅(qū)動(dòng)方式計(jì)算機(jī)模型,按控制機(jī)制對(duì)計(jì)算機(jī)模型分類，Treleaven教授提出劃分為四種驅(qū)動(dòng)方式： 控制驅(qū)動(dòng) 數(shù)據(jù)驅(qū)動(dòng) 需求驅(qū)動(dòng) 模式匹配驅(qū)動(dòng),4,控制驅(qū)動(dòng)模型,這是傳統(tǒng)的馮諾依曼型結(jié)構(gòu) 基本特征： 命令式語言 程序順序執(zhí)行，指令的執(zhí)行次序受指令計(jì)數(shù)器的控制，即

2、由程序員指定序列操作 影響并行性主要因素: “共享數(shù)據(jù)，順序執(zhí)行”,5,控制驅(qū)動(dòng)發(fā)展并行控制流模型 如Fork和Join結(jié)構(gòu)，允許在同一時(shí)刻有幾個(gè)控制流同時(shí)活動(dòng)。 并行控制流模型關(guān)鍵技術(shù)之一是采用同步手段（如Join操作符）來處理數(shù)據(jù)的相關(guān)性。 存在問題： 用程序計(jì)數(shù)器（PC）確定程序中指令執(zhí)行的順序，程序流由程序員顯式控制 控制流計(jì)算機(jī)用共享存儲(chǔ)器來保存指令和數(shù)據(jù)對(duì)象，共享存儲(chǔ)器中的變量可被多條指令修改。由于存儲(chǔ)器是共享的，所以一條指令執(zhí)行后可能會(huì)對(duì)其它指令產(chǎn)生副作用。副作用會(huì)妨礙并行處理。,6,數(shù)據(jù)驅(qū)動(dòng)模型,程序中任意一條指令中所需的操作數(shù)（數(shù)據(jù)令牌）到齊，立即啟動(dòng)執(zhí)行（稱為“點(diǎn)火”）。一

3、條指令的運(yùn)算結(jié)果又流向下一條指令，作為下一條指令的操作數(shù)來驅(qū)動(dòng)此指令的啟動(dòng)執(zhí)行 能充分地利用程序中指令級(jí)并行性 不存在共享數(shù)據(jù)，也不存在指令計(jì)數(shù)器，指令啟動(dòng)執(zhí)行的時(shí)機(jī)僅取決于操作數(shù)具備與否。只要有足夠多的處理單元，凡是相互間不存在數(shù)據(jù)相關(guān)的指令都可以并行執(zhí)行,7,數(shù)據(jù)驅(qū)動(dòng)模型,8,需求驅(qū)動(dòng)模型,一個(gè)操作僅在需要用到其輸出結(jié)果時(shí)才開始啟動(dòng)。 如果這時(shí)該操作由于操作數(shù)未到而不能得到輸出結(jié)果，則該操作再去啟動(dòng)能得到它的各個(gè)輸入數(shù)的操作，也可能那些操作還要去啟動(dòng)另外一些操作，這樣就把需求鏈一直延伸下去，直至遇到常數(shù)或外部輸入的數(shù)據(jù)已經(jīng)到達(dá)為止，然后再反方向地去執(zhí)行運(yùn)算。,9,需求驅(qū)動(dòng)模型,10,需求驅(qū)

4、動(dòng)的系統(tǒng)結(jié)構(gòu)也取消了共享數(shù)據(jù)和指令計(jì)數(shù)器，但其執(zhí)行操作的次序與數(shù)據(jù)驅(qū)動(dòng)方式不同。由于需求驅(qū)動(dòng)方式只對(duì)需要用到其結(jié)果的操作進(jìn)行求值，也即只執(zhí)行最低限度的求值，免除了許多冗余的計(jì)算，從總體而言，它比數(shù)據(jù)驅(qū)動(dòng)執(zhí)行的計(jì)算量小。歸約機(jī)就是基于需求驅(qū)動(dòng)的計(jì)算機(jī),11,計(jì)算的運(yùn)行是由謂詞模式匹配加以驅(qū)動(dòng)的，程序的執(zhí)行主要適合于求解非數(shù)值的符號(hào)演算。面向智能的計(jì)算機(jī)就是基于“模式匹配驅(qū)動(dòng)”的計(jì)算機(jī)。,模式匹配驅(qū)動(dòng),12,6.2 數(shù)據(jù)流計(jì)算機(jī),基本工作思路 由數(shù)據(jù)驅(qū)動(dòng)程序的執(zhí)行； 一條指令執(zhí)行后不送存儲(chǔ)器保存，以供其他指令共享，而是直接流向需要該結(jié)果的指令，作為新的操作數(shù)供下一條指令使用。,每個(gè)操作數(shù)經(jīng)過指令的

5、一次使用后便消失。,如果若干條指令要求使用相同的數(shù)據(jù)，那么就需要事先復(fù)制該數(shù)據(jù)的若干個(gè)副本，分別供多條指令使用。,13,數(shù)據(jù)流驅(qū)動(dòng)的特點(diǎn) 指令的執(zhí)行是由數(shù)據(jù)可用性來驅(qū)動(dòng)，而不是由程序計(jì)數(shù)器來控制。 任何指令只要操作數(shù)可用，應(yīng)該說是做好了執(zhí)行的準(zhǔn)備。 數(shù)據(jù)驅(qū)動(dòng)程序中的指令不用任何方式來排定次序。 數(shù)據(jù)直接保存在指令內(nèi)，不是存在共享存儲(chǔ)器中。,14,計(jì)算結(jié)果（數(shù)據(jù)令牌）直接在指令間傳遞。一條指令產(chǎn)生的數(shù)據(jù)可被復(fù)制成多份副本直接送給所有缺乏數(shù)據(jù)的指令。數(shù)據(jù)令牌一旦被一條指令使用后，它就不能再被其它指令重復(fù)使用。 不需要共享存儲(chǔ)器，不需要程序計(jì)數(shù)器，不需要控制定序器。,15,需要專門的機(jī)構(gòu)來檢測(cè)數(shù)據(jù)可

6、用性，將數(shù)據(jù)令牌和缺乏數(shù)據(jù)的指令進(jìn)行匹配，同時(shí)使指令執(zhí)行的異步鏈結(jié)作用得以實(shí)現(xiàn)。 沒有存儲(chǔ)共享就不會(huì)產(chǎn)生副作用。 異步性意味著需要握手信息或令牌匹配操作。 純數(shù)據(jù)流計(jì)算機(jī)可開發(fā)指令級(jí)細(xì)粒度并行性。,16,可重入結(jié)構(gòu)、可重入程序 要求可以被多個(gè)任務(wù)所調(diào)用，需要： 程序模塊本身在執(zhí)行過程中不能被修改 調(diào)用它的各程序應(yīng)自帶參數(shù)工作區(qū),17,數(shù)據(jù)流計(jì)算機(jī)指令結(jié)構(gòu),指令主要由操作包(Operation Packet)和數(shù)據(jù)令牌(Data Token)兩部分組成 操作包由操作碼(Operation Code)，一個(gè)或幾個(gè)源操作數(shù)(Source Data)及后繼指令地址(Next Address)等等組成

7、數(shù)據(jù)令牌通常由結(jié)果數(shù)值和目標(biāo)地址等組成。其中的結(jié)果值是上條指令的運(yùn)算結(jié)果，而目標(biāo)地址直接取自上條指令的后繼指令地址， 如果一條指令的運(yùn)算結(jié)果要送往幾個(gè)目的地，則分別形成幾個(gè)數(shù)據(jù)令牌，多個(gè)數(shù)據(jù)令牌同時(shí)在各個(gè)操作部件之間傳送，允許有多條指令并行執(zhí)行。,18,數(shù)據(jù)流機(jī)指令格式,19,數(shù)據(jù)流計(jì)算機(jī)中指令的執(zhí)行過程,函數(shù)x=(a+b)(a-b)在數(shù)據(jù)流計(jì)算機(jī)中的計(jì)算過 其中符號(hào)( )表示數(shù)據(jù)令牌所攜帶的操作數(shù),20,“.”表示數(shù)據(jù)令牌,21,第一步，數(shù)據(jù)令牌( )=a，( )=b； 第二步，指令K、K+1被激活并行執(zhí)行，產(chǎn)生結(jié)果數(shù)據(jù)送下一 條指令、 第三步，指令K+2被激活，進(jìn)行乘法運(yùn)算產(chǎn)生結(jié)果X。,2

8、2,例1：數(shù)據(jù)流計(jì)算機(jī)和控制流計(jì)算機(jī)的比較 任務(wù)描述：解方程 ax2 + bx + c = 0，解的形式為：,23,串行程序如下（它只能順序執(zhí)行）： begin input( a, b, c ) a:= 2*a; c:= b2-4*a*c; c:= sqrt( c ); c:= c/a; b:= -b/a; a:= b+c; b:= b-c; output( a, b ); end,24,并行控制驅(qū)動(dòng)、共享存儲(chǔ)模型的FORK-JOIN程序如下，它增加了控制流的復(fù)雜性，但還不能從根本上改變它的操作有序性。 begin input( a, b, c ) a:= 2*a; c:= b2-4*a*c;

9、 FORK L1, L2;(控制程序并行執(zhí)行) L1: begin c:= sqrt( c ); c:= c/a; goto L3; end,25,L2: begin b:= -b/a; goto L3; end L3: JOIN L1, L2; (等L1,L2完成） FORK L4, L5;( L4, L5并行執(zhí)行) L4: begin a:= b+c; goto L6; end,26,L5: begin b:= b-c; goto L6; end L6: JOIN L4, L5; (等L4,L5完成） output( a, b); end,27,數(shù)據(jù)流相關(guān)圖如下：,各計(jì)算步，只要輸入數(shù)據(jù)到

10、齊就可以計(jì)算。比如上圖中的（2）與（3），（6）與（7）是可以同時(shí)操作的。,28,例2：數(shù)據(jù)流計(jì)算機(jī)和控制流計(jì)算機(jī)的比較 程序描述： input d, e, f c0 = 0 for i from 1 to 8 do begin ai = di ei bi = ai fi ci = bi + ci end output a, b, c,29,數(shù)據(jù)流圖：,+,d1,e1,a1,f1,b1,c0,+,d2,e2,a2,f2,b2,c1,+,d3,e3,a3,f3,b3,c2,+,d4,e4,a4,f4,b4,c3,+,d5,e5,a5,f5,b5,c4,+,d6,e6,a6,f6,b6,c5,+,

11、d7,e7,a7,f7,b7,c6,+,d8,e8,a8,f8,b8,c7,c8,其中： 加法需要一個(gè)時(shí)鐘周期，乘法需要2個(gè)周期，除法需要3個(gè)周期。,30,單處理機(jī)用48個(gè)周期完成計(jì)算：,a1,b1,c1,a2,b2,c2,a8,b8,c8,1,4,6,7,10,12,13,43,46,48,4臺(tái)處理機(jī)的數(shù)據(jù)流計(jì)算機(jī)用14個(gè)周期完成：,a1,b1,c1,a5,b2,c2,a2,b8,1,4,7,8,10,9,11,12,13,14,c3,c4,c5,c6,c7,c8,b4,b6,b3,b5,a3,b7,a6,a4,a7,a8,P1：,P2：,P3：,P4：,31,共享存儲(chǔ)的4臺(tái)處理機(jī)系統(tǒng)用14

12、個(gè)周期完成：,a1,b1,c1,a5,b2,a2,b8,1,4,7,9,11,12,13,14,c3,c4,c5,c7,c8,b4,b6,b3,b5,a3,b7,a6,a4,a7,a8,P1：,P2：,P3：,P4：,s1,t1,c2,c6,s2,t2,s1,t1,s2,t2,其中：,32,數(shù)據(jù)流驅(qū)動(dòng)四個(gè)性質(zhì)：,異步(Asynchrony)只要本條指令所需要的數(shù)據(jù)令牌都到達(dá)，指令即可獨(dú)立地執(zhí)行，而不必關(guān)心其他指令及數(shù)據(jù)的情況如何。 并行性(Parallelism)可同時(shí)地并行執(zhí)行多條指令， 而且這種并行性通常是隱含的。 函數(shù)性(Functionalism) 由于不使用共享的數(shù)據(jù)存儲(chǔ)單元，所以數(shù)

13、據(jù)流程序不會(huì)產(chǎn)生諸如改變存儲(chǔ)字這樣的副作用。也可以說，數(shù)據(jù)流運(yùn)算是純函數(shù)性的。 局部性(Locality) 操作數(shù)不是作為“地址”變量， 而是作為數(shù)據(jù)令牌直接傳送，因此數(shù)據(jù)流運(yùn)算沒有產(chǎn)生長(zhǎng)遠(yuǎn)影響的后果，運(yùn)算效果具有局部性。,33,2. 數(shù)據(jù)流程序圖和數(shù)據(jù)流語言,數(shù)據(jù)流程序圖有兩種表示方法： 活動(dòng)片表示法(Activity Templete)； 有向圖(Directed Graph)法。 活動(dòng)片表示法的基本單元是活動(dòng)片，每個(gè)活動(dòng)片通常相當(dāng)于一個(gè)或幾個(gè)操作結(jié)點(diǎn)。一個(gè)活動(dòng)片由一個(gè)操作碼域，一個(gè)或幾個(gè)操作數(shù)域，一個(gè)或幾個(gè)后繼指令地址域及有關(guān)標(biāo)志等組成 (與傳統(tǒng)計(jì)算機(jī)指令系統(tǒng)相似）,34,有向圖法(Di

14、rected Graph)，通過特殊有向圖描述數(shù)據(jù)流計(jì)算機(jī)的工作過程。 由有限個(gè)結(jié)點(diǎn)(Node)集合以及把這些結(jié)點(diǎn)連接起來的單向分支線(Unidirectional Branch)組成。 通過數(shù)據(jù)令牌沿有向分支線傳送來表示數(shù)據(jù)在數(shù)據(jù)流程序圖中的流動(dòng)。用結(jié)點(diǎn)表示進(jìn)行相應(yīng)的操作，當(dāng)一個(gè)結(jié)點(diǎn)的所有輸入分支線上都出現(xiàn)數(shù)據(jù)令牌，且輸出分支線上沒有數(shù)據(jù)令牌時(shí)，該結(jié)點(diǎn)的操作即可執(zhí)行。,35,函數(shù)x=(a+b)(a-c)的數(shù)據(jù)流程序圖 圓點(diǎn)“.”表示數(shù)據(jù)令牌，三個(gè)算術(shù)運(yùn)算結(jié)點(diǎn)，執(zhí)行加、減、乘操作,36,算邏運(yùn)算結(jié)點(diǎn)：加()、減()、乘()、除() 、與 ()、或()等。 常數(shù)產(chǎn)生結(jié)點(diǎn)：它沒有輸入端，只產(chǎn)生常數(shù)

15、 復(fù)制操作結(jié)點(diǎn)：數(shù)據(jù)或控制量的多個(gè)復(fù)制。數(shù)據(jù)令牌d經(jīng)過復(fù)制結(jié)點(diǎn)激發(fā)后，執(zhí)行復(fù)制操作變成多個(gè)數(shù)據(jù)令牌d1，d2，d3控制復(fù)制操作類同。,基本結(jié)點(diǎn)：,37,T門控結(jié)點(diǎn)：僅當(dāng)布爾控制端為真、 且輸入端有數(shù)據(jù)令牌，而輸出端沒有數(shù)據(jù)令牌時(shí)才能激發(fā)， F門控結(jié)點(diǎn)：與T門控結(jié)點(diǎn)類似，僅當(dāng)布爾控制端為假時(shí)，才能激發(fā),38,開關(guān)門控結(jié)點(diǎn)(SW結(jié)點(diǎn))：有一個(gè)數(shù)據(jù)輸入端和兩個(gè)數(shù)據(jù)輸出端和一個(gè)控制端，根據(jù)控制端令牌的真假確定T輸出端或F輸出端上帶有輸入端的數(shù)據(jù)令牌 合并門控結(jié)點(diǎn)(MG結(jié)點(diǎn))：有兩個(gè)數(shù)據(jù)輸入端和一個(gè)數(shù)據(jù)輸出端和一個(gè)控制端， 并受控制端控制。激發(fā)后， 根據(jù)控制端值真假在輸出端上產(chǎn)生來自T輸入端還是F輸入端

16、上的數(shù)據(jù)令牌。,39,判斷操作結(jié)點(diǎn)： 當(dāng)滿足條件時(shí)（小于、等于、大于0，兩個(gè)數(shù)據(jù)的大小比較等）在輸出端產(chǎn)生T的控制令牌， 否則便產(chǎn)生F的控制令牌,40,復(fù)合類型結(jié)點(diǎn),條件結(jié)構(gòu)數(shù)據(jù)流圖,41,IF X=100 THEN (X+Y)/Y ELSE (X-Y)/Y,42,循環(huán)結(jié)構(gòu)的數(shù)據(jù)流程序圖,43,例：給定一個(gè)自然數(shù)x， 求它的階乘x!,C語言程序描述,44,計(jì)算X階乘的數(shù)據(jù)流程序圖,45,數(shù)據(jù)流語言,對(duì)應(yīng)于數(shù)據(jù)流程圖，最大限度地描述隱含的并行性，能方便地被編譯成數(shù)據(jù)流程序，以便在數(shù)據(jù)流計(jì)算機(jī)上執(zhí)行，并具有易讀、易于理解和調(diào)試、維護(hù)方便 常用的數(shù)據(jù)流語言有美國的ID和VAL，法國的LAU以及英國曼

17、徹斯特大學(xué)的SISAL 語言等,46,單賦值規(guī)則。單賦值的含義是指在程序中每個(gè)變量只能賦值一次，即同一變量在賦值語句的左部只允許出現(xiàn)一次，不允許對(duì)同一變量進(jìn)行多次賦值。遵循單賦值規(guī)則。這有利于運(yùn)算并行性的開發(fā)，同時(shí)也可防止“副作用”。所謂“副作用”是指在程序執(zhí)行過程中修改了某些參數(shù)的值 指令的執(zhí)行次序由數(shù)據(jù)依賴關(guān)系確定，指令執(zhí)行規(guī)則簡(jiǎn)單地僅受數(shù)據(jù)相關(guān)性約束。 控制變量的應(yīng)用范圍,數(shù)據(jù)流語言基本特征：,47,例： for ( i=1; i=n ; i+) xi=ai+1; yi=xi+2; zi=yi+3 需要3n周期 x1=a1+1; y1=x1+2;x2=a2=1; for ( i=1; i

18、=n-1; i+) zi=yi+3; yi+1=xi+1+2; xi+2=ai+2+1 zn-1=yn-1+3; yn=xn+2; zn=yn+3 需要n2周期,支持循環(huán)迭代展開,48,ID語言舉例：procedure inner-product (a，b，n)initial s0for I from 1 to n donew ss+ (ai*bj)return s,49,3. 數(shù)據(jù)流計(jì)算機(jī)結(jié)構(gòu),靜態(tài)數(shù)據(jù)流計(jì)算機(jī) 基本點(diǎn)：數(shù)據(jù)令牌不帶任何標(biāo)號(hào)，每條有向分支線上在某一個(gè)時(shí)刻只能傳送一個(gè)數(shù)據(jù)令牌，每個(gè)結(jié)點(diǎn)一次只能執(zhí)行一個(gè)操作。 執(zhí)行規(guī)則：結(jié)點(diǎn)的每一條輸入分支線上都有一個(gè)令牌出現(xiàn)（數(shù)據(jù)分支線上出現(xiàn)的

19、數(shù)據(jù)令牌，控制分支線上出現(xiàn)攜帶結(jié)點(diǎn)操作所要求控制信號(hào)的控制令牌），而且輸出分支線上沒有令牌時(shí)，該結(jié)點(diǎn)的操作才能夠被執(zhí)行。 具有數(shù)據(jù)令牌，還有控制令牌，由這兩種令牌同時(shí)來決定結(jié)點(diǎn)的操作是否執(zhí)行,50,靜態(tài)數(shù)據(jù)流計(jì)算機(jī)模型 Jack Dennis1972年提出,51,操作過程,指令存儲(chǔ)部件ISU中存放要執(zhí)行的數(shù)據(jù)流程序 收到所需數(shù)據(jù)令牌的指令由取指令部件RU按更新部件UU送來的指令地址逐個(gè)取出，送到可執(zhí)行指令隊(duì)列IQ中，此時(shí)若有空閑的處理部件，分派程序?qū)⒌却龍?zhí)行的指令按次序分配給指令處理部件PU，使它們并發(fā)執(zhí)行。執(zhí)行后的結(jié)果形成新的數(shù)據(jù)令牌， 數(shù)據(jù)令牌又被送到更新部件中，再按它們的目標(biāo)地址送往指令

20、存儲(chǔ)部件內(nèi)相應(yīng)指令的有關(guān)位置，當(dāng)更新部件將所有已收到所需數(shù)據(jù)令牌的指令地址傳送給取指令部件，完成了一次循環(huán)流動(dòng),52,Dennis靜態(tài)數(shù)據(jù)流計(jì)算機(jī)的結(jié)構(gòu)框圖,靜態(tài)數(shù)據(jù)流計(jì)算機(jī)實(shí)例1,53,指令存儲(chǔ)器：用于存放指令。每條指令有一個(gè)唯一的地址，也稱為指令單元標(biāo)識(shí)符 處理部件：主要由多個(gè)相同或不同的處理單元組成，主要完成數(shù)據(jù)的函數(shù)運(yùn)算。 仲裁網(wǎng)絡(luò)(Arbitration Network)： 其主要作用是把操作包從指令存儲(chǔ)器傳送到處理部件。 控制網(wǎng)絡(luò)(Control Network)： 把控制令牌從處理部件傳送到指令存儲(chǔ)器。 分配網(wǎng)絡(luò)(Distributed Network)： 把數(shù)據(jù)令牌從處理部件傳

21、送到指令存儲(chǔ)器。,54,靜態(tài)數(shù)據(jù)流計(jì)算機(jī)實(shí)例2,Mondala靜態(tài)數(shù)據(jù)流機(jī),55,11 個(gè),0,31,OPR本指令所需操作數(shù)個(gè)數(shù)（數(shù)據(jù)令牌） AKR本指令所需收到的控制信號(hào)個(gè)數(shù)（控制令牌） ES計(jì)數(shù)器，分別對(duì)到達(dá)數(shù)據(jù)令牌和控制令牌計(jì)數(shù),指令格式,56,兩種實(shí)現(xiàn)可重入代碼的并發(fā)調(diào)用方法 重入代碼復(fù)制 當(dāng)數(shù)據(jù)流程序需要調(diào)用一段可重入代碼時(shí)，復(fù)制這段代碼形成一個(gè)副本被調(diào)用執(zhí)行。執(zhí)行結(jié)束后把結(jié)果送到輸出端保留，以備其它指令應(yīng)用，副本隨即消失。問題：復(fù)制過程開銷大，程序副本占大量的存儲(chǔ)空間。,動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī),57,馮.諾依曼結(jié)構(gòu)可重入代碼的遞歸調(diào)用均是一次調(diào)用總是在上次調(diào)用之后進(jìn)行。每時(shí)刻僅有一個(gè)可重

22、入代碼的副本在運(yùn)行，從而保證了多次調(diào)用的順序。 數(shù)據(jù)流機(jī)的并行可能并發(fā)調(diào)用同一個(gè)可重入代碼，即同一時(shí)刻有多個(gè)副本在運(yùn)行，流動(dòng)著不同次的操作數(shù)，流動(dòng)路徑的不同可能導(dǎo)致產(chǎn)生結(jié)果的時(shí)間不同，引發(fā)不同次操作數(shù)的混亂。 帶標(biāo)志數(shù)據(jù)令牌 對(duì)同一次調(diào)用的重入代碼中的數(shù)據(jù)令牌加相同的標(biāo)志,58,基本點(diǎn)：每個(gè)數(shù)據(jù)令牌都帶有標(biāo)號(hào)（令牌標(biāo)號(hào)及其他特征信息），從而使數(shù)據(jù)流程圖中的一條有向分支線上可同時(shí)傳送（帶不同標(biāo)號(hào)）幾個(gè)數(shù)據(jù)令牌 不需要用控制令牌來確認(rèn)指令間數(shù)據(jù)令牌的傳送。采用一個(gè)專門硬件（匹配部件）對(duì)數(shù)據(jù)令牌中的標(biāo)號(hào)進(jìn)行符合比較并加以識(shí)別。,59,動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī)模型,60,匹配部件將各個(gè)處理部件送來的結(jié)果數(shù)據(jù)令

23、牌賦予相應(yīng)的標(biāo)號(hào)，并將流向同一指令的數(shù)據(jù)令牌進(jìn)行匹配成對(duì)或成組，然后將它們送往更新讀出部件，當(dāng)一條指令所要求的數(shù)據(jù)令牌都到齊后，就立即從指令存儲(chǔ)器中取出這條指令，并把該指令與數(shù)據(jù)令牌中攜帶的操作數(shù)一起組成一個(gè)操作包形成一條可執(zhí)行指令，送入可執(zhí)行指令隊(duì)列。如果指令所要求的數(shù)據(jù)令牌沒有全部到齊（匹配失敗），則把剛剛到達(dá)的數(shù)據(jù)令牌暫時(shí)存入匹配部件的緩沖存儲(chǔ)器中，以供下次匹配時(shí)再使用。 動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī)中間結(jié)果不返回存儲(chǔ)器，減少了操作開銷，能更加充分地開發(fā)程序中的并行性,61,動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī)實(shí)例,Manchester動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī)結(jié)構(gòu),62,處理部件由15個(gè)PE組成，可執(zhí)行定點(diǎn)、浮點(diǎn)、數(shù)據(jù)轉(zhuǎn)移及打

24、標(biāo)記等指令。每個(gè)PE都有輸入緩沖器和輸出緩沖器。 88開關(guān)網(wǎng)絡(luò)可同時(shí)提供多條通路與外部交換信息。令牌隊(duì)列可存放64K個(gè)數(shù)據(jù)令牌。 匹配部件按照令牌的特征值對(duì)令牌進(jìn)行匹配，它內(nèi)部有16K97位的緩沖存儲(chǔ)器。,63,緩沖存儲(chǔ)器有8組組相聯(lián)存儲(chǔ)器組成， 采用硬件散列技術(shù)來減少相聯(lián)比較器的位數(shù)。 當(dāng)從令牌隊(duì)列中送來的數(shù)據(jù)令牌與匹配部件中已經(jīng)存在的令牌相匹配（有相應(yīng)的特征值）時(shí)，表示令牌中目標(biāo)地址字段指示的指令為可執(zhí)行指令，于是97位數(shù)據(jù)令牌和36位匹配特征值合在一起組成 133位的令牌組包送往結(jié)點(diǎn)存儲(chǔ)器。如果從令牌隊(duì)列送來的數(shù)據(jù)令牌不能與匹配部件中已經(jīng)存放的令牌相匹配時(shí)，則把新送來的令牌暫時(shí)存入匹配部

25、件的緩沖存儲(chǔ)器中。 結(jié)點(diǎn)存儲(chǔ)器按照匹配部件送來的令牌組包中給定的目標(biāo)地址取出指令，并把令牌組包中攜帶的操作數(shù)代入指令中， 形成167位的執(zhí)行包送往處理部件。,64,Manchester動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī)的指令與數(shù)據(jù)令牌格式,65,數(shù)據(jù)流計(jì)算機(jī)的優(yōu)點(diǎn),高度并行運(yùn)算。不僅能開發(fā)程序中有規(guī)則的并行性，還能開發(fā)程序中任意的并行性。從理論上講，由于沒有指令執(zhí)行順序的限制。只要硬件資源充分就能獲得最大的并行性。 流水線異步操作。 在指令中直接使用數(shù)值本身， 而不是使用存放數(shù)值的地址，從而能實(shí)現(xiàn)無副作用的純函數(shù)型程序設(shè)計(jì)方法，可以在過程級(jí)及指令級(jí)充分開發(fā)異步并行性，可以把實(shí)際串行的問題用簡(jiǎn)單的辦法展開成并行問

26、題來計(jì)算。例如，把一個(gè)循環(huán)程序的幾個(gè)相鄰循環(huán)體同時(shí)展開，把體內(nèi)、體間本來相關(guān)的操作數(shù)直接互相替代，形成一條異步流水線，使不同層次的循環(huán)體能并行執(zhí)行。,66,與VLSI技術(shù)相適應(yīng)。數(shù)據(jù)流計(jì)算機(jī)結(jié)構(gòu)具有模塊性和均勻性。指令存儲(chǔ)器、數(shù)據(jù)令牌緩沖器及可執(zhí)行指令隊(duì)列緩沖器等存儲(chǔ)部件，可以用VLSI存儲(chǔ)陣列均勻地構(gòu)成。處理部件及信息包開關(guān)網(wǎng)絡(luò)也可以分別用模塊化的標(biāo)準(zhǔn)單元有規(guī)則地連接而成。有可能研制出具有很高性能價(jià)格比的計(jì)算機(jī)系統(tǒng)。 有利于提高軟件生產(chǎn)能力。 在傳統(tǒng)語言如Fortran、Pascal等中，由于大量使用全局變量和同義名變量而產(chǎn)生副作用，給軟件的生產(chǎn)和調(diào)試帶來很多困難。而在數(shù)據(jù)流計(jì)算機(jī)中，執(zhí)行的

27、是純函數(shù)操作，使用函數(shù)程序設(shè)計(jì)語言來編程，從含義上取消了“變量”，取消了變量賦值機(jī)制。因而消除了巴科斯所說的馮諾依曼賦值操作的瓶頸口。,67,數(shù)據(jù)流計(jì)算機(jī)的缺點(diǎn),操作開銷過大 數(shù)據(jù)流計(jì)算機(jī)的每條指令都很長(zhǎng)。占用較多的存儲(chǔ)單元，存取指令過程復(fù)雜且費(fèi)時(shí)間。 數(shù)據(jù)流計(jì)算機(jī)中有大量中間結(jié)果形成的數(shù)據(jù)令牌在系統(tǒng)中流動(dòng)，使信息的流動(dòng)相當(dāng)頻繁，增加沖突。為減小沖突，要設(shè)置許多局部緩沖器，增加了開銷和通信時(shí)延。,68,數(shù)據(jù)流計(jì)算機(jī)操作開銷大的根本原因是把并行性完全放在指令級(jí)上。在一個(gè)實(shí)際的計(jì)算機(jī)系統(tǒng)中，將高一級(jí)的并行性都依賴低級(jí)的并行性來實(shí)現(xiàn)，往往要付出過高的代價(jià)。 操作開銷大的另一個(gè)原因是完全采用異步操作，

28、沒有集中控制。為解決這些異步操作和隨機(jī)調(diào)度引起的混亂，需要花費(fèi)大量的操作開銷。,69,數(shù)據(jù)流計(jì)算機(jī)指令級(jí)的異步操作使得程序調(diào)試過程十分困難。,70,(2) 不能有效利用傳統(tǒng)計(jì)算機(jī)的研究成果。 數(shù)據(jù)流計(jì)算機(jī)完全放棄了傳統(tǒng)計(jì)算機(jī)的結(jié)構(gòu)，獨(dú)樹一幟，這樣做一方面使它擺脫了傳統(tǒng)結(jié)構(gòu)的束縛，具有活躍的生命力。另一方面卻使它不能吸取傳統(tǒng)計(jì)算機(jī)已經(jīng)證明行之有效的許多研究成果。 數(shù)據(jù)流計(jì)算機(jī)提高了并行性，但并未解決如存儲(chǔ)器按模塊訪問引起的沖突、復(fù)雜昂貴的互聯(lián)網(wǎng)絡(luò)、多進(jìn)程之間的同步與通信等 問題。,71,(3) 數(shù)據(jù)流語言尚不完善 目前已經(jīng)見到的數(shù)據(jù)流語言，如VAL及ID等都不完善，輸入輸出操作因?yàn)椴皇呛瘮?shù)運(yùn)算至今未被引到數(shù)據(jù)流語言中來。 數(shù)據(jù)流語言以隱含的方式描述并行性，由編譯器開發(fā)這種并行成分，并不十分有效。 數(shù)據(jù)流程序中引入了大量隱含的并行性，使得程序的調(diào)試工作變得非常困難。,72,需要解決的幾個(gè)主要問題,合理的劃分并行性，減少開銷 多級(jí)并行（作業(yè)，進(jìn)程，函數(shù)級(jí)），一部分在編譯時(shí)完成，一部分在運(yùn)行時(shí)完成） 復(fù)合函數(shù)、過程級(jí)（循環(huán)，數(shù)組等操作）的并行（Gajks,Motooka等人） 同步與異步結(jié)合 函數(shù)級(jí)異步，指令級(jí)同步。程序如何分解并如何把程序模塊分配給各處理部件。 研制易于使用，易于由硬件實(shí)現(xiàn)的高級(jí)數(shù)據(jù)流語言。,73,設(shè)計(jì)出性能價(jià)格比高的信息包交換網(wǎng)絡(luò)，以支持