第8章__其它計(jì)算機(jī)結(jié)構(gòu)第一頁(yè)，共37頁(yè)。?本章重點(diǎn)：

脈動(dòng)陣列機(jī)原理和結(jié)構(gòu)特點(diǎn)，大規(guī)模并行處理機(jī)MPP與機(jī)群系統(tǒng)的特點(diǎn)，數(shù)據(jù)流機(jī)的原理和組織，歸約機(jī)結(jié)構(gòu)特點(diǎn)和兩種形式，智能機(jī)的特點(diǎn)和組成。?本章難點(diǎn)：脈動(dòng)陣列機(jī)原理和結(jié)構(gòu)特點(diǎn)，數(shù)據(jù)流機(jī)的原理和組織，智能機(jī)的特點(diǎn)和組成。第二頁(yè)，共37頁(yè)。8.1脈動(dòng)陣列機(jī)8.1.1脈動(dòng)陣列結(jié)構(gòu)的原理和特點(diǎn)脈動(dòng)陣列結(jié)構(gòu)是由一組處理單元PE構(gòu)成的陣列。每個(gè)PE的內(nèi)部結(jié)構(gòu)相同，一般由一個(gè)加法/邏輯運(yùn)算部件或加法/乘法運(yùn)算部件再加上若干個(gè)鎖存器構(gòu)成，可完成少數(shù)基本的算術(shù)邏輯運(yùn)算操作。陣列中的輸入數(shù)據(jù)流和結(jié)果數(shù)據(jù)輸出流可各自沿著多個(gè)方向向前推進(jìn)。就好象血液受心臟壓力有節(jié)奏地搏動(dòng)在各條血管中同步向前流動(dòng)一樣。第三頁(yè)，共37頁(yè)。

脈動(dòng)陣列機(jī)主要適用要求計(jì)算量很大的信號(hào)/圖象的處理，以及某些特定計(jì)算類算法題目的求解，特別是需要對(duì)大量數(shù)據(jù)執(zhí)行重復(fù)計(jì)算的運(yùn)算受限類問(wèn)題的求解。根據(jù)具體計(jì)算的問(wèn)題不同，脈動(dòng)陣列可以有一維線形、二維矩形/六邊形/二叉數(shù)形/三角形等陣列互連構(gòu)形，如207頁(yè)圖8.1所示。

例：在一個(gè)脈動(dòng)式二維陣列結(jié)構(gòu)上進(jìn)行兩個(gè)3*3矩陣A、B相乘的例子。如207頁(yè)圖8.2所示。脈動(dòng)陣列結(jié)構(gòu)的主要特點(diǎn)：1、結(jié)構(gòu)簡(jiǎn)單、規(guī)整，模塊性強(qiáng)，可擴(kuò)充性好。非常適合用超大規(guī)模集成電路實(shí)現(xiàn)。第四頁(yè)，共37頁(yè)。2、PE間數(shù)據(jù)通信距離短、規(guī)則，使數(shù)據(jù)流和控制流的設(shè)計(jì)、同步控制等均簡(jiǎn)單規(guī)整。3、脈動(dòng)陣列中所有PE能同時(shí)運(yùn)算，具有極高的計(jì)算并行性，可通過(guò)流水獲得很高的運(yùn)算效率和吞吐率。4、脈動(dòng)陣列結(jié)構(gòu)的構(gòu)形與特定計(jì)算任務(wù)和算法密切相關(guān)，具有某種專用性，限制了應(yīng)用的范圍。這對(duì)VLSI是不利的。8.1.2通用的脈動(dòng)陣列結(jié)構(gòu)造成脈動(dòng)陣列機(jī)應(yīng)用范圍有限的關(guān)鍵因素是，受陣列結(jié)構(gòu)的通用性和i/o帶寬約束所限制的陣列結(jié)構(gòu)規(guī)模大小。第五頁(yè)，共37頁(yè)。發(fā)展通用脈動(dòng)陣列結(jié)構(gòu)的途徑主要有三種：1、通過(guò)增設(shè)附加的硬件，對(duì)陣列的拓?fù)浣Y(jié)構(gòu)和互連方式用可編程開(kāi)關(guān)進(jìn)行重構(gòu)，即經(jīng)程序重新配置陣列的結(jié)構(gòu)。2、用軟件把不同的算法映象到固定的陣列結(jié)構(gòu)上。3、探尋與問(wèn)題大小無(wú)關(guān)的脈動(dòng)陣列處理方法，以及VLSI運(yùn)算系統(tǒng)的分割矩陣算法，使它們可以克服陣列只能求解固定大小題目的缺陷，同時(shí)探尋發(fā)展適合一類計(jì)算問(wèn)題的通用算法和相應(yīng)的設(shè)置方案。第六頁(yè)，共37頁(yè)。8.2大規(guī)模并行處理機(jī)MPP

