《MIMD計(jì)算機(jī)》PPT課件

2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),1,第九章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í)的并行。,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),2,CU2,CU1,CUn,PUn,PU2,PU1,MMn,MM2,MM1,IS1,IS1,IS2,IS2,ISn,DS1,ISn,DS2,DSn,多指令流多數(shù)據(jù)流MIMD,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),3,9.1MIMD的典型結(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ò)。,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),4,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),5,它有多個(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ū)別,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),6,結(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),2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),7,并行任務(wù)的派生并行處理機(jī)依靠單指令流對(duì)多數(shù)據(jù)流實(shí)現(xiàn)并行操作，這種并行操作是通過(guò)各條單獨(dú)的指令加以反映和控制的，指令本身就可以啟動(dòng)多個(gè)處理部件并行。多處理機(jī)是處于多指令流操作方式，一個(gè)程序當(dāng)中就存在多個(gè)并發(fā)的程序段，需要專門(mén)的指令來(lái)表示它們的并發(fā)關(guān)系以控制它們的并發(fā)執(zhí)行，以便一個(gè)任務(wù)開(kāi)始被執(zhí)行時(shí)就能派生出可與它并行執(zhí)行的另一些任務(wù)。該過(guò)程稱為并行任務(wù)派生?？赡苓_(dá)到較高的效率,9.2MIMD的并行程序控制(P608),2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),8,進(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.2MIMD的并行程序控制(P608),2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),9,(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(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，,9.2MIMD的并行程序控制(P608),2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),10,實(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ǔ)句寫(xiě)成如下形式：k:Forkk+3k+1:AddA,B,T1k+2:Gotok+4k+3:SubA,C,T2k+4:Join2,1k+5:MulT1,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）。,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),11,9.4MIMD的加速性能模型(P502P512),(1)兩個(gè)處理機(jī)的并行模型（P504）；總處理時(shí)間=RmaxM-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第13行。(2)N個(gè)處理機(jī)的并行模型（P505）?？偺幚頃r(shí)間=RmaxKi+(C/2)Ki(M-Ki)=RmaxKi+(C/2)(M2-Ki2),2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),12,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),13,9.5多處理機(jī)實(shí)例（P521）,9.5.1MPP（P521）大規(guī)模并行處理系統(tǒng)MPP幾百臺(tái)以上處理機(jī)通過(guò)專用互連網(wǎng)絡(luò)構(gòu)成的高性能MIMD系統(tǒng)。造價(jià)高，性能也高。9.5.2SMP（P528）共享存儲(chǔ)型多處理機(jī)系統(tǒng)SMP所有處理機(jī)共享統(tǒng)一編址的內(nèi)存空間，由硬件協(xié)調(diào)訪存沖突，并行程序設(shè)計(jì)者感覺(jué)特別方便。9.5.3CLUSTER（機(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)相反。,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),14,機(jī)群系統(tǒng)的具體知識(shí),9.5.3.1什么是機(jī)群系統(tǒng)利用高速通用網(wǎng)絡(luò)將一組高性能工作站或高檔PC機(jī)，按某種結(jié)構(gòu)連接起來(lái)，并在并行程序設(shè)計(jì)以及可視化人機(jī)交互集成開(kāi)發(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ò)，既可縮短開(kāi)發(fā)周期又可利用最新微處理器技術(shù)。大多機(jī)群系統(tǒng)的并行編程環(huán)境是建立在Unix操作系統(tǒng)之上，盡量利用商用系統(tǒng)的研究成果，減少系統(tǒng)開(kāi)發(fā)與維護(hù)費(fèi)用。,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),15,機(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/620M；以太網(wǎng)1000M；甚至有的產(chǎn)品已接近了多處理機(jī)專用互聯(lián)網(wǎng)（如交叉開(kāi)關(guān)網(wǎng)絡(luò)、多機(jī)網(wǎng)絡(luò)）性能。例如MyriCom公司的Myrinet1.28G，開(kāi)關(guān)延遲只有1us。(3)并行編程環(huán)境的開(kāi)發(fā)使得編制并行程序或改寫(xiě)串行程序更加容易。,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),16,ComputerFoodChain,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),17,與傳統(tǒng)的并行處理機(jī)相比，機(jī)群系統(tǒng)有下列特點(diǎn)：（1）開(kāi)發(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)。,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),18,（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)的。,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),19,機(jī)群系統(tǒng)的關(guān)鍵技術(shù)主要包括：（1）高效通信系統(tǒng)機(jī)群系統(tǒng)一般采用通用局域網(wǎng)，目前局域網(wǎng)技術(shù)大體分兩類共享介質(zhì)網(wǎng)絡(luò)。例：Ethernet開(kāi)關(guān)網(wǎng)絡(luò)。例：ATMMyrinet和100M交換式Ethernet。,三、機(jī)群系統(tǒng)的關(guān)鍵技術(shù)人們希望機(jī)群系統(tǒng)具有以下特點(diǎn)：較高的節(jié)點(diǎn)運(yùn)算速度；系統(tǒng)加速比性能接近線性增長(zhǎng)；并行應(yīng)用程序的開(kāi)發(fā)要高效、方便。,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),20,網(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層次太多。,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),21,（2）并行程序設(shè)計(jì)語(yǔ)言和環(huán)境一般都是基于消息傳遞(MessagePassing)?，F(xiàn)在的實(shí)現(xiàn)方法一般是：使用原有順序編譯器連接并行程序庫(kù)。研究方向：1）擴(kuò)展原有順序語(yǔ)言2）開(kāi)發(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。,2020/4/27,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),22,（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í)間僅為讀取本地硬盤(pán)的五分之一