計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)：第五章 并行處理機(jī)和多處理機(jī)

1、二、 并行處理技術(shù)的發(fā)展三、 陣列處理機(jī)原理四、 互連網(wǎng)絡(luò)五、 多處理機(jī)第五章 并行處理機(jī)和多處理機(jī)一、 概述一.并行性概念在數(shù)值計(jì)算，數(shù)據(jù)處理，信息處理或人工智能求解過(guò)程中，可能存在某些能同時(shí)進(jìn)行運(yùn)算或操作的部分。在同一時(shí)刻或同一時(shí)間間隔內(nèi)完成多個(gè)性質(zhì)相同或不同的任務(wù)。同時(shí)性（simultaneity）:指兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā)生在多個(gè)資源中。并發(fā)性（concurrency）:指兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生在多個(gè)資源中。并行處理技術(shù)涉及：并行結(jié)構(gòu)、并行軟件、并行算法等多個(gè)方面。一、 概述第五章 并行處理機(jī)和多處理機(jī)1從計(jì)算機(jī)系統(tǒng)處理數(shù)據(jù)的并行性來(lái)看，并行性等級(jí)從低到 高可分：位串字

2、串-通常指?jìng)鹘y(tǒng)的串行單處理機(jī)。 位并字串-通常指?jìng)鹘y(tǒng)的并行單處理機(jī)。 字并位串-同時(shí)對(duì)多個(gè)字的同一位（稱(chēng)位片）進(jìn)行處理 ，開(kāi)始進(jìn)入并行處理領(lǐng)域。 全并行-同時(shí)對(duì)多個(gè)字的全部或部分位組進(jìn)行處理。2從計(jì)算機(jī)信息加工步驟和階段看，并行性等級(jí)可分為：存儲(chǔ)器操作并行-并行存儲(chǔ)器系統(tǒng)和以相聯(lián)存儲(chǔ)器為核心構(gòu)成的相聯(lián)處理機(jī)。二. 并行的等級(jí)和分類(lèi)處理器操作步驟并行-可以是一條指令的取指、分析、執(zhí)行等操作步驟，也可以是具體運(yùn)算，如流水計(jì)算機(jī)。第五章 并行處理機(jī)和多處理機(jī)并行性的開(kāi)發(fā)還可以按程序大小劃分不同粒度的開(kāi)發(fā)方式。并行粒度（granularity）或顆粒規(guī)模（grain size）- 衡量軟件進(jìn)程所含計(jì)算

3、量的尺度。測(cè)量方法是數(shù)一下顆粒（程序段）中的指令數(shù)目。一般用細(xì)、中、粗來(lái)描述，決定并行處理的基本程序段。3. 程序劃分和粒度并行性粒度：每次并行處理的規(guī)模大小。用字母G表示 G=TW/TCTW：所有處理器進(jìn)行計(jì)算的時(shí)間總和；TC：所有處理器進(jìn)行通信的時(shí)間總和。（設(shè)系統(tǒng)共有P個(gè)處理器）當(dāng)TC較大時(shí)，通信量大，則G較小處理粒度較細(xì)。反之對(duì)于粗粒度的并行，通信量較小。處理器操作并行-為支持向量、數(shù)組運(yùn)算，可以通過(guò)重復(fù)設(shè)置處理單元進(jìn)行，如并行處理機(jī)指令、任務(wù)、作業(yè)并行-較高級(jí)并行，屬于MIMD計(jì)算機(jī)。第五章 并行處理機(jī)和多處理機(jī)時(shí)延（TC ）機(jī)器各子系統(tǒng)間通信開(kāi)銷(xiāo)的時(shí)間量度。如：存貯時(shí)延是處理機(jī)訪問(wèn)存

4、貯器所需時(shí)間；同步時(shí)延是兩臺(tái)處理機(jī)互相同步所需的時(shí)間。通信時(shí)延問(wèn)題：計(jì)算機(jī)中不同的時(shí)延是由機(jī)器內(nèi)部系統(tǒng)結(jié)構(gòu)，實(shí)現(xiàn)技術(shù)和通信方式?jīng)Q定。系統(tǒng)結(jié)構(gòu)和實(shí)現(xiàn)技術(shù)將會(huì)影響子系統(tǒng)間容許時(shí)延的選擇?？梢杂闷胶饬６群蜁r(shí)延的辦法來(lái)求得較好的計(jì)算機(jī)系統(tǒng)性能。處理機(jī)間通信引起的時(shí)延：除數(shù)據(jù)通路中的信號(hào)延遲外，還受到通信方式的影響。一般情況下n個(gè)處理任務(wù)互相通信時(shí)，它們之間需有n（n-1）/2 條通信鏈路。由此看出復(fù)雜性是以平方關(guān)系增長(zhǎng)，這將限制大型計(jì)算機(jī)系統(tǒng)中允許使用的處理機(jī)數(shù)量。 第五章 并行處理機(jī)和多處理機(jī)作業(yè)級(jí)（程序）任務(wù)級(jí)（過(guò)程或程序段）子任務(wù)級(jí)（例行程序或子程序）指令或語(yǔ)句循環(huán)或迭代級(jí)5級(jí)4級(jí)3級(jí)2級(jí)1通信

5、需求與調(diào)度開(kāi)銷(xiāo)并行程度粗粒度中粒度細(xì)粒度現(xiàn)代計(jì)算機(jī)程序運(yùn)行并行性級(jí)別 五種程序執(zhí)行級(jí)別體現(xiàn)了不同的算法粒度規(guī)模以及通信和控制要求的變化。級(jí)別越低，軟件進(jìn)程的粒度越細(xì)。一般情況，程序可在這些級(jí)別的組合狀態(tài)下運(yùn)行。第五章 并行處理機(jī)和多處理機(jī)（1）指令級(jí)：并行性發(fā)生在指令內(nèi)部微操作之間或指令之間。取決于程序的具體情況?？山柚趦?yōu)化編譯器開(kāi)發(fā)細(xì)粒度并行性，它能自動(dòng)檢測(cè)并行性并將源代碼換成運(yùn)行時(shí)系統(tǒng)能識(shí)別的并行形式。（2）循環(huán)級(jí)：相當(dāng)于迭代循環(huán)操作，典型循環(huán)包含的指令大約幾百條，循環(huán)級(jí)并行性是并行機(jī)或向量計(jì)算機(jī)上運(yùn)行的最優(yōu)程序結(jié)構(gòu)，并行處理主要由編譯器在循環(huán)級(jí)中進(jìn)行開(kāi)發(fā)。（3）子任務(wù)級(jí)：屬于中粒度。子

