《數(shù)據(jù)流機(jī)和規(guī)約機(jī)》PPT課件.ppt

1、第八章 數(shù)據(jù)流機(jī)和規(guī)約機(jī),目錄,數(shù)據(jù)流機(jī) 基于數(shù)據(jù)驅(qū)動的，使用數(shù)據(jù)流語言 規(guī)約機(jī) 基于需求驅(qū)動的，使用函數(shù)式語言,數(shù)據(jù)流計(jì)算機(jī),數(shù)據(jù)驅(qū)動的概念 數(shù)據(jù)流程序圖和語言 數(shù)據(jù)流計(jì)算機(jī)的結(jié)構(gòu) 數(shù)據(jù)流機(jī)器存在的問題,數(shù)據(jù)驅(qū)動的概念,Von Neumann型計(jì)算機(jī)的特點(diǎn) 在程序計(jì)數(shù)器集中控制下，順序地執(zhí)行指令 以控制流（Control Flow）方式工作 可以在系統(tǒng)結(jié)構(gòu)、程序語言、編譯技術(shù)等方面改進(jìn) 很難最大限度地發(fā)掘出計(jì)算的并行性,任務(wù)描述：解方程 ax2 + bx + c = 0，解的形式為：,舉例：解一元二次方程組,Fortran程序,READ *,A,B,C X1=2*A D=SQRT(B*B-4

2、*A*C) D=D/X1 X2=-B/X1 X1=X2+D X2=X2-D PRINT *,X1,X2 END,數(shù)據(jù)流方式,數(shù)據(jù)驅(qū)動方式（Data Driven） 只要一條或一組指令所要求的操作數(shù)全部準(zhǔn)備就緒，就可立即激發(fā)相應(yīng)的指令或指令組執(zhí)行 不需要程序計(jì)數(shù)器 指令執(zhí)行是無序的，完全受數(shù)據(jù)流的驅(qū)動 只要數(shù)據(jù)不相關(guān)和資源可以利用，就可以并行,數(shù)據(jù)相互關(guān)系,求一元二次方程根的數(shù)據(jù)流 程序圖,控制驅(qū)動的控制流方式的特點(diǎn),通過訪問共享存儲單元讓數(shù)據(jù)在指令之間傳遞 指令執(zhí)行的順序隱含與控制流中，但卻可以顯示使用專門的控制操作符來實(shí)現(xiàn)并行處理 指令執(zhí)行的順序受程序計(jì)數(shù)器控制 受控制令牌所支配,數(shù)據(jù)驅(qū)動的

3、數(shù)據(jù)流方式,只要一條或一組指令所要求的操作數(shù)全部準(zhǔn)備就緒，就可立即激發(fā)相應(yīng)的指令或指令組執(zhí)行 執(zhí)行結(jié)果的輸出將送往等待這一數(shù)據(jù)的下一條或下一組指令 不需要程序計(jì)數(shù)器 指令的執(zhí)行基本上是無序的，完全受數(shù)據(jù)流的驅(qū)動，與指令在程序中出現(xiàn)的先后次序無關(guān) 程序設(shè)計(jì)者完全擺脫了檢查和定義程序中所有可能存在的并行性這一繁重工作，只要數(shù)據(jù)不相關(guān)且資源可以利用，就可以并行,數(shù)據(jù)驅(qū)動的數(shù)據(jù)流方式特點(diǎn),沒有共享變量的概念，即沒有共享存儲數(shù)據(jù)的概念 指令執(zhí)行順序只受指令中數(shù)據(jù)相關(guān)性的制約 數(shù)據(jù)是以數(shù)據(jù)令牌方式直接在指令之間傳遞 數(shù)據(jù)令牌：是一種表示操作數(shù)或參數(shù)已準(zhǔn)備就緒的標(biāo)志,數(shù)據(jù)流計(jì)算模型,數(shù)據(jù)驅(qū)動計(jì)算 是按輸入數(shù)

