MIMD計算機

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

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

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

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

并行程序可用,Fork/Join,語句寫成如下形式：,,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臺處理機的,MIMD,系統(tǒng)上運行的時空關系可用資源時間圖表示（假設進程,k,執(zhí)行時間大于進程,k+3）2003.3.1,10,,計算機系統(tǒng)結構,9.,4 MIMD,的加速性能模型(,P502～P512),(1)兩個處理機的并行模型（,P504,）；,,,,總處理時間 =,R×max{ M-K，K } + C×( M-K )×K,,,其中：,M ──,任務總數(shù)；,,,K ──,分配給處理機1的任務數(shù)；,,,R ──,執(zhí)行1個任務所需時間；,,,C ──,進行1次通信所需時間最優(yōu)解：,P505,第1～3行2),N,個處理機的并行模型（,P505,）總處理時間 =,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,,計算機系統(tǒng)結構,2003.3.1,12,,計算機系統(tǒng)結構,9.,5,多處理機實例（,P521,）,9.,5.1,MPP（,P521,）,,大規(guī)模并行處理系統(tǒng),MPP,───,,幾百臺以上處理機通過專用互連網(wǎng)絡構成的高性能,MIMD,系統(tǒng)。

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

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

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

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

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

2003.3.1,24,,計算機系統(tǒng)結構,。