6、程序是在單處理機(jī)或多處理機(jī)的多道程序設(shè)計(jì)這一級(jí)進(jìn)行的。這一級(jí)并行性由算法設(shè)計(jì)者或程序員開(kāi)發(fā)而非用編譯器開(kāi)發(fā)。（4）任務(wù)級(jí)：這是與任務(wù)、過(guò)程、程序段、協(xié)同程序級(jí)相對(duì)應(yīng)的中粒度或粗粒度規(guī)模。典型粒度包含的指令幾千條，檢測(cè)本級(jí)的并行性比細(xì)粒度級(jí)困難得多，需要更多地涉及過(guò)程間的相關(guān)性分析。需編譯器支持。（5）作業(yè)（程序）級(jí)：對(duì)于少量幾臺(tái)高性能處理機(jī)構(gòu)成的超級(jí)計(jì)算機(jī)開(kāi)發(fā)這種粗粒度并行性切實(shí)可行。第五章 并行處理機(jī)和多處理機(jī)小結(jié)： 細(xì)粒度并行性常在指令級(jí)或循環(huán)級(jí)上借助于并行化或向量化編譯器來(lái)進(jìn)行開(kāi)發(fā)的。 任務(wù)或作業(yè)步驟（過(guò)程級(jí)）中粒度并行性開(kāi)發(fā)需要程序員和編譯器的共同作用。 開(kāi)發(fā)程序作業(yè)級(jí)的粗粒度并行性主

7、要取決于高效的操作系統(tǒng)和所用算法的效率。 共享變量通信常用于支持中、細(xì)粒度計(jì)算。消息傳遞型多計(jì)算機(jī)用于中粒度和粗粒度的計(jì)算。通常情況下，粒度越細(xì)，并行性潛力越大，通信和調(diào)度的開(kāi)銷(xiāo)也越大。細(xì)粒度能提供較高的并行度，但與粗粒度計(jì)算相比，其通信開(kāi)銷(xiāo)也較大。大規(guī)模并行性通常是在細(xì)粒度級(jí)上開(kāi)發(fā)。如：SIMD或MIMD計(jì)算機(jī)上開(kāi)發(fā)的數(shù)據(jù)并行性。第五章 并行處理機(jī)和多處理機(jī)提高計(jì)算機(jī)系統(tǒng)的并行性的技術(shù)途徑： 時(shí)間重疊（Time Interleaving）：在并行性概念中引入時(shí)間因素。讓多個(gè)處理過(guò)程在時(shí)間上相互錯(cuò)開(kāi)，輪流重疊地使用同一套硬件設(shè)備的各個(gè)部分，以加快硬件周轉(zhuǎn)而贏得速度。資源重復(fù)（Resource

8、Replication）：并行性概念中引入空間因素。通過(guò)重復(fù)設(shè)置的硬件資源來(lái)提高系統(tǒng)可靠性或性能。例如，通過(guò)使用兩臺(tái)或多臺(tái)完全相同的計(jì)算機(jī)完成同樣的任務(wù)來(lái)提高可靠性。資源共享（Resource Sharing）：利用軟件的方法讓多個(gè)用戶(hù)按一定時(shí)間順序輪流地使用同一套資源，以提高其利用率，這樣相應(yīng)地提高整個(gè)系統(tǒng)的性能。例如多道程序分時(shí)系統(tǒng).二、 并行處理技術(shù)發(fā)展第五章 并行處理機(jī)和多處理機(jī)多道程序分時(shí)系統(tǒng)虛擬存儲(chǔ)器多終端遠(yuǎn)程終端分布處理系統(tǒng)局域計(jì)算機(jī)網(wǎng)通信處理機(jī)計(jì)算機(jī)網(wǎng)多存儲(chǔ)體多操作部件相聯(lián)處理機(jī)并行處理機(jī)同構(gòu)型多處理機(jī)系統(tǒng)可重構(gòu),容錯(cuò)多處理機(jī)緊密耦合系統(tǒng)先行控制高速緩存指令操作宏流水線異構(gòu)型多

9、處理機(jī)系統(tǒng)高級(jí)語(yǔ)言數(shù)據(jù)庫(kù)處理機(jī)松散耦合系統(tǒng)、專(zhuān)用外圍處理機(jī)多計(jì)算機(jī)系統(tǒng)單處理機(jī)資源共享資源重復(fù)時(shí)間重疊多機(jī)互連功能專(zhuān)用化網(wǎng)絡(luò)化 并行處理技術(shù)發(fā)展第五章 并行處理機(jī)和多處理機(jī)并行處理中的需研究的課題：（1）在處理機(jī)數(shù)目很多的情況下，要把任何一個(gè)問(wèn)題分成足夠多的并行過(guò)程（即任務(wù)分配）非常困難，并且也不是所有問(wèn)題都能做到這一點(diǎn)。（2）現(xiàn)有的并行算法絕大多數(shù)是由串行算法發(fā)展而來(lái)的，因此很難擺脫傳統(tǒng)串行的思維和處理方式方法的約束。（3）現(xiàn)有算法語(yǔ)言對(duì)并行性限制很大?，F(xiàn)行的SIMD和MIMD系統(tǒng)結(jié)構(gòu)仍然沒(méi)有擺脫傳統(tǒng)的以指令流為主導(dǎo)的Von Neumann模式。因指令相關(guān)和地址空間相關(guān)等矛盾的出現(xiàn)，使并行效

10、率受到嚴(yán)重的限制。（4）在并行處理過(guò)程中，各處理機(jī)間的通信開(kāi)銷(xiāo)有可能使并行處理技術(shù)得不償失。（5）并行處理技術(shù)的主要困難是軟件，軟件的關(guān)鍵在于如何高效地進(jìn)行存儲(chǔ)管理和機(jī)間通信，尤其是并行編譯程序發(fā)展，對(duì)發(fā)揮硬件特性改善系統(tǒng)性能影響更大。第五章 并行處理機(jī)和多處理機(jī)一、陣列處理機(jī)的基本構(gòu)成基本思路：陣列處理機(jī)是通過(guò)重復(fù)設(shè)置大量相同的處理單元PE，將它們按一定的方式互連，在統(tǒng)一的控制部件CU（Control Unit）控制下，對(duì)各自分配來(lái)的不同數(shù)據(jù)并行地完成同一條指令所規(guī)定的操作。它依靠操作一級(jí)的并行處理來(lái)提高系統(tǒng)的速度。陣列處理機(jī)的控制部件中進(jìn)行的是單指令流，因此與高性能單處理機(jī)一樣，指令基本上

11、是串行執(zhí)行，最多加上使用指令重疊或流水線的方式工作。指令重疊是將指令分成兩類(lèi)，把只適合串行處理的控制和標(biāo)量類(lèi)指令留給控制部件自己執(zhí)行，而把適合于并行處理的向量類(lèi)指令播送到所有處理單元，控制讓處于活躍的那些處理單元去并行執(zhí)行。因此這是一種標(biāo)量控制類(lèi)指令和向量類(lèi)指令的重疊執(zhí)行。三、 陣列處理機(jī)的原理第五章 并行處理機(jī)和多處理機(jī)二 、陣列處理機(jī)分類(lèi) 陣列處理機(jī)根據(jù)存貯器采用的組成方式不同分成兩種基本構(gòu)成。 （1）分布存貯的陣列處理機(jī) 各個(gè)處理單元設(shè)有局部存貯器存放分布式數(shù)據(jù)，只能被本處理單元直接訪問(wèn)。此種局部存貯器稱(chēng)為處理單元存貯器（Processing Element Memory）PEM。在控制

