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

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

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

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

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

5、11,操作系統(tǒng)與編程語言,并行計算機(jī)主流操作系統(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,并行機(jī)上編譯系統(tǒng)通常具有一定的對用戶程序,(C/Fortran),進(jìn)程自動并行化的能力,但經(jīng)常需要人工干預(yù),(,通過編譯制導(dǎo),命令行選項等,),以達(dá)到理想的并行效率,.,且并行主要針對循環(huán)進(jìn)行

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

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

8、實踐的人往往把精力耗費在為變量分配內(nèi)存、為循環(huán)體尋求并行上，卻忽略對問題本身的分析。其實能否并行的決定因素是應(yīng)用問題本身?！?在并行算法的設(shè)計階段,最大限度地開發(fā)出問題本身固有的并行性,才是提高計算效率的根本手段。只有,粗粒度的并行,，才能具有高的計算通信比，而粗粒度的并行只能在算法設(shè)計階段開發(fā)出來,15,并行編程環(huán)境,常見的并行編程環(huán)境,消息傳遞,、,共享存儲、數(shù)據(jù)并行,特征,消息傳遞,共享數(shù)據(jù),數(shù)據(jù)并行,典型代表,可移植性,存儲方式,學(xué)習(xí)難度,可擴(kuò)展性,MPI,，,PVM,所有流行并行機(jī),分布式存儲,較難,好,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é)點間進(jìn)行消息傳遞,在節(jié)點內(nèi)進(jìn)行共享變量編程,.,18,并行算法,適合在并行機(jī)上實現(xiàn)的算法,好的并行算法應(yīng)充分發(fā)揮并行機(jī)計算機(jī)的潛在性能,并行算法,并行算法分類,按運算

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

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

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

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

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

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