與機(jī)群系統(tǒng)8.2.1大規(guī)模并行處理機(jī)MPP由于VLSI和微處理器技術(shù)的發(fā)展，以及高科技應(yīng)用領(lǐng)域?qū)τ?jì)算機(jī)和通訊網(wǎng)絡(luò)在計(jì)算、處理和通信性能上不斷提出更高的要求，使發(fā)展大規(guī)模的并行處理成了20世紀(jì)80年代中期計(jì)算機(jī)發(fā)展的熱點(diǎn)。

大規(guī)模并行處理機(jī)MPP是由數(shù)百至數(shù)萬(wàn)個(gè)高性能、低成本的RISC微處理器用互連網(wǎng)絡(luò)互連而成。第七頁(yè)，共37頁(yè)。這種處理機(jī)可進(jìn)行中粒度和細(xì)粒度大規(guī)模并行處理，構(gòu)成SIMD或MIMD系統(tǒng)。它具有性能價(jià)格比高和可擴(kuò)展性好的優(yōu)點(diǎn)。

典型的大規(guī)模并行處理機(jī)MPP：參閱教材209頁(yè)相關(guān)內(nèi)容。MPP的系統(tǒng)軟件要求能讓用戶像使用單處理機(jī)那樣來(lái)使用MPP，性能卻要數(shù)倍于單處理機(jī)的，為此，操作系統(tǒng)采用微內(nèi)核和大外殼。內(nèi)核只提供中斷處理、進(jìn)程調(diào)度、進(jìn)程間簡(jiǎn)單通訊及其它最基本的功能，將大量的服務(wù)功能搬移到內(nèi)核之外。第八頁(yè)，共37頁(yè)。8.2.2機(jī)群系統(tǒng)

機(jī)群系統(tǒng)是將多個(gè)高性能的工作站或高檔微型計(jì)算機(jī)，使用高速的通信網(wǎng)絡(luò)加以互連組成的系統(tǒng)。

在并行程序設(shè)計(jì)和集成開(kāi)發(fā)環(huán)境的支持下，進(jìn)行統(tǒng)一調(diào)度和協(xié)調(diào)處理，以實(shí)現(xiàn)對(duì)中、粗細(xì)粒度并行進(jìn)程的高效并行處理。機(jī)群系統(tǒng)中的主機(jī)和網(wǎng)絡(luò)可以是同構(gòu)的，也可以是異構(gòu)的。主機(jī)間的通訊主要采用消息傳遞。從結(jié)構(gòu)和結(jié)點(diǎn)間的通訊來(lái)看，是一種分布式存儲(chǔ)方式，而從用戶來(lái)看，表現(xiàn)出是一個(gè)完整的并行系統(tǒng)。

第九頁(yè)，共37頁(yè)。機(jī)群系統(tǒng)比起傳統(tǒng)的并行處理系統(tǒng)有如下幾個(gè)明顯的優(yōu)點(diǎn)：1、系統(tǒng)有高的性能價(jià)格比。2、系統(tǒng)的開(kāi)發(fā)周期短。3、系統(tǒng)的可擴(kuò)展性好。4、系統(tǒng)的資源利用率高。5、用戶投資風(fēng)險(xiǎn)小。6、用戶編程方便。

基于機(jī)群系統(tǒng)的上述優(yōu)點(diǎn)，使之已成為當(dāng)前并行處理系統(tǒng)研究的熱點(diǎn)。第十頁(yè)，共37頁(yè)。8.3數(shù)據(jù)流機(jī)8.3.1數(shù)據(jù)驅(qū)動(dòng)的概念

VonNeumann型計(jì)算機(jī)的基本特點(diǎn)是在程序計(jì)數(shù)器集中控制下，順次地執(zhí)行指令。因此，是以控制流方式工作的。其本質(zhì)仍是指令在程序計(jì)數(shù)器控制下順序執(zhí)行，這就很難最大限度地發(fā)掘出計(jì)算的并行性。開(kāi)發(fā)并行性的另一種途徑是改用數(shù)據(jù)驅(qū)動(dòng)的數(shù)據(jù)流方式來(lái)工作。