12、部件CU內(nèi)設(shè)有一個(gè)用來(lái)存放程序的主存貯器CUM。整個(gè)系統(tǒng)在CU統(tǒng)一控制下運(yùn)行系統(tǒng)程序的用戶(hù)程序。執(zhí)行主存中的用戶(hù)程序指令播送給各個(gè)PE，控制PE并行地執(zhí)行。 特點(diǎn)：處理器陣列一般是通過(guò)CU接到一臺(tái)管理處理機(jī)SC上，SC一般是一種通用計(jì)算機(jī)，用于管理整個(gè)系統(tǒng)的全部資源，完成系統(tǒng)維護(hù)、輸入輸出、用戶(hù)程序的匯編及向量化編譯、作業(yè)調(diào)度、存貯分配、設(shè)備管理、文件管理等操作系統(tǒng)的功能。第五章 并行處理機(jī)和多處理機(jī)PEM0PE0PEM1PE1PEMN-1PEN-1ICNCUCUMI/O接口DSC分布存貯器陣列處理機(jī)結(jié)構(gòu)第五章 并行處理機(jī)和多處理機(jī)ILLIAC-IV 結(jié)構(gòu) （分布存貯器并行處理機(jī)結(jié)構(gòu)）處理單元

13、陣列 由64個(gè)結(jié)構(gòu)完全相同的處理單元PEi 構(gòu)成，每個(gè)處理單元PEi字長(zhǎng)64位，PEMi為隸屬于PEi的局部存儲(chǔ)器，每個(gè)存儲(chǔ)器有2K字，全部PEi由CU統(tǒng)一管理，PEi都有一根方式位線，用來(lái)向CU傳送每個(gè)PEi的方式寄存器D中的方式位，使CU能了解各PEi的狀態(tài)是否活動(dòng)，作為控制它們工作的依據(jù)。 第五章 并行處理機(jī)和多處理機(jī)ILLIAC-IV的處理單元原理圖 012047PEM0。204701PEM1。204701PEM63。PE630163。ACAR0ACAR1ACAR2ACAR3ALU控制器CU累加器ADB.方位總線指令控制線CU總線.XDABRSPE1到PE63到PE0.CDBXDABR

14、SPE0第五章 并行處理機(jī)和多處理機(jī)PU間互連狀態(tài)：PUi代表64位處理單元PEi、所帶局部存貯器PEMi及存貯器邏輯部件總稱(chēng)。每臺(tái)PUi只能與它的4個(gè)近鄰連接。PUi的4個(gè)近鄰是PUi-1，PUi+1，PUi-8，PUi+8（mod64）。這種連接稱(chēng)為閉合螺線陣列。這種互連網(wǎng)絡(luò)中,當(dāng)數(shù)據(jù)從一個(gè)PUi傳送另一個(gè)PUi要走好幾步，中間經(jīng)過(guò)其它PUi轉(zhuǎn)送。傳送步數(shù)IN -1。（N為PEi總數(shù)）當(dāng)N=64時(shí)，最多步數(shù)為7。在每次數(shù)據(jù)傳送操作時(shí)由軟件算出最短路徑。 第五章 并行處理機(jī)和多處理機(jī)PU16PU0PU8PU7PU55PU63PU0PU1PU7PU8PU9PU15PU56PU57PU63PU0

15、PU1PU7PU56PU57PU58ILLIAC-IV的處理單元互連圖 將PU63傳送到PU10，最快可經(jīng)PU63PU7PU8PU9PU10。 第五章 并行處理機(jī)和多處理機(jī)控制器的功能有以下五個(gè)方面： 對(duì)指令流進(jìn)行控制和譯碼，包括執(zhí)行一整套標(biāo)量操作指 令； 向各處理單元發(fā)出執(zhí)行數(shù)組操作指令所需的控制信號(hào)； 產(chǎn)生和向所有處理單元廣播的公共的地址部分； 產(chǎn)生和向所有處理單元廣播的公共數(shù)據(jù)； 接收和處理由各PE（計(jì)算出錯(cuò)時(shí)）、系統(tǒng)I/O操作以及B6700所生產(chǎn)的陷阱中斷信號(hào)。陣列控制器 除了對(duì)陣列的處理單元實(shí)行控制以外，還能利用本身的內(nèi)部資源執(zhí)行一整套指令，用以完成標(biāo)量操作，在時(shí)間上與各PE的數(shù)組操

16、作重疊起來(lái)。 第五章 并行處理機(jī)和多處理機(jī)I/O系統(tǒng) 由磁盤(pán)文件系統(tǒng)DFS、I/O分系統(tǒng)和B6700組成， 完成輸入輸出及其他管理功能。 ILLIAC-IV系統(tǒng)的操作系統(tǒng)，連同編譯程序、匯編程序、輸入輸出服務(wù)子程序等都駐留在宿主機(jī)B6700中，處理單元陣列就像是宿主機(jī)的一臺(tái)專(zhuān)門(mén)作向量處理的后端機(jī)?；蛘哒f(shuō)宿主機(jī)是處理單元陣列的一臺(tái)輸入輸出處理機(jī)。 第五章 并行處理機(jī)和多處理機(jī)（2）集中式共享存貯的陣列處理機(jī)特點(diǎn)：每個(gè)PE沒(méi)有局部存儲(chǔ)器，存儲(chǔ)模塊以集中形式為所有PE共享，互連網(wǎng)絡(luò)ICN受CU控制。 ICNPE0PE1PEN-1MM0MM1MMK-1CUSCI/O-CHI/OSM具有共享存貯器陣列處

17、理機(jī)結(jié)構(gòu)KN互連網(wǎng)絡(luò)ICN的作用不同第五章 并行處理機(jī)和多處理機(jī)指令譯碼控制部件處理器存儲(chǔ)器NW2NW117個(gè)存儲(chǔ)塊16個(gè)處理單元對(duì)準(zhǔn)網(wǎng)絡(luò)對(duì)準(zhǔn)網(wǎng)絡(luò)BSP的五級(jí)數(shù)據(jù)流水線構(gòu)圖 （集中式共享存貯器）（1）并行處理機(jī)（2）控制處理器（3）文件存儲(chǔ)器（4）對(duì)準(zhǔn)網(wǎng)絡(luò)（5）BSP的五級(jí) 數(shù)據(jù)流水線示例：Burroughs公司與依里諾大學(xué)聯(lián)合研制的科學(xué)處理機(jī)BSP（Burroughs Scientific Processor）第五章 并行處理機(jī)和多處理機(jī)作用：（1）由17個(gè)存儲(chǔ)器模塊并行讀出16個(gè)操作數(shù)；（2）經(jīng)對(duì)準(zhǔn)網(wǎng)絡(luò)NW1將16個(gè)操作數(shù)重新排列成16個(gè)處理單元所需要的次 序；（3）將排列好的16個(gè)操作送

18、到并行處理單元完成操作；（4）所得的16個(gè)結(jié)果經(jīng)過(guò)對(duì)準(zhǔn)網(wǎng)絡(luò)NW2重新排列成17個(gè)存儲(chǔ)器模塊所需要的次序；（5）寫(xiě)入存儲(chǔ)器；第五章 并行處理機(jī)和多處理機(jī)共同特點(diǎn)：可以通過(guò)各種途徑把它們轉(zhuǎn)化成為對(duì)數(shù)組或向量的處理，利用多個(gè)處理單元對(duì)向量或數(shù)組所包含的各個(gè)分量同時(shí)進(jìn)行運(yùn)算，從而易于獲得很高的處理速度。三陣列處理機(jī)的特點(diǎn)并行處理機(jī)有如下特點(diǎn)：（1）利用資源重復(fù)（空間因素）而非時(shí)間重疊。（2）利用同時(shí)性而非并發(fā)性。（3）提高運(yùn)算速度主要是靠增大處理單元個(gè)數(shù)，比起向量流水線處理機(jī)主要依靠縮短時(shí)鐘周期來(lái)說(shuō)，速度提高的潛力要大得多。（4）使用簡(jiǎn)單而又規(guī)整的互連網(wǎng)絡(luò)來(lái)確定多個(gè)處理單元之間的連接模式。 （5）并行

