1、第一章 并行計算基礎知識第1頁，共55頁。第一章 并行計算基礎知識1.1 并行計算的主要研究目標和內容 1.1.1 并行計算的定義 1.1.2 并行計算的研究內容 1.1.3 并行計算的應用范圍 1.1.4 并行計算的應用分類1.2 并行計算機發展歷史 1.2.1 并行計算機發展簡述 1.3 并行計算機體系結構 1.3.1 并行計算機體系結構的要素 1.3.2 并行計算機的類型2第2頁，共55頁。1.1 并行計算的主要研究目標 和內容第3頁，共55頁。1.1.1并行計算的定義并行計算是指同時對多個任務或多條指令、或對多個數據項進行處理。完成此項處理的計算機系統稱為并行計算機系統，它是將多個處理

2、器（可以幾個、幾十個、幾千個、幾萬個等）通過網絡連接以一定的方式有序地組織起來（一定的連接方式涉及網絡的互聯拓撲、通信協議等，而有序的組織則涉及操作系統、中間件軟件等）。并行計算的主要目的：一是為了提供比傳統計算機快的計算速度；二是解決傳統計算機無法解決的問題。 4第4頁，共55頁。1.1.2并行計算的研究內容 并行計算的研究內容廣泛，包括并行計算機系統結構、并行算法設計、并行編程環境等，具體表現在下面幾個方面：(1)并行計算機的設計包括本并行計算機的結構設計、互聯拓撲、網絡通信等。設計并行計算機重要的一點要考慮處理機數目的按比例增長（即可擴展性）及支持快速通信及處理機間的數據共享等。5第5頁

3、，共55頁。1.1.2并行計算的研究內容 (2)有效算法的設計如果沒有有效的并行算法，并行計算機無法使用，而并行算法的設計完全不同于串行算法的設計，不同的并行計算機的算法設計不同，只有將不同的并行計算機與不同的實際問題相結合，才能設計出有效的并行算法。主要研究內容包括并行計算模型、并行算法的一般設計方法、基本設計技術和一般設計過程，并討論一些數值并行算法與非數值并行算法的設計。 6第6頁，共55頁。1.1.2并行計算的研究內容 (3)評價并行算法的方法對于給定的并行計算機及運行在上面的并行算法，需要評價運行性能。性能分析需解決的問題：如何利用基于并行計算機及其相適應的并行算法去快速地解決問題，

4、及如何有效地利用各個處理器。研究內容包括結合機器與算法，提出相應的性能評測指標，為設計高效的并行算法提供依據。7第7頁，共55頁。1.1.2并行計算的研究內容 (4)并行計算機語言與傳統的機器語言不同，并行計算機語言依賴于并行計算機，并行計算機語言必須簡潔，編程容易，可以有效地實現，目前的語言有：PVM、MPI、HPF等，而且新的編程語言和編程模式正在不斷地出現。 8第8頁，共55頁。1.1.2并行計算的研究內容 (5)并行編程環境與工具為了使編程容易，必須開發綜合的編程環境與工具，且能達到兩個目的：并行計算機的底層機構對用戶透明；為用戶提供設計與開發程序所需要的調試器與模擬器等工具。9第9頁

5、，共55頁。1.1.2并行計算的研究內容 (6)并行程序的可移植性 可移植性為并行程序設計的主要問題，要求在一臺并行機上開發的程序不加修改或進行少量修改即可在另一臺計算機上運行。這一點為目前受到了廣泛關注的重要課題。(7) 并行計算機的自動編程可否設計一個并行化編譯器，使用戶的串行程序通過并行化編譯器編譯，直接可在并行機上運行。到目前為此，這種編譯器還不存在，而僅有一些半自動并行化編譯器。10第10頁，共55頁。1.1.3 并行計算的應用范圍 并行計算在許多計算機應用領域都產生了巨大的影響，使原來無法解決的應用問題成為可能。 天氣預報、衛星數據處理、石油數據處理（連續優化問題），調度問題、平面

