MIMD計(jì)算機(jī)

單擊此處編輯母版標(biāo)題樣式,,2003.3.1,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),*,第九章,MIMD,計(jì)算機(jī)(,P499),,MIMD,計(jì)算機(jī)與,SIMD,計(jì)算機(jī)的主要區(qū)別，在于,SIMD,只能在,同一時(shí)刻,做,多件相同,的事情，而,MIMD,卻可以,在,同一時(shí)刻,做,多件相同,或,不同,的事情（多指令流所致），所以求解同一個(gè)問(wèn)題時(shí)采用,MIMD,將能實(shí)現(xiàn)更大比例的并行操作，即處理效率更高從并行處理的級(jí)別看，,SIMD,是,數(shù)據(jù)級(jí)并行處理,，,流水線,是,指令級(jí)并行處理,，,MIMD,是,任務(wù)級(jí)并行處理,由于技術(shù)上的原因，目前實(shí)現(xiàn)的,MIMD,計(jì)算機(jī)都是,多處理機(jī)系統(tǒng),，包括,多計(jì)算機(jī)系統(tǒng),多處理機(jī)系統(tǒng)由多臺(tái)處理機(jī)連接而成，它們能夠并行執(zhí)行獨(dú)立的程序模塊，并且相互通信和同步，以實(shí)現(xiàn)作業(yè)、任務(wù)級(jí)的并行2003.3.1,1,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),CU2,CU1,CUn,PUn,PU2,PU1,MMn,MM2,MM1,IS1,IS1,IS2,IS2,ISn,DS1,ISn,DS2,DSn,多,指令流,多數(shù)據(jù)流,MIMD,2003.3.1,2,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),9.1,MIMD,的典型結(jié)構(gòu)(,P500),多處理機(jī)系統(tǒng)通常包含多個(gè)處理機(jī)模塊、多個(gè)存儲(chǔ)器模塊、多個(gè),I/O,通道，這些設(shè)備與單處理機(jī)系統(tǒng)中的設(shè)備沒(méi)有本質(zhì)不同，,最大的差別是互連網(wǎng)絡(luò)和多機(jī)操作系統(tǒng),。

由于多處理機(jī)系統(tǒng)是在作業(yè)、任務(wù)級(jí)并行，處理機(jī)之間的通信不像,SIMD,系統(tǒng)那樣頻繁和急迫，所以,互連網(wǎng)絡(luò)可以采用通用網(wǎng)實(shí)現(xiàn),，以便在滿足流量需要的前提下降低成本1)共享存儲(chǔ)器方案（緊耦合型）,,,P500,圖9.1(,a),存儲(chǔ)器和,I/O,設(shè)備是獨(dú)立的子系統(tǒng)，通過(guò)互連網(wǎng)絡(luò)為所有的處理機(jī)共享2)分布存儲(chǔ)器方案（松耦合型）,,,P500,圖9.1(,b),每臺(tái)處理機(jī)有自己的存儲(chǔ)器和,I/O,設(shè)備處理機(jī)之間的信息交換通過(guò)互連網(wǎng)絡(luò)2003.3.1,3,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),2003.3.1,4,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),它有多個(gè)控制器，至少有多個(gè)指令部件，用以對(duì)各個(gè),PE,實(shí)現(xiàn)單獨(dú)的控制，而又相互協(xié)調(diào)配合多處理機(jī)的外圍設(shè)備要能夠被多個(gè),PE,分別調(diào)用，因而要,通過(guò)互連網(wǎng)絡(luò),轉(zhuǎn)接，而不像并行處理機(jī)的外圍設(shè)備那樣統(tǒng)一訪問(wèn)主存儲(chǔ)器并行處理機(jī)由于主要完成數(shù)組向量運(yùn)算，它的,PE,和,MM,之間的數(shù)據(jù)交往比較有規(guī)則，互連網(wǎng)絡(luò)的作用主要放在數(shù)據(jù)對(duì)準(zhǔn)上，功能簡(jiǎn)單；,多處理機(jī)的互連網(wǎng)絡(luò)必須滿足各個(gè),PE,隨機(jī)地訪問(wèn)主存儲(chǔ)器的要求,，連接模式、頻帶和路徑選擇等問(wèn)題都要復(fù)雜多處理機(jī)屬,任務(wù)級(jí)并行,，,SIMD,屬于數(shù)據(jù)級(jí)并行。

