第7章--新型計(jì)算機(jī)結(jié)構(gòu).ppt

1、2020年7月15日星期三,1,第1章 計(jì)算機(jī)系統(tǒng)的設(shè)計(jì)基礎(chǔ) 第2章 數(shù)據(jù)表示與指令系統(tǒng) 第3章 輸入輸出系統(tǒng) 第4章 存貯系統(tǒng) 第5章 流水技術(shù)和向量處理 第6章 并行處理技術(shù) 第7章 新型計(jì)算機(jī)結(jié)構(gòu),2020年7月15日星期三,2,本章學(xué)習(xí)要求,了解幾種非傳統(tǒng)計(jì)算機(jī)結(jié)構(gòu)的概念和工作原理 掌握數(shù)據(jù)流計(jì)算機(jī)的工作原理和結(jié)構(gòu)特點(diǎn) 了解人工智能計(jì)算機(jī)的研制情況,2020年7月15日星期三,3,第7章 新型計(jì)算機(jī)結(jié)構(gòu),脈動(dòng)陣列計(jì)算機(jī) 數(shù)據(jù)流計(jì)算機(jī) 歸約機(jī) 人工智能計(jì)算機(jī),2020年7月15日星期三,4,7.1 脈動(dòng)陣列計(jì)算機(jī),脈動(dòng)陣列結(jié)構(gòu)是由一組相同的處理單元PE構(gòu)成的陣列機(jī)。每個(gè)PE可完成少數(shù)基本

2、的算術(shù)邏輯運(yùn)算操作 工作原理：陣列內(nèi)所有處理單元的數(shù)據(jù)鎖存器都受同一個(gè)時(shí)鐘控制，運(yùn)算時(shí)數(shù)據(jù)在陣列結(jié)構(gòu)的各個(gè)處理單元間沿各自的方向同步向前推進(jìn)，就像血液受心臟有節(jié)奏地搏動(dòng)在各條血管中同步向前流動(dòng)一樣,2020年7月15日星期三,5,脈動(dòng)陣列機(jī)主要適用要求計(jì)算量很大的信號(hào)圖像的處理，以及某些特定計(jì)算類算法題目的求解，特別是需要對(duì)大量數(shù)據(jù)執(zhí)行重復(fù)計(jì)算的運(yùn)算受限類問題的求解。,根據(jù)具體計(jì)算的問題不同，脈動(dòng)陣列可以 有一維線形、二維矩形六邊形/二叉樹形 三角形等陣列互連構(gòu)形。,2020年7月15日星期三,6,脈動(dòng)式二維陣列流水機(jī),2020年7月15日星期三,7,1i3,1j3,現(xiàn)有矩陣A、B如下，要在二

3、維脈動(dòng)陣列機(jī)上求兩矩陣 的乘積C,其中,在圖中給出了在t1、t2 、t3 時(shí)刻送入數(shù)據(jù)，到t6 時(shí)，從 45 方向上將同時(shí)輸出 的值，t7 時(shí)輸出 的值，t8 時(shí)輸出 的值。 可以看出，總共只需用8拍就可以完成兩個(gè)33矩陣相乘，比單處理機(jī)上循環(huán)執(zhí)行所需的27拍，速度提高了兩倍多。,2020年7月15日星期三,8,a11 a12 a13 0 0 t1,0 a21 a22 a23 0 t2,0 0 a31 a32 a33 t3,0,0,0,0,0,t1 0 0 b31 b21 b11,t2 0 b32 b22 b12 0,t3 b33 b23 b13 0 0,2020年7月15日星期三,9,脈動(dòng)陣