19、處理機(jī)（陣列機(jī)）研究必須與并行算法研究密切結(jié)合，使之適應(yīng)性更強(qiáng)，應(yīng)用面更廣。第五章 并行處理機(jī)和多處理機(jī)概念：一種由開(kāi)關(guān)元件，按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的，用來(lái)實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部的多個(gè)功能部件或者是多個(gè)處理機(jī)之間的相互連接。 MIMD計(jì)算機(jī)SIMD計(jì)算機(jī)四、 互連網(wǎng)絡(luò)第五章 并行處理機(jī)和多處理機(jī)IPMNSM1SM2SMnPIONCnPnLMnC1P1LM1 IPCN磁盤(pán)部件磁帶部件打印機(jī)終端網(wǎng)絡(luò)（共享I/O和外圍設(shè)備）常用多處理機(jī)系統(tǒng)的互連結(jié)構(gòu)圖 .第五章 并行處理機(jī)和多處理機(jī)互連網(wǎng)絡(luò)的特性 網(wǎng)絡(luò)規(guī)模：網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)。 結(jié)點(diǎn)度：與結(jié)點(diǎn)相連接的邊（即鏈路或通道）數(shù)，用d表示。結(jié)點(diǎn)度是入度、出

20、度之和。 距離： 兩結(jié)點(diǎn)之間相連的最少邊數(shù)。 網(wǎng)絡(luò)直徑：它是網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)之間距離的最大值。 等分寬度：某一網(wǎng)絡(luò)被切成相等的兩半時(shí)，沿切口的最小邊數(shù)（通道），用b表示。 結(jié)點(diǎn)間的線長(zhǎng)：兩個(gè)結(jié)點(diǎn)間線的長(zhǎng)度。 對(duì)稱(chēng)性：從任何結(jié)點(diǎn)看拓?fù)浣Y(jié)構(gòu)都是一樣。對(duì)稱(chēng)網(wǎng)絡(luò)較易實(shí)現(xiàn)，編程也較容易。 第五章 并行處理機(jī)和多處理機(jī) 機(jī)器A 機(jī)器B 連接兩臺(tái)計(jì)算機(jī)的簡(jiǎn)單網(wǎng)絡(luò)一臺(tái)機(jī)器發(fā)送消息給另一臺(tái)機(jī)器時(shí)，發(fā)送方的步驟如下：（1） 應(yīng)用程序把要發(fā)送的數(shù)據(jù)拷貝到操作系統(tǒng)的緩沖區(qū)。（2） 操作系統(tǒng)根據(jù)要發(fā)送的數(shù)據(jù)計(jì)算出檢查和，并把它加在消息中，同時(shí)啟動(dòng)超時(shí)計(jì)數(shù)器。（3） 操作系統(tǒng)把緩沖區(qū)中的數(shù)據(jù)送到網(wǎng)絡(luò)接口硬件并通知硬件開(kāi)

21、始發(fā)送消息。第五章 并行處理機(jī)和多處理機(jī)消息包的接收步驟：（1） 系統(tǒng)把數(shù)據(jù)從網(wǎng)絡(luò)接口硬件數(shù)據(jù)拷貝到操作系統(tǒng)緩沖區(qū)。（2） 系統(tǒng)根據(jù)接收到的數(shù)據(jù)計(jì)算出檢查和。（3） 如果數(shù)據(jù)通過(guò)檢查，系統(tǒng)把接收到的數(shù)據(jù)拷貝到用戶(hù)地址空間并啟動(dòng)應(yīng)用程序繼續(xù)執(zhí)行。第五章 并行處理機(jī)和多處理機(jī) 發(fā)送方 開(kāi)銷(xiāo)（5） 傳輸時(shí)間（2） 發(fā)送方 “飛行”時(shí)間（3） 傳輸時(shí)間 接收方開(kāi)銷(xiāo)（6） 接收方 傳輸時(shí)延（4） 總時(shí)延 互連網(wǎng)絡(luò)的傳輸性能參數(shù) 傳輸時(shí)延=“飛行”時(shí)間+傳輸時(shí)間一個(gè)消息的總時(shí)延 = 發(fā)送方開(kāi)銷(xiāo) + “飛行”時(shí)間 + 消息長(zhǎng)度/頻寬（1） +接收方開(kāi)銷(xiāo) 第五章 并行處理機(jī)和多處理機(jī)概念：表示互連網(wǎng)絡(luò)的出端號(hào)

22、和入端號(hào)的一一對(duì)應(yīng)關(guān)系。 作用：對(duì)于所有的0iN-1，同時(shí)存在入端j連至出端f（j）的對(duì)應(yīng)關(guān)系。當(dāng)互連函數(shù)用來(lái)實(shí)現(xiàn)處理機(jī)之間數(shù)據(jù)變換時(shí)，互連函數(shù)也反映了網(wǎng)絡(luò)輸入數(shù)組與輸出數(shù)組間對(duì)應(yīng)的排列關(guān)系或者置換關(guān)系。 互連函數(shù)有三種表示法： 輸入輸出對(duì)應(yīng)表示法 循環(huán)表示法 函數(shù)表示法 （一） 互聯(lián)函數(shù)第五章 并行處理機(jī)和多處理機(jī)1、輸入輸出對(duì)應(yīng)表示法 0變換為f(0),1變換為f(1),N-1變換成f(N-1)。 f是互連函數(shù)。2、 循環(huán)表示法 f（X0）= X1，f（X1）= X2，f（Xj）= Xj+1， f（Xk-1）= X0，其中Xi為結(jié)點(diǎn)編號(hào)，這里k為循環(huán)長(zhǎng)度。第五章 并行處理機(jī)和多處理機(jī)3、

23、函數(shù)表示法 如x：bn-1bn-2bib0，互連函數(shù)對(duì)應(yīng)地表示為f（bn-1bn-2bib0）。 例如交換置換： E（ bn-1bn-2bib0 ）= bn-1bn-2bib0 它表示實(shí)現(xiàn)二進(jìn)制地址編號(hào)中第0位位值不同的輸入端和輸出端之間連接。第五章 并行處理機(jī)和多處理機(jī)幾種基本的互連函數(shù)用N表示節(jié)點(diǎn)數(shù)目，當(dāng)用二進(jìn)制表示這些節(jié)點(diǎn)號(hào)時(shí)，將用n 位二進(jìn)制數(shù)表示，其中 n=log2N。1、 恒等置換 相同編號(hào)的輸入端與輸出端一一對(duì)應(yīng)互連所實(shí)現(xiàn)的置換即為恒等置換，其表達(dá)式為： I（Xn-1Xn-2X1X0）= Xn-1Xn-2X1X0 其中等式左邊括號(hào)內(nèi)的Xn-1Xn-2X1X0和等式右邊的Xn-1X

