并行計算機模型課件

并行計算機模型

1計算技術的現(xiàn)狀

2多處理機和多計算機

3多向量機和SIMD計算機

4并行計算機的抽象模型

5可擴展的范圍和設計

1計算技術的現(xiàn)狀一、并行技術的出現(xiàn)二、現(xiàn)代并行計算機的組成涉及6個問題：1.計算問題

現(xiàn)實生活中對問題要求快速而精確地求解推動了計算機的廣泛使用?？茖W技術中的數(shù)值計算問題人工智能(AI)問題2.算法和數(shù)據(jù)結(jié)構(gòu)并行計算問題中的運算和通信，需要各種專門的算法和數(shù)據(jù)結(jié)構(gòu)。符號處理：存在的問題

：3.硬件資源處理機、存儲器和外圍設備組成了計算機系統(tǒng)的硬件核心外圍設備可以直接或通過局域網(wǎng)和廣域網(wǎng)與主機相連4.操作系統(tǒng)管理用戶程序執(zhí)行過程中的資源分配和再分配。映射是一種算法結(jié)構(gòu)與硬件結(jié)構(gòu)相匹配的雙向過程。并行操作系統(tǒng)的映射算法和數(shù)據(jù)結(jié)構(gòu)到機器結(jié)構(gòu)的映射包括處理機調(diào)度、存儲器映象、處理器間的通信等。這些問題通常都與系統(tǒng)結(jié)構(gòu)有關。5.系統(tǒng)軟件支持

存在的問題：不能以通用和可移植方式進行并行程序設計開發(fā)并行編程環(huán)境：一種與系統(tǒng)結(jié)構(gòu)無關的語言、編譯器和軟件工具。兩個方向：對于開發(fā)并行語言，我們將著眼點放在語言執(zhí)行的效率、對不同機器的可移植性、與現(xiàn)有的順序語言的兼容性、并行性的表達和編程的簡便性等上面。可以設計一種新的語言，逐步擴展現(xiàn)有的順序語言。新語言有用顯式高級結(jié)構(gòu)描述并行性的優(yōu)點，但是新語言往往與現(xiàn)有語言不兼容，而需要新的編譯器或者通過新的步驟才能利用現(xiàn)有的編譯器。大部分系統(tǒng)選用的是語言擴展方式。6.編譯器支持

改進編譯器有三種途徑：預處理程序;預編譯器;并行化編譯器。預處理程序采用順序編譯器和目標計算機的低層程序庫實現(xiàn)高級并行結(jié)構(gòu)。預編譯器需要程序流分析、相關性檢查和有限的優(yōu)化來檢測并行性。聯(lián)接過程的效果取決于預處理程序、預編譯器、并行化編譯器、加載程序和操作系統(tǒng)支持的功效。由于程序行為的不可預測，現(xiàn)有的編譯器在檢測所有類型的并行性時都不是完全自動或完全智能進行的。有效的方法：將編譯器命令插入源代碼，幫編譯器做出較好的結(jié)果。這樣，用戶可與編譯器進行交互重構(gòu)程序，這已被證明對提高并行計算機性能是十分有用的。7.并行程序的設計環(huán)境