4、列計(jì)算機(jī)具有如下特點(diǎn)：,（1）結(jié)構(gòu)簡(jiǎn)單、規(guī)整，模塊化強(qiáng)，可擴(kuò)充性好。非常 適合于超大規(guī)模集成電路的實(shí)現(xiàn)。,（2）PE間數(shù)據(jù)通信距離短、規(guī)則，使數(shù)據(jù)流和控制流 的設(shè)計(jì)、同步控制簡(jiǎn)單規(guī)整。,（3）具有極高的計(jì)算并行性，可通過流水獲得很高的 運(yùn)算效率和吞吐率。,（4）脈動(dòng)陣列結(jié)構(gòu)的構(gòu)形與特定的計(jì)算任務(wù)和算法密 切相關(guān)，限制了其應(yīng)用范圍。,脈動(dòng)陣列機(jī)的發(fā)展目標(biāo)：研制通用型脈動(dòng)陣列機(jī)。,2020年7月15日星期三,10,7.2 數(shù)據(jù)流計(jì)算機(jī),數(shù)據(jù)流計(jì)算機(jī)的基本工作原理 數(shù)據(jù)流程序圖和數(shù)據(jù)流語(yǔ)言 數(shù)據(jù)流計(jì)算機(jī)的基本結(jié)構(gòu) 數(shù)據(jù)流計(jì)算機(jī)存在的主要問題,2020年7月15日星期三,11,7.2.1數(shù)據(jù)流計(jì)算機(jī)的

5、基本工作原理,數(shù)據(jù)驅(qū)動(dòng)的數(shù)據(jù)流方式：只要一條或一組指令所要求的操作數(shù)全部準(zhǔn)備就緒，就可立即激發(fā)相應(yīng)的指令或指令組執(zhí)行。,特點(diǎn)：指令的執(zhí)行基本上是無(wú)序的，完全受數(shù)據(jù)流的驅(qū)動(dòng)；沒有程序計(jì)數(shù)器PC，取而代之的是“數(shù)據(jù)令牌”。,“數(shù)據(jù)令牌”是一種表示某一操作數(shù)或參數(shù)已準(zhǔn)備就緒的標(biāo)志。,2020年7月15日星期三,12,7.2.2 數(shù)據(jù)流程序圖和數(shù)據(jù)流語(yǔ)言,數(shù)據(jù)流程序圖：是一種用來(lái)表示指令級(jí)的數(shù)據(jù)流程序的有向圖(directed graph)，它由多個(gè)結(jié)點(diǎn)(node)和一些連接它們的弧所組成。它說明了指令之間執(zhí)行順序的約束條件。 數(shù)據(jù)流程序圖中的結(jié)點(diǎn)除表示一般的算術(shù)邏輯操作外，還可表示常數(shù)產(chǎn)生、復(fù)制操作

6、、判定操作和控制操作等。,2020年7月15日星期三,13,數(shù)據(jù)流程序圖中常用的結(jié)點(diǎn),（1）算邏運(yùn)算結(jié)點(diǎn)：,算術(shù)運(yùn)算結(jié)點(diǎn)：加、減、乘、除、加l、減1等 布爾運(yùn)算結(jié)點(diǎn)：與、或、異或、非等,2020年7月15日星期三,14,（2）常數(shù)結(jié)點(diǎn)：,常數(shù)結(jié)點(diǎn)的功能是用來(lái)產(chǎn)生一個(gè)常數(shù)。 常數(shù)產(chǎn)生結(jié)點(diǎn)沒有輸入端，只有一條輸出線。,激發(fā)后,2,數(shù)據(jù)令牌,一般表示,數(shù)據(jù)復(fù)制,控制復(fù)制,（3）復(fù)制結(jié)點(diǎn)：,數(shù)據(jù)復(fù)制結(jié)點(diǎn)：圖中圓點(diǎn)和箭頭用實(shí)心表示。 控制量（布爾量）復(fù)制結(jié)點(diǎn)：圖中的圓點(diǎn)和箭頭用空心表示。,2020年7月15日星期三,15,（4）控制操作結(jié)點(diǎn) ：,T門控結(jié)點(diǎn),F門控結(jié)點(diǎn),T門控：僅當(dāng)布爾控制端為真、且輸入