多處理機(jī)與并行處理機(jī)（,SIMD,）,的主要區(qū)別,2003.3.1,5,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),?,結(jié)構(gòu)靈活性,,并行處理機(jī)是針對(duì)數(shù)組、向量處理而設(shè)計(jì)的而多處理機(jī)不限于數(shù)組向量的處理，力圖把能并行處理的任務(wù)、數(shù)組，以至標(biāo)量都進(jìn)行并行處理?,程序并行性的識(shí)別,,并行處理機(jī)實(shí)現(xiàn)操作一級(jí)的并行，其并行性存在于指令內(nèi)部多處理機(jī)中，因?yàn)椴幌抻诮鉀Q數(shù)組向量處理問(wèn)題，并行性存在于指令外部，即表現(xiàn)在多個(gè)任務(wù)之間再加上系統(tǒng)通用性的要求，就使程序并行性的識(shí)別難度較大因此，它必須利用多種途徑，如算法、程序語(yǔ)言、編譯、操作系統(tǒng)、以至指令、硬件等，盡量挖掘各種潛在的并行性多處理機(jī)的特點(diǎn),2003.3.1,6,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),?,并行任務(wù)的派生,,并行處理機(jī)依靠單指令流對(duì)多數(shù)據(jù)流實(shí)現(xiàn)并行操作，這種并行操作是通過(guò)各條單獨(dú)的指令加以反映和控制的，指令本身就可以啟動(dòng)多個(gè)處理部件并行多處理機(jī),是處于多指令流操作方式，一個(gè)程序當(dāng)中就,存在多個(gè)并發(fā)的程序段,，需要專門的指令來(lái)表示它們的并發(fā)關(guān)系以控制它們的并發(fā)執(zhí)行，以便一個(gè)任務(wù)開始被執(zhí)行時(shí)就能派生出可與它并行執(zhí)行的另一些任務(wù)該過(guò)程稱為,并行任務(wù)派生,可能達(dá)到較高的效率,9.2,MIMD,的并行程序控制(,P608),2003.3.1,7,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),?,進(jìn)程同步,,并行處理機(jī)是操作級(jí)的并行，所有處于活動(dòng)狀態(tài)的處理單元同時(shí)執(zhí)行共同的指令，受同一個(gè)控制器控制，工作自然同步。

多處理機(jī)所實(shí)現(xiàn)的是指令、任務(wù)、程序級(jí)的并行在同一時(shí)刻，不同的處理機(jī)執(zhí)行著不同的指令要區(qū)分進(jìn)程之間的多種不同的依賴關(guān)系要求多處理機(jī)采取特殊的同步措施，使并發(fā)進(jìn)程之間保持程序所要求的正確順序?,資源分配和進(jìn)程調(diào)度,,處理機(jī)執(zhí)行并發(fā)任務(wù)，需用處理機(jī)的數(shù)目沒(méi)有固定要求，各個(gè)處理機(jī)進(jìn)入或退出任務(wù)的時(shí)刻互不相同，所需共享資源的品種、數(shù)量又隨時(shí)變化，情況十分復(fù)雜，需要好的資源分配和進(jìn)程調(diào)度策略9.2,MIMD,的并行程序控制(,P608),2003.3.1,8,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),(1)任務(wù)派生語(yǔ)句 ───,當(dāng)前運(yùn)行的進(jìn)程向操作系統(tǒng)申請(qǐng)創(chuàng)建一個(gè)新進(jìn)程，并試圖用一個(gè)空閑處理機(jī)來(lái)運(yùn)行它如果操作系統(tǒng)沒(méi)有找到空閑處理機(jī)資源，則讓新進(jìn)程排隊(duì)等待格式：,FORX <,進(jìn)程名>,,(2)任務(wù)匯合語(yǔ)句 ───,檢查包括當(dāng)前進(jìn)程在內(nèi)的各先期并發(fā)進(jìn)程是否完成，如未完成則停止當(dāng)前進(jìn)程，釋放其處理機(jī)資源，如已完成則讓當(dāng)前進(jìn)程繼續(xù)執(zhí)行，通常是轉(zhuǎn)入后繼進(jìn)程匯合語(yǔ)句的每次執(zhí)行會(huì)對(duì)一個(gè)計(jì)數(shù)器加1（該計(jì)數(shù)器初值為0），直至達(dá)到語(yǔ)句所要求的匯合進(jìn)程數(shù)格式：,JOIN <,匯合進(jìn)程數(shù)>，,9.2,MIMD,的并行程序控制(,P608),2003.3.1,9,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),實(shí)例：,x = ( a + b )×( a - c ),,,我們?cè)O(shè)想用3個(gè)進(jìn)程來(lái)完成上式中3個(gè)運(yùn)算，則它們之間的相關(guān)關(guān)系可用數(shù)據(jù)相關(guān)圖來(lái)描述（右圖）。