隱式并行性伊利諾依大學的DavidKuck和Rice大學的KenKennedy以及他們的合作者都已采用這種隱式并行性方法。顯式并行性加州理工學院的CharlesSeitz和麻省理工學院的WilliamDaily在開發(fā)多計算機時采用了這種顯式方法?？偨Y(jié)：要使一個環(huán)境對用戶更加友好，必須要有專用軟件工具。一些工具是傳統(tǒng)高級語言的并行擴展；一些則是集成環(huán)境其中包括提供不同級別的程序抽象、驗證、測試、查錯和調(diào)試等各種工具；性能預測和監(jiān)控；輔助程序開發(fā)的可視化支持、性能測量以及計算結(jié)果的圖形顯示及動畫表示三、計算機系統(tǒng)結(jié)構(gòu)向高性能發(fā)展歷程主要探討順序到并行的過程1.先行、并行性和流水線技術用先行技術預取指令可使I／E(指令讀取／譯碼和執(zhí)行)支持功能并行性的方法有兩種：一種是同時使用多個功能部件；另一種是在不同處理級分別實施流水線技術。流水線指令執(zhí)行、流水線算術計算和存儲器存取操作。2.Flynn分類法MkhealFlynn(1972)根據(jù)指令和數(shù)據(jù)流概念提出了不同計算機系統(tǒng)結(jié)構(gòu)的分類法。傳統(tǒng)的順序機被稱為SISD(單指令流單數(shù)據(jù)流)計算機。向量計算機--標量和向量硬件裝備，或以SIMD(單指令流多數(shù)據(jù)流)機的形式出現(xiàn)。并行計算機則屬MIMD(多指令流多數(shù)據(jù)流)機MISD(多指令流單數(shù)據(jù)流)機在執(zhí)行不同的指令流時，同一數(shù)據(jù)流通過處理機線性陣列。這種系統(tǒng)結(jié)構(gòu)也就是所謂流水線執(zhí)行特定算法的脈動陣列(Systolicarrays)。由卡內(nèi)基—梅隆大學的美籍華人學者H．T．Kung于1978年提出的。這一結(jié)構(gòu)是隨著VLSI技術的發(fā)展和各種大運算量的信號/圖象處理及科學計算的運算要求而建立起來的。例1：用脈動陣列(Systolicarray)結(jié)構(gòu)計算矩陣乘脈動陣列的特點：處理單元簡單流水算法專業(yè)例2：數(shù)據(jù)流計算機數(shù)據(jù)流的計算模型--試圖使并行計算的基本方面在機器層顯式化，而不利用有可能限制程序并行性的人為約束。它的想法是程序由一個基本數(shù)據(jù)依賴圖來表示；一個指令可能在獲得了它的操作數(shù)后的任意時刻被執(zhí)行，不是顯式控制線性程序列的固定組合。3.并行／向量計算機

真正的并行計算機是那些以MIMD模式執(zhí)行程序的計算機。并行計算機有兩大類，即共享存儲型多處理機和消息傳遞型多計算機。多處理機和多計算機之間的主要差別就在于存儲器共享和處理機間通信機制的不同。多處理機系統(tǒng)中的處理機通過公用存儲器的共享變量實現(xiàn)互相通信。多計算機系統(tǒng)的每個計算機結(jié)點有一個與其它結(jié)點不共享的本地存儲器。處理機之間的通信通過結(jié)點間的消息傳遞來實現(xiàn)。顯式向量計算機指令是隨向量處理機的問世而出現(xiàn)的。一臺向量處理機可以裝備有用硬件或固件并發(fā)控制的多條向量流水線。4.開發(fā)層次

LionelNi的最新分類法(1990)，并行計算機的分層開發(fā)可表示于下圖四、性能的系統(tǒng)屬性1

.時鐘頻率和CPI