數(shù)據(jù)驅(qū)動(dòng)的數(shù)據(jù)流方式指的是，只要一條或一組指令所要求的操作數(shù)全部就緒，就可立即激發(fā)相應(yīng)的指令或指令組執(zhí)行。執(zhí)行結(jié)果的輸出將送往等待這一數(shù)據(jù)的下一條或下一組指令。第十一頁(yè)，共37頁(yè)。在這種機(jī)器上不需要程序計(jì)數(shù)器，指令的執(zhí)行基本上是無(wú)序的，完全受數(shù)據(jù)流的驅(qū)動(dòng)，與指令在程序中出現(xiàn)的先后順序無(wú)關(guān)。只要數(shù)據(jù)不相關(guān)和資源可以利用，就可以并行，因而最有利于計(jì)算并行性的開(kāi)發(fā)。

控制驅(qū)動(dòng)的控制流方式的特點(diǎn)：通過(guò)訪問(wèn)共享存儲(chǔ)單元讓數(shù)據(jù)在指令之間傳遞；指令執(zhí)行的順序性隱含于控制流中，可以顯式使用專門(mén)的控制操作符來(lái)實(shí)現(xiàn)并行處理；指令執(zhí)行順序受程序計(jì)數(shù)器控制，即受控制令牌支配。

數(shù)據(jù)驅(qū)動(dòng)的數(shù)據(jù)流方式的特點(diǎn)：沒(méi)有通常的共享變量的概念，即沒(méi)有共享存儲(chǔ)數(shù)據(jù)的概念。第十二頁(yè)，共37頁(yè)。指令執(zhí)行順序只受指令中數(shù)據(jù)相關(guān)性的制約，數(shù)據(jù)是以數(shù)據(jù)令牌方式直接在指令之間傳遞的。1、數(shù)據(jù)令牌的概念

實(shí)質(zhì)上是一種表示某一操作數(shù)或參數(shù)已準(zhǔn)備就緒的標(biāo)志。一旦執(zhí)行某一操作的所有操作數(shù)令牌都到齊，則標(biāo)志著這一才操作是什么操作，以及操作結(jié)果所得出的數(shù)據(jù)令牌應(yīng)發(fā)送到哪些等待此數(shù)據(jù)令牌的操作的第幾個(gè)操作數(shù)部位等相關(guān)信息，都將作為一個(gè)消息包，傳送到處理單元或操作不見(jiàn)并予執(zhí)行。

第十三頁(yè)，共37頁(yè)。2、數(shù)據(jù)流計(jì)算模型（1）數(shù)據(jù)驅(qū)動(dòng)計(jì)算：其操作是按輸入數(shù)據(jù)可用性決定的次序進(jìn)行。只要所要求的輸入數(shù)據(jù)全部就緒，即可驅(qū)動(dòng)操作執(zhí)行，是一種提前求值策略。（2）需求驅(qū)動(dòng)計(jì)算：其操作按數(shù)據(jù)需求所決定的次序進(jìn)行。按需求值，只有當(dāng)某一函數(shù)需要用到某一自變量時(shí)，才驅(qū)動(dòng)對(duì)該變量的求值操作，是一種滯后求值策略。該模型可以減少許多不必要的值，輔助開(kāi)銷(xiāo)少，有助于提高系統(tǒng)的效率。第十四頁(yè)，共37頁(yè)。本節(jié)所討論的數(shù)據(jù)流機(jī)一般是指數(shù)據(jù)驅(qū)動(dòng)計(jì)算，需求驅(qū)動(dòng)更適合于面向函數(shù)程序設(shè)計(jì)的計(jì)算機(jī)。從語(yǔ)義上講，數(shù)據(jù)流是基于異步性和函數(shù)性的一種計(jì)算模型。所謂異步性，是指一旦操作數(shù)到齊就開(kāi)始操作，這是數(shù)據(jù)流計(jì)算機(jī)開(kāi)拓并行性的基礎(chǔ)。所謂函數(shù)性，是指每一數(shù)據(jù)流操作都是消耗一組輸入值，產(chǎn)生一組輸出值而不發(fā)生副作用，具有變量出現(xiàn)在賦值語(yǔ)句左邊僅一次的單賦值特性，從而保證任何兩個(gè)并發(fā)操作可以按任意次序執(zhí)行，而不會(huì)發(fā)生干擾。第十五頁(yè)，共37頁(yè)。8.3.2數(shù)據(jù)流程序圖和語(yǔ)言數(shù)據(jù)流程序圖可以看成是數(shù)據(jù)流機(jī)器的機(jī)器語(yǔ)言。數(shù)據(jù)流程序圖是用結(jié)點(diǎn)和有向弧組成的有向圖。