24、n-2X1X0均為網(wǎng)絡(luò)輸入端和輸出端的二進(jìn)制地址編號(hào)。 第五章 并行處理機(jī)和多處理機(jī) 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 N=8的恒等置換 N=8的交換置換 2、 交換置換 交換置換是實(shí)現(xiàn)二進(jìn)制地址編號(hào)中第0位位值不同的輸入端和輸出端之間的連接。其表達(dá)式為： E（ Xn-1Xn-2X1X0 ）= Xn-1Xn-2X1X0第五章 并行處理機(jī)和多處理機(jī)3、 方體置換 方體置換是實(shí)現(xiàn)二進(jìn)制地址編號(hào)中第k位位值不同的輸入端輸出端之間的連接。其表達(dá)式為：Cubek(Xn-1Xn-2Xk+1XkXk-1X1X0)

25、= Xn-1Xn-2 Xk+1XkXk-1 X1X0 第五章 并行處理機(jī)和多處理機(jī) 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 （a）C0方體置換 （b）C1方體置換 （c）C2方體置換第五章 并行處理機(jī)和多處理機(jī)4、 均勻洗牌置換 將輸入端分成數(shù)目相等的兩半，前一半和后一半按序一個(gè)隔一個(gè)地從頭至尾依次與輸出端相連，其函數(shù)關(guān)系可表示為：逆均勻洗牌是均勻洗牌的逆函數(shù)，兩者的輸入端和輸出端正好互換了位置，其函數(shù)表達(dá)式為：第五章 并行處理機(jī)和多處理機(jī) 0

26、 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 N=8的均勻洗牌置換和逆均勻洗牌置換 第五章 并行處理機(jī)和多處理機(jī)5.蝶式置換（Butterfly）被定義為： （Xn-1Xn-2X1X0）= X0Xn-2X1 Xn-1子蝶式（subbutterfly）(k) 置換：(K)(Xn-1Xn-2 Xk+1XkXk-1X1X0） = Xn-1Xn-2 Xk+1X0Xk-1X1Xk超蝶式置換(k) : (k) (Xn-1Xn-2 Xn-kXn-k-1X1X0） = X n-k-1Xn-2Xn-kXn-1Xn-k-2 X1 X0

27、 第五章 并行處理機(jī)和多處理機(jī)012345670123456701234567012345670123456701234567(a)=置換 （b）(1)=(1)置換 （c） (1)=(1)置換 N=8的蝶式置換 第五章 并行處理機(jī)和多處理機(jī)6、移數(shù)置換將輸入端數(shù)組循環(huán)移動(dòng)一定的位置向輸出端傳輸。其函數(shù)表達(dá)式無(wú)需用二進(jìn)制編號(hào)來(lái)寫(xiě)，可表達(dá)如下： a(X)=(X+k) mod N, 0X N k為常數(shù)，指移動(dòng)的位置值。 0123456701234567 移數(shù)置換k=2第五章 并行處理機(jī)和多處理機(jī)7、 加減2i（PM2I）置換加減2i 置換實(shí)際上是一種移數(shù)置換包含2n個(gè)互連函數(shù)，其表達(dá)式為 PM2+i

28、（j）=j+2 i （mod N） PM2-i（j）=j-2 i （mod N）式中，0jN-1，0in-1，n=log2N012345670123456701234567012345670123456701234567(a)i=0(b) i=+1(c) i=+2第五章 并行處理機(jī)和多處理機(jī)0 0輸入端 輸出端 N-1 N-1IS0IS1ISN-1OS0OS1OSN-1單級(jí)互連網(wǎng)的普遍模型 （二） 互聯(lián)網(wǎng)結(jié)構(gòu)第五章 并行處理機(jī)和多處理機(jī)三個(gè)單級(jí)互連網(wǎng)（以N=8為例）立方體網(wǎng)立方體單級(jí)網(wǎng)循環(huán)表示為：Cube0：（0 1）（2 3）（4 5）（6 7）Cube1：（0 2）（1 3）（4 6）（5

29、 7）Cube2：（0 4）（1 5）（2 6）（3 7） 第五章 并行處理機(jī)和多處理機(jī)011010001101100000110111Cube0001011010101100000110111011010001101100000110111Cube2Cube1立方體網(wǎng)共有n=Log2N種互連函數(shù)，即為CUBEK(Xn-1Xn-2Xk+1XkXk-1X1X0)=Xn-1Xn-2Xk+1XkXk-1X1X0 其中Xk為輸入端標(biāo)號(hào)的第K 位二進(jìn)制代號(hào),且0=k=n-1 第五章 并行處理機(jī)和多處理機(jī)PM2I單級(jí)互聯(lián)網(wǎng) PM2I單級(jí)網(wǎng)結(jié)點(diǎn)間的互連函數(shù)關(guān)系為加減2i 置換,對(duì)于N=8，PM2I單級(jí)網(wǎng)共有

30、2*3=6個(gè)互連函數(shù)，循環(huán)表示為： PM2+0：（0 1 2 3 4 5 6 7） PM2-0：（7 6 5 4 3 2 1 0） PM2+1：（0 2 4 6）（1 3 5 7） PM2-1：（6 4 2 0）（7 5 3 1） PM22：（0 4）（1 5）（2 6）（3 7） 第五章 并行處理機(jī)和多處理機(jī)PM2+0 0 1 2 3 4 5 6 7PM2+1 0 1 2 3 4 5 6 7 PM22 0 1 2 3 4 5 6 7 PM2I互連網(wǎng)連接圖 第五章 并行處理機(jī)和多處理機(jī) 混洗交換單級(jí)互聯(lián)網(wǎng)絡(luò)全混洗（Perfect shuffle）、交換（Exchange）01234567全混洗

31、交換單級(jí)網(wǎng) 第五章 并行處理機(jī)和多處理機(jī)基本的循環(huán)互連網(wǎng)和多級(jí)互連網(wǎng)循環(huán)互連網(wǎng)：將同一套單級(jí)互連網(wǎng)循環(huán)使用，組成循環(huán)互連網(wǎng)絡(luò).單級(jí)互連網(wǎng)絡(luò)MUXDTRiDTRoMUXDTRiDTRo.循環(huán)循環(huán)PE0來(lái)去PE0PEN-1來(lái)去PEN-1傳送寄存器多路開(kāi)關(guān)第五章 并行處理機(jī)和多處理機(jī)多級(jí)互連網(wǎng)：將多套單級(jí)互連網(wǎng)串聯(lián)使用，組成多級(jí)互連網(wǎng)。優(yōu)點(diǎn):縮短了通過(guò)時(shí)間而提高了速度;可以利用各種單級(jí)互連網(wǎng)絡(luò)進(jìn)行不同的組合，產(chǎn)生具有各種特性和連接模式的多級(jí)互連網(wǎng)絡(luò)，靈活性較好。缺點(diǎn):增加了設(shè)備和成本。第五章 并行處理機(jī)和多處理機(jī)最基本的多級(jí)互連網(wǎng)絡(luò)：多級(jí)立方體互連網(wǎng)絡(luò)，多級(jí)混洗交換網(wǎng)絡(luò)和PM2I網(wǎng)絡(luò)。實(shí)現(xiàn)各種多級(jí)網(wǎng)

32、絡(luò)的區(qū)別：所用開(kāi)關(guān)模塊、控制方式和拓?fù)浣Y(jié)構(gòu)（級(jí)間連接模式）三個(gè)因素不同。 直連 交換 上播 下播22交叉開(kāi)關(guān)連接模式 開(kāi)關(guān)模塊ijijijijijijijij第五章 并行處理機(jī)和多處理機(jī)控制方式：是對(duì)各個(gè)開(kāi)關(guān)模塊進(jìn)行控制的方式。拓?fù)浣Y(jié)構(gòu)：指各級(jí)之間出端和入端相互連接的規(guī)則或連接模式。級(jí)控制-每一級(jí)的所有開(kāi)關(guān)只用一個(gè)控制信號(hào)控制，同時(shí)只能處于同一種狀態(tài)；單元控制-每一個(gè)開(kāi)關(guān)都有自己?jiǎn)为?dú)的控制信號(hào)控制，可各自處于不同的狀態(tài)；部分級(jí)控制-第i級(jí)的所有開(kāi)關(guān)分別用i+1個(gè)信號(hào)控制，0in-1，n為級(jí)數(shù)。第五章 并行處理機(jī)和多處理機(jī)多級(jí)立方體網(wǎng)AEIBFJCGKDHL 0 1 2 3 4 5 6 7012

