計(jì)算機(jī)體系結(jié)構(gòu) - 第8章.ppt

1、第 8 章 具有現(xiàn)代特色的計(jì)算機(jī),8.1 脈動(dòng)陣列機(jī) 8.2 數(shù)據(jù)流機(jī) 8.3 歸約機(jī) 8.4 智能機(jī) 8.5 大規(guī)模并行處理機(jī)MPP與機(jī)群系統(tǒng),8.2 數(shù) 據(jù) 流 機(jī),8.2.1 數(shù)據(jù)驅(qū)動(dòng)的概念,以計(jì)算一元二次方程ax2+bx+c=0的根作為例子。假定b2-4ac0，可以寫出如下的FORTRAN程序： READ *, A, B, C X1=2*A D=SQRT(B*B-4*A*C) D=D/X1 X2=-B/X1 X1=X2+D X2=X2-D PRINT *, X1, X2 END,圖 8.8 求一元二次方程根的程序中的數(shù)據(jù)相關(guān)關(guān)系,圖 8.9 求一元二次方程根的數(shù)據(jù)流程序圖,8.2.2

2、數(shù)據(jù)流程序圖和語言,1. 數(shù)據(jù)流程序圖,圖 8.10 計(jì)算z=(a+b)*(a-b)的數(shù)據(jù)流程序圖,圖 8.11 數(shù)據(jù)流程序圖的執(zhí)行過程,圖 8.12 常用非控制類操作結(jié)點(diǎn)及其激發(fā)規(guī)則,圖 8.13 常用控制類操作結(jié)點(diǎn)及其激發(fā)規(guī)則,圖 8.14 具有條件分支結(jié)構(gòu)的數(shù)據(jù)流程序圖例,圖 8.15 具有循環(huán)結(jié)構(gòu)的數(shù)據(jù)流程序圖例,圖 8.16 計(jì)算z=(a+b)*(a-b)的活動(dòng)模片表示法,圖 8.17 圖 8.14 數(shù)據(jù)流程序圖等效的活動(dòng)模片表示,2. 數(shù)據(jù)流語言,單賦值語言是指在程序中，每個(gè)變量均只賦值一次，即同一變量名在不同賦值語句的左部最多只出現(xiàn)一次。因此，實(shí)際上并沒有傳統(tǒng)計(jì)算機(jī)中的變量的概念

3、，只是一種值名。例如， 一個(gè)程序允許出現(xiàn)如下語句序列： C=A+B C=C*D F=(C-D)/E,則所使用的語言就不是單賦值語言。 若這時(shí)只允許把程序?qū)懗?C=A+B C1=C*D F=(C1-D)/E 其所用的語言就體現(xiàn)出單賦值的規(guī)則和要求了。單賦值語言的語義清楚， 程序中的并行性易于被編譯程序所開發(fā)。,下面以這個(gè)語言列舉其單賦值語言具備的基本特點(diǎn)。 遵循單賦值規(guī)則。 (2) 有豐富的數(shù)據(jù)類型。 (3) 具有很強(qiáng)的類型性。 (4) 具有模塊化結(jié)構(gòu)的程序設(shè)計(jì)思想。 (5) 沒有全局存貯器和狀態(tài)的概念。 (6) 程序不規(guī)定語句的執(zhí)行順序。,8.2.3 數(shù)據(jù)流計(jì)算機(jī)的結(jié)構(gòu),1. 靜態(tài)數(shù)據(jù)流機(jī),圖