它有多個(gè)結(jié)點(diǎn)，并用一些弧把它們連接而成。每一個(gè)結(jié)點(diǎn)用圓圈或三角形或其它特殊符號(hào)表示，認(rèn)為是一種處理部件，結(jié)點(diǎn)內(nèi)的符號(hào)或字母表示一種操作，所以也稱操作符?；〈頂?shù)據(jù)令牌在結(jié)點(diǎn)間的流向。在數(shù)據(jù)流機(jī)中，根據(jù)這樣的數(shù)據(jù)流程序圖，通過(guò)一個(gè)分配器或分配程序，不斷分配適當(dāng)?shù)奶幚聿考?lái)實(shí)現(xiàn)操作符的操作。第十六頁(yè)，共37頁(yè)。例：教材213頁(yè)圖8.4和圖8.5表示了計(jì)算z=(a+b)*(a-b)的數(shù)據(jù)流程序圖。數(shù)據(jù)流程序圖中程序的執(zhí)行過(guò)程是一種數(shù)據(jù)不斷進(jìn)行激發(fā)的過(guò)程。一個(gè)操作符的執(zhí)行從每個(gè)輸入端只吸收一個(gè)令牌，進(jìn)行計(jì)算后，只在有效的輸出端上產(chǎn)生一個(gè)輸出令牌。這種單賦值規(guī)則使結(jié)點(diǎn)在生成和消亡時(shí)，可以有序地分配和回收值，而不會(huì)產(chǎn)生競(jìng)爭(zhēng)。1、常用的數(shù)據(jù)流結(jié)點(diǎn)（圖見(jiàn)214頁(yè)圖8.6和215頁(yè)圖8.7）（1）常數(shù)產(chǎn)生結(jié)點(diǎn)：沒(méi)有輸入端，只產(chǎn)生常數(shù)。第十七頁(yè)，共37頁(yè)。（2）算邏運(yùn)算操作結(jié)點(diǎn)：激發(fā)后輸出帶相應(yīng)操作結(jié)果的令牌。（3）復(fù)制操作結(jié)點(diǎn)（4）判定操作結(jié)點(diǎn)（5）控制類操作結(jié)點(diǎn)：T門(mén)控結(jié)點(diǎn)、F門(mén)控結(jié)點(diǎn)、開(kāi)關(guān)門(mén)控結(jié)點(diǎn)、歸并門(mén)控結(jié)點(diǎn)。2、數(shù)據(jù)流機(jī)器語(yǔ)言的表示方法（1）數(shù)據(jù)流程序圖：用結(jié)點(diǎn)和有向弧組成的有向圖。（2）活動(dòng)模片：數(shù)據(jù)流程序可以看成是一組活動(dòng)模片組成的集合體。每一個(gè)活動(dòng)模片相應(yīng)于第十八頁(yè)，共37頁(yè)。數(shù)據(jù)流程序圖中一個(gè)或多個(gè)操作結(jié)點(diǎn)，且由4個(gè)域組成，它們是一個(gè)操作碼域、兩個(gè)操作數(shù)域和一個(gè)目的域。（圖見(jiàn)216頁(yè)圖8.10和圖8.11）

活動(dòng)模片就是結(jié)點(diǎn)在數(shù)據(jù)流機(jī)器內(nèi)部具體實(shí)現(xiàn)時(shí)的存儲(chǔ)器映象。數(shù)據(jù)流程序圖實(shí)際上是數(shù)據(jù)流機(jī)的機(jī)器語(yǔ)言，優(yōu)點(diǎn)是直觀易懂，但是編程效率很低，難以為一般用戶所接受。所以要研究適合于數(shù)據(jù)流機(jī)使用的高級(jí)語(yǔ)言。主要是發(fā)展新的、適合于數(shù)據(jù)流控制機(jī)制的高級(jí)語(yǔ)言。目前主要有單賦值語(yǔ)言和函數(shù)程序設(shè)計(jì)語(yǔ)言。另外還有邏輯程序設(shè)計(jì)語(yǔ)言PROLOG這樣一類的描述式語(yǔ)言，也可以作為數(shù)據(jù)流機(jī)的高級(jí)語(yǔ)言。第十九頁(yè)，共37頁(yè)。單賦值語(yǔ)言是指在程序中，每個(gè)變量均只賦值一次，即同一變量名在不同賦值語(yǔ)句的左部最多只出現(xiàn)一次。因此，實(shí)際上并沒(méi)有傳統(tǒng)計(jì)算機(jī)中變量的概念，只是一種值名。例如：一個(gè)程序允許出現(xiàn)如下語(yǔ)句序列：