并行程序可用,Fork/Join,語(yǔ)句寫成如下形式：,,k: Fork k+3,,k+1: Add A,B,T1,,k+2:,Goto,k+4,,k+3: Sub A,C,T2,,k+4: Join 2,1,,k+5:,Mul,T1,T2,X,,,該程序在2臺(tái)處理機(jī)的,MIMD,系統(tǒng)上運(yùn)行的時(shí)空關(guān)系可用資源時(shí)間圖表示（假設(shè)進(jìn)程,k,執(zhí)行時(shí)間大于進(jìn)程,k+3）2003.3.1,10,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),9.,4 MIMD,的加速性能模型(,P502～P512),(1)兩個(gè)處理機(jī)的并行模型（,P504,）；,,,,總處理時(shí)間 =,R×max{ M-K，K } + C×( M-K )×K,,,其中：,M ──,任務(wù)總數(shù)；,,,K ──,分配給處理機(jī)1的任務(wù)數(shù)；,,,R ──,執(zhí)行1個(gè)任務(wù)所需時(shí)間；,,,C ──,進(jìn)行1次通信所需時(shí)間最優(yōu)解：,P505,第1～3行2),N,個(gè)處理機(jī)的并行模型（,P505,）總處理時(shí)間 =,R×max{,K,i,} + (C/2)×Σ[K,i,×( M-,K,i,)],,= R×max{,K,i,} + (C/2)×( M,2,-ΣK,i,2,),,2003.3.1,11,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),2003.3.1,12,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),9.,5,多處理機(jī)實(shí)例（,P521,）,9.,5.1,MPP（,P521,）,,大規(guī)模并行處理系統(tǒng),MPP,───,,幾百臺(tái)以上處理機(jī)通過(guò)專用互連網(wǎng)絡(luò)構(gòu)成的高性能,MIMD,系統(tǒng)。

造價(jià)高，性能也高9.,5.2 SMP（P528）,,,共享存儲(chǔ)型多處理機(jī)系統(tǒng),SM,P,───,,所有處理機(jī)共享統(tǒng)一編址的內(nèi)存空間，由硬件協(xié)調(diào)訪存沖突，并行程序設(shè)計(jì)者感覺(jué)特別方便9.,5,.3,CLUSTER（,機(jī)群系統(tǒng)，,P541,）,,,機(jī)群系統(tǒng),CLUSTER,───,,幾臺(tái)至十幾臺(tái)微機(jī)或工作站通過(guò)通用網(wǎng)絡(luò)構(gòu)成的低成本并行處理,MIMD,系統(tǒng)，與,MPP,特點(diǎn)相反2003.3.1,13,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),機(jī)群系統(tǒng)的具體知識(shí),9.,5.3.1,什么是機(jī)群系統(tǒng),,利用,高速通用網(wǎng)絡(luò),將一組高性能工作站或,高檔,PC,機(jī),，按某種結(jié)構(gòu)連接起來(lái)，并在并行程序設(shè)計(jì)以及可視化人機(jī)交互集成開發(fā)環(huán)境支持下，統(tǒng)一調(diào)度脅調(diào)處理，實(shí)現(xiàn)高效并行處理的系統(tǒng)從結(jié)構(gòu)和結(jié)點(diǎn)間的通信方式來(lái)看，它,屬于分布存儲(chǔ),系統(tǒng)，主要利用,消息傳遞方式,實(shí)現(xiàn)各主機(jī)之間的通信，由建立在一般操作系統(tǒng)之上的并行編程環(huán)境完成系統(tǒng)的資源管理及相互協(xié)作，同時(shí)也屏蔽工作站及網(wǎng)絡(luò)的異構(gòu)性，對(duì)程序員和用戶來(lái)說(shuō)，機(jī)群系統(tǒng)是,一個(gè)整體,的并行系統(tǒng)機(jī)群系統(tǒng)中的,主機(jī)和網(wǎng)絡(luò)可以是同構(gòu)的，也可以是異構(gòu)的,目前已實(shí)現(xiàn)和正研究中的機(jī)群系統(tǒng)大多采用現(xiàn)有商用工作站和通用,LAN,網(wǎng)絡(luò)，既可縮短開發(fā)周期又可利用最新微處理器技術(shù)。

