《并行計算工作原理》由會員分享，可在線閱讀，更多相關《并行計算工作原理（28頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,2004,年,4,月,1,/149,并行計算-高性能計算,并行計算,(Parallel Computing,）,高端計算,(High-end Parallel Computing),高性能計算,(High Performance Computing),超級計算,(Super Computing),任何高性能計算和超級計算都離不開使用并

2、行技術,2004,年,4,月,2,/149,什么是并行計算?,并行計算,:,由運行在多個部件上的小任務合作來求解一個規(guī)模很大的計算問題的一種方法,例,:,在曙光,2000,上用,8,個節(jié)點計算的,Mandelbrot,集結果,(Mandelbrot,為分形理論創(chuàng)始人,),2004,年,4,月,3,/149,現(xiàn)代計算機的共同特點：并行性,2004,年,4,月,4,/149,現(xiàn)代計算機的共同特點：并行性,2004,年,4,月,5,/149,如何實現(xiàn)并行計算?,分而治之,!,2004,年,4,月,6,/149,分而治之,并行化的主要方法,:,分而治之,根據(jù)問題的求解過程，把任務分成若干子任務,(,任

3、務級并行或功能并行,),根據(jù)處理數(shù)據(jù)的方式，形成多個相對獨立的數(shù)據(jù)區(qū)，由不同的處理器分別處理,(,數(shù)據(jù)并行,),并行計算的特點,為利用并行計算，通常計算問題表現(xiàn)為以下特征：,（,1,）將工作分離成離散部分，有助于同時解決；,（,2,）隨時并及時地執(zhí)行多個程序指令；,（,3,）多計算資源下解決問題的耗時要少于單個計算資源下的耗時。,并行計算是相對于串行計算來說的，并行計算分為,時間上的并行,和,空間上的并行,。時間上的并行就是指流水線技術，而空間上的并行則是指用多個處理器并發(fā)的執(zhí)行計算。,并行計算機的分類,并行計算科學中主要研究的是空間上的并行問題,?？臻g上的并行導致了兩類并行機的產(chǎn)生，按照,F

4、lynn,的說法分為：單指令流多數(shù)據(jù)流（,SIMD,）和多指令流多數(shù)據(jù)流（,MIMD,Multiple Instruction Stream Multiple Data Stream,）。我們常用的串行機也叫做單指令流單數(shù)據(jù)流（,SISD,）。,SISD,SIMD,MIMD,9,并行計算機體系結構,組成要素,結點,（,node,）：一個或多個處理器組成,互聯(lián)網(wǎng)絡,（,interconnetct network,）：連接結點,內存,（,memory,）：多個存儲模塊組成,10,并行計算機體系結構,并行計算機體系 結構示意圖,內存模塊與結點分離,并行計算機體系 結構示意圖,內存模塊位于 結點內部,

5、11,操作系統(tǒng)與編程語言,并行計算機主流操作系統(tǒng)：,UNIX,/,Linux,AIX,（,IBM,）,HPUX,（,HP,）,Solaris,（,SUN,）,IRIX,（,SGI,）,Linux,編程語言,Fortran 77,/,90,/,95,C,/,C+,2004,年,4,月,12,/149,并行計算軟件環(huán)境及現(xiàn)狀,操作系統(tǒng)：,UNIX,、,LINUX,、,Windows NT,在,SMP,DSM,并行機上編譯系統(tǒng)通常具有一定的對用戶程序,(C/Fortran),進程自動并行化的能力,但經(jīng)常需要人工干預,(,通過編譯制導,命令行選項等,),以達到理想的并行效率,.,且并行主要針對循環(huán)進行

6、,(,屬于細粒度并行,);,在分布式內存并行機上尚無通過高效的自動并行工具,主要依靠人工編寫并行程序,;,并行算法的設計及并行程序的編制已成為目前特約大規(guī)模并行計算機應用的主要障礙,.,并行編程現(xiàn)狀,:,并行軟件開發(fā)遠遠落后于并行系統(tǒng)體系結構的發(fā)展。缺少合適的并行軟件是阻礙主流用戶社會接納并行計算的原因。,:,與串行軟件相比，并行軟件數(shù)量少，功能原始。,2004,年,4,月,13,/149,?,編程環(huán)境,落后的并行編譯器、調試器,vs.,通用先進的串行編程環(huán)境,.,自動并行編譯器遠遠滿足不了程序并行化的要求,.,3,算法,并行模型的多樣化,(,并行計算機系統(tǒng)結構的多樣性,)vs.,串行編程中的

7、唯一模型,:,馮,.,諾依曼模型,問題的并行求解的困難在于問題的多樣性和求解過程中所需的創(chuàng)造性勞動，使得這一過程難以進行自動化,對串行機而言,解法,=,唯一串行算法,+,計算程序,(,通用,),對并行機而言,解法,=,某種并行算法,+,有針對性的計算程序,(,很難通用,),J,人,稀少而初級的并行編程人員,vs.,成熟而經(jīng)驗豐富的串行程序員,2004,年,4,月,14,/149,一些途徑,充分,利用順序程序開發(fā)的經(jīng)驗、方法和工具,，特別是順序領域中的問題求解、算法設計方法，這是簡化并行程序開發(fā)的重要手段。,并行程序開發(fā)的困難主要在于,問題的并行求解,，而不是并行程序設計語言?！皬氖虏⑿谐绦蛟O計

8、實踐的人往往把精力耗費在為變量分配內存、為循環(huán)體尋求并行上，卻忽略對問題本身的分析。其實能否并行的決定因素是應用問題本身。”,在并行算法的設計階段,最大限度地開發(fā)出問題本身固有的并行性,才是提高計算效率的根本手段。只有,粗粒度的并行,，才能具有高的計算通信比，而粗粒度的并行只能在算法設計階段開發(fā)出來,15,并行編程環(huán)境,常見的并行編程環(huán)境,消息傳遞,、,共享存儲、數(shù)據(jù)并行,特征,消息傳遞,共享數(shù)據(jù),數(shù)據(jù)并行,典型代表,可移植性,存儲方式,學習難度,可擴展性,MPI,，,PVM,所有流行并行機,分布式存儲,較難,好,OpenMP,SMP,，,DSM,共享存儲,容易,較差,HPF,SMP,，,DS

9、M,，,MPP,共享存儲,偏易,一般,三種并行編程環(huán)境主要特征一覽,實現(xiàn),并行編程,常見方法,1.,線程模型（,OpenMP,POSIX),2.,消息傳遞模型（,PVM,，,MPI,）,PVM:Parallel Virtual Machine Computing,MPI:Message Passing Interface,3.,數(shù)據(jù)并行模型（,HPF,）,三者可混合使用,:,如對以,SMP,為節(jié)點的,Cluster,來說,可以在節(jié)點間進行消息傳遞,在節(jié)點內進行共享變量編程,.,18,并行算法,適合在并行機上實現(xiàn)的算法,好的并行算法應充分發(fā)揮并行機計算機的潛在性能,并行算法,并行算法分類,按運算