C=A+BC=C*DF=(C-D)/E則所使用的語(yǔ)言就不是單賦值語(yǔ)言。若這時(shí)只允許程序?qū)懗桑?/p>

C=A+BC1=C*DF=(C1-D)/E其所用的語(yǔ)言就體現(xiàn)出單賦值的規(guī)則和要求了。單賦值語(yǔ)言的語(yǔ)義清楚，程序中的并行性易于被編譯程序所開(kāi)發(fā)。第二十頁(yè)，共37頁(yè)。8.3.3數(shù)據(jù)流計(jì)算機(jī)的結(jié)構(gòu)根據(jù)對(duì)數(shù)據(jù)令牌處理的方式不同，可以把數(shù)據(jù)流計(jì)算機(jī)的結(jié)構(gòu)分為靜態(tài)和動(dòng)態(tài)兩類。

靜態(tài)數(shù)據(jù)流機(jī)的數(shù)據(jù)令牌沒(méi)加標(biāo)號(hào)。為正確工作，任意給定時(shí)刻當(dāng)結(jié)點(diǎn)操作時(shí)，其任何一條輸入弧上只能有一個(gè)數(shù)據(jù)令牌。只有當(dāng)結(jié)點(diǎn)的所有輸入弧上都有數(shù)據(jù)令牌時(shí)，該結(jié)點(diǎn)才被激活執(zhí)行相應(yīng)的操作。靜態(tài)數(shù)據(jù)流機(jī)不支持遞歸的并發(fā)激活，只支持一般的循環(huán)。

動(dòng)態(tài)數(shù)據(jù)流機(jī)最主要的特點(diǎn)是讓令牌帶上標(biāo)記，使得在任意給定時(shí)刻，數(shù)據(jù)流程序圖任何一條弧上允許出現(xiàn)多個(gè)帶不同標(biāo)記的令牌。令牌的標(biāo)記是令牌附帶的一個(gè)能識(shí)別該令牌時(shí)間先后第二十一頁(yè)，共37頁(yè)。相對(duì)關(guān)系的標(biāo)號(hào)，有的機(jī)器上也稱其為顏色。動(dòng)態(tài)數(shù)據(jù)流機(jī)都讓數(shù)據(jù)令牌帶有標(biāo)記，通過(guò)對(duì)令牌標(biāo)記的配對(duì)來(lái)支持遞歸的并發(fā)激活。8.3.4數(shù)據(jù)流機(jī)器存在的問(wèn)題數(shù)據(jù)流計(jì)算機(jī)在提高并行處理效能上有著非常顯著的長(zhǎng)處，但也存在一定問(wèn)題。1、數(shù)據(jù)流機(jī)主要目的是為了提高操作級(jí)并行的開(kāi)發(fā)水平，但如果題目本身數(shù)據(jù)相關(guān)性很強(qiáng)，內(nèi)涵并行成分并不多時(shí)，就會(huì)是效率比傳統(tǒng)的VonNeumann型機(jī)還要低。2、在數(shù)據(jù)流機(jī)中為給數(shù)據(jù)建立、識(shí)別、處理標(biāo)記，需要花費(fèi)較多的輔助開(kāi)銷(xiāo)和較大的存儲(chǔ)空間。但如果不使用標(biāo)記則無(wú)法遞歸并會(huì)降低并行能力。第二十二頁(yè)，共37頁(yè)。3、數(shù)據(jù)流機(jī)不保存數(shù)組。數(shù)據(jù)流機(jī)對(duì)標(biāo)量運(yùn)算有利，對(duì)數(shù)組、遞歸及其它高級(jí)操作較難管理。4、數(shù)據(jù)流語(yǔ)言的變量代表數(shù)值而不是存儲(chǔ)單元的位置，使程序員無(wú)法控制存儲(chǔ)分配。5、數(shù)據(jù)流機(jī)互連網(wǎng)絡(luò)設(shè)計(jì)困難，輸入/輸出系統(tǒng)仍不夠完善。6、數(shù)據(jù)流機(jī)沒(méi)有程序計(jì)數(shù)器，給診斷和維護(hù)帶來(lái)困難。因此，目前數(shù)據(jù)流機(jī)尚難批量生產(chǎn)，仍需進(jìn)一步改進(jìn)。第二十三頁(yè)，共37頁(yè)。8.4歸約機(jī)