6、性問題及VLSI設計（離散優化問題）、生物工程、醫藥研究、飛機制造、汽車設計、環境保護等領域。11第11頁，共55頁。1.1.4并行計算的應用分類 科學與工程計算對并行計算的需求是十分廣泛的，但所有的應用可概括為三個方面：（1）計算密集型（Compute-Intensive）這一類型的應用問題主要集中在大型科學工程計算與數值模擬（氣象預報、地球物理勘探等） 12第12頁，共55頁。1.1.4并行計算的應用分類 （2）數據密集型 (Data-Intensive)Internet的發展，為我們提供了大量的數據資源，但有效地利用這些資源，需要進行大量地處理，且對計算機的要求也相當高，這些應用包括數字

7、圖書館、數據倉庫、數據挖掘、計算可視化。（3）網絡密集型 (Network-Intensive)通過網絡進行遠距離信息交互，來完成用傳統方法不同的一些應用問題。如協同工作、遙控與遠程醫療診斷等。13第13頁，共55頁。1.2 并行計算機發展歷史第14頁，共55頁。1.2.1 并行計算機發展簡述 40年代開始的現代計算機發展歷程可以分為兩個明顯的發展時代：串行計算時代、并行計算時代。每一個計算時代都從體系結構發展開始，接著是系統軟件（特別是編譯器與操作系統）、應用軟件，最后隨著問題求解環境的發展而達到頂峰。創建和使用并行計算機的主要原因是因為并行計算機是解決單處理器速度瓶頸的最好方法之一。 15

8、第15頁，共55頁。1.2.1 并行計算機發展簡述并行計算機是由一組處理單元組成的，這組處理單元通過相互之間的通信與協作，以更快的速度共同完成一項大規模的計算任務。因此，并行計算機的兩個最主要的組成部分是計算節點和節點間的通信與協作機制。并行計算機體系結構的發展也主要體現在計算節點性能的提高以及節點間通信技術的改進兩方面。 16第16頁，共55頁。1.2.1 并行計算機發展簡述 60年代初期，由于晶體管以及磁芯存儲器的出現，處理單元變得越來越小，存儲器也更加小巧和廉價。這些技術發展的結果導致了并行計算機的出現，這一時期的并行計算機多是規模不大的共享存儲多處理器系統，即所謂大型主機（Mainfr

9、ame）。IBM 360是這一時期的典型代表。 17第17頁，共55頁。1.2.1 并行計算機發展簡述 到了60年代末期，同一個處理器開始設置多個功能相同的功能單元，流水線技術也出現了。與單純提高時鐘頻率相比，這些并行特性在處理器內部的應用大大提高了并行計算機系統的性能。 18第18頁，共55頁。1.2.1 并行計算機發展簡述1972年，誕生了第一臺并行計算機ILLIAC (Illinois Integrator and Automatic Computer) 伊利諾斯(理工學院)積分儀和自動計算機。它由Illinois 大學和Burrouphs公司合作研制成功的。運算速度為1.5億次/秒 (

10、1.5*108次/秒)由64臺處理器組成的陣列機(Array Computer)可對數組進行并行計算它是當時性能最高的 CDC 7600 機器速度的26倍。19第19頁，共55頁。1.2.1 并行計算機發展簡述從80年代開始，微處理器技術一直在高速前進。稍后又出現了非常適合于SMP 方式的總線協議，而伯克利加州大學則對總線協議進行了擴展，提出了Cache一致性問題的處理方案。從此，共享存儲多處理器之路越走越寬；現在，這種體系結構已經基本上統治了服務器和桌面工作站市場。 同一時期，基于消息傳遞機制的并行計算機也開始不斷涌現。80年代中期，加州理工成功地將64個i8086/i8087處理器通過超立