10、對象：,數(shù)值并行算法、非數(shù)值并行算法,按并行進程執(zhí)行順序：,同步并行算法、異步并行算法、獨立并行算法,按計算任務：,細粒度并行算法（基于向量和循環(huán)級并行）中粒度并行算法（基于較大的循環(huán)級并行）大粒度并行算法（基于子任務級并行）,并行的層次,程序級并行,子程序級并行,語句級并行,操作級并行,微操作級并行,并行粒度,粗,細,后三層大都由硬件和編譯器負責處理，程序員通常處理前兩層的并行,并行計算機的存儲結構,共享內存、分布式內存、混合型分布式共享內存,接點間的連接,按連接方式分類：,Completely-connected,Star,Tree,Linear Array and Ring,Hyperc

11、ube,集群計算機：,通過高速網(wǎng)絡,LAN,將,PC,機或工作站連結而成。,接點間的連接,按連接方式分類：,Completely-connected,Star,Tree,Linear Array and Ring,Hypercube,集群計算機：,通過高速網(wǎng)絡,LAN,將,PC,機或工作站連結而成。,問題分解,1.,作用域分解：,與問題相關的數(shù)據(jù)將會被分解。每個并行的任務只能使用部分數(shù)據(jù)。,2.,功能分解：關注要被完成的計算而不是操作數(shù)據(jù)的計算。問題是根據(jù)當前一定要完成的任務劃分的。每個任務完成全部工作的一部分。,關注的問題,1,、通信,2,、同步,3,、數(shù)據(jù)依賴,4,、負載平衡,5,、,I/