33、34567N=8間接二進(jìn)制n方體互連網(wǎng) 特點(diǎn)：第i級(jí)（0in-1）控制信號(hào)為“1”時(shí)，處于交換狀態(tài)，實(shí)現(xiàn)的是cube i 互連函數(shù)，當(dāng)該信號(hào)為“0”時(shí)，相應(yīng)單元處于直連狀態(tài)代碼不變，它們都采用兩個(gè)功能（直接、交換）的交換單元。常用的多級(jí)立方體網(wǎng)有STARAN網(wǎng)，間接二進(jìn)制n方體網(wǎng)等。交換網(wǎng)絡(luò)：級(jí)控移數(shù)網(wǎng)絡(luò)：部分級(jí)控第五章 并行處理機(jī)和多處理機(jī)三級(jí)STARAN交換網(wǎng)絡(luò)實(shí)現(xiàn)的入出端連接級(jí)控制信號(hào) 000 001 010 011 100 101 110 111入 0 1端 2 3 4號(hào) 5 6 7 0 1 2 3 4 5 6 7 1 0 3 2 5 4 7 6 2 3 0 1 6 7 4 5 3 2

34、 1 0 7 6 5 4 4 5 6 7 0 1 2 3 5 4 7 6 1 0 3 2 6 7 4 5 2 3 0 1 7 6 5 4 3 2 1 0第五章 并行處理機(jī)和多處理機(jī)多級(jí)混洗交換網(wǎng)絡(luò)又稱(chēng)omega網(wǎng)絡(luò)，由n級(jí)相同的網(wǎng)絡(luò)組成，每一級(jí)都包含一個(gè)全混拓?fù)浜碗S后一列2n-1個(gè)四功能交換單元，（直連、交換、上播、下播），采用單元控制方式。DHL 6 767AEIBFJCGK 0 1 2 3 4 5012345N=8 多級(jí)混洗交換網(wǎng)第五章 并行處理機(jī)和多處理機(jī) 多級(jí)PM2I互連網(wǎng)又稱(chēng)為數(shù)據(jù)交換網(wǎng); 其中N=8，n=log2N=3各級(jí)中的處理單元按PM2I互連函數(shù)關(guān)系連接起來(lái)。 第0級(jí)、第一級(jí)

35、、第二級(jí)完成的都是PM2I。 網(wǎng)絡(luò)中提供了冗余通路，提高了可靠性。 多級(jí)PM2I互連網(wǎng)STARAN網(wǎng)絡(luò)和omega網(wǎng)絡(luò)都是為了進(jìn)行存儲(chǔ)器與處理器之間的數(shù)據(jù)交換，間接二進(jìn)制n方體網(wǎng)絡(luò)是為了連接成微處理器陣列。第五章 并行處理機(jī)和多處理機(jī)互連網(wǎng)絡(luò)的設(shè)計(jì)特性計(jì)算機(jī)中，衡量互連網(wǎng)絡(luò)性能好壞的主要因素是它的連接度、延時(shí)性、帶寬、可靠性和成本。連接度：指一個(gè)結(jié)點(diǎn)與其他結(jié)點(diǎn)的連接程度。如果一個(gè)結(jié)點(diǎn)直接連接的其他結(jié)點(diǎn)數(shù)越多，連接度就越高，表明連接性越好。延時(shí)性：指從一個(gè)結(jié)點(diǎn)傳送信息到任何另一個(gè)結(jié)點(diǎn)所需的時(shí)間。通?？捎媒Y(jié)點(diǎn)間最大距離加以表示。第五章 并行處理機(jī)和多處理機(jī)1、 通信工作方式 通信工作方式可分為同步

36、和異步兩種。2、 控制策略 控制策略分為集中和分散兩種。3、 交換方式 交換方式分為線路交換和分組交換兩種。4、 網(wǎng)絡(luò)拓?fù)?網(wǎng)絡(luò)拓?fù)浞譃殪o態(tài)和動(dòng)態(tài)兩種。這里的拓?fù)涫侵富ミB網(wǎng)絡(luò)中的各個(gè)結(jié)點(diǎn)間連接關(guān)系，通常用圖來(lái)描述?；ミB網(wǎng)絡(luò)設(shè)計(jì)的四個(gè)特征第五章 并行處理機(jī)和多處理機(jī)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 靜態(tài)網(wǎng)絡(luò)常用來(lái)實(shí)現(xiàn)集中式系統(tǒng)的多系統(tǒng)之間或分布式系統(tǒng)的多個(gè)計(jì)算機(jī)結(jié)點(diǎn)間固定連接。它一旦構(gòu)成后就固定不變。 1 靜態(tài)互連網(wǎng)絡(luò)第五章 并行處理機(jī)和多處理機(jī)一維拓?fù)浣Y(jié)構(gòu) 環(huán)形拓?fù)浣Y(jié)構(gòu) 樹(shù)形拓?fù)浣Y(jié)構(gòu)星形拓?fù)浣Y(jié)構(gòu)網(wǎng)格拓?fù)浣Y(jié)構(gòu) 全連接網(wǎng)絡(luò) 三維立方體結(jié)構(gòu) 第五章 并行處理機(jī)和多處理機(jī)各種互連網(wǎng)主要性能比較 互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)連接數(shù)最

37、大連接度最大結(jié)點(diǎn)距離（網(wǎng)絡(luò)直徑）線性N12N1環(huán)狀N2N/2網(wǎng)格（N*N）2N（N1）42（N1）星形N-1N-12超立方（N2K ）kN/2Log2NLog2N全互連N（N1）/2N11二叉樹(shù)N132Log2(N+1)-1第五章 并行處理機(jī)和多處理機(jī)2 動(dòng)態(tài)互連網(wǎng)根據(jù)程序要求實(shí)現(xiàn)所有的通信模式；通常緊耦合多處理機(jī)系統(tǒng)的互連網(wǎng)絡(luò)采用動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)；不用固定連接，而是沿著連接通路使用開(kāi)關(guān)于仲裁器以提供動(dòng)態(tài)連接特性，實(shí)現(xiàn)所要求的通訊模式；按照價(jià)格和性能增加的順序，動(dòng)態(tài)連接網(wǎng)絡(luò)分為總線系統(tǒng)，多端口存儲(chǔ)器，交叉開(kāi)關(guān)和多處理機(jī)的多級(jí)網(wǎng)絡(luò)等。 第五章 并行處理機(jī)和多處理機(jī)1、多處理機(jī)概念一種系統(tǒng)構(gòu)造方式;多