7、端有數(shù)據(jù)令牌時(shí) 才能激發(fā)，然后在輸出端產(chǎn)生數(shù)據(jù)令牌而輸入端的數(shù)據(jù) 令牌消失。,F門控：僅當(dāng)布爾控制端為假、且輸入端有數(shù)據(jù)令牌時(shí) 才能激發(fā)，然后在輸出端產(chǎn)生數(shù)據(jù)令牌而輸入端的數(shù)據(jù) 令牌消失。,2020年7月15日星期三,16,開關(guān)門控結(jié)點(diǎn),歸并門控結(jié)點(diǎn),2020年7月15日星期三,17,（5）條件判斷結(jié)點(diǎn) ：,判斷輸入數(shù)據(jù)(通常是單個(gè)或兩個(gè))是否滿足某種條件， 如輸入數(shù)據(jù)是否小于、等于、大于0，兩個(gè)輸入數(shù)據(jù)的 大小比較等。當(dāng)滿足條件時(shí)，將在輸出端產(chǎn)生T的控制 令牌，否則便產(chǎn)生F的控制令牌。,利用上述常用結(jié)點(diǎn)，可以畫出一些程序結(jié)構(gòu)的數(shù)據(jù)流 程圖。,2020年7月15日星期三,18,Z,Z=X+Y

8、X0 Z=X-Y X0,數(shù)據(jù)流程序圖舉例,問題：圖中有多少個(gè)結(jié)點(diǎn)？ 出現(xiàn)了多少種結(jié)點(diǎn)？,復(fù)制,判斷,開關(guān),控制復(fù)制,算術(shù)運(yùn)算,歸并,2020年7月15日星期三,19,數(shù)據(jù)流語(yǔ)言,數(shù)據(jù)流語(yǔ)言的結(jié)構(gòu)類似于命令式程序設(shè)計(jì)語(yǔ)言，但又要能方便地被編譯成數(shù)據(jù)流程圖。 數(shù)據(jù)流語(yǔ)言大都是單賦值語(yǔ)言。單賦值的含義是指，在程序中每個(gè)變量只能賦值一次，即同一變量在賦值語(yǔ)句的左部只允許出現(xiàn)一次，不允許對(duì)同一變量進(jìn)行多次賦值。 常用的數(shù)據(jù)流語(yǔ)言有美國(guó)的ID和VAL，法國(guó)的LAU以及英國(guó)曼徹斯特大學(xué)的SISAL語(yǔ)言等。,2020年7月15日星期三,20,數(shù)據(jù)流語(yǔ)言舉例,對(duì)于點(diǎn)積操作，用ID語(yǔ)言則可寫成如下的過程： pro

9、cedure inner_product(a,b,n) initial S0 for i from 1 to n do new SS+(ai *bi) return S,2020年7月15日星期三,21,7.2.3數(shù)據(jù)流計(jì)算機(jī)的基本結(jié)構(gòu),依據(jù)處理數(shù)據(jù)令牌的不同，數(shù)據(jù)流機(jī)可分成靜態(tài)和動(dòng)態(tài)兩大類。 靜態(tài)數(shù)據(jù)流機(jī)的數(shù)據(jù)令牌不帶任何標(biāo)號(hào)，在任何一條弧上只允許存在一個(gè)數(shù)據(jù)令牌。 動(dòng)態(tài)數(shù)據(jù)流機(jī)的數(shù)據(jù)令牌帶有標(biāo)號(hào)。這樣就可使數(shù)據(jù)流程序圖中的任一條弧上同時(shí)存在帶有不同標(biāo)號(hào)(或稱顏色)的數(shù)據(jù)令牌。,2020年7月15日星期三,22,靜態(tài)數(shù)據(jù)流計(jì)算機(jī),2020年7月15日星期三,23,動(dòng)態(tài)數(shù)據(jù)流計(jì)算機(jī),由于任一條