4、 8.18 靜態(tài)數(shù)據(jù)流機(jī)的結(jié)構(gòu),圖 8.19 MIT靜態(tài)數(shù)據(jù)流機(jī)主體結(jié)構(gòu),圖 8.20 278的仲裁網(wǎng)絡(luò)示意圖,2. 動(dòng)態(tài)數(shù)據(jù)流機(jī),圖 8.21 動(dòng)態(tài)數(shù)據(jù)流機(jī)的結(jié)構(gòu)框圖,圖 8.22 MIT動(dòng)態(tài)數(shù)據(jù)流機(jī)結(jié)構(gòu),圖 8.23 MIT動(dòng)態(tài)數(shù)據(jù)流機(jī)典型指令的格式,圖 8.24 MIT動(dòng)態(tài)數(shù)據(jù)流機(jī)每個(gè)PE的內(nèi)部結(jié)構(gòu),圖 8.25 Manchester數(shù)據(jù)流機(jī)結(jié)構(gòu)框圖,8.2.4 數(shù)據(jù)流機(jī)器存在的問題,(1) 數(shù)據(jù)流機(jī)主要目的是為了提高操作級(jí)并行的開發(fā)水平，但如果題目本身數(shù)據(jù)相關(guān)性很強(qiáng)，內(nèi)含并行性成分不多時(shí)，就會(huì)導(dǎo)致數(shù)據(jù)流機(jī)的效率反而不如傳統(tǒng)的Von Neumann型機(jī)器的高。 (2) 在數(shù)據(jù)流機(jī)器中為了

5、給數(shù)據(jù)建立標(biāo)記并識(shí)別和處理該標(biāo)記，需要花費(fèi)較多的輔助開銷和較大的存貯空間(可能比Neumann型的要大出 2 至 3 倍)。 (3) 數(shù)據(jù)流機(jī)不保存數(shù)組。,(4) 數(shù)據(jù)流語言的變量代表數(shù)值而不是存貯單元位置， 使程序員無法控制存貯分配。 為了能有效地回收不用的存貯單元， 就增大了編譯程序設(shè)計(jì)的難度。 (5) 專門適合于數(shù)據(jù)流機(jī)用的互連網(wǎng)絡(luò)的設(shè)計(jì)較困難， 而且， 對(duì)數(shù)據(jù)流機(jī)的輸入/輸出尚待完善。 (6) 數(shù)據(jù)流機(jī)沒有程序計(jì)數(shù)器， 給診斷和維護(hù)帶來困難。,8.3 歸 約 機(jī),從函數(shù)程序設(shè)計(jì)的角度看，一個(gè)程序就是一個(gè)函數(shù)的表達(dá)式。通過定義一組“程序形成算符”(ProgramForming Opera

6、tors), 可以用簡(jiǎn)單函數(shù)(即簡(jiǎn)單程序)構(gòu)成任意復(fù)雜的程序，也就是， 構(gòu)成任意復(fù)雜函數(shù)的表達(dá)式。反過來，如果給出了一個(gè)屬函數(shù)表達(dá)式集合中的復(fù)雜函數(shù)的表達(dá)式，利用提供的函數(shù)集合中的子函數(shù)經(jīng)過有限次歸約代換之后，總可以得到所希望的結(jié)果， 即由常量構(gòu)成的目標(biāo)。函數(shù)表達(dá)式指的是函數(shù)之間的映射。 從語法上講是按規(guī)定的語法規(guī)則構(gòu)成的符號(hào)串，從語義上講是多個(gè)運(yùn)算符的組合。,函數(shù)集合中包括了所有的原函數(shù)和復(fù)合函數(shù)。原函數(shù)(Primitive Function)指的是，由一個(gè)目標(biāo)變換為另一個(gè)目標(biāo)的基本映射，是歸約機(jī)建成時(shí)安裝上的函數(shù)。 它們可以包括有： 從一個(gè)元素序列中選出某一個(gè)元素的函數(shù)， 加、 減、 乘、