歸約機(jī)和數(shù)據(jù)流機(jī)一樣，都是基于數(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á)式的歸約。

函數(shù)式語(yǔ)言是由所有函數(shù)表達(dá)式的集合、所有目標(biāo)的集合及所有由函數(shù)表達(dá)式到目標(biāo)的函數(shù)集合3部分組成。函數(shù)是其基本成分，是從一批目標(biāo)到另一批目標(biāo)的映射。第二十四頁(yè)，共37頁(yè)。

函數(shù)式程序本質(zhì)上是屬于解釋執(zhí)行方式，從函數(shù)式程序的歸約來(lái)看，機(jī)器內(nèi)部通常采用鏈表的存儲(chǔ)結(jié)構(gòu)，且依賴于動(dòng)態(tài)存儲(chǔ)分配，存儲(chǔ)空間的大小無(wú)法預(yù)測(cè)，需要頻繁地進(jìn)行空白單元的回收，使空間、時(shí)間開(kāi)銷(xiāo)都較大，頻繁的函數(shù)應(yīng)用和參數(shù)傳遞，加上自變量動(dòng)態(tài)取值，同樣的計(jì)算往往要重復(fù)多次。所以，必須針對(duì)函數(shù)程序設(shè)計(jì)語(yǔ)言的特點(diǎn)和問(wèn)題來(lái)設(shè)計(jì)支持函數(shù)式程序運(yùn)行的計(jì)算機(jī)，這就是歸約機(jī)。第二十五頁(yè)，共37頁(yè)。（1）歸約機(jī)的一般特點(diǎn)1、歸約機(jī)應(yīng)當(dāng)是面向函數(shù)式語(yǔ)言，或以函數(shù)式語(yǔ)言為機(jī)器語(yǔ)言的非Neumann型機(jī)器。其內(nèi)部結(jié)構(gòu)應(yīng)不同于Neumann型機(jī)器。2、具有大容量物理存儲(chǔ)器并采用大虛存容量的虛擬存儲(chǔ)器，具備高效的動(dòng)態(tài)存儲(chǔ)分配和管理的軟硬件支持，滿足歸約機(jī)對(duì)動(dòng)態(tài)存儲(chǔ)分配及所需存儲(chǔ)空間大的要求。3、處理部分應(yīng)當(dāng)是一種有多個(gè)處理器或多個(gè)處理機(jī)并行的結(jié)構(gòu)形式，以發(fā)揮函數(shù)式程序并行處理的特長(zhǎng)。有多個(gè)處理機(jī)可高度并行。第二十六頁(yè)，共37頁(yè)。4、采用適合于函數(shù)式程序運(yùn)行的多處理機(jī)互連的結(jié)構(gòu)，最好采用樹(shù)型方式的互連結(jié)構(gòu)或多層次復(fù)合的互連結(jié)構(gòu)形式。5、為減少進(jìn)程調(diào)度及進(jìn)程間通訊開(kāi)銷(xiāo)，盡量把運(yùn)行進(jìn)程的結(jié)點(diǎn)機(jī)安排成緊靠該進(jìn)程所需用的數(shù)據(jù)，并使運(yùn)行時(shí)需相互通訊的進(jìn)程所占用的處理機(jī)也靠近，并使各處理機(jī)的負(fù)荷平衡。（2）歸約機(jī)的分類

根據(jù)機(jī)器所用歸約方式的不同，分為串歸約機(jī)和圖歸約機(jī)兩類。