38、個(gè)處理機(jī)共享主存或輸入輸出的子系統(tǒng);統(tǒng)一操作系統(tǒng)控制;實(shí)現(xiàn)作業(yè)，任務(wù)級(jí)甚至指令級(jí)間并行。多計(jì)算機(jī)系統(tǒng)：共享主存；每個(gè)處理機(jī)都有自己局部存儲(chǔ)器，甚至輸入、輸出設(shè)備，本身就構(gòu)成了一臺(tái)完整的計(jì)算機(jī)；每臺(tái)計(jì)算機(jī)分別受各自獨(dú)立操作系統(tǒng)控制，機(jī)間往往以通道或通信線路進(jìn)行通訊，以文件或數(shù)據(jù)集交互作用實(shí)現(xiàn)任務(wù)作業(yè)級(jí)并行。五、 多處理機(jī)的硬件結(jié)構(gòu)第五章 并行處理機(jī)和多處理機(jī)2 、 多處理機(jī)特點(diǎn) 具有更大的靈活性和更強(qiáng)的通用性。 主要開(kāi)發(fā)高層次作業(yè)及任務(wù)級(jí)（粗粒性）并行性。 并行任務(wù)的派生需要用顯式的專(zhuān)用語(yǔ)句或指令加以表示。 并發(fā)執(zhí)行的進(jìn)程間的同步需要采取特殊措施，以保證程序 原來(lái)的正確語(yǔ)義。 對(duì)資源分配和任務(wù)分

39、配要進(jìn)行良好的調(diào)度。 MIMD系統(tǒng)在執(zhí)行條件語(yǔ)句時(shí)比SIMD系統(tǒng)有較高的效率。 MIMD的異步特性使得它在執(zhí)行一串完成時(shí)間可變的指令時(shí)，比SIMD有更快的速率。第五章 并行處理機(jī)和多處理機(jī)處理機(jī)1處理機(jī)N.處理機(jī)2存儲(chǔ)器存儲(chǔ)器.存儲(chǔ)器互連網(wǎng)絡(luò)I/OI/O（a）共享存儲(chǔ)型 處理機(jī)1處理機(jī)N.處理機(jī)2存儲(chǔ)器存儲(chǔ)器.存儲(chǔ)器互連網(wǎng)絡(luò)I/OI/O.I/O（b）點(diǎn)對(duì)點(diǎn)型（分布型） 3、兩種多處理機(jī)結(jié)構(gòu) 第五章 并行處理機(jī)和多處理機(jī)（1）共享存儲(chǔ)型（緊耦合系統(tǒng)） 特點(diǎn)： 1）多處理機(jī)系統(tǒng)中，多個(gè)處理器、高速緩存（cache）一般利用公 共總線實(shí)現(xiàn)互連。 2）通過(guò)共享主存實(shí)現(xiàn)處理機(jī)間的相互通信，相互間的聯(lián)系比