大多機(jī)群系統(tǒng)的并行編程環(huán)境是建立在,Unix,操作系統(tǒng)之上，盡量利用商用系統(tǒng)的研究成果，減少系統(tǒng)開發(fā)與維護(hù)費(fèi)用2003.3.1,14,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),?,機(jī)群系統(tǒng)出現(xiàn)的原因（有利條件）：,,,(1),微處理器性能機(jī)價(jià)格比迅速提高,，可充當(dāng)機(jī) 群系統(tǒng)的運(yùn)算節(jié)點(diǎn)；,,,,(2),網(wǎng)絡(luò)技術(shù)進(jìn)步使得松散耦合系統(tǒng)的通信瓶頸得到緩解,例,：,ATM155M/620 M,；以太網(wǎng),1000 M,；甚至有的產(chǎn)品已接近了多處理機(jī)專用互聯(lián)網(wǎng)（如交叉開關(guān)網(wǎng)絡(luò)、多機(jī)網(wǎng)絡(luò)）性能例如,MyriCom,公司的,Myrinet,1.28G,，開關(guān)延遲只有,1us,3),并行編程環(huán)境,的開發(fā)使得編制并行程序或改寫串行程序更加容易2003.3.1,15,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),Computer Food Chain,2003.3.1,16,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),與傳統(tǒng)的并行處理機(jī)相比，機(jī)群系統(tǒng)有下列特點(diǎn)：,,（,1,）開發(fā)周期短,,,·,結(jié)點(diǎn),——,商用工作站,,,,·,網(wǎng)絡(luò),——,通用網(wǎng)絡(luò)，例如,,ATM,,·,操作系統(tǒng),——Unix/LINUX,,·,并行程序設(shè)計(jì)語(yǔ)言,——,在,C,、,Fortran,上擴(kuò)充2,）用戶投資風(fēng)險(xiǎn)小,,購(gòu)置巨型機(jī)或多處理機(jī)系統(tǒng)，投資大，但很可能用不起來(lái)。

9.,5.3.2,機(jī)群系統(tǒng)的特點(diǎn)（,P541,） P542 (1)-(6),2003.3.1,17,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),（,3,） 系統(tǒng)價(jià)格低,,（,4,）充分利用系統(tǒng)資源,,某計(jì)算機(jī)系,100,多臺(tái)工作站，一般單機(jī)系統(tǒng)的使用率不到,10%,而組成機(jī)群系統(tǒng)后，可達(dá)到,80%,左右機(jī)群系統(tǒng)可分批更新5,）系統(tǒng)擴(kuò)展性好,,（,6,）用戶編程方便,,并行程序設(shè)計(jì)語(yǔ)言一般是在,C,、,C++,或,Fortran,中加入,",通信原語(yǔ),",擴(kuò)展出來(lái)的2003.3.1,18,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),機(jī)群系統(tǒng)的關(guān)鍵技術(shù)主要包括：,,（,1,）高效通信系統(tǒng),,機(jī)群系統(tǒng)一般采用通用局域網(wǎng)，目前局域網(wǎng)技術(shù)大體分兩類,,,·,共享介質(zhì)網(wǎng)絡(luò) 例：,Ethernet,,·,開關(guān)網(wǎng)絡(luò)例：,ATM,Myrinet,和,100M,交換式,Ethernet,三、機(jī)群系統(tǒng)的關(guān)鍵技術(shù),,人們希望機(jī)群系統(tǒng)具有以下特點(diǎn)：,,·,較高的節(jié)點(diǎn)運(yùn)算速度；,,·,系統(tǒng)加速比性能接近線性增長(zhǎng)；,,·,并行應(yīng)用程序的開發(fā)要高效、方便2003.3.1,19,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),網(wǎng)絡(luò)性能的性能描述：,,,·,帶寬速度：,10-100-1000Mbps,,往返延遲：,1,字節(jié)的數(shù)據(jù)包的往返傳輸時(shí)間。