主頻當前數(shù)字計算機的CPU(或簡稱處理機)是由一個恒定周期(τ，以ns表示)的時鐘驅(qū)動的。周期的倒數(shù)是時鐘頻率(ｆ＝1/

τ）（以MHz表示）。程序的規(guī)模是由其指令數(shù)(Ic)，也就是程序串要執(zhí)行的機器指令數(shù)來決定的。執(zhí)行不同的機器指令所需要的時鐘周期數(shù)也是不一樣的。一條指令的周期數(shù)(CPl)就成為衡量執(zhí)行每條指令所需時間的重要參數(shù)。2.性能因子執(zhí)行程序所需的CPU時間：設Ic為已知程序的指令條數(shù)。執(zhí)行程序所需的CPU時間(T，以秒/程序表示)可用三個主要因素的乘積來計算：

T＝Ic

×CPI×τ可將上式重寫成如下形式：

T＝Ic

×(p+m×k)×τ

一種指令類型的CPI可分為完成指令所需的處理機周期數(shù)和存儲器周期數(shù)兩部分。完整的指令執(zhí)行過程可能包含一至四次存儲器訪問(一次用于取指令，兩次用于取操作數(shù)，一次用于存儲結(jié)果)，這與指令的類型有關。式中的細化：p為指令譯碼和執(zhí)行所需的處理機周期數(shù);m為所需的存儲器訪問次數(shù);k為存儲周期與處理機周期之比;Ic為指令條數(shù)，為處理機周期。3.系統(tǒng)屬性計算機系統(tǒng)屬性可以由五元組表示：(Ic，p，m，k，τ),五個量可以稱為性能因子。與四種系統(tǒng)屬性有關：指令系統(tǒng)結(jié)構(gòu)、編譯技術、CPU實現(xiàn)和控制技術、高速緩存與存儲器層次結(jié)構(gòu)。4.Mips速率5.吞吐率系統(tǒng)的吞吐率:系統(tǒng)在單位時間內(nèi)能執(zhí)行多少個程序，這稱為系統(tǒng)的吞吐率(單位為程序數(shù)／秒)Ws

。在多道程序系統(tǒng)中，系統(tǒng)吞吐率常低于CPU吞吐率Wp。Wp可用下式表示：

或：Wp=(MIPS)×106／Ic

Wp的單位是程序數(shù)／秒。CPU吞吐率是根據(jù)MIPS速率和程序的平均長度(Ic)來衡量機器每秒鐘能執(zhí)行多少個程序的尺度。Ws<Wp，用多道程序或分時操作在CPU上交叉執(zhí)行多個程序時，I／O、編譯器和操作系統(tǒng)產(chǎn)生的額外系統(tǒng)開銷所造成的。總結(jié)：并行的產(chǎn)生并行背景下的計算問題串行向并行的演化并行的性能與系統(tǒng)的關系并行處理與體系結(jié)構(gòu)第一章并行計算機模型

1計算技術的現(xiàn)狀

2多處理機和多計算機

3多向量機和SIMD計算機

4并行計算機的抽象模型

5可擴展的范圍和設計

2多處理機和多計算機一、共享存儲型多處理機1.UMA模型UMA

--UniformMemoryAccess

結(jié)構(gòu)和特點：緊耦合系統(tǒng)(tightlycoupledsystem)多處理機由于高度資源共享系統(tǒng)的互連采用總線、交叉開關、或多級網(wǎng)絡形式對稱(symmetric)多處理機當所有處理機都能同樣訪問所有外圍設備時。例Fortran程序可在單處理機上順序執(zhí)行，分析CPU的運行時間，假設條件：所有數(shù)組A(I)，B(I)，C(I)都有N個元素；分析：求和Fortran程序L1:Do10I＝1，NL2:A(I)＝B(I)+C(I)L3:10ContinueL4:SUM＝0L5:Do20J＝1，NL6:SUM＝SUM+A(J)L7:20Continue假定取指令和加載數(shù)據(jù)的開銷可以忽略不計；所有數(shù)組已經(jīng)裝人主存儲器，并且短程序段已經(jīng)裝入高速緩沖存儲器。忽略總線爭用或存儲器存取沖突問題。再假設：

執(zhí)行代碼行L2，L4和L6，每行要用一個機器周期。執(zhí)行程序控制語句L1，L3，L5和L7所需的時間可以忽略。假定經(jīng)過共享存儲器的處理機之間的每次通信操作需要k個周期。結(jié)論：CPU用2N個周期串行程序并行化在M—處理機系統(tǒng)上執(zhí)行程序?qū)⒀h(huán)操作劃分成M段，每段有L＝N／M個元素。假設經(jīng)過共享存儲器的處理機之間的每次通信操作需要：k個周期。

Doall表示所有M段在M臺處理機上并行執(zhí)行Doallk＝1，MDo10I＝L(k-1)+1，kL。

A(I)＝B(I)+C(I)10Continue

SUM(k)＝0Do20J＝1，L

SUM(k)=SUM(k)+A(L(k-1)+J)20ContinueENDall分析：循環(huán)1是L個周期；循環(huán)2是L個周期總時間：2L+h(k+1)=2N/M+(k+1)log2M2.NUAM模型3.COMA模型概念：只使用高速緩存的多處理機實現(xiàn)的機器：瑞典計算機科學研究所的數(shù)據(jù)擴散機(DDM，Hagersten等，1990)KendallSquareReserch公司的KSR—1機器(Burkhart等，1992)。特點：COMA模型是NUMA機的一種特例，將NUMA中分布主存儲器換成了高速緩存；全部高速緩沖存儲器組成了全局地址空間；遠程高速緩存訪問則借助于分布高速緩存目錄進行，分級目錄往往可用來尋找高速緩存塊的副本，這與所用的互連網(wǎng)絡有關；數(shù)據(jù)的初始位置并不重要，因為它最終將會遷移到要用到它的地方。模型的演變：例如，高速緩存一致性非均勻存儲存取(CC—NUMA)模型。可以用分布共享存儲器和高速緩存目錄來描述。CC—NUMA模型的實例斯坦福大學的Dash系統(tǒng)(Lenosh等，1990)和麻省理工學院的Alewife系統(tǒng)(Agarwal等，1990)；這些將在后面討論。4.典型的多處理機二、分布存儲型多計算機系統(tǒng)1.概念由多個計算機結(jié)點，通過消息傳遞網(wǎng)絡互相連接而成，每個結(jié)點是一臺由處理機、本地存儲器和有時接有磁盤或I／0外圍設備組成的自治的計算機。2.特點：消息傳遞網(wǎng)絡提供結(jié)點之間的點到點靜態(tài)連接傳統(tǒng)的多計算機已被稱為近地存儲訪問(NORMA)機所有本地存儲器是私用的，而且只有本地處理機才能訪問；私用存儲器逐漸在分布共享存儲器的多計算機中將被逐步取消。3.多計算機的換代現(xiàn)代多計算機用硬件尋徑器來傳送信息；計算機結(jié)點與尋徑器相連，邊界上的尋徑器與I／O和外圍設備連接；任何兩結(jié)點間的消息傳遞會涉及一連串的尋徑器和通道。在異構(gòu)多計算機系統(tǒng)中，可以有多種類型的結(jié)點，結(jié)點間的通信是通過可兼容的數(shù)據(jù)表示和消息傳遞協(xié)議來實現(xiàn)的。消息傳遞型多計算機的發(fā)展換代