4、據(jù)可用性決定的次序進(jìn)行 所要求的輸入數(shù)據(jù)全部就緒，即可驅(qū)動操作執(zhí)行 提前求值策略 需求驅(qū)動計(jì)算 是按數(shù)據(jù)需求決定的次序進(jìn)行 按需求值，只有當(dāng)某一函數(shù)需要用到某一自變量時，才驅(qū)動對該變量的求值操作 滯后求值策略 減少不必要的求值，輔助開銷少，有利于提高系統(tǒng)的效率,數(shù)據(jù)流的語義,異步性（Asynchriny）：指一旦操作數(shù)到齊就開始操作 函數(shù)性（Functionality）：指每一數(shù)據(jù)流操作都是消耗一組輸入值，產(chǎn)生一組輸出值而不發(fā)生副作用（Side Effect），具有變量出現(xiàn)在賦值語句左邊僅一次的單賦值特性，從而保證任何兩個并發(fā)操作可以按任意次序執(zhí)行，而不會發(fā)生相互干擾,數(shù)據(jù)流程序,用有向圖表示

5、指令級的數(shù)據(jù)流程序，數(shù)據(jù)流機(jī)器的機(jī)器語言 有多個結(jié)點(diǎn)（Node），并用一些?。ˋrc）把它們連接而成 每一結(jié)點(diǎn)用圓圈或三角形或其他特殊符號表示，處理部件 結(jié)點(diǎn)內(nèi)的符號或字母表示一種操作，操作符（Actor）,舉例：計(jì)算z=(a+b)*(a-b),數(shù)據(jù)流程序的執(zhí)行過程,常數(shù)產(chǎn)生的結(jié)點(diǎn)（Identity）,沒有輸入端，只產(chǎn)生常數(shù)，激發(fā)后輸出帶常數(shù)的令牌,算邏運(yùn)算操作結(jié)點(diǎn)（Operator）,主要包括常用的+、-、*、/、開方等算術(shù)運(yùn)算及非、與、或、異或、或非等布爾邏輯運(yùn)算，激發(fā)后輸出帶相應(yīng)操作結(jié)果的令牌,復(fù)制操作結(jié)點(diǎn)（Copy）,a,激發(fā)后,a,a,a,是數(shù)據(jù)的多個復(fù)制，也可以是控制量的多個復(fù)制,

6、復(fù)制操作結(jié)點(diǎn)（Copy）,判定操作結(jié)點(diǎn)（Decider）,對輸入數(shù)據(jù)按某種關(guān)系進(jìn)行判斷和比較，激發(fā)后再輸出控制端給出帶邏輯值真或假的控制令牌,控制類操作結(jié)點(diǎn),T,a,T,T,a,激發(fā)后,T門控結(jié)點(diǎn),F,a,F,F,a,激發(fā)后,F門控結(jié)點(diǎn),SW T F,T,SW T F,a,a,激發(fā)后,SW T F,F,SW T F,a,a,激發(fā)后,開關(guān)門控結(jié)點(diǎn),T F MG,T,a,激發(fā)后,T F MG,a,T F MG,T,a,激發(fā)后,T F MG,a,歸并門控結(jié)點(diǎn),舉例1：具有條件分支結(jié)構(gòu)的數(shù)據(jù)流程序,If x0 z=x+y Else z=x-y,舉例2：具有循環(huán)結(jié)構(gòu)的數(shù)據(jù)流程序,實(shí)現(xiàn)對x循環(huán)累加，直到x

7、值超過1000為止，結(jié)果為z,活動模片表示法,Activity Templete 數(shù)據(jù)流看成是一組活動模片組成的集合體 每一個活動模片相應(yīng)于數(shù)據(jù)流程序圖中一個或多個操作結(jié)點(diǎn)，且由4個域組成，1個操作域，2個操作數(shù)域和1個目的域。,舉例1：計(jì)算z=(a+b)*(a-b),舉例2：,If x0 z=x+y Else z=x-y,活動模片就是結(jié)點(diǎn)在數(shù)據(jù)流機(jī)器內(nèi)部具體實(shí)現(xiàn)時的存儲映像，認(rèn)為是數(shù)據(jù)流機(jī)的可執(zhí)行的機(jī)器代碼程序，有硬件直接解釋執(zhí)行 數(shù)據(jù)流機(jī)操作系統(tǒng)中的分派程序（Allocator），就是根據(jù)活動模片數(shù)據(jù)流程序圖來調(diào)度各個活動模片，分配給多個處理器并行執(zhí)行 數(shù)據(jù)流程序圖實(shí)際上是數(shù)據(jù)流機(jī)的機(jī)器語