7、 除等算術(shù)函數(shù)， 交叉置換函數(shù)， 比較、 測(cè)試函數(shù)， 附加序列函數(shù)， 加 1/減 1 函數(shù)， 等等。 復(fù)合函數(shù)指的是利用一組“程序形成算符”由已有的函數(shù)(程序)構(gòu)成復(fù)雜的函數(shù)(程序)。 使用的“程序形成算符”一般有組合、 構(gòu)造、 條件、 插入、 作用于全體等多種。,從歸約的角度來理解，函數(shù)是一種特殊的表達(dá)式， 即為有局部變量的表達(dá)式。例如，經(jīng)DEF f(x)=x+z定義后，使表達(dá)式x+z變成了函數(shù)，其中x為局部變量，z為全局變量。函數(shù)也可以理解成是定義了一種子表達(dá)式的替換規(guī)則。例如，已定義了f函數(shù)后，對(duì)表達(dá)式5*f(3)求值時(shí)，f(3)就可以用 3+z代換，從 5*f(3)轉(zhuǎn)換成 5*(3+z

8、)。 由目標(biāo)、函數(shù)、函數(shù)表達(dá)式、定義(DEF)和作用算符就可以構(gòu)成函數(shù)程序。這里，定義(Definition)“DEF”就是指的從原有函數(shù)定義一個(gè)新的函數(shù)。采用的作用算符一般是用冒號(hào)(：)，例如， 函數(shù)f作用于目標(biāo)x，可以表示成fx。,以表達(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ù)向下歸約。,有如下主要的優(yōu)點(diǎn)： (1)程序的每一行語句可以表達(dá)出更多有關(guān)算法的信息。 (2) 沒有狀態(tài)和存貯單

9、元的概念，函數(shù)自變量的值隨函數(shù)的應(yīng)用動(dòng)態(tài)獲得， 因此不會(huì)產(chǎn)生一個(gè)過程的變量受到另一過程影響的副作用，即被應(yīng)用的函數(shù)改變不了函數(shù)定義時(shí)的約束關(guān)系。 (3) 沒有賦值語句，不會(huì)出現(xiàn)像命令式語言里的賦值語句x=x+1那樣一種與數(shù)學(xué)里的變量不相符和違反數(shù)學(xué)中“相等性”演繹推理規(guī)則的現(xiàn)象；同時(shí)，沒有使用GO TO類控制語句。,(4) 指令執(zhí)行的順序只受操作數(shù)的需求所制約， 只要沒有數(shù)據(jù)依賴關(guān)系的函數(shù)，原則上都可以在不同處理器上并行處理， 所以程序中的并行性較易檢測(cè)和開發(fā)。 (5) 程序具有單一的遞歸結(jié)構(gòu)，即函數(shù)又是由函數(shù)構(gòu)成。一個(gè)函數(shù)程序的功能只與組成該函數(shù)程序的各函數(shù)成分有關(guān)。數(shù)據(jù)結(jié)構(gòu)是目標(biāo)的組成部分

10、，不是程序的組成部分，因此同一個(gè)函數(shù)程序可以處理結(jié)構(gòu)、大小不同的目標(biāo)，增強(qiáng)了程序的通用性。,8.3.2 面向函數(shù)程序設(shè)計(jì)的歸約機(jī),歸約機(jī)的基本結(jié)構(gòu)特點(diǎn),(1) 歸約機(jī)應(yīng)當(dāng)面向函數(shù)式語言， 或以函數(shù)式語言為機(jī)器語言的非Neumann型機(jī)器。 (2) 具有大容量的物理存貯器并采用有虛存容量很大的虛擬存貯器系統(tǒng)， 具備高效的動(dòng)態(tài)存貯分配和管理的軟硬件支持， 滿足歸約機(jī)對(duì)動(dòng)態(tài)存貯分配及所需存貯空間較大的要求。 (3) 處理部分應(yīng)當(dāng)是一種含有多個(gè)處理器或多個(gè)處理機(jī)并行的結(jié)構(gòu)形式，以發(fā)揮函數(shù)式程序并行處理的特長(zhǎng)。,(4) 采用適合于函數(shù)式程序運(yùn)行的多處理器(機(jī))互連的機(jī)構(gòu)。 盡管過去介紹過的各種機(jī)間互連結(jié)