40、較緊密。 3）所有處理機(jī)共享I/O設(shè)備或通過(guò)通道和外設(shè)相連，整個(gè)系統(tǒng)有統(tǒng)一的操作系統(tǒng)管理，提供處理機(jī)及程序之間的作業(yè)、任務(wù)、文件、數(shù)據(jù)各個(gè)級(jí)別上的相互聯(lián)系。 按系統(tǒng)所用的處理機(jī)結(jié)構(gòu)類(lèi)型是否相同及操作功能是否對(duì)稱(chēng)，可分為：同構(gòu)對(duì)稱(chēng)型多機(jī)系統(tǒng)異構(gòu)非對(duì)稱(chēng)型多機(jī)系統(tǒng)。 第五章 并行處理機(jī)和多處理機(jī)I/OSM1SMmP1P2Pn 系統(tǒng)互連(總線,交叉開(kāi)關(guān),多級(jí)網(wǎng)絡(luò))處理機(jī) 共享存儲(chǔ)器 UMA多處理機(jī)模型 三種模型 （按存取方式）1）均勻存儲(chǔ)器存取(Uniform-Memory-Access）UMA2）非均勻存儲(chǔ)器存?。∟onuniform-Memory-Access）NUMA3）高速緩存存儲(chǔ)結(jié)構(gòu)（Cac

41、he-Only-Memory Architecture） COMA模型第五章 并行處理機(jī)和多處理機(jī) LM1 P1 LM2 P2 LMn Pn 互連網(wǎng)絡(luò). . （a） NUMA共享本地存儲(chǔ)器（如BBN Butterfly） 多處理機(jī)系統(tǒng)的兩種NUMA模型 第五章 并行處理機(jī)和多處理機(jī)GSM 全局互連網(wǎng)絡(luò)GSMGSMCI N P1 P2 PnCSM1CSM 2CSM3 P1 P2 PnCSM1CSM2CSMn CI N（b）層次式機(jī)群模型（如伊利諾伊大學(xué)的Cedar系統(tǒng)） 第五章 并行處理機(jī)和多處理機(jī)互連網(wǎng)絡(luò) D Cache P D Cache P D Cache P.多處理機(jī)的COMA模型 第五

42、章 并行處理機(jī)和多處理機(jī)PM I/ONI模塊1 消息傳送系統(tǒng)MTSPMI/ONI模塊N.計(jì)算機(jī)模塊（節(jié)點(diǎn)機(jī)）NI節(jié)點(diǎn)機(jī)接口 （2）分布存儲(chǔ)型（松散耦合的多處理機(jī)系統(tǒng) ）層次式和非層次式兩種第五章 并行處理機(jī)和多處理機(jī) Cmn層次式多機(jī)系統(tǒng) 第五章 并行處理機(jī)和多處理機(jī)總線結(jié)構(gòu)：把所有功能模塊（或部件、或計(jì)算機(jī)）連接到一條公共通信通路上，又稱(chēng)為分時(shí)或公共總線。機(jī)間互連形式.全局存儲(chǔ)器處理機(jī)1Cache1本地存儲(chǔ)器1I/O處理機(jī)2Cache1本地存儲(chǔ)器2I/O處理機(jī)NCache1本地存儲(chǔ)器pI/O.第五章 并行處理機(jī)和多處理機(jī)采用總線結(jié)構(gòu)的多處理機(jī)系統(tǒng)優(yōu)點(diǎn)： （1）系統(tǒng)硬件成本最低且最簡(jiǎn)單，每個(gè)處

43、理機(jī)的物理 接口、尋址、判優(yōu)和分時(shí)邏輯線路與單處理機(jī)系統(tǒng)相同。 （2）通過(guò)增、刪功能模塊可方便地改變系統(tǒng)硬件配置。缺點(diǎn)： （1）全部存貯訪問(wèn)都要經(jīng)過(guò)總線，所以全系統(tǒng)的速度 受到總線工作周期的限制，帶寬窄，可連接的處理機(jī)數(shù)少。 （2）系統(tǒng)以增加模塊方式進(jìn)行擴(kuò)充會(huì)降低整個(gè)系統(tǒng)的 吞吐率； （3）這種互聯(lián)方式其可靠性差，系統(tǒng)效率較低。第五章 并行處理機(jī)和多處理機(jī)常用的仲裁算法靜態(tài)優(yōu)先級(jí)算法：為每個(gè)連到總線上的處理機(jī)（或計(jì)算機(jī)模塊）分配一個(gè)唯一的固定優(yōu)先級(jí)。優(yōu)點(diǎn)：算法簡(jiǎn)單，易實(shí)現(xiàn)。缺點(diǎn)：優(yōu)先級(jí)低的處理機(jī)將很少有機(jī)會(huì)使用總線。平等算法：以輪轉(zhuǎn)方式將總線按固定大小的時(shí)間片依次供各處理機(jī)使用，常用于同步總線

44、。優(yōu)點(diǎn)：算法較簡(jiǎn)單且能保證各處理機(jī)有均等機(jī)會(huì)使用總線。缺點(diǎn)：平均等待時(shí)間較長(zhǎng)。第五章 并行處理機(jī)和多處理機(jī)動(dòng)態(tài)優(yōu)先級(jí)算法：根據(jù)總線使用情況和相應(yīng)規(guī)則，能動(dòng)態(tài)地改變連接到總線上的多處理機(jī)的優(yōu)先級(jí)。優(yōu)點(diǎn)：兼顧了前兩種算法的優(yōu)點(diǎn)，即有較短的平均等待時(shí)間,并可使系統(tǒng)中的各處理機(jī)有均等機(jī)會(huì)使用總線。缺點(diǎn)：控制邏輯較為復(fù)雜。先來(lái)先服務(wù)算法：不是按優(yōu)先級(jí)選擇主控器。優(yōu)點(diǎn)：具有最好的均等性，該算法是性能最好的仲裁算法。缺點(diǎn)：實(shí)現(xiàn)困難。該算法的作用只提供一種標(biāo)準(zhǔn)以衡量其他算法好壞。第五章 并行處理機(jī)和多處理機(jī)交叉開(kāi)關(guān)網(wǎng)絡(luò) 包含一組縱橫開(kāi)關(guān)陣列，把縱向的處理機(jī)P及I/O通道與橫向的存儲(chǔ)器模塊M連接起來(lái)，使每個(gè)處理

45、器都有有它單獨(dú)可用的通路與存儲(chǔ)器模塊相連，這樣可以加大頻帶寬度，每個(gè)交叉點(diǎn)都有開(kāi)關(guān)、多路控制轉(zhuǎn)換及仲裁部件。 M1 M2 MnP0Pp-1I/O0I/OD-1第五章 并行處理機(jī)和多處理機(jī)特點(diǎn)：（1） 互連系統(tǒng)最復(fù)雜，潛在的總通信速率最高；（2） 控制和切換邏輯在開(kāi)關(guān)內(nèi)部，所以功能模塊最簡(jiǎn)單且最便宜；（3） 任何功能模塊要裝配到系統(tǒng)中都需要使用一個(gè)基本開(kāi)關(guān)矩陣，所以面向多處理機(jī)才會(huì)能使性能價(jià)格比趨于合理。（4） 系統(tǒng)擴(kuò)充會(huì)提高整個(gè)系統(tǒng)性能，而且不必重寫(xiě)操作系統(tǒng)，有最高的系統(tǒng)潛在效率。（5） 從理論上講，系統(tǒng)擴(kuò)充只受開(kāi)關(guān)矩陣大小限制，而開(kāi)關(guān)矩陣的設(shè)計(jì)和控制可采用模塊化方式予以擴(kuò)展。（6） 開(kāi)關(guān)內(nèi)部

46、采用與/或的冗余方法提高了開(kāi)關(guān)的可靠性，因此，也就提高了系統(tǒng)的可靠性。 對(duì)于分布存儲(chǔ)的松散耦合方式的大規(guī)模并行多處理機(jī)系統(tǒng)可采用縱橫交叉開(kāi)關(guān)實(shí)現(xiàn)互連。第五章 并行處理機(jī)和多處理機(jī)多端口存儲(chǔ)器互連方式 每個(gè)存貯器模塊有多個(gè)存取端口，將分布在交叉開(kāi)關(guān)矩陣中的控制，轉(zhuǎn)換和優(yōu)先級(jí)仲裁邏輯分別移到相應(yīng)存貯器模塊的接口中，構(gòu)成多端口存貯器的結(jié)構(gòu)。M1p1p2M2M3M4I/O1I/O1四端口存儲(chǔ)器形式的結(jié)構(gòu)第五章 并行處理機(jī)和多處理機(jī)優(yōu)點(diǎn)：（1） 比較簡(jiǎn)單。（2） 傳送速率可以較高。（3） 增加安全性，防止無(wú)權(quán)使用的用戶(hù)訪問(wèn)，還可以保護(hù)存放在存貯器 中的重要程序不被其它處理機(jī)修改破壞。 缺點(diǎn)：比總線結(jié)構(gòu)復(fù)

47、雜，在存貯器系統(tǒng)中要增加很多硬件。 第五章 并行處理機(jī)和多處理機(jī)多級(jí)互連網(wǎng) MIMD和SIMD計(jì)算機(jī)都使用多級(jí)網(wǎng)絡(luò)。每一級(jí)都用了多個(gè)ab開(kāi)關(guān)，相鄰各級(jí)開(kāi)關(guān)之間都有固定的級(jí)間連接。為了在輸入和輸出之間建立所需的連接，可用動(dòng)態(tài)設(shè)置開(kāi)關(guān)的狀態(tài)來(lái)實(shí)現(xiàn)。 各種多級(jí)網(wǎng)絡(luò)的區(qū)別就在于所用開(kāi)關(guān)模塊、控制方式和級(jí)間連接（ISC）模式的不同。最簡(jiǎn)單的開(kāi)關(guān)模塊是22開(kāi)關(guān)。前面介紹的有立方體多級(jí)網(wǎng)，多級(jí)混洗交換網(wǎng)等。這些交叉開(kāi)關(guān)在處理機(jī)時(shí)比較復(fù)雜，可采用改進(jìn)的方法，即把多個(gè)較小規(guī)模交叉開(kāi)關(guān)“串聯(lián)”和“并聯(lián)”，組成多級(jí)交叉開(kāi)關(guān)網(wǎng)絡(luò)。 第五章 并行處理機(jī)和多處理機(jī)單處理機(jī)：cache一致性問(wèn)題只存在于cache與主存之間，即使有I/O通道共享cache亦可通過(guò)全寫(xiě)法或回寫(xiě)法較好地加以解決；多處理機(jī)：由于每一個(gè)處理機(jī)都有一個(gè)cache，因此在寫(xiě)操作時(shí)，必須保證各cache之間的數(shù)據(jù)一致性。導(dǎo)致多處理機(jī)系統(tǒng)中cache內(nèi)容不一致的因素有三個(gè)：（1）可寫(xiě)數(shù)據(jù)的共享。（2）輸入輸出活動(dòng)。（3）進(jìn)程遷移。二、 多處理機(jī)cache一致性第五章 并行處理機(jī)和多處理機(jī)解決多處理機(jī)CACHE一致性的方法監(jiān)視cache協(xié)議法（snoopy cache protoc