11、方體互連結構連結起來。此后，便先后出現了Intel iPSC系列、INMOS Transputer 系列、Intel Paragon 以及IBM SP 的前身Vulcan等基于消息傳遞機制的并行計算機。 20第20頁，共55頁。1.2.1 并行計算機發展簡述 80年代末到90年代初，共享存儲器方式的大規模并行計算機又獲得了新的發展。IBM 將大量早期RISC微處理器通過蝶形互連網絡連結起來。人們開始考慮如何才能在實現共享存儲器緩存一致的同時，使系統具有一定的可擴展性（Scalability）。90年代初期，斯坦福大學提出了DASH計劃，它通過維護一個保存有每一緩存塊位置信息的目錄結構來實現分布

12、式共享存儲器的緩存一致性。后來，IEEE在此基礎上提出了緩存一致性協議的標準。 21第21頁，共55頁。1.2.1 并行計算機發展簡述 90年代以來，主要的幾種體系結構開始走向融合。屬于數據并行類型的CM-5除大量采用商品化的微處理器以外，也允許用戶層的程序傳遞一些簡單的消息；CRAY T3D是一臺NUMA結構的共享存儲型并行計算機，但是它也提供了全局同步機制、消息隊列機制，并采取了一些減少消息傳遞延遲的技術。 22第22頁，共55頁。1.3 并行計算機體系結構第23頁，共55頁。結點（node）：包含一個或多個CPU，這些CPU通過HUB或全互聯交叉開關相互聯接，并共享內存，也可以直接與外部

13、進行I/O操作。 互聯網絡（interconnect network）：所有結點通過互聯網絡相互連接相互通信。內存（memory）：內存由多個存儲模塊組成，這些模塊可以與結點對稱地分布在互聯網絡的兩側，或者位于各個結點的內部。1.3.1 并行計算機體系結構的要素24第24頁，共55頁。結點是構成并行機的最基本單位。一個結點包含2 個或2 個以上微處理器（CPU），并行程序執行時，程序分派的各個進程將并行地運行在結點的各個微處理器上。每個微處理器擁有局部的二級高速緩存（L2 cache）。L2 cache 是現代高性能微處理器用于彌補日益增長的CPU 執行速度和內存訪問速度差距（訪存墻）而采取的

14、關鍵部件。它按cache 映射策略緩存內存訪問的數據，同時為CPU 內部的一級cache 提供計算數據。CPU 內部的一級cache為寄存器提供數據，寄存器為邏輯運算部件提供數據。1.3.1 并行計算機體系結構的要素25第25頁，共55頁。隨著處理器速度的日益增長，結點內配置的內存容量也在增長。傳統地，1 個單位的浮點運算速度配1 個字節的內存單元，是比較合理的。但是，考慮到日益增長的內存墻的影響，這個比例可以適當縮小。例如，1 個單位的浮點運算速度配0.4 個字節的內存單元。如果以單個微處理器速度為每秒60 億次計算，包含4 個處理器的單結點的峰值運算速度可達240 億次，內存空間需要8GB

15、 以上。于是，在當前并行機的結點內，一般需要采用64 位的微處理器，才能操作如此大的內存空間。1.3.1 并行計算機體系結構的要素26第26頁，共55頁?；ヂ摼W絡是連接所有結點成并行機的高速網絡。對于一般的并行機使用者，無須知道互聯網絡底層復雜的通信原理，而只需從拓撲結構的角度了解互聯網絡。互聯網絡的拓撲結構可用無向圖表示。其中，圖中的結點唯一地代表并行機的各個結點，圖中的邊表示在兩個端點代表的并行機結點之間，存在直接連接的物理通信通道。1.3.1 并行計算機體系結構的要素27第27頁，共55頁。拓撲結構的幾個重要定義： 并行機規模：并行機包含的結點總數，或者包含的CPU總數； 結點度：互聯網