11、構(gòu)原則上都是可用的，但最好采用樹型方式的互連結(jié)構(gòu)或多層次復(fù)合的互連結(jié)構(gòu)形式。 (5) 為了減少進(jìn)程調(diào)度及進(jìn)程間通信的開銷，盡可能把運(yùn)行進(jìn)程的結(jié)點(diǎn)機(jī)安排成緊靠該進(jìn)程所需用的數(shù)據(jù)，并使運(yùn)行時(shí)需相互通信的進(jìn)程所占用的處理機(jī)也靠近。此外還應(yīng)盡可能使各個(gè)處理機(jī)的負(fù)荷平衡。,根據(jù)機(jī)器內(nèi)部對(duì)函數(shù)表達(dá)式所采用的存貯方式不同，將歸約方式又分成了串歸約(String Reduction)和圖歸約(Graph Reduction)兩類。 為說明這兩種歸約方式的區(qū)別，仍以表達(dá)式z=(y-1)*(y+x)為例。 假定x和y分別賦以 2 和 5。 串歸約方式是當(dāng)提出求函數(shù)z=f(u)的請(qǐng)求后，立即轉(zhuǎn)化成執(zhí)行由操作符*和兩

12、個(gè)子函數(shù)g與h的作用所組成的“指令”。 g和h的作用又引起“指令”(-y, 1)和(+y, x)的執(zhí)行。于是，從存貯單元中分別取出y和x的值，算出y-1和y+x的結(jié)果，然后將返回值再各自取代g和h，最后求(*4, 7)，得結(jié)果28。,圖 8.26 串歸約和圖歸約,2. 串歸約機(jī) 串歸約機(jī)可看成是一種特殊的符號(hào)串處理機(jī)， 函數(shù)定義、 表達(dá)式和目標(biāo)都以字符串的形式存貯于機(jī)器中。 函數(shù)式語言源程序可以不經(jīng)翻譯， 直接在串歸約機(jī)上進(jìn)行處理。 前面已經(jīng)說過串歸約機(jī)一個(gè)主要問題是不能共享子表達(dá)式， 多次應(yīng)用就得多次復(fù)制和求值運(yùn)算，所以時(shí)間和空間的輔助開銷相對(duì)都比較大。,圖 8.27 表達(dá)式在細(xì)胞歸約機(jī)中的

13、存貯形式,圖 8.28 FFP機(jī)的結(jié)構(gòu),圖 8.29 FP程序在FFP子樹上由(a)到(d)的執(zhí)行過程舉例,3. 圖歸約機(jī),圖 8.30 Guzman并行LISP機(jī)的結(jié)構(gòu),8.4 智 能 機(jī),8.4.1 智能信息處理與智能機(jī),具有智能的計(jì)算機(jī)主要應(yīng)當(dāng)是一個(gè)知識(shí)信息處理系統(tǒng)。 在這樣的系統(tǒng)中，必須解決好有關(guān)知識(shí)的獲取、 知識(shí)的表示、 知識(shí)的存貯、知識(shí)的處理和知識(shí)的應(yīng)用等諸方面的問題， 使計(jì)算機(jī)能更好地模擬人類大腦的思維活動(dòng)，提高學(xué)習(xí)、 推理、 判斷和問題求解的能力。,8.4.2 智能機(jī)的結(jié)構(gòu)及所用的機(jī)器語言,1. 智能機(jī)的結(jié)構(gòu),圖 8.31 智能機(jī)的結(jié)構(gòu)框圖,2. 邏輯程序設(shè)計(jì)語言 邏輯程序設(shè)計(jì)

