并行計(jì)算工作原理

單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,2004,年,4,月,1,/149,并行計(jì)算-高性能計(jì)算,并行計(jì)算,(Parallel Computing,）,高端計(jì)算,(High-end Parallel Computing),高性能計(jì)算,(High Performance Computing),超級(jí)計(jì)算,(Super Computing),任何高性能計(jì)算和超級(jí)計(jì)算都離不開(kāi)使用并行技術(shù),2004,年,4,月,2,/149,什么是并行計(jì)算?,并行計(jì)算,:,由運(yùn)行在多個(gè)部件上的小任務(wù)合作來(lái)求解一個(gè)規(guī)模很大的計(jì)算問(wèn)題的一種方法,例,:,在曙光,2000,上用,8,個(gè)節(jié)點(diǎn)計(jì)算的,Mandelbrot,集結(jié)果,(Mandelbrot,為分形理論創(chuàng)始人,),2004,年,4,月,3,/149,現(xiàn)代計(jì)算機(jī)的共同特點(diǎn)：并行性,2004,年,4,月,4,/149,現(xiàn)代計(jì)算機(jī)的共同特點(diǎn)：并行性,2004,年,4,月,5,/149,如何實(shí)現(xiàn)并行計(jì)算?,分而治之,!,2004,年,4,月,6,/149,分而治之,并行化的主要方法,:,分而治之,根據(jù)問(wèn)題的求解過(guò)程，把任務(wù)分成若干子任務(wù),(,任務(wù)級(jí)并行或功能并行,),根據(jù)處理數(shù)據(jù)的方式，形成多個(gè)相對(duì)獨(dú)立的數(shù)據(jù)區(qū)，由不同的處理器分別處理,(,數(shù)據(jù)并行,),并行計(jì)算的特點(diǎn),為利用并行計(jì)算，通常計(jì)算問(wèn)題表現(xiàn)為以下特征：,（,1,）將工作分離成離散部分，有助于同時(shí)解決；,（,2,）隨時(shí)并及時(shí)地執(zhí)行多個(gè)程序指令；,（,3,）多計(jì)算資源下解決問(wèn)題的耗時(shí)要少于單個(gè)計(jì)算資源下的耗時(shí)。

并行計(jì)算是相對(duì)于串行計(jì)算來(lái)說(shuō)的，并行計(jì)算分為,時(shí)間上的并行,和,空間上的并行,時(shí)間上的并行就是指流水線技術(shù)，而空間上的并行則是指用多個(gè)處理器并發(fā)的執(zhí)行計(jì)算并行計(jì)算機(jī)的分類,并行計(jì)算科學(xué)中主要研究的是空間上的并行問(wèn)題,空間上的并行導(dǎo)致了兩類并行機(jī)的產(chǎn)生，按照,Flynn,的說(shuō)法分為：?jiǎn)沃噶盍鞫鄶?shù)據(jù)流（,SIMD,）和多指令流多數(shù)據(jù)流（,MIMD,Multiple Instruction Stream Multiple Data Stream,）我們常用的串行機(jī)也叫做單指令流單數(shù)據(jù)流（,SISD,）SISD,SIMD,MIMD,9,并行計(jì)算機(jī)體系結(jié)構(gòu),組成要素,結(jié)點(diǎn),（,node,）：一個(gè)或多個(gè)處理器組成,互聯(lián)網(wǎng)絡(luò),（,interconnetct network,）：連接結(jié)點(diǎn),內(nèi)存,（,memory,）：多個(gè)存儲(chǔ)模塊組成,10,并行計(jì)算機(jī)體系結(jié)構(gòu),并行計(jì)算機(jī)體系 結(jié)構(gòu)示意圖,內(nèi)存模塊與結(jié)點(diǎn)分離,并行計(jì)算機(jī)體系 結(jié)構(gòu)示意圖,內(nèi)存模塊位于 結(jié)點(diǎn)內(nèi)部,11,操作系統(tǒng)與編程語(yǔ)言,并行計(jì)算機(jī)主流操作系統(tǒng)：,UNIX,/,Linux,AIX,（,IBM,）,HPUX,（,HP,）,Solaris,（,SUN,）,IRIX,（,SGI,）,Linux,編程語(yǔ)言,Fortran 77,/,90,/,95,C,/,C+,2004,年,4,月,12,/149,并行計(jì)算軟件環(huán)境及現(xiàn)狀,操作系統(tǒng)：,UNIX,、,LINUX,、,Windows NT,在,SMP,DSM,并行機(jī)上編譯系統(tǒng)通常具有一定的對(duì)用戶程序,(C/Fortran),進(jìn)程自動(dòng)并行化的能力,但經(jīng)常需要人工干預(yù),(,通過(guò)編譯制導(dǎo),命令行選項(xiàng)等,),以達(dá)到理想的并行效率,.,且并行主要針對(duì)循環(huán)進(jìn)行,(,屬于細(xì)粒度并行,);,在分布式內(nèi)存并行機(jī)上尚無(wú)通過(guò)高效的自動(dòng)并行工具,主要依靠人工編寫(xiě)并行程序,;,并行算法的設(shè)計(jì)及并行程序的編制已成為目前特約大規(guī)模并行計(jì)算機(jī)應(yīng)用的主要障礙,.,并行編程現(xiàn)狀,:,并行軟件開(kāi)發(fā)遠(yuǎn)遠(yuǎn)落后于并行系統(tǒng)體系結(jié)構(gòu)的發(fā)展。