新網(wǎng)絡(luò)技術(shù)大幅提高了傳輸速度，但延遲時(shí)間還沒(méi)多大變化（如下表）,,,,,,,,,,所以機(jī)群系統(tǒng)中局域網(wǎng)研究方向主要是：減少往返延遲和提高帶寬利用率目前網(wǎng)絡(luò)帶寬利用率較低例如,640Mbps,的,Myrinet,,,應(yīng)用程序可見(jiàn)帶寬才,38Mpbs,提高帶寬利用率途徑之一： 精減協(xié)議， 例,TCP/IP,層次太多2003.3.1,20,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),（,2,）并行程序設(shè)計(jì)語(yǔ)言和環(huán)境,,一般都是基于消息傳遞,(Message Passing ),現(xiàn)在的實(shí)現(xiàn)方法一般是：使用原有順序編譯器連接并行程序庫(kù)研究方向：,1,）擴(kuò)展原有順序語(yǔ)言,,,2,）開發(fā)全新的并行語(yǔ)言,,,3,）研究自動(dòng)化并行編譯器，直接將順,,序程序編譯成并行代碼并行程序設(shè)計(jì)環(huán)境（,P551,）,,,是介于分布式操作系統(tǒng)與并行應(yīng)用程序之間的支撐軟件組，提供并行運(yùn)算所需的各種軟件模塊和管理功能，以此提升操作系統(tǒng)功能來(lái)全面支持并行計(jì)算最著名的并行程序設(shè)計(jì)環(huán)境是,PVM,2003.3.1,21,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),（,3,）全局資源管理及利用,,有效的利用資源是機(jī)群系統(tǒng)的重要目標(biāo)當(dāng)前的方法：在一般的操作系統(tǒng)（,Unix,、,NT,等）上建立一個(gè)全局,Unix,。

共享資源,——,例如各節(jié)點(diǎn)的內(nèi)存，在,155M,的,ATM,網(wǎng)絡(luò)上，讀取其它節(jié)點(diǎn)內(nèi)存的時(shí)間僅為讀取本地硬盤的五分之一據(jù)統(tǒng)計(jì)，對(duì)需經(jīng)常訪問(wèn)硬盤的的應(yīng)用程序，使用這種方法可以比使用本地磁盤快,5~10,倍2003.3.1,22,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),對(duì)比,,多組織,可以多個(gè)組織（復(fù)用）,一個(gè)組織,一個(gè)組織,中等,高或者容錯(cuò),低,低或中,多,多,單一,多,/,單地址空間,(,分布式共享內(nèi)存,),同類,OS,或異構(gòu),OS,N,個(gè)同類,OS,獨(dú)立的完整的,OS,一個(gè)主要的內(nèi)核和多個(gè)微內(nèi)核,目前不支持,某一層次支持,支持完全的,SSI,部分支持,獨(dú)立運(yùn)行隊(duì)列,多隊(duì)列協(xié)同運(yùn)行,單一運(yùn)行隊(duì)列,主機(jī)單一隊(duì)列,跨地區(qū)或國(guó)家,樓區(qū)范圍,一個(gè)機(jī)箱,一個(gè)房間,10,～,1000,以上數(shù)量級(jí),100,左右的數(shù)量級(jí),10,～,100,數(shù)量級(jí),100~1000,數(shù)量級(jí),歸屬單位,系統(tǒng)可用性,地址空間,結(jié)點(diǎn)操作系統(tǒng),單一系統(tǒng)映像,任務(wù)調(diào)度,連接距離,結(jié)點(diǎn)個(gè)數(shù),分布式系統(tǒng),集群,SMP,MPP,特征,2003.3.1,23,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),本章小結(jié),(1),MIMD,的2種典型結(jié)構(gòu),,,(2),MIMD,的并行程序控制,,,(3),MIMD,的加速性能模型,,,,,,,,,,,習(xí)題：,P561,，題6，題18（參看,P,346,題18,(3)和,P321,倒2段）。

2003.3.1,24,,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),。