16、絡拓撲結構中聯入或聯出的一個結點的邊的條數，稱為該結點的度； 結點距離：兩個結點之間跨越的圖的邊的條數； 網絡直徑：網絡中任意兩個結點之間的最長距離； 點對點帶寬：圖中邊對應的物理聯接的物理帶寬； 點對點延遲：圖中任意兩個結點之間的一次零長度消息傳遞必須花費的時間。延遲與結點間距離相關，其中所有結點之間的最小延遲稱為網絡的最小延遲，所有結點之間的最大延遲稱為網絡的最大延遲； 折半寬度：對分網絡成兩個部分（它們的結點個數至多相差1）所必須去掉的邊的網絡帶寬的總和； 總通信帶寬：所有邊的帶寬之和； 1.3.1 并行計算機體系結構的要素28第28頁，共55頁?；ヂ摼W絡評價： 大：結點度、點對點帶寬、

17、折半寬度、總通信帶寬； ?。壕W絡直徑、點對點延遲； 1.3.1 并行計算機體系結構的要素29第29頁，共55頁。按結點間連接的性質，拓撲結構可分為靜態拓撲結構、動態拓撲結構和寬帶互聯網絡三類。靜態拓撲結構：結點之間存在固定的物理聯接方式，程序執行過程中，結點間的點對點聯接關系不變。動態拓撲結構：結點之間無固定的物理聯接關系，而是在聯接路徑的交叉點處用電子開關、路由器或仲裁器等提供動態聯接的特性，主要包含單一總線、多層總線、交叉開關、多級互聯網絡。寬帶互聯網絡：當前，除了專用MPP 系統采用靜態的拓撲結構外，微機機群均采用寬帶互聯網絡連接各個計算結點。1.3.1 并行計算機體系結構的要素30第3

18、0頁，共55頁。Flynn(1966年)分類法是根據系統的指令流和數據流對計算機系統進行分類的一種方法。指令流：機器所執行的指令序列數據流：指令流調用的數據序列（包括輸入數據和中間結果）SISD (Single Instruction stream Single Data stream)SIMD (Single Instruction stream Multiple Data stream)MISD (Multiple Instruction stream Single Data stream)MIMD (Multiple Instruction stream Multiple Data st

19、ream)1.3.2 并行計算機的類型31第31頁，共55頁。SISD：傳統的單處理機系統。由程序生成的一個單指令流，在任意時刻處理單獨的數據項。SIMD：如：陣列處理機系統(Processor Arrays)。由一個控制器負責從存儲器中取出指令并將這些指令發送給各個處理器，每個處理器同步執行相同的指令，但操作不同的數據。MISD：相當于在指令一級并行，而在被操作的數據級串行的情況，實際上這種模型是不能實現的。1.3.2 并行計算機的類型32第32頁，共55頁。MIMD：當今絕大多數并行計算機都屬于這一類。每個處理器擁有一個單獨的程序，每個程序為每一個處理器生成一個指令流，每條指令對不同的數據

20、進行操作。Flynn分類法實際上并不能對所有計算機進行分類，如流水線向量處理機就難于按Flynn分類法簡單地歸為上述四類之一。并行計算機系統除少量專用的SIMD系統外，絕大部分為MIMD系統。1.3.2 并行計算機的類型33第33頁，共55頁。進程：具有一定功能的一段程序的一次運行活動。進程的并行執行方式分為以下幾種：MPMD (Multiple Programs & Multiple Data) 控制并行結構：在這種并行結構中各進程執行的程序不同，操作的數據也不同。各進程既可以是異步執行的，也可以以同步方式執行。SPMD (Single Program & Multiple Data) 數據

21、域并行結構：在分布存儲并行計算機系統上執行的程序，每個進程執行相同的程序，但處理不同的數據。1.3.2 并行計算機的類型34第34頁，共55頁。在SPMD 程序設計中，所有節點機得到相同的程序副本，但程序中可以含有條件語句來決定哪個節點機執行某段程序與否。SPMD并行結構常用于主從結構并行機中從節點機中。1.3.2 并行計算機的類型35第35頁，共55頁。1.3.2 并行計算機的類型（1）并行向量處理機 (Parallel Vector Processors PVP)1976年，出現了具有實用價值的向量處理機Cray-1單處理機，多向量寄存器模式運算速度： 3160M flops平均速度： 2