14、語言的典型代表是PROLOG語言。它是1972 年法國(guó)馬賽的A.Colmerauer首先開發(fā)的，是以一階謂詞演算為基礎(chǔ)的交互式語言。謂詞邏輯(Predicate Logic)與人類基于對(duì)客觀世界的認(rèn)識(shí)所形成的抽象概念進(jìn)行思考、 推理的方式十分吻合。PROLOG語言是一種完全面向問題的語言，盡管它也帶有過程性的成分， 但PROLOG程序完全不同于一般著眼于算法描述的程序。PROLOG程序是關(guān)于問題的已知事實(shí)及其關(guān)系的說明。其程序的執(zhí)行大部分依賴于PROLOG程序中語句所固有的邏輯關(guān)系和語言本身按產(chǎn)生式規(guī)則進(jìn)行演繹推理的能力。從已有事實(shí)推導(dǎo)出新的事實(shí)。 僅有一部分依賴于由用戶顯式給出的控制信息。,

15、以X=6、Y=2, 求Z=(X+1)*(X-Y)的值為例， 若用PROLOG語言描述，只需要一條產(chǎn)生式規(guī)則，即 assign(Z, X, Y):-P is plus(X,1), Q is minus(X,Y), Z is times(P, Q). 即可， 其中， “:-”表示if, “,”表示邏輯與。 該規(guī)則的意思是，如果P=X+1(第一子句)與Q=X-Y(第二子句)以及Z=P*Q(第三子句)都滿足，則總目標(biāo)，即產(chǎn)生式左邊的規(guī)則頭(對(duì)變量Z、 X、 Y的賦值)最終得到滿足。 在給定X=6、 Y=2 時(shí)， 求解Z的問題可寫成 ?-assign(Z, 6, 2).,3. 智能計(jì)算機(jī)的進(jìn)展,日本經(jīng)過

16、 3 年的調(diào)查研究和準(zhǔn)備，于 1981 年 10 月宣布了從 1982 年至 1991 年的所謂“第五代計(jì)算機(jī)”的研究計(jì)劃， 曾引起國(guó)際上極大的反響。 之后， 美國(guó)、 英國(guó)以及西歐各國(guó)相繼在人工智能和智能機(jī)研究上取得不少階段性成果。 1982年4 月日本正式成立了“新一代計(jì)算機(jī)技術(shù)研究所”(Institute for New Generation Computer Technology, ICOT), 由多家大公司、 研究所和大學(xué)派人參加。相應(yīng)成立了核心語言、 自然語言處理、知識(shí)庫子系統(tǒng)、推理子系統(tǒng)、應(yīng)用子系統(tǒng)等 5 個(gè)研究室。,8.5 大規(guī)模并行處理機(jī)MPP與機(jī)群系統(tǒng),大規(guī)模并行處理需要有新

17、的計(jì)算方法、新的存貯技術(shù)、新的處理手段和新的結(jié)構(gòu)組織方式。于是，將數(shù)百、數(shù)千乃至數(shù)萬個(gè)高性能、低成本的RISC微處理器用互連網(wǎng)絡(luò)互連，組成大規(guī)模并行處理機(jī)MPP就是自然的了。這種處理機(jī)可進(jìn)行中粒度和細(xì)粒度大規(guī)模并行處理，構(gòu)成SIMD或MIMD的系統(tǒng)。它具有性能價(jià)格比高和可擴(kuò)展性好的優(yōu)點(diǎn)。如果一個(gè)RISC微處理器的性能為 100 MFLOPS，則 1 024 個(gè)這樣的微處理器組搭成的MPP系統(tǒng)，其最高性能就可達(dá) 100GFLOPS。這比用單一主處理機(jī)構(gòu)成的巨型機(jī)的性能要高出許多倍，而造價(jià)可能只是它的1/5。 可擴(kuò)展性好表現(xiàn)在能比較方便地增減節(jié)點(diǎn)處理器數(shù)，來使系統(tǒng)的規(guī)模、 處理速度、 系統(tǒng)價(jià)格滿足應(yīng)用的需要。,機(jī)群系統(tǒng)是將多個(gè)高性能的工作站或高檔微型計(jì)算機(jī)通過高速