12、O,并行計算的性能分析,1,、加速比（,speedup),2,、并行效率,并行計算的術語（,1,）,Task,：可計算工作在邏輯上不連續(xù)的分區(qū)。一個任務通常是一個程序或者類似程序一樣的可以被處理器執(zhí)行的指令集。,Parallel Task,：一個任務可以被多個處理器安全的并行的執(zhí)行，產(chǎn)生正確的結果。,Serial Execution,：程序相繼的執(zhí)行，每次一個狀態(tài)。在最簡單的情況下，單核處理器就是這樣運行的?？墒?，實際上所有并行的任務有一些并行程序的區(qū)域一定要串行的執(zhí)行。,Parallel Execution,：一個或多個任務同時執(zhí)行的程序，每個任務同時能夠執(zhí)行相同的或不同的代碼語句。,Pip

13、elining,：不同的處理器單元把一個任務根據(jù)輸入流來分解成一系列步驟來執(zhí)行，相當于一條流水線；并行計算的一種。,并行計算的術語（,2),Shared Memory,（共享內存）：,完全從硬件的視角來描述計算機體系結構，所有的處理器直接存取通用的物理內存（基于總線結構）。在編程的角度上來看，他指出從并行任務看內存是同樣的視圖，并且能夠直接定位存取相同的邏輯內存位置上的內容，不管物理內存是否真的存在。,Symmetric Multi-Processor,（對稱多處理器）：,這種硬件體系結構是多處理器共享一個地址空間訪問所有資源的模型；共享內存計算。,Distributed Memory,（分布

14、式存儲）：,從硬件的角度來看，基于網(wǎng)絡存儲的物理內存訪問是不常見的。在程序模型中，任務只能看到本地機器的內存，當任務執(zhí)行時一定要用通信才能訪問其他機器上的內存空間。,Communication,：,并行任務都需要交換數(shù)據(jù)。有幾種方法可以完成，例如：共享內存總線、網(wǎng)絡傳輸，然而不管用什么方法，真實的數(shù)據(jù)交換事件通常與通信相關。,Synchronization,：,實時并行任務的調度通常與通信相關。總是通過建立一個程序內的同步點來完成，一個任務在這個程序點上等待，直到另一個任務到達相同的邏輯設備點是才能繼續(xù)執(zhí)行。同步至少要等待一個任務，致使并行程序的執(zhí)行時間增加。,并行計算的術語,(3),Obse

15、rved Speedup,：測量代碼并行化之后的加速比。這是最簡單也最廣泛使用的測量并行程序性能的方法。,Parallel Overhead,（并行開銷）,：對并行任務調度花費的時間沒有做有用的工作。并行開銷可以包含如下因素：任務啟動時間、同步、數(shù)據(jù)通信、并行編譯器、庫、工具、操作系統(tǒng)等花費的軟件開銷，任務終止的時間等。,Scalability,：指的是并行系統(tǒng)通過增加更多的處理器的個數(shù)按比例提高并行性能的能力。促進可擴展性的因素有：硬件,特別是內存、,CPU,帶寬和網(wǎng)絡通信，應用程序算法，相關的并行開銷、特定的應用和編碼方式的特征。,Multi-core Processors,：一個,CPU,上有多個處理器。,Cluster Computing,：用一般的處理器單元（處理器、網(wǎng)絡、,SMP,）來構建并行系統(tǒng)。,Supercomputing/High Performance Computing,（高性能計算）,：使用世界上最快最大的機器來解決大規(guī)模的問題。,