22、080M flops向量點積速度： 22M flops利用大量的向量寄存器快速地實現向量運算1985年，Cray Inc.推出Cray-2 超級計算機，該機的向量處理速度是Cray-1的12倍 (1G flops)36第36頁，共55頁。PVP結構模型VPVPVP交叉開關SMSMSMVP: Vector Processor SM: Shared Memory37第37頁，共55頁。1.3.2 并行計算機的類型典型的PVP機型80年代中、后期是PVP的時代，有很多PVP相繼問世，如：Convex公司的C3800系列DEC公司的 VAX 9000IBM公司的IBM 390/VFFujitsu公司的

23、VP 2000Cray公司的 YMP-9038第38頁，共55頁。1.3.2 并行計算機的類型（2）對稱多處理機 (Symmetric Multiprocessor SMP)將各處理器經由高速總線（或交叉開關）與共享存儲器相連每個處理器對共享存儲器具有同等的訪問權利每個處理器對I/O設備和其它系統資源享有同等的訪問權利在SMP系統中一般要求每個處理機是相同的 因此稱之為對稱多處理機39第39頁，共55頁。對稱多處理機結構模型P/C總線或交叉開關SMSMSMP/CP/CP/C: Processor/Cache SM: Shared Memory40第40頁，共55頁。1.3.2 并行計算機的類型

24、典型SMP機型SGI公司的SGI Onyx系統和SGI Power ChallengeSequent Computer System, Inc.的Sequent Symmetry S-81系統IBM公司的ES/9000系統和R50Sun公司的SparcCenter 2000我國的曙光1號41第41頁，共55頁。1.3.2 并行計算機的類型（3）大規模并行處理機 (Massively Parallel Processors MPP)采用松耦合體系結構連接各種不同的處理器 即各處理器以使用自己的局部內存為主，處理器之間進行同步通信實現數據交換42第42頁，共55頁。大規模并行處理機結構模型LM1L

25、M2LMnP/C1P/C2P/Cn專用互連網絡P/C: Processor/Cache LM: Local Memory43第43頁，共55頁。1.3.2 并行計算機的類型MPP的優點：突破了只看到一個統一的存儲空間的方式具有良好的可擴展性MPP的缺點：分布存儲要求用戶必須將被操作的數據分配到各局部存儲器中運算過程中用戶要考慮數據在各節點間的傳送和同步44第44頁，共55頁。1.3.2 并行計算機的類型典型的MPP機型：Intel公司的Paragon XP/SMasPar公司的MP-2Thinking Machine公司的CM-5IBM公司的SP 2Cray公司的Cray T3D我國的曙光 1

26、00045第45頁，共55頁。1.3.2 并行計算機的類型（4）分布式共享存儲多處理機系統 (Distributed Shared Memory DSM)DSM系統具有以下特點：存儲器在物理上分布于各處理器附近，但在邏輯上可由多個處理器共享整個內存DSM系統實際上是SMP和MPP結構的折中46第46頁，共55頁。分布式共享存儲多處理機系統LM1LM2LMnP/C1P/C2P/Cn專用互連網絡47第47頁，共55頁。1.3.2 并行計算機的類型DSM的優點：避免了集中式存儲結構中處理器和存儲器的復雜連接有良好的可擴展性相對MPP來說，更容易編程DSM系統需著重考慮的問題：系統應具有維持存儲器訪問一致性的硬件支持相對SMP系統來說，其訪問非物理局部存儲器的時間要更長。48第48頁，共55頁。1.3.2 并行計算機的類型典型的DSM機型：Cray公司的Cray T3ESGI/Cray公司的Origon 2000BBN公司的TC