10、弧上同時(shí)存在帶有不同標(biāo)號(hào)(或稱顏色)的 數(shù)據(jù)令牌只要對(duì)令牌標(biāo)號(hào)進(jìn)行符合比較就可加以識(shí)別。 為此，需要有一個(gè)稱為匹配部件的硬件機(jī)構(gòu)將標(biāo)號(hào)附 加到數(shù)據(jù)令牌上，并完成標(biāo)號(hào)的匹配工作。,2020年7月15日星期三,24,7.2.4數(shù)據(jù)流機(jī)存在的主要問題,1指令級(jí)的數(shù)據(jù)驅(qū)動(dòng)導(dǎo)致每條指令的執(zhí)行有較大的時(shí)間開銷，因?yàn)樵谶\(yùn)行時(shí)需要對(duì)每一個(gè)和每一次操作進(jìn)行數(shù)據(jù)相關(guān)分析。,2由于數(shù)據(jù)流程序的操作包代碼長(zhǎng)度較長(zhǎng)， 將占用較多的存儲(chǔ)空間。,3當(dāng)機(jī)器規(guī)模變大時(shí)，接到轉(zhuǎn)接網(wǎng)絡(luò)上的流 水環(huán)數(shù)將增加，從而使轉(zhuǎn)接網(wǎng)絡(luò)變成系統(tǒng)性能 的新瓶頸口。,2020年7月15日星期三,25,7.3 歸 約 機(jī),歸約機(jī)和數(shù)據(jù)流機(jī)一樣，都是基于

11、數(shù)據(jù)流的計(jì)算模型，只是其采用的驅(qū)動(dòng)方式不同。 數(shù)據(jù)流機(jī)是采用數(shù)據(jù)驅(qū)動(dòng)，執(zhí)行的操作序列取決于輸入數(shù)據(jù)的可用性； 歸約機(jī)則是需求驅(qū)動(dòng)，執(zhí)行的操作序列取決于對(duì)數(shù)據(jù)的需求，對(duì)數(shù)據(jù)的需求又來(lái)源于函數(shù)式程序設(shè)計(jì)語(yǔ)言對(duì)表達(dá)式的歸約(Reduction)。,2020年7月15日星期三,26,7.3.1函數(shù)式程序設(shè)計(jì)語(yǔ)言,函數(shù)式語(yǔ)言是由所有函數(shù)表達(dá)式的集合、所有目標(biāo)(也是表達(dá)式)的集合及所有由函數(shù)表達(dá)式到目標(biāo)的函數(shù)集合三部分組成。函數(shù)是其基本成分，是從一批目標(biāo)到另一批目標(biāo)的映射。從函數(shù)程序設(shè)計(jì)的角度看，一個(gè)程序就是一個(gè)函數(shù)的表達(dá)式。通過定義一組“程序形成算符”(ProgramForming Operators)

12、，可以用簡(jiǎn)單函數(shù)(即簡(jiǎn)單程序)構(gòu)成任意復(fù)雜的程序，也就是構(gòu)成任意復(fù)雜函數(shù)的表達(dá)式。,2020年7月15日星期三,27,以表達(dá)式z=(y-1)(y+x)為例，可以理解成z=f(u)，而 f(u)等價(jià)于g(v) h(w)，其中g(shù)(V)=y-1，h(w)=y+x， 也就是說，函數(shù)z=f(u)的求解可歸約成求兩個(gè)子函數(shù) g(v)和h(w)的積，而g(v)和h(w)又可以分別繼續(xù)向下 歸約。,針對(duì)函數(shù)程序設(shè)計(jì)語(yǔ)言的特點(diǎn)和問題來(lái)設(shè)計(jì)支持函數(shù) 式程序運(yùn)行的新計(jì)算機(jī)，這就是歸約機(jī)。,2020年7月15日星期三,28,7.3.2面向函數(shù)式語(yǔ)言的歸約機(jī),歸約機(jī)按其歸約模型可分為串歸約(String Reducti

13、on)機(jī)和圖歸約(Graph Reduction)機(jī)兩類。兩者的區(qū)分主要是對(duì)函數(shù)表達(dá)式所使用的存儲(chǔ)方式不同，前者以字符串形式存儲(chǔ)而后者則以圖的形式存儲(chǔ)。,2020年7月15日星期三,29,z：,串歸約:,z,圖歸約:,以表達(dá)式z=(y-1)(y+x)為例，假定x和y分別賦以2和5。,28,4,7,5,5,2,2020年7月15日星期三,30,串歸約特點(diǎn)：是一種不斷地在定義表達(dá)式集合中去查 找和復(fù)制的過程，而且對(duì)每次函數(shù)作用都要重復(fù)執(zhí)行， 因而時(shí)間和空間的輔助開銷都比較大。,圖歸約方式與串歸約方式主要的不同在于，定義表達(dá)式 時(shí)設(shè)置了Z1、Z2等指針。這樣，下一層作用的返回 結(jié)果將直接取代上一層作