8、言，直觀易懂，但編程效率很低，難以接受,單賦值語言,在程序中，每個量均只賦值一次，即同一個量名在不同賦值語句的左部最多只出現(xiàn)一次。 美國的ID(Irvine Data Flow)語言、VAL(Value Oriented Algorithm Language)語言、法國的LAU語言，英國曼徹斯特大學(xué)的SISAL語言等,C=A+B C=C*D F=(C-D)/E,C=A+B C1=C*D F=(C-D)/E,單賦值語言的特點(diǎn),遵循單賦值規(guī)則 有豐富的數(shù)據(jù)類型 具有很好的類型性 具有模塊化結(jié)構(gòu)的程序設(shè)計(jì)思想 沒有全局存儲器和狀態(tài)的概念 程序中不規(guī)定語句的執(zhí)行順序,數(shù)據(jù)流計(jì)算機(jī)的結(jié)構(gòu),靜態(tài)數(shù)據(jù)流機(jī)：

9、數(shù)據(jù)令牌沒有標(biāo)號，不支持遞歸的并發(fā)激活 MIT的J. B. Dennis提出的MIT靜態(tài)數(shù)據(jù)流機(jī) 動態(tài)數(shù)據(jù)流機(jī)：令牌有標(biāo)記 Arvind研制的Irvine數(shù)據(jù)流機(jī)的改進(jìn)機(jī) 英國曼徹斯特大學(xué)的Manchester數(shù)據(jù)流機(jī),數(shù)據(jù)流機(jī)器存在的問題,目的是為了提高操作級并行的開發(fā)水平，如果項(xiàng)目本身數(shù)據(jù)相關(guān)性很強(qiáng)，內(nèi)涵并行性成分不多時，效率低 在數(shù)據(jù)流機(jī)器中為給數(shù)據(jù)建立、識別、處理標(biāo)記需要花費(fèi)較多的開銷和空間，如果不標(biāo)記，則降低并行能力 不保存數(shù)組，對標(biāo)量運(yùn)算有利，而對數(shù)組、遞歸及其他高級操作難以管理 變量代表數(shù)值而不是存儲單元位置，無法控制存儲分配，增大編譯難度 互聯(lián)網(wǎng)絡(luò)設(shè)計(jì)困難，輸入/輸出系統(tǒng)不夠完

10、善 沒有程序計(jì)數(shù)器，給診斷和維護(hù)帶來困難,數(shù)據(jù)流計(jì)算機(jī)的發(fā)展,采用提高并行度等級的數(shù)據(jù)流機(jī) 采用同步、異步結(jié)合的數(shù)據(jù)流機(jī) 采用控制流和數(shù)據(jù)流相結(jié)合的數(shù)據(jù)流機(jī),規(guī)約機(jī),與數(shù)據(jù)流機(jī)一樣，基于數(shù)據(jù)流的計(jì)算模型 需求驅(qū)動，執(zhí)行的操作序列取決于對數(shù)據(jù)的需求，對數(shù)據(jù)的需求又來源于函數(shù)式程序設(shè)計(jì)語言對表達(dá)式的規(guī)約（Reduction）,規(guī)約機(jī)的結(jié)構(gòu)特點(diǎn),面向函數(shù)式語言，或以函數(shù)式語言為機(jī)器語言的非Von Neumann型機(jī)器，其內(nèi)部結(jié)構(gòu)不同于Von Neumann型機(jī)器 具有大容量物理存儲器并采用大圩村容量的虛擬存儲器，具備高效的動態(tài)存儲分配和管理的軟、硬件支持，滿足規(guī)約機(jī)對動態(tài)存儲分配及所需存儲空間大的要求 處理部分應(yīng)當(dāng)是一種有多個處理器或多處理機(jī)并行的結(jié)構(gòu)形式，以發(fā)揮函數(shù)式結(jié)構(gòu)并行處理的特長 采用適合于函數(shù)式程序運(yùn)行的多處理器（機(jī)）互聯(lián)的結(jié)構(gòu)，最好采用樹形方式的