《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第二版尹朝慶主編第7章數(shù)據(jù)流計(jì)算機(jī)》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第二版尹朝慶主編第7章數(shù)據(jù)流計(jì)算機(jī)（52頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、1第第7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)7.1 數(shù)據(jù)流計(jì)算機(jī)的基本原理數(shù)據(jù)流計(jì)算機(jī)的基本原理 7.2 數(shù)據(jù)流程序圖和數(shù)據(jù)流語(yǔ)言數(shù)據(jù)流程序圖和數(shù)據(jù)流語(yǔ)言7.3 數(shù)據(jù)流計(jì)算機(jī)結(jié)構(gòu)數(shù)據(jù)流計(jì)算機(jī)結(jié)構(gòu)7.4 數(shù)據(jù)流計(jì)算機(jī)的性能評(píng)價(jià)及發(fā)展趨勢(shì)數(shù)據(jù)流計(jì)算機(jī)的性能評(píng)價(jià)及發(fā)展趨勢(shì)第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)2傳統(tǒng)的馮諾依曼(Von Neumann) 型計(jì)算機(jī)采用的是指令驅(qū)動(dòng)方式，即在程序計(jì)數(shù)器的集中控制下順序地執(zhí)行指令以實(shí)現(xiàn)各種功能，因此屬于控制流計(jì)算機(jī)。由于機(jī)器本質(zhì)上的串行順序處理工作機(jī)制，使其并行性的提高受到限制。為了設(shè)計(jì)高性能計(jì)算機(jī)的系統(tǒng)結(jié)構(gòu)，其方法之一是突破馮諾依曼型計(jì)算機(jī)的結(jié)構(gòu)，采用數(shù)據(jù)驅(qū)動(dòng)
2、方式形成數(shù)據(jù)流計(jì)算機(jī)，從而實(shí)現(xiàn)大規(guī)模的并行處理。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)37.1 數(shù)據(jù)流計(jì)算機(jī)的基本原理數(shù)據(jù)流計(jì)算機(jī)的基本原理7.1.1數(shù)據(jù)流計(jì)算機(jī)的驅(qū)動(dòng)方式數(shù)據(jù)流計(jì)算機(jī)的驅(qū)動(dòng)方式 數(shù)據(jù)流計(jì)算機(jī)是以數(shù)據(jù)驅(qū)動(dòng)機(jī)制為基礎(chǔ)，在數(shù)據(jù)可用性控制下并行執(zhí)行指令。所謂數(shù)據(jù)驅(qū)動(dòng)的數(shù)據(jù)流方式，指的是任何指令只要它所需要的數(shù)據(jù)準(zhǔn)備就緒，這些指令就可并行地執(zhí)行。執(zhí)行的結(jié)果并不送往存儲(chǔ)器保存起來(lái)，以供其他指令共享，而是直接流向所有需要該結(jié)果的指令，并作為這些指令的操作數(shù)，驅(qū)動(dòng)這些指令的執(zhí)行。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)4數(shù)據(jù)以數(shù)據(jù)令牌方式直接在指令之間傳遞。所謂數(shù)據(jù)令牌，是一種表示某一操作
3、數(shù)或參數(shù)已準(zhǔn)備就緒的標(biāo)志。由于操作結(jié)果不改變機(jī)器狀態(tài)，從而具有純函數(shù)的特點(diǎn)。這種機(jī)器需要有專(zhuān)門(mén)的機(jī)構(gòu)來(lái)檢測(cè)數(shù)據(jù)可用性，將數(shù)據(jù)令牌和缺乏數(shù)據(jù)的指令進(jìn)行匹配，同時(shí)使指令執(zhí)行的異步鏈接作用得以實(shí)現(xiàn)。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)5對(duì)于表達(dá)式a(b2)(bc)串行控制驅(qū)動(dòng)方式的處理過(guò)程如圖7.1所示。操作按事先指定的指令執(zhí)行序列順序進(jìn)行，主要受PC控制。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)6圖7.2所示為并行控制驅(qū)動(dòng)方式的處理過(guò)程。使用FORK語(yǔ)句結(jié)構(gòu)派生出并行任務(wù)，使i1和i2 兩者并行執(zhí)行，然后用JOIN語(yǔ)句結(jié)構(gòu)對(duì)它們進(jìn)行同步。對(duì)存儲(chǔ)器中的數(shù)據(jù)訪(fǎng)問(wèn)與圖7.1中相同。 第第7 7章章
4、數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)7在數(shù)據(jù)驅(qū)動(dòng)方式中，操作按數(shù)據(jù)相關(guān)和資源可用性所確定的序列來(lái)進(jìn)行。當(dāng)一條指令所需的操作數(shù)(數(shù)據(jù)令牌)全部到達(dá)，且有可用的計(jì)算資源時(shí)，便可進(jìn)行計(jì)算，過(guò)程如圖7.3所示。 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)8數(shù)據(jù)流計(jì)算機(jī)還有另一種以需求驅(qū)動(dòng)機(jī)制為基礎(chǔ)的歸約計(jì)算機(jī)。它的操作是由對(duì)一個(gè)操作結(jié)果的需求而啟動(dòng)的。即當(dāng)一些計(jì)算需要用到一種操作的結(jié)果時(shí)，歸約機(jī)制就啟動(dòng)這種操作。 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)9數(shù)據(jù)驅(qū)動(dòng)具有以下特性。1.異步性(Asynchrony)。2.并行性(Parallelism)。3.函數(shù)性(Functionalism)。4.局部性(Locali
5、ty)。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)107.1.2 數(shù)據(jù)流計(jì)算機(jī)的指令結(jié)構(gòu)數(shù)據(jù)流計(jì)算機(jī)的指令結(jié)構(gòu)數(shù)據(jù)流計(jì)算機(jī)的指令結(jié)構(gòu)如圖7.4所示 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)11數(shù)據(jù)流計(jì)算機(jī)不需要像傳統(tǒng)計(jì)算機(jī)那樣用程序計(jì)數(shù)器控制指令的執(zhí)行順序，也不需要通過(guò)訪(fǎng)問(wèn)共享存儲(chǔ)器來(lái)實(shí)現(xiàn)指令之間的數(shù)據(jù)傳送。它通過(guò)在需要數(shù)據(jù)的指令之間傳送數(shù)據(jù)令牌來(lái)實(shí)現(xiàn)指令之間傳送數(shù)據(jù)和激活指令執(zhí)行，程序的執(zhí)行過(guò)程主要受到指令之間數(shù)據(jù)相關(guān)性的限制。另外，數(shù)據(jù)流計(jì)算機(jī)允許多個(gè)操作包和多個(gè)數(shù)據(jù)令牌同時(shí)在各個(gè)操作部件之間傳送，允許多條指令并行執(zhí)行。為此，數(shù)據(jù)流計(jì)算機(jī)需要有一套能夠并行執(zhí)行多條指令的操作部件和高效的操作包
6、與數(shù)據(jù)令牌的傳送機(jī)構(gòu)。 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)127.2 數(shù)據(jù)流程序圖和數(shù)據(jù)流語(yǔ)言數(shù)據(jù)流程序圖和數(shù)據(jù)流語(yǔ)言7.2.1 數(shù)據(jù)流程序圖數(shù)據(jù)流程序圖數(shù)據(jù)流程序圖是一種用來(lái)表示數(shù)據(jù)流計(jì)算機(jī)指令級(jí)的數(shù)據(jù)流程序的有向圖，它是由多個(gè)結(jié)點(diǎn)和一些連接這些結(jié)點(diǎn)的單向弧線(xiàn)組成。數(shù)據(jù)流程序圖中的每個(gè)結(jié)點(diǎn)是一個(gè)用圓圈 、三角形或其他圖形表示的處理部件。結(jié)點(diǎn)內(nèi)的符號(hào)或字母表示某種操作，故稱(chēng)為操作符。單向弧線(xiàn)表示數(shù)據(jù)令牌在結(jié)點(diǎn)間的流向。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)131. 數(shù)據(jù)流程序圖的操作結(jié)點(diǎn)（1）常數(shù)產(chǎn)生結(jié)點(diǎn)如圖7.5(a)所示，它沒(méi)有輸入端，只有一個(gè)輸出端，其功能是產(chǎn)生常數(shù)。結(jié)點(diǎn)操作激發(fā)
7、執(zhí)行后輸出攜帶指定常數(shù)的數(shù)據(jù)令牌。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)14（2）復(fù)制操作結(jié)點(diǎn)如圖7.5(b)所示，復(fù)制結(jié)點(diǎn)分為兩種，一種是數(shù)據(jù)復(fù)制結(jié)點(diǎn)，實(shí)現(xiàn)數(shù)據(jù)的多個(gè)復(fù)制，數(shù)據(jù)端以實(shí)箭頭表示；另一種是控制復(fù)制結(jié)點(diǎn)，實(shí)現(xiàn)控制量的多個(gè)復(fù)制，控制端以空心箭頭表示。復(fù)制操作結(jié)點(diǎn)有時(shí)也稱(chēng)連接操作結(jié)點(diǎn)，圖7.5(c)所示分別為數(shù)據(jù)連接結(jié)點(diǎn)和控制連接結(jié)點(diǎn)以及激發(fā)執(zhí)行的結(jié)果。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)15（3）運(yùn)算操作結(jié)點(diǎn)運(yùn)算操作結(jié)點(diǎn)用圓圈表示，圈中有相應(yīng)的操作符。主要的運(yùn)算操作包括加、減、乘、除、加1、減1、乘方、開(kāi)方等算術(shù)運(yùn)算以及與、或、非、異或、或非等布爾邏輯運(yùn)算。激發(fā)執(zhí)行后輸出帶有相
8、應(yīng)操作結(jié)果的令牌。 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)16（4）判斷操作結(jié)點(diǎn)如圖7.5(d)所示，判斷操作結(jié)點(diǎn)用一個(gè)菱形表示，它有若干個(gè)數(shù)據(jù)輸入端和一個(gè)控制輸出端。結(jié)點(diǎn)對(duì)輸入數(shù)據(jù)按某種關(guān)系進(jìn)行判斷和比較，如果條件滿(mǎn)足，將在輸出端產(chǎn)生T(Ture)的控制令牌，否則便產(chǎn)生F(False)的控制令牌。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)17（5）控制操作結(jié)點(diǎn)控制操作結(jié)點(diǎn)的激發(fā)條件需要加入布爾控制端，用來(lái)控制數(shù)據(jù)令牌的傳送時(shí)刻?？刂撇僮鹘Y(jié)點(diǎn)有四種，如圖7.6所示。lT門(mén)結(jié)點(diǎn)：僅當(dāng)布爾控制端為真，且輸入端有數(shù)據(jù)令牌時(shí)才能激發(fā)執(zhí)行，執(zhí)行結(jié)果是將輸入端的數(shù)據(jù)令牌傳送到輸出端。lF門(mén)結(jié)點(diǎn)：僅當(dāng)布爾控
9、制端為假，且輸入端有數(shù)據(jù)令牌時(shí)才能激發(fā)執(zhí)行，執(zhí)行結(jié)果仍是將輸入端的數(shù)據(jù)令牌傳送到輸出端。l開(kāi)關(guān)門(mén)控結(jié)點(diǎn)(SW結(jié)點(diǎn))：開(kāi)關(guān)門(mén)控結(jié)點(diǎn)用一個(gè)橢圓形表示，它有一個(gè)數(shù)據(jù)輸入端和兩個(gè)數(shù)據(jù)輸出端，并受控制端控制。激發(fā)執(zhí)行的結(jié)果是根據(jù)控制端值的真假，確定T輸出端或F輸出端帶有輸入端的數(shù)據(jù)令牌。l歸并門(mén)控結(jié)點(diǎn)(MG結(jié)點(diǎn))：歸并門(mén)控結(jié)點(diǎn)也用一個(gè)橢圓形表示，它有兩個(gè)數(shù)據(jù)輸入端和一個(gè)數(shù)據(jù)輸出端，并受控制端控制。激發(fā)執(zhí)行的結(jié)果是根據(jù)控制端值的真假，在輸出端上產(chǎn)生來(lái)自T輸入端或F輸入端的數(shù)據(jù)令牌。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)18圖7.6 控制操作結(jié)點(diǎn)第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)192. 數(shù)據(jù)流程序
10、圖的活動(dòng)模片表示法 活動(dòng)模片表示法是數(shù)據(jù)流程序圖的另一種更接近于機(jī)器語(yǔ)言，也更容易理解機(jī)器的工作原理的表示方法。此方法將數(shù)據(jù)流程序圖中一個(gè)或多個(gè)操作結(jié)點(diǎn)與一個(gè)活動(dòng)模片相對(duì)應(yīng)，數(shù)據(jù)流程序可以看成是一組活動(dòng)模片的集合體。每一個(gè)活動(dòng)模片由4個(gè)域組成，包括一個(gè)操作碼域，兩個(gè)操作數(shù)域和一個(gè)目的域，其結(jié)構(gòu)如圖7.7所示。 活動(dòng)模片實(shí)際上是結(jié)點(diǎn)在數(shù)據(jù)流機(jī)器內(nèi)部具體實(shí)現(xiàn)時(shí)的存儲(chǔ)器映像。可以將活動(dòng)模片表示的數(shù)據(jù)流程序圖作為數(shù)據(jù)流機(jī)的可執(zhí)行機(jī)器代碼程序，能夠由數(shù)據(jù)流機(jī)硬件直接解釋執(zhí)行。數(shù)據(jù)流機(jī)操作系統(tǒng)中的分派程序可根據(jù)活動(dòng)模片數(shù)據(jù)流程圖來(lái)調(diào)度各個(gè)活動(dòng)模片，分配給多個(gè)處理器并行執(zhí)行。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)
11、流計(jì)算機(jī)203. 數(shù)據(jù)流程序圖舉例例7.1用數(shù)據(jù)流程序圖和等效的活動(dòng)模片表示如下功能(具有順序結(jié)構(gòu))：z(ab)(ab)解：數(shù)據(jù)流程序圖如圖7.8(a)所示 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)21z(ab)(ab) 等效的活動(dòng)模片表示如圖7.8(b)所示。 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)22 例7.2用數(shù)據(jù)流程序圖描述功能(具有條件分支結(jié)構(gòu))：當(dāng)x0時(shí)，zxy；否則 zxy。解：數(shù)據(jù)流程序圖如圖7.9(a)所示。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)23 當(dāng)x0時(shí)，zxy；否則zxy。等效的活動(dòng)模片表示如圖7.9(b)所示。 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)24 例7
12、.3用數(shù)據(jù)流程序圖描述功能（具有循環(huán)結(jié)構(gòu)）：對(duì)x進(jìn)行循環(huán)累加，直至超過(guò)1000時(shí)，z等于x的累加值。解：數(shù)據(jù)流程序圖如圖7.10所示。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)25例7.4畫(huà)出求一元二次方程兩個(gè)實(shí)數(shù)根的數(shù)據(jù)流程序圖，基本的運(yùn)算結(jié)點(diǎn)有、*、和。指出哪些基本運(yùn)算操作可以并行執(zhí)行？如果每個(gè)操作結(jié)點(diǎn)的執(zhí)行時(shí)間均為一個(gè)時(shí)鐘周期，則整個(gè)計(jì)算過(guò)程總共需要多少個(gè)時(shí)鐘周期？解：可并行執(zhí)行的基本運(yùn)算操作如圖7.11所示，其中與、與、與均可并行工作，但相互之間因?yàn)榇嬖跀?shù)據(jù)相關(guān)而不能并行。 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)26 求一元二次方程根的數(shù)據(jù)流程序圖如圖7.12所示，如果每個(gè)操作結(jié)點(diǎn)的執(zhí)
13、行時(shí)間均為一個(gè)時(shí)鐘周期，則整個(gè)計(jì)算過(guò)程總共需要8個(gè)時(shí)鐘周期。 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)277.2.2 數(shù)據(jù)流語(yǔ)言數(shù)據(jù)流語(yǔ)言數(shù)據(jù)流程序圖作為數(shù)據(jù)流機(jī)器語(yǔ)言，雖然直觀易懂，但編程效率低，故需要研究適合于數(shù)據(jù)流機(jī)使用的高級(jí)語(yǔ)言。 發(fā)展新型、適合于數(shù)據(jù)流控制機(jī)制的高級(jí)語(yǔ)言一直是數(shù)據(jù)流計(jì)算機(jī)研究的重要內(nèi)容。希望新的數(shù)據(jù)流語(yǔ)言能自然而充分地表達(dá)出計(jì)算并行性，編程方便、高效。目前這方面的研究還不成熟，沒(méi)有形成像傳統(tǒng)高級(jí)語(yǔ)言那樣的完整性和規(guī)范性。 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)281. 數(shù)據(jù)流語(yǔ)言的類(lèi)型（1）單賦值語(yǔ)言(Single Assignment Language)（2）函數(shù)
14、類(lèi)語(yǔ)言(Functional Language)（3）命令類(lèi)語(yǔ)言(Command Language) 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)292. 數(shù)據(jù)流語(yǔ)言的特點(diǎn) 傳統(tǒng)的程序設(shè)計(jì)語(yǔ)言是建立在馮諾依曼系統(tǒng)結(jié)構(gòu)上的，這種控制流語(yǔ)言不能充分表達(dá)程序中的并行性。數(shù)據(jù)流語(yǔ)言與傳統(tǒng)程序設(shè)計(jì)語(yǔ)言相比具有以下特點(diǎn)。 （1）并行性好 程序不規(guī)定語(yǔ)句的執(zhí)行順序，語(yǔ)句的執(zhí)行順序也不會(huì)影響計(jì)算的最終結(jié)果。程序的執(zhí)行過(guò)程僅受指令之間數(shù)據(jù)相關(guān)性的約束，而與指令的存儲(chǔ)位置無(wú)關(guān)。因此，數(shù)據(jù)流語(yǔ)言能夠以很自然的方式最大限度地表達(dá)程序中的并行性。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)30 （2）單賦值規(guī)則所謂單賦值規(guī)則，
15、是指在程序中每個(gè)變量只能賦值一次，即在所有語(yǔ)句的左邊，同一個(gè)變量名只能出現(xiàn)一次。單賦值語(yǔ)言沒(méi)有傳統(tǒng)計(jì)算機(jī)語(yǔ)言中的變量的概念，只是一種值名。單賦值規(guī)則使程序中的語(yǔ)句語(yǔ)義清楚，且程序中的并行性易于被編譯程序識(shí)別和開(kāi)發(fā)。 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)31 （3）不產(chǎn)生副作用 在傳統(tǒng)的程序設(shè)計(jì)語(yǔ)言中，允許使用全局變量或公共變量，使變量的使用范圍擴(kuò)大。任何一個(gè)過(guò)程在執(zhí)行中都可以對(duì)全局變量賦值，打破了操作結(jié)果的局部性；程序執(zhí)行時(shí)還可能出現(xiàn)對(duì)同名變量多處賦值；調(diào)用子程序時(shí)修改了調(diào)用程序中的變量等情況。這將導(dǎo)致產(chǎn)生一個(gè)程序執(zhí)行后由于改變了公共變量，從而影響其他程序的正確執(zhí)行的副作用。 在數(shù)據(jù)流語(yǔ)言
16、中，不使用全局變量和公共變量，嚴(yán)格控制變量的使用范圍。數(shù)據(jù)傳送采用數(shù)據(jù)令牌直接在指令之間進(jìn)行，使每一個(gè)操作產(chǎn)生的結(jié)果都具有局部性。另外，采用賦值調(diào)用而不是傳統(tǒng)語(yǔ)言中的引用調(diào)用，而賦值調(diào)用過(guò)程只復(fù)制變量而不修改變量。因此，在子程序中決不會(huì)修改調(diào)用程序傳送來(lái)的變量。也就是說(shuō)，數(shù)據(jù)流語(yǔ)言的各程序模塊之間的I/O是完全隔離的，可以避免產(chǎn)生不必要的副作用。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)327.3 數(shù)據(jù)流計(jì)算機(jī)結(jié)構(gòu)數(shù)據(jù)流計(jì)算機(jī)結(jié)構(gòu) 7.3.1靜態(tài)數(shù)據(jù)流計(jì)算機(jī)靜態(tài)數(shù)據(jù)流計(jì)算機(jī)靜態(tài)數(shù)據(jù)流計(jì)算機(jī)結(jié)構(gòu)模型如圖7.13所示。 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)33靜態(tài)數(shù)據(jù)流計(jì)算機(jī)中的數(shù)據(jù)令牌是按反映
17、程序要求的數(shù)據(jù)流程序圖來(lái)流動(dòng)的。靜態(tài)數(shù)據(jù)流計(jì)算機(jī)的主要特點(diǎn)是數(shù)據(jù)令牌不帶任何標(biāo)記，在數(shù)據(jù)流程序圖的任何一條弧上只允許存在一個(gè)數(shù)據(jù)令牌。 MIT靜態(tài)數(shù)據(jù)流計(jì)算機(jī)結(jié)構(gòu)框圖如圖7.14所示。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)34圖圖7.14 MIT靜態(tài)數(shù)據(jù)流計(jì)算機(jī)結(jié)構(gòu)框圖靜態(tài)數(shù)據(jù)流計(jì)算機(jī)結(jié)構(gòu)框圖第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)35系統(tǒng)主要由五個(gè)部分組成：l存儲(chǔ)部件(MS)由若于指令單元組成。每個(gè)指令單元保存數(shù)據(jù)流程序中的一條指令，它與數(shù)據(jù)流程序圖中的結(jié)點(diǎn)對(duì)應(yīng)且由惟一的地址所指明。l處理部件(PS)由對(duì)數(shù)據(jù)值進(jìn)行基本運(yùn)算的多個(gè)處理單元(PU)組成，可以并發(fā)執(zhí)行已被激活的指令所要求的操作。
18、l仲裁網(wǎng)絡(luò)(AN)將可執(zhí)行的操作包由存儲(chǔ)部件發(fā)送到處理部件，允許有多個(gè)操作包同時(shí)在多個(gè)通路上傳輸。l控制網(wǎng)絡(luò)(CN)將控制令牌由處理部件發(fā)送到存儲(chǔ)部件相應(yīng)的指令單元中。l分配網(wǎng)絡(luò)(DN)將處理部件產(chǎn)生的多個(gè)結(jié)果數(shù)據(jù)令牌依其各自的目的地址分別傳送至存儲(chǔ)部件相應(yīng)的指令單元。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)367.3.2 動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī)動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī) 動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī)中的每個(gè)數(shù)據(jù)令牌都帶有標(biāo)記，從而可以使數(shù)據(jù)流程序圖中的任一條弧上同時(shí)出現(xiàn)多個(gè)帶不同標(biāo)記的令牌。因令牌的標(biāo)記中包含能識(shí)別該令牌時(shí)間先后相應(yīng)關(guān)系的標(biāo)號(hào)，故無(wú)需像靜態(tài)數(shù)據(jù)流機(jī)中那樣依賴(lài)控制令牌來(lái)確認(rèn)指令間數(shù)據(jù)令牌的傳送。動(dòng)態(tài)數(shù)據(jù)流
19、計(jì)算機(jī)的同步是由匹配部件實(shí)現(xiàn)的，它將標(biāo)記附加到數(shù)據(jù)令牌上，并對(duì)數(shù)據(jù)令牌中的標(biāo)記進(jìn)行符合比較，完成標(biāo)記的匹配工作。典型的動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī)的基本結(jié)構(gòu)如圖7.15所示。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)37圖7.15 典型的動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī)的基本結(jié)構(gòu)第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)381. 網(wǎng)絡(luò)型結(jié)構(gòu)動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī)MIT動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī)是網(wǎng)絡(luò)型的典型代表，其基本結(jié)構(gòu)如圖7.16所示。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)39 MIT動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī)由N個(gè)處理單元(PE)和一個(gè)用于實(shí)現(xiàn)PE間通信的NN的包交換開(kāi)關(guān)網(wǎng)絡(luò)組成。每個(gè)PE基本上是一臺(tái)完整的處理機(jī)，它包括有自己的程序/數(shù)據(jù)存儲(chǔ)
20、器、I結(jié)構(gòu)存儲(chǔ)器、標(biāo)記匹配部件、算術(shù)邏輯部件、打標(biāo)記和對(duì)標(biāo)記特征控制的部件及其他硬件。NN的包交換開(kāi)關(guān)網(wǎng)絡(luò)為令牌提供從發(fā)出它的PEi到吸收它的PEj的通路。如果吸收令牌的PE就是發(fā)出此令牌的PE，則不經(jīng)開(kāi)關(guān)網(wǎng)絡(luò)傳送。 MIT動(dòng)態(tài)數(shù)據(jù)流機(jī)指令的一般格式如圖7.17所示。 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)40PE的內(nèi)部結(jié)構(gòu)如圖7.18所示。 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)412. 環(huán)型結(jié)構(gòu)動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī) Manchester動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī)是環(huán)形結(jié)構(gòu)的典型代表，其結(jié)構(gòu)如圖7.19所示 。它的5個(gè)功能部件形成一個(gè)環(huán)狀流水線(xiàn)，采用令牌包通信。這種結(jié)構(gòu)允許多個(gè)令牌以先進(jìn)先出的隊(duì)列形式
21、同時(shí)存在于數(shù)據(jù)流程序圖的一個(gè)弧上，故屬于動(dòng)態(tài)數(shù)據(jù)流機(jī)。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)427.4 數(shù)據(jù)流計(jì)算機(jī)的性能評(píng)價(jià)及發(fā)展趨勢(shì)數(shù)據(jù)流計(jì)算機(jī)的性能評(píng)價(jià)及發(fā)展趨勢(shì) 7.4.1數(shù)據(jù)流計(jì)算機(jī)的優(yōu)點(diǎn)數(shù)據(jù)流計(jì)算機(jī)的優(yōu)點(diǎn)1. 高度的操作并行性 由于數(shù)據(jù)驅(qū)動(dòng)方法沒(méi)有指令執(zhí)行順序的限制，從理論上講，只要有充分的硬件資源，就能獲得最大的并行性。已經(jīng)得到驗(yàn)證，數(shù)據(jù)流計(jì)算機(jī)在處理許多應(yīng)用問(wèn)題時(shí)的加速比隨使用處理機(jī)數(shù)目的增加而線(xiàn)性地增長(zhǎng)。 數(shù)據(jù)流計(jì)算機(jī)顯示了操作的高度并行性，它不僅可用來(lái)開(kāi)發(fā)程序中有規(guī)則的并行性，而且也能夠開(kāi)發(fā)程序中隱含的并行性。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)432. 便于開(kāi)發(fā)過(guò)程
22、和指令級(jí)的異步并行 數(shù)據(jù)流計(jì)算機(jī)的指令直接使用操作數(shù)，而不是使用存放操作數(shù)的地址，因此能實(shí)現(xiàn)無(wú)副作用的純函數(shù)型程序設(shè)計(jì)方法。便于在過(guò)程級(jí)和指令級(jí)充分開(kāi)發(fā)程序中的異步并行性，可以把串行計(jì)算的問(wèn)題用簡(jiǎn)單的方法展開(kāi)成并行計(jì)算問(wèn)題進(jìn)行并行處理。如通過(guò)同時(shí)展開(kāi)一個(gè)循環(huán)程序中的多個(gè)相鄰循環(huán)體，將循環(huán)體內(nèi)和循環(huán)體間本來(lái)相關(guān)的操作數(shù)直接互相迭代而形成一條異步流水線(xiàn)，從而使一個(gè)循環(huán)程序內(nèi)的不同層次的循環(huán)體能夠并行執(zhí)行。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)443. 機(jī)器結(jié)構(gòu)與VLSI技術(shù)發(fā)展相適應(yīng)數(shù)據(jù)流計(jì)算機(jī)結(jié)構(gòu)的基本組成具有模塊性和均勻性，與VLSI技術(shù)相適應(yīng)。其指令存儲(chǔ)器、數(shù)據(jù)令牌緩沖器和可執(zhí)行指令隊(duì)列緩
23、沖器等存儲(chǔ)部件均可采用VLSI技術(shù)制造的存儲(chǔ)陣列均勻地構(gòu)成，處理部件和信息包開(kāi)關(guān)網(wǎng)絡(luò)也可用模塊化的標(biāo)準(zhǔn)單元有規(guī)則地連接實(shí)現(xiàn)。VLSI技術(shù)的進(jìn)一步發(fā)展，必然為研制高性能價(jià)格比的數(shù)據(jù)流計(jì)算機(jī)提供更好的支持。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)454. 有利于提高程序設(shè)計(jì)效率 在數(shù)據(jù)流計(jì)算機(jī)中，采用函數(shù)程序設(shè)計(jì)語(yǔ)言。這種純函數(shù)操作取消了變量和變量賦值機(jī)制，從根本上消除了傳統(tǒng)編程語(yǔ)言中因大量使用全局變量和同名變量而產(chǎn)生的副作用。 函數(shù)程序設(shè)計(jì)語(yǔ)言的自動(dòng)向量識(shí)別能力大為提高，便于對(duì)數(shù)據(jù)流的分析和處理?；谶@種語(yǔ)言編寫(xiě)的程序符合程序設(shè)計(jì)方法學(xué)的要求，良好的程序結(jié)構(gòu)不僅降低了程序編制的難度，而且為程序的
24、調(diào)試和驗(yàn)證提供了很好的基礎(chǔ)。從而可以提高程序設(shè)計(jì)的生產(chǎn)能力、效率及可靠性。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)467.4.2 數(shù)據(jù)流計(jì)算機(jī)存在的主要問(wèn)題數(shù)據(jù)流計(jì)算機(jī)存在的主要問(wèn)題1. 系統(tǒng)開(kāi)銷(xiāo)大 數(shù)據(jù)流計(jì)算機(jī)的指令格式與傳統(tǒng)計(jì)算機(jī)不同，它包含一個(gè)操作碼、兩個(gè)源操作數(shù)以及一個(gè)或多個(gè)后繼指令地址，某些動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī)的指令中還有許多標(biāo)記位，所以其指令長(zhǎng)度一般較長(zhǎng)。與傳統(tǒng)計(jì)算機(jī)相比，需要占用更多的系統(tǒng)存儲(chǔ)器資源來(lái)保存用這種指令編寫(xiě)的程序，而用于完成其指令的存取所花費(fèi)的時(shí)間更長(zhǎng)。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)472不能有效利用傳統(tǒng)計(jì)算機(jī)的研究成果 數(shù)據(jù)流計(jì)算機(jī)獨(dú)特的解題方法使它具有與傳統(tǒng)
25、計(jì)算機(jī)完全不同的結(jié)構(gòu)，令其可以擺脫傳統(tǒng)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的束縛，但同時(shí)意味著它無(wú)法吸收利用許多經(jīng)證明在傳統(tǒng)計(jì)算機(jī)中行之有效的研究成果。 另外，數(shù)據(jù)流計(jì)算機(jī)采用的基于數(shù)據(jù)流程序圖的機(jī)器語(yǔ)言，使得在傳統(tǒng)計(jì)算機(jī)上長(zhǎng)期積累的大量軟件成果無(wú)法實(shí)現(xiàn)軟件繼承。這將導(dǎo)致數(shù)據(jù)流計(jì)算機(jī)在市場(chǎng)上與傳統(tǒng)計(jì)算機(jī)竟?fàn)幹械牟焕?。第? 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)483數(shù)據(jù)流語(yǔ)言尚不完善 目前提出的數(shù)據(jù)流語(yǔ)言都不夠完善，仍需要進(jìn)一步改進(jìn)。例如，計(jì)算機(jī)的輸入輸出操作至今還未引入到數(shù)據(jù)流語(yǔ)言中來(lái)。數(shù)據(jù)流語(yǔ)言是以隱含的方式描述并行性，并由編譯器來(lái)開(kāi)發(fā)其中的并行成分，這將對(duì)編譯器提出很高的要求。而在數(shù)據(jù)流程序中存在的大量隱含的并行
26、性，使得程序的調(diào)試變得非常困難，目前還缺少有效的解決方法。另外，對(duì)數(shù)據(jù)流計(jì)算機(jī)操作系統(tǒng)的研究也還很不成熟。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)497.4.3 數(shù)據(jù)流計(jì)算機(jī)的研究方向數(shù)據(jù)流計(jì)算機(jī)的研究方向1. 提高并行級(jí)別 把并行提高到函數(shù)一級(jí)或復(fù)合函數(shù)一級(jí)，利用數(shù)據(jù)直接驅(qū)動(dòng)函數(shù)和復(fù)合函數(shù)計(jì)算，以減少操作開(kāi)銷(xiāo)。在這種復(fù)合函數(shù)驅(qū)動(dòng)方案中，數(shù)據(jù)流程序圖中用有向分支線(xiàn)連接復(fù)合函數(shù)結(jié)點(diǎn)而不是操作結(jié)點(diǎn)，實(shí)現(xiàn)的是復(fù)合函數(shù)級(jí)的并行。這樣就可以利用傳統(tǒng)高級(jí)語(yǔ)言來(lái)編寫(xiě)程序，也就可以繼承長(zhǎng)期積累的大量軟件。 第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)502. 同步與異步相結(jié)合在指令級(jí)采用同步操作，而在函數(shù)級(jí)及函數(shù)
27、以上級(jí)采用異步操作的方法作為解決數(shù)據(jù)流計(jì)算機(jī)操作開(kāi)銷(xiāo)過(guò)大的有效途徑。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)513. 控制流與數(shù)據(jù)流相結(jié)合 在指令級(jí)仍采用傳統(tǒng)的控制流方法實(shí)現(xiàn)，而把并行級(jí)別確定在函數(shù)級(jí)，重點(diǎn)實(shí)現(xiàn)復(fù)合函數(shù)級(jí)的并行操作。已經(jīng)有人設(shè)計(jì)出這種類(lèi)型的數(shù)據(jù)流計(jì)算機(jī)，它既有數(shù)據(jù)流技術(shù)的優(yōu)點(diǎn)，實(shí)現(xiàn)函數(shù)級(jí)并行操作，使控制簡(jiǎn)單，操作開(kāi)銷(xiāo)不大；又在機(jī)器中采用向量處理技術(shù)，以繼承傳統(tǒng)控制流計(jì)算機(jī)中行之有效的技術(shù)成果。在軟件方面，使用傳統(tǒng)高級(jí)語(yǔ)言編程，實(shí)現(xiàn)軟件繼承。第第7 7章章 數(shù)據(jù)流計(jì)算機(jī)數(shù)據(jù)流計(jì)算機(jī)52 數(shù)據(jù)流計(jì)算機(jī)研究中需要進(jìn)一步解決的其他主要技術(shù)問(wèn)題還包括：v 研制易于使用、易于用硬件實(shí)現(xiàn)的高級(jí)數(shù)據(jù)流語(yǔ)言。v 研究程序分解、分配給各個(gè)處理部件的算法。v 設(shè)計(jì)性能價(jià)格比高的信息包交換網(wǎng)絡(luò)，實(shí)現(xiàn)資源沖突 的仲裁和數(shù)據(jù)令牌分配等大量通信工作。v 研制智能化的數(shù)據(jù)驅(qū)動(dòng)機(jī)構(gòu)，研究如何在數(shù)據(jù)流環(huán)境 中高效率地處理復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。v 研究支持?jǐn)?shù)據(jù)流運(yùn)算的存儲(chǔ)系統(tǒng)和存儲(chǔ)分配方案。v 研究數(shù)據(jù)流計(jì)算機(jī)的操作系統(tǒng)。v 開(kāi)發(fā)數(shù)據(jù)流語(yǔ)言的跟蹤調(diào)試工具。
計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第二版尹朝慶主編第7章數(shù)據(jù)流計(jì)算機(jī)