缺少合適的并行軟件是阻礙主流用戶社會(huì)接納并行計(jì)算的原因與串行軟件相比，并行軟件數(shù)量少，功能原始2004,年,4,月,13,/149,?,編程環(huán)境,落后的并行編譯器、調(diào)試器,vs.,通用先進(jìn)的串行編程環(huán)境,.,自動(dòng)并行編譯器遠(yuǎn)遠(yuǎn)滿足不了程序并行化的要求,.,3,算法,并行模型的多樣化,(,并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的多樣性,)vs.,串行編程中的唯一模型,:,馮,.,諾依曼模型,問(wèn)題的并行求解的困難在于問(wèn)題的多樣性和求解過(guò)程中所需的創(chuàng)造性勞動(dòng)，使得這一過(guò)程難以進(jìn)行自動(dòng)化,對(duì)串行機(jī)而言,解法,=,唯一串行算法,+,計(jì)算程序,(,通用,),對(duì)并行機(jī)而言,解法,=,某種并行算法,+,有針對(duì)性的計(jì)算程序,(,很難通用,),J,人,稀少而初級(jí)的并行編程人員,vs.,成熟而經(jīng)驗(yàn)豐富的串行程序員,2004,年,4,月,14,/149,一些途徑,充分,利用順序程序開(kāi)發(fā)的經(jīng)驗(yàn)、方法和工具,，特別是順序領(lǐng)域中的問(wèn)題求解、算法設(shè)計(jì)方法，這是簡(jiǎn)化并行程序開(kāi)發(fā)的重要手段并行程序開(kāi)發(fā)的困難主要在于,問(wèn)題的并行求解,，而不是并行程序設(shè)計(jì)語(yǔ)言從事并行程序設(shè)計(jì)實(shí)踐的人往往把精力耗費(fèi)在為變量分配內(nèi)存、為循環(huán)體尋求并行上，卻忽略對(duì)問(wèn)題本身的分析。

其實(shí)能否并行的決定因素是應(yīng)用問(wèn)題本身在并行算法的設(shè)計(jì)階段,最大限度地開(kāi)發(fā)出問(wèn)題本身固有的并行性,才是提高計(jì)算效率的根本手段只有,粗粒度的并行,，才能具有高的計(jì)算通信比，而粗粒度的并行只能在算法設(shè)計(jì)階段開(kāi)發(fā)出來(lái),15,并行編程環(huán)境,常見(jiàn)的并行編程環(huán)境,消息傳遞,、,共享存儲(chǔ)、數(shù)據(jù)并行,特征,消息傳遞,共享數(shù)據(jù),數(shù)據(jù)并行,典型代表,可移植性,存儲(chǔ)方式,學(xué)習(xí)難度,可擴(kuò)展性,MPI,，,PVM,所有流行并行機(jī),分布式存儲(chǔ),較難,好,OpenMP,SMP,，,DSM,共享存儲(chǔ),容易,較差,HPF,SMP,，,DSM,，,MPP,共享存儲(chǔ),偏易,一般,三種并行編程環(huán)境主要特征一覽,實(shí)現(xiàn),并行編程,常見(jiàn)方法,1.,線程模型（,OpenMP,POSIX),2.,消息傳遞模型（,PVM,，,MPI,）,PVM:Parallel Virtual Machine Computing,MPI:Message Passing Interface,3.,數(shù)據(jù)并行模型（,HPF,）,三者可混合使用,:,如對(duì)以,SMP,為節(jié)點(diǎn)的,Cluster,來(lái)說(shuō),可以在節(jié)點(diǎn)間進(jìn)行消息傳遞,在節(jié)點(diǎn)內(nèi)進(jìn)行共享變量編程,.,18,并行算法,適合在并行機(jī)上實(shí)現(xiàn)的算法,好的并行算法應(yīng)充分發(fā)揮并行機(jī)計(jì)算機(jī)的潛在性能,并行算法,并行算法分類,按運(yùn)算對(duì)象：,數(shù)值并行算法、非數(shù)值并行算法,按并行進(jìn)程執(zhí)行順序：,同步并行算法、異步并行算法、獨(dú)立并行算法,按計(jì)算任務(wù)：,細(xì)粒度并行算法（基于向量和循環(huán)級(jí)并行）中粒度并行算法（基于較大的循環(huán)級(jí)并行）大粒度并行算法（基于子任務(wù)級(jí)并行）,并行的層次,程序級(jí)并行,子程序級(jí)并行,語(yǔ)句級(jí)并行,操作級(jí)并行,微操作級(jí)并行,并行粒度,粗,細(xì),后三層大都由硬件和編譯器負(fù)責(zé)處理，程序員通常處理前兩層的并行,并行計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu),共享內(nèi)存、分布式內(nèi)存、混合型分布式共享內(nèi)存,接點(diǎn)間的連接,按連接方式分類：,Completely-connected,Star,Tree,Linear Array and Ring,Hypercube,集群計(jì)算機(jī)：,通過(guò)高速網(wǎng)絡(luò),LAN,將,PC,機(jī)或工作站連結(jié)而成。