串歸約機(jī)可看成是一種特殊的符號(hào)串處理機(jī)，函數(shù)定義、表達(dá)式和目標(biāo)都以字符串的形式存儲(chǔ)于機(jī)器中。函數(shù)式語(yǔ)言源程序可以不經(jīng)翻譯，直接在串歸約機(jī)上進(jìn)行處理。第二十七頁(yè)，共37頁(yè)。串歸約機(jī)存在的主要問(wèn)題是不能共享子表達(dá)式，多次應(yīng)用就得多次復(fù)制和求值運(yùn)算，所以時(shí)間和空間的輔助開(kāi)銷(xiāo)相對(duì)都比較大。

圖歸約機(jī)采取將函數(shù)定義、表達(dá)式和目標(biāo)以圖的形式存儲(chǔ)于機(jī)器中，圖是其處理對(duì)象。最常用的圖是二叉數(shù)和N叉數(shù)。采用給每個(gè)結(jié)點(diǎn)設(shè)置指針的方式來(lái)存儲(chǔ)圖。

例：以表達(dá)式z=(y-1)*(y+x)為例來(lái)說(shuō)明串歸約和圖歸約的工作原理。（教材219頁(yè)圖8.12)總之，歸約方式體現(xiàn)了按需求驅(qū)動(dòng)的思想，根據(jù)對(duì)函數(shù)求值的需求來(lái)激活相應(yīng)指令。而且，不論是采用先內(nèi)后外，或先外后內(nèi)，或先右后左，還是先左后右的順序歸約，也不論是采用串行歸約，還是并行歸約，都不影響最終結(jié)果值。第二十八頁(yè)，共37頁(yè)。8.5智能機(jī)8.5.1智能信息處理與智能機(jī)

智能機(jī)主要是一個(gè)知識(shí)信息處理系統(tǒng)，必須解決好有關(guān)知識(shí)的獲取、表示、存儲(chǔ)、處理和應(yīng)用等諸方面的問(wèn)題，使計(jì)算機(jī)能更好地模擬人類大腦的思維活動(dòng)，提高學(xué)習(xí)、推理、判斷和問(wèn)題求解的能力。知識(shí)的表現(xiàn)形式可以是自然語(yǔ)言、語(yǔ)音、圖形、圖象、文件等，有些很難規(guī)范和提取，有些很難在機(jī)器中表示。不少知識(shí)是不完全、不確定和模糊的，有些可能屬于直覺(jué)、聯(lián)想、體驗(yàn)等非邏輯范疇。人工智能問(wèn)題的求解往往是一種非確定性的試探推理過(guò)程，往往搜索的范圍很廣，也無(wú)確定的算法可循。第二十九頁(yè)，共37頁(yè)。

智能機(jī)是具有高智能的計(jì)算機(jī)，它是一個(gè)知識(shí)信息的處理系統(tǒng)。智能機(jī)能不斷地學(xué)習(xí)、積累、完善知識(shí)，利用知識(shí)進(jìn)行推理、判斷和求解問(wèn)題。智能機(jī)是一種結(jié)構(gòu)動(dòng)態(tài)可變，易擴(kuò)充的開(kāi)放式系統(tǒng)。智能機(jī)應(yīng)當(dāng)提供良好的人—機(jī)界面，帶有自然語(yǔ)言、聲音、文字、圖形、圖象等多種智能接口。智能機(jī)的3個(gè)重要組成部分是：知識(shí)庫(kù)機(jī)、推理機(jī)和智能接口處理機(jī)。第三十頁(yè)，共37頁(yè)。8.5.2智能機(jī)的結(jié)構(gòu)和機(jī)器語(yǔ)言智能機(jī)的結(jié)構(gòu)框圖如221頁(yè)圖8.13所示。

知識(shí)庫(kù)機(jī)相當(dāng)于傳統(tǒng)機(jī)器的主存、虛擬存儲(chǔ)器和文件存儲(chǔ)器的結(jié)合。由于要處理的信息90%以上都是非數(shù)值型的，其處理主要是代數(shù)運(yùn)算。知識(shí)庫(kù)的基礎(chǔ)是關(guān)系數(shù)據(jù)庫(kù)和相關(guān)代數(shù)機(jī)的集合。知識(shí)庫(kù)以高效可用形式存放有各種知識(shí)、語(yǔ)義和規(guī)則，通常又有通用知識(shí)庫(kù)和專用知識(shí)庫(kù)之分。通用知識(shí)庫(kù)的知識(shí)由系統(tǒng)提供，用于存放用戶要用到的通用知識(shí)。知識(shí)庫(kù)機(jī)的效能直接影響整個(gè)智能機(jī)的