14、用的自變量，省去了歸約時(shí)的 復(fù)制開銷；同時(shí)，實(shí)現(xiàn)了自變量返回值的共享，不用對(duì) 同一函數(shù)作用重復(fù)執(zhí)行，就可以直接引用此函數(shù)求值的 結(jié)果。,歸約方式體現(xiàn)了按需求驅(qū)動(dòng)的思想，根據(jù)對(duì)函數(shù)求值的 需求來(lái)激活相應(yīng)指令。,2020年7月15日星期三,31,7.4 人工智能計(jì)算機(jī),人工智能計(jì)算特征 AI計(jì)算機(jī)的分類 AI計(jì)算機(jī)的研究進(jìn)展 RWC研究計(jì)劃,2020年7月15日星期三,32,7.4.1人工智能計(jì)算特征,1AI計(jì)算的主要對(duì)象是符號(hào)而不是數(shù)值 2AI計(jì)算是非確定計(jì)算 3AI計(jì)算是動(dòng)態(tài)進(jìn)行的 4具有并行和分布處理的巨大潛力 5知識(shí)管理問題,2020年7月15日星期三,33,AI處理的基本要點(diǎn):有關(guān)知識(shí)的

15、獲取、表示和智慧地 加以使用(知識(shí)處理)。,知識(shí)的獲取:AI系統(tǒng)應(yīng)能從視覺、聲音和書寫等各種 信息源獲取信息。由于這些信息的來(lái)源往往是不完整、 不精確甚至是相互矛盾的，因此必須對(duì)它們進(jìn)行止確 的識(shí)別和理解。,知識(shí)的表示：主要是對(duì)有關(guān)對(duì)象、關(guān)系、目標(biāo)、動(dòng)作 以及處理過程的信息加以編碼，形成數(shù)據(jù)結(jié)構(gòu)和編寫 成過程。,知識(shí)的處理：主要用于問題求解、邏輯演繹和情報(bào)檢 索等。,2020年7月15日星期三,34,7.4.2 AI機(jī)的分類,1基于語(yǔ)言的AI計(jì)算機(jī) 2基于知識(shí)的AI計(jì)算機(jī) 3連接式(Connectionist)AI計(jì)算機(jī) 4帶智能接口的AI計(jì)算機(jī),2020年7月15日星期三,35,7.4.3 AI計(jì)算機(jī)的研究進(jìn)展,日本五代機(jī)的研究計(jì)劃分三個(gè)階段進(jìn)行 ： 第一階段為3年，主要是對(duì)并行推理機(jī)的基本結(jié)構(gòu)、并行推理機(jī)制以及知識(shí)庫(kù)機(jī)結(jié)構(gòu)等進(jìn)行研究和模擬試驗(yàn)。 第二階段用了4年時(shí)間，側(cè)重研究并行推理機(jī)PIM(Parallel inference machine)以及知識(shí)庫(kù)子系統(tǒng)的管理軟件系統(tǒng) 。 最后階段的3年，主要是構(gòu)成一個(gè)智能信息處理系統(tǒng)，它以VLSI技術(shù)實(shí)現(xiàn)的知識(shí)庫(kù)機(jī)和并行推理機(jī)為硬件核心，并配以基本核心軟件和應(yīng)用軟件。,2020年7月15日星期三,36,7.4.4 RWC研究計(jì)劃,所謂真實(shí)世界計(jì)算機(jī)(RWCR