接點(diǎn)間的連接,按連接方式分類：,Completely-connected,Star,Tree,Linear Array and Ring,Hypercube,集群計(jì)算機(jī)：,通過(guò)高速網(wǎng)絡(luò),LAN,將,PC,機(jī)或工作站連結(jié)而成問(wèn)題分解,1.,作用域分解：,與問(wèn)題相關(guān)的數(shù)據(jù)將會(huì)被分解每個(gè)并行的任務(wù)只能使用部分?jǐn)?shù)據(jù)2.,功能分解：關(guān)注要被完成的計(jì)算而不是操作數(shù)據(jù)的計(jì)算問(wèn)題是根據(jù)當(dāng)前一定要完成的任務(wù)劃分的每個(gè)任務(wù)完成全部工作的一部分關(guān)注的問(wèn)題,1,、通信,2,、同步,3,、數(shù)據(jù)依賴,4,、負(fù)載平衡,5,、,I/O,并行計(jì)算的性能分析,1,、加速比（,speedup),2,、并行效率,并行計(jì)算的術(shù)語(yǔ)（,1,）,Task,：可計(jì)算工作在邏輯上不連續(xù)的分區(qū)一個(gè)任務(wù)通常是一個(gè)程序或者類似程序一樣的可以被處理器執(zhí)行的指令集Parallel Task,：一個(gè)任務(wù)可以被多個(gè)處理器安全的并行的執(zhí)行，產(chǎn)生正確的結(jié)果Serial Execution,：程序相繼的執(zhí)行，每次一個(gè)狀態(tài)在最簡(jiǎn)單的情況下，單核處理器就是這樣運(yùn)行的可是，實(shí)際上所有并行的任務(wù)有一些并行程序的區(qū)域一定要串行的執(zhí)行Parallel Execution,：一個(gè)或多個(gè)任務(wù)同時(shí)執(zhí)行的程序，每個(gè)任務(wù)同時(shí)能夠執(zhí)行相同的或不同的代碼語(yǔ)句。

Pipelining,：不同的處理器單元把一個(gè)任務(wù)根據(jù)輸入流來(lái)分解成一系列步驟來(lái)執(zhí)行，相當(dāng)于一條流水線；并行計(jì)算的一種并行計(jì)算的術(shù)語(yǔ)（,2),Shared Memory,（共享內(nèi)存）：,完全從硬件的視角來(lái)描述計(jì)算機(jī)體系結(jié)構(gòu)，所有的處理器直接存取通用的物理內(nèi)存（基于總線結(jié)構(gòu)）在編程的角度上來(lái)看，他指出從并行任務(wù)看內(nèi)存是同樣的視圖，并且能夠直接定位存取相同的邏輯內(nèi)存位置上的內(nèi)容，不管物理內(nèi)存是否真的存在Symmetric Multi-Processor,（對(duì)稱多處理器）：,這種硬件體系結(jié)構(gòu)是多處理器共享一個(gè)地址空間訪問(wèn)所有資源的模型；共享內(nèi)存計(jì)算Distributed Memory,（分布式存儲(chǔ)）：,從硬件的角度來(lái)看，基于網(wǎng)絡(luò)存儲(chǔ)的物理內(nèi)存訪問(wèn)是不常見(jiàn)的在程序模型中，任務(wù)只能看到本地機(jī)器的內(nèi)存，當(dāng)任務(wù)執(zhí)行時(shí)一定要用通信才能訪問(wèn)其他機(jī)器上的內(nèi)存空間Communication,：,并行任務(wù)都需要交換數(shù)據(jù)有幾種方法可以完成，例如：共享內(nèi)存總線、網(wǎng)絡(luò)傳輸，然而不管用什么方法，真實(shí)的數(shù)據(jù)交換事件通常與通信相關(guān)Synchronization,：,實(shí)時(shí)并行任務(wù)的調(diào)度通常與通信相關(guān)總是通過(guò)建立一個(gè)程序內(nèi)的同步點(diǎn)來(lái)完成，一個(gè)任務(wù)在這個(gè)程序點(diǎn)上等待，直到另一個(gè)任務(wù)到達(dá)相同的邏輯設(shè)備點(diǎn)是才能繼續(xù)執(zhí)行。

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