第一代(1983—1987)是基于處理機板技術，采用了超立方體結(jié)構(gòu)和軟件控制的消息交換方法。加州理工學院的Cosmic和InteliPSC／1是這一代研制的代表。第二代(1988—1992)是用網(wǎng)格連接的系統(tǒng)結(jié)構(gòu)、硬件消息尋徑和中粒度分布計算的軟件環(huán)境實現(xiàn)的；IntelParagon和ParsysSuperNodel000可作為代表性產(chǎn)品?，F(xiàn)在面臨的第三代(1993—)預期是細粒度計算機麻省理工學院的J-Machine和加州工學院的Mosaic，VLSI片上實現(xiàn)處理機和通訊工具。

示例：IBMPOWER4體系結(jié)構(gòu)特點PowerPC64位體系結(jié)構(gòu)單芯片雙處理器，MCM八處理器集成多處理器互連接口集成I/O控制器集成L3Cache控制器集成存儲控制器IBMPOWER4(MCM結(jié)構(gòu))IBMPOWER4(32CPU)4.典型多計算機多計算機的可編程性取決于:高效編譯器實用高效的分布式操作系統(tǒng)實用總結(jié)：本節(jié)區(qū)分了多處理機和多計算機的主要差別和分類。

3多向量機和SIMD計算機一、向量超級計算機1.早期的超級計算機可分為：流水線向量機；SIMD計算機兩類。執(zhí)行過程：當譯出的指令為向量操作；它將被送至向量控制器，控制器將監(jiān)督主存儲器與向量功能流水線之間的向量數(shù)據(jù)流，向量數(shù)據(jù)流由控制器協(xié)調(diào)控制；向量處理機則裝有若干條向量功能流水線。2.寄存器—寄存器的系統(tǒng)結(jié)構(gòu)如1976年推出的Cray1。向量寄存器用來保存向量操作數(shù)、中間和最終的向量結(jié)果;向量功能流水線從向量寄存器檢索操作數(shù)，并將結(jié)果放入寄存器。

3.存儲器—存儲器結(jié)構(gòu)這種結(jié)構(gòu)比較早，與寄存器—寄存器結(jié)構(gòu)的區(qū)別就在于采用向量流水部件代替了向量寄存器。例如:二、SIMD超級計算機1.SIMD的操作模型可用五元組表示M＝<N，C，I，M，R>N為機器的處理單元(PE)數(shù)。例如，illiacIV有64個PE，而連接機(ConnectionMachine)CM—2采用65536個PE。C為由控制部件(CU)直接執(zhí)行的指令集；包括標量和程序流控制指令。I為由CU廣播至所有PE進行并行執(zhí)行的指令集；它包括算術運算、邏輯運算、數(shù)據(jù)尋徑、屏蔽以及其它由每個活動的PE對它的數(shù)據(jù)所執(zhí)行的局部操作。M為屏蔽方案集其中每種屏蔽將PE集劃分為允許操作和禁止操作兩種子集。R是數(shù)據(jù)尋徑功能集說明互連網(wǎng)絡中PE間通信所需要的各種設置模式。示例：描述具體的SIMD機器MasParMP—1計算機的操作特性--五元組特性：MP—1是一種SIMD機器，其PE數(shù)N＝1024