《MIMD計算機》PPT課件

2020/4/27,計算機系統(tǒng)結構,1,第九章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è)、任務級的并行。,2020/4/27,計算機系統(tǒng)結構,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,計算機系統(tǒng)結構,3,9.1MIMD的典型結構(P500),多處理機系統(tǒng)通常包含多個處理機模塊、多個存儲器模塊、多個I/O通道，這些設備與單處理機系統(tǒng)中的設備沒有本質(zhì)不同，最大的差別是互連網(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)絡。,2020/4/27,計算機系統(tǒng)結構,4,2020/4/27,計算機系統(tǒng)結構,5,它有多個控制器，至少有多個指令部件，用以對各個PE實現(xiàn)單獨的控制，而又相互協(xié)調(diào)配合。多處理機的外圍設備要能夠被多個PE分別調(diào)用，因而要通過互連網(wǎng)絡轉接，而不像并行處理機的外圍設備那樣統(tǒng)一訪問主存儲器。并行處理機由于主要完成數(shù)組向量運算，它的PE和MM之間的數(shù)據(jù)交往比較有規(guī)則，互連網(wǎng)絡的作用主要放在數(shù)據(jù)對準上，功能簡單；多處理機的互連網(wǎng)絡必須滿足各個PE隨機地訪問主存儲器的要求，連接模式、頻帶和路徑選擇等問題都要復雜。多處理機屬任務級并行，SIMD屬于數(shù)據(jù)級并行。,多處理機與并行處理機（SIMD）的主要區(qū)別,2020/4/27,計算機系統(tǒng)結構,6,結構靈活性并行處理機是針對數(shù)組、向量處理而設計的。而多處理機不限于數(shù)組向量的處理，力圖把能并行處理的任務、數(shù)組，以至標量都進行并行處理。程序并行性的識別并行處理機實現(xiàn)操作一級的并行，其并行性存在于指令內(nèi)部。多處理機中，因為不限于解決數(shù)組向量處理問題，并行性存在于指令外部，即表現(xiàn)在多個任務之間。再加上系統(tǒng)通用性的要求，就使程序并行性的識別難度較大。因此，它必須利用多種途徑，如算法、程序語言、編譯、操作系統(tǒng)、以至指令、硬件等，盡量挖掘各種潛在的并行性。,多處理機的特點,2020/4/27,計算機系統(tǒng)結構,7,并行任務的派生并行處理機依靠單指令流對多數(shù)據(jù)流實現(xiàn)并行操作，這種并行操作是通過各條單獨的指令加以反映和控制的，指令本身就可以啟動多個處理部件并行。多處理機是處于多指令流操作方式，一個程序當中就存在多個并發(fā)的程序段，需要專門的指令來表示它們的并發(fā)關系以控制它們的并發(fā)執(zhí)行，以便一個任務開始被執(zhí)行時就能派生出可與它并行執(zhí)行的另一些任務。該過程稱為并行任務派生。可能達到較高的效率,9.2MIMD的并行程序控制(P608),2020/4/27,計算機系統(tǒng)結構,8,進程同步并行處理機是操作級的并行，所有處于活動狀態(tài)的處理單元同時執(zhí)行共同的指令，受同一個控制器控制，工作自然同步。多處理機所實現(xiàn)的是指令、任務、程序級的并行。在同一時刻，不同的處理機執(zhí)行著不同的指令。要區(qū)分進程之間的多種不同的依賴關系。要求多處理機采取特殊的同步措施，使并發(fā)進程之間保持程序所要求的正確順序。資源分配和進程調(diào)度處理機執(zhí)行并發(fā)任務，需用處理機的數(shù)目沒有固定要求，各個處理機進入或退出任務的時刻互不相同，所需共享資源的品種、數(shù)量又隨時變化，情況十分復雜，需要好的資源分配和進程調(diào)度策略。,9.2MIMD的并行程序控制(P608),2020/4/27,計算機系統(tǒng)結構,9,(1)任務派生語句當前運行的進程向操作系統(tǒng)申請創(chuàng)建一個新進程，并試圖用一個空閑處理機來運行它。如果操作系統(tǒng)沒有找到空閑處理機資源，則讓新進程排隊等待。格式：FORX(2)任務匯合語句檢查包括當前進程在內(nèi)的各先期并發(fā)進程是否完成，如未完成則停止當前進程，釋放其處理機資源，如已完成則讓當前進程繼續(xù)執(zhí)行，通常是轉入后繼進程。匯合語句的每次執(zhí)行會對一個計數(shù)器加1（該計數(shù)器初值為0），直至達到語句所要求的匯合進程數(shù)。格式：JOIN，,9.2MIMD的并行程序控制(P608),2020/4/27,計算機系統(tǒng)結構,10,實例：x=(a+b)(a-c)我們設想用3個進程來完成上式中3個運算，則它們之間的相關關系可用數(shù)據(jù)相關圖來描述（右圖）。并行程序可用Fork/Join語句寫成如下形式：k:Forkk+3k+1:AddA,B,T1k+2:Gotok+4k+3:SubA,C,T2k+4:Join2,1k+5:MulT1,T2,X該程序在2臺處理機的MIMD系統(tǒng)上運行的時空關系可用資源時間圖表示（假設進程k執(zhí)行時間大于進程k+3）。,2020/4/27,計算機系統(tǒng)結構,11,9.4MIMD的加速性能模型(P502P512),(1)兩個處理機的并行模型（P504）；總處理時間=RmaxM-K，K+C(M-K)K其中：M任務總數(shù)；K分配給處理機1的任務數(shù)；R執(zhí)行1個任務所需時間；C進行1次通信所需時間。最優(yōu)解：P505第13行。(2)N個處理機的并行模型（P505）。總處理時間=RmaxKi+(C/2)Ki(M-Ki)=RmaxKi+(C/2)(M2-Ki2),2020/4/27,計算機系統(tǒng)結構,12,2020/4/27,計算機系統(tǒng)結構,13,9.5多處理機實例（P521）,9.5.1MPP（P521）大規(guī)模并行處理系統(tǒng)MPP幾百臺以上處理機通過專用互連網(wǎng)絡構成的高性能MIMD系統(tǒng)。造價高，性能也高。9.5.2SMP（P528）共享存儲型多處理機系統(tǒng)SMP所有處理機共享統(tǒng)一編址的內(nèi)存空間，由硬件協(xié)調(diào)訪存沖突，并行程序設計者感覺特別方便。9.5.3CLUSTER（機群系統(tǒng)，P541）機群系統(tǒng)CLUSTER幾臺至十幾臺微機或工作站通過通用網(wǎng)絡構成的低成本并行處理MIMD系統(tǒng)，與MPP特點相反。,2020/4/27,計算機系統(tǒng)結構,14,機群系統(tǒng)的具體知識,9.5.3.1什么是機群系統(tǒng)利用高速通用網(wǎng)絡將一組高性能工作站或高檔PC機，按某種結構連接起來，并在并行程序設計以及可視化人機交互集成開發(fā)環(huán)境支持下，統(tǒng)一調(diào)度脅調(diào)處理，實現(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ā)與維護費用。,2020/4/27,計算機系統(tǒng)結構,15,機群系統(tǒng)出現(xiàn)的原因（有利條件）：(1)微處理器性能機價格比迅速提高，可充當機群系統(tǒng)的運算節(jié)點；(2)網(wǎng)絡技術進步使得松散耦合系統(tǒng)的通信瓶頸得到緩解。例：ATM155M/620M；以太網(wǎng)1000M；甚至有的產(chǎn)品已接近了多處理機專用互聯(lián)網(wǎng)（如交叉開關網(wǎng)絡、多機網(wǎng)絡）性能。例如MyriCom公司的Myrinet1.28G，開關延遲只有1us。(3)并行編程環(huán)境的開發(fā)使得編制并行程序或改寫串行程序更加容易。,2020/4/27,計算機系統(tǒng)結構,16,ComputerFoodChain,2020/4/27,計算機系統(tǒng)結構,17,與傳統(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)。,2020/4/27,計算機系統(tǒng)結構,18,（3）系統(tǒng)價格低（4）充分利用系統(tǒng)資源某計算機系100多臺工作站，一般單機系統(tǒng)的使用率不到10%。而組成機群系統(tǒng)后，可達到80%左右。機群系統(tǒng)可分批更新。（5）系統(tǒng)擴展性好（6）用戶編程方便并行程序設計語言一般是在C、C+或Fortran中加入通信原語擴展出來的。,2020/4/27,計算機系統(tǒng)結構,19,機群系統(tǒng)的關鍵技術主要包括：（1）高效通信系統(tǒng)機群系統(tǒng)一般采用通用局域網(wǎng)，目前局域網(wǎng)技術大體分兩類共享介質(zhì)網(wǎng)絡。例：Ethernet開關網(wǎng)絡。例：ATMMyrinet和100M交換式Ethernet。,三、機群系統(tǒng)的關鍵技術人們希望機群系統(tǒng)具有以下特點：較高的節(jié)點運算速度；系統(tǒng)加速比性能接近線性增長；并行應用程序的開發(fā)要高效、方便。,2020/4/27,計算機系統(tǒng)結構,20,網(wǎng)絡性能的性能描述：帶寬速度：10-100-1000Mbps往返延遲：1字節(jié)的數(shù)據(jù)包的往返傳輸時間。新網(wǎng)絡技術大幅提高了傳輸速度，但延遲時間還沒多大變化（如下表）所以機群系統(tǒng)中局域網(wǎng)研究方向主要是：減少往返延遲和提高帶寬利用率。目前網(wǎng)絡帶寬利用率較低。例如640Mbps的Myrinet,應用程序可見帶寬才38Mpbs。提高帶寬利用率途徑之一：精減協(xié)議，例TCP/IP層次太多。,2020/4/27,計算機系統(tǒng)結構,21,（2）并行程序設計語言和環(huán)境一般都是基于消息傳遞(MessagePassing)?，F(xiàn)在的實現(xiàn)方法一般是：使用原有順序編譯器連接并行程序庫。研究方向：1）擴展原有順序語言2）開發(fā)全新的并行語言3）研究自動化并行編譯器，直接將順序程序編譯成并行代碼。,并行程序設計環(huán)境（P551）是介于分布式操作系統(tǒng)與并行應用程序之間的支撐軟件組，提供并行運算所需的各種軟件模塊和管理功能，以此提升操作系統(tǒng)功能來全面支持并行計算。最著名的并行程序設計環(huán)境是PVM。,2020/4/27,計算機系統(tǒng)結構,22,（3）全局資源管理及利用有效的利用資源是機群系統(tǒng)的重要目標。當前的方法：在一般的操作系統(tǒng)（Unix、NT等）上建立一個全局Unix。共享資源例如各節(jié)點的內(nèi)存，在155M的ATM網(wǎng)絡上，讀取其它節(jié)點內(nèi)存的時間僅為讀取本地硬盤的五分之一