并行計(jì)算簡(jiǎn)介課件

單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),單擊此處編輯母版標(biāo)題樣式,2004,年,4,月,*,/149,2004,年,4,月,1,/149,講座主要內(nèi)容提示,并行計(jì)算簡(jiǎn)介,編譯環(huán)境,數(shù)學(xué)庫(kù),并行計(jì)算機(jī)體系結(jié)構(gòu),并行軟件環(huán)境,并行計(jì)算機(jī)性能評(píng)測(cè),MPI,、,PVM,、,OpenMP,,2004年4月1/149講座主要內(nèi)容提示并行計(jì)算簡(jiǎn)介,2004,年,4,月,2,/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ù),,計(jì)算科學(xué),與傳統(tǒng)的兩種科學(xué)，即,理論科學(xué),和,實(shí)驗(yàn)科學(xué),，并立被認(rèn)為是人類(lèi)認(rèn)識(shí)自然的三大支柱，他們彼此相輔相成地推動(dòng)科學(xué)發(fā)展與社會(huì)進(jìn)步。在許多情況下，或者是理論模型復(fù)雜甚至理論尚未建立，或者實(shí)驗(yàn)費(fèi)用昂貴甚至無(wú)法進(jìn)行時(shí)，計(jì)算就成了求解問(wèn)題的唯一或主要的手段。,2004年4月2/149并行計(jì)算--高性能計(jì)算并行計(jì)算(Pa,2004,年,4,月,3,/149,并行,:,古老的思想,!,“...,并行計(jì)算并不是什么新的思想,,,只是將它擴(kuò)展應(yīng)用于計(jì)算機(jī)而已”,.,作者也不認(rèn)為這種擴(kuò)展應(yīng)用會(huì)存在什么無(wú)法克服的困難,.,但也不要期待有效的并行編程方法與技術(shù)能夠在一夜之間誕生,.,期間還需要有許多的工作和實(shí)驗(yàn)要做,.,畢竟,,,今天的編程技術(shù),(,串行,),是若干年來(lái)艱苦的探索才取得的,.,現(xiàn)在編程工作似乎成了一種令人單調(diào)乏味的工作,,,事實(shí)上,,,并行編程的出現(xiàn)將會(huì)使重新恢復(fù)編程工作者們的探索精神,...”,(,Gill, S. (1958),,“Parallel Programming”,,The Computer Journal, vol. 1, April, pp. 2-10.),Parallel Programming with MPI,by Peter Pacheco(2000),2004年4月3/149并行:古老的思想!“...并行計(jì)算并,2004,年,4,月,4,/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月4/149什么是并行計(jì)算?并行計(jì)算: 由運(yùn)行在,2004,年,4,月,5,/149,現(xiàn)代計(jì)算機(jī)的共同特點(diǎn)： 并行性,2004年4月5/149現(xiàn)代計(jì)算機(jī)的共同特點(diǎn)：,2004,年,4,月,6,/149,現(xiàn)代計(jì)算機(jī)的共同特點(diǎn)： 并行性,2004年4月6/149現(xiàn)代計(jì)算機(jī)的共同特點(diǎn)：,2004,年,4,月,7,/149,為什么要做并行計(jì)算？ －－應(yīng)用需求,2004年4月7/149為什么要做并行計(jì)算？,2004,年,4,月,8,/149,為什么要做并行計(jì)算？,人類(lèi)對(duì)計(jì)算及性能的要求是無(wú)止境的,從系統(tǒng)的角度,：集成系統(tǒng)資源，以滿足不斷增長(zhǎng)的對(duì)性能和功能的要求,從應(yīng)用的角度,：適當(dāng)分解應(yīng)用，以實(shí)現(xiàn),更大規(guī)模,或,更細(xì)致,的計(jì)算,2004年4月8/149為什么要做并行計(jì)算？人類(lèi)對(duì)計(jì)算及性能,2004,年,4,月,9,/149,為什么要做并行計(jì)算？,問(wèn)題,:,科學(xué)和工程問(wèn)題的數(shù)值模擬與仿真,計(jì)算密集,數(shù)據(jù)密集,網(wǎng)絡(luò)密集,三種混合,,要求,:,在合理的時(shí)限內(nèi)完成計(jì)算任務(wù),秒級(jí) 制造業(yè),分鐘級(jí) 短時(shí)天氣預(yù)報(bào),(,當(dāng)天,),小時(shí)級(jí) 中期天氣預(yù)報(bào),(3~10,日,),盡可能快 長(zhǎng)期天氣預(yù)報(bào),(,氣候,),可計(jì)算 湍流模擬,2004年4月9/149為什么要做并行計(jì)算？問(wèn)題: 科學(xué)和工,2004,年,4,月,10,/149,2004年4月10/149,2004,年,4,月,11,/149,并行計(jì)算的功能,降低單個(gè)問(wèn)題求解的時(shí)間,,增加問(wèn)題求解規(guī)模、提高問(wèn)題求解精度,,(,多機(jī)同時(shí)執(zhí)行多個(gè)串行程序,),容錯(cuò)、更高的可用性、提高吞吐率,2004年4月11/149并行計(jì)算的功能降低單個(gè)問(wèn)題求解的時(shí),2004,年,4,月,12,/149,如何實(shí)現(xiàn)并行計(jì)算,?,,分而治之,!,2004年4月12/149如何實(shí)現(xiàn)并行計(jì)算?分而治之!,2004,年,4,月,13,/149,分而治之,并行化的主要方法,:,分而治之,根據(jù)問(wèn)題的求解過(guò)程，把任務(wù)分成若干子任務(wù),(,任務(wù)級(jí)并行或功能并行,),根據(jù)處理數(shù)據(jù)的方式，形成多個(gè)相對(duì)獨(dú)立的數(shù)據(jù)區(qū)，由不同的處理器分別處理,(,數(shù)據(jù)并行,),2004年4月13/149分而治之并行化的主要方法:分而治之,2004,年,4,月,14,/149,講座主要內(nèi)容提示,并行計(jì)算簡(jiǎn)介,編譯環(huán)境,常用編譯器,編譯優(yōu)化,如何編譯,數(shù)學(xué)庫(kù),并行計(jì)算機(jī)體系結(jié)構(gòu),并行軟件環(huán)境,并行計(jì)算機(jī)性能評(píng)測(cè),MPI,、,PVM,、,OpenMP,,2004年4月14/149講座主要內(nèi)容提示并行計(jì)算簡(jiǎn)介,2004,年,4,月,15,/149,GNU Compiler,GNU Compiler,自由軟件，一般操作系統(tǒng)都自帶,支持,C/C++,、,Fortran77,、,Java,、,COBAL,等等許多語(yǔ)言,支持大部分硬件平臺(tái),高性能計(jì)算中常用的：,C/C++,：,GCC (GNU C/C++ Compiler),Fortran 77,：,G77,不支持,Fortran 90/ 95,不支持,OpenMP,是最常用的編譯器，性能一般,(,相對(duì)于一些針對(duì)特定平臺(tái)優(yōu)化的編譯器,),由于缺少對(duì),Fortran 90/ 95,，限制了其在高性能計(jì)算中的使用,2004年4月15/149GNU CompilerGNU C,2004,年,4,月,16,/149,PGI Compiler,PGI Compiler,由,Portland,公司開(kāi)發(fā)的編譯器,支持,AMD Opteron/Althon,處理器、,Intel Xeon,處理器等，在,Opteron,上同時(shí)支持,32-bit,和,64-bit(),支持,Linux,、,Windows,支持,C/C++,（,pgcc,）、,Fortran77(pgf77),、,Fortran90/95,（,pgf90),、,HPF,（,High Performance Fortran,）,支持多線程和,OpenMP,最新版本：,5.1,需要購(gòu)買(mǎi)，但可以從網(wǎng)上得到,15,天試用版本,,,2004年4月16/149PGI CompilerPGI C,2004,年,4,月,17,/149,Intel Compiler,Intel Compiler,由,Intel,公司針對(duì),Intel,處理器開(kāi)發(fā)（,Xeon,、,Pentium,）,支持,Linux,、,Windows,支持,C/C++,（,icc,：,Intel C/C++ Compiler,）、,Fortran77/90/95,（,ifc,：,Intel Fortran Compiler),支持多線程和,OpenMP,最新版本：,8.0,需要購(gòu)買(mǎi)，但可以從網(wǎng)上得到,30,天試用版本, CompilerInt,2004,年,4,月,18,/149,編譯優(yōu)化,編譯優(yōu)化對(duì)于計(jì)算密集型程序的性能提高非常幫助,優(yōu)化消耗,CPU,資源最多的那部分，即計(jì)算密集部分,一般采用,-O2,、,-O3,可以采用,SIMD,指令集，,eg: Intel,和,AMD,處理器的,MMX,、,SSE1,、,SSE2,具體編譯優(yōu)化的選項(xiàng)和編譯器以及,CPU,相關(guān)，參見(jiàn)編譯器手冊(cè),對(duì)于有些應(yīng)用程序，過(guò)分的優(yōu)化會(huì)導(dǎo)致計(jì)算結(jié)果錯(cuò)誤,2004年4月18/149編譯優(yōu)化編譯優(yōu)化對(duì)于計(jì)算密集型程序,2004,年,4,月,19,/149,編譯優(yōu)化,在雙路,Intel Xeon,平臺(tái)上，采用,SSE2,優(yōu)化和不采用,SSE2,優(yōu)化，所獲得的,HPL,性能。,在這種情況下，,采用,SSE2,技術(shù)得到的性能高出近,90,％,,,2004年4月19/149編譯優(yōu)化在雙路Intel Xeon,2004,年,4,月,20,/149,編譯簡(jiǎn)介,在,Linux,系統(tǒng)中，可執(zhí)行文件沒(méi)有統(tǒng)一的后綴，系統(tǒng)從文件的屬性來(lái)區(qū)分可執(zhí)行文件和不可執(zhí)行文件,大部分編譯器通過(guò)后綴來(lái)區(qū)別輸入文件的類(lèi)別，下面來(lái)介紹常用的一些后綴,.c,：,C,語(yǔ)言源代碼文件,.f,：,Fortran 77,語(yǔ)言源代碼文件,.o,：編譯后的目標(biāo)文件,.a,：由目標(biāo)文件構(gòu)成的檔案庫(kù)文件,.C,、,.cc,、,.cxx,：,C++,源代碼文件,.f90,：,Fortran 90,語(yǔ)言源代碼文件,.h,：程序所包含的頭文件,2004年4月20/149編譯簡(jiǎn)介在Linux系統(tǒng)中，可執(zhí)行,2004,年,4,月,21,/149,基本的用法,,cc/f77/f90 [options] [filenames],,編譯器名 編譯參數(shù) 編譯文件,,其中,options,就是編譯器所需要的參數(shù)，,filenames,給出相關(guān)的文件名稱(chēng),,2004年4月21/149基本的用法,2004,年,4,月,22,/149,常用編譯參數(shù),-c,：只編譯，不連接成為可執(zhí)行文件，編譯器只是由輸入的,.c/.f,等源代碼文件生成,.o,為后綴的目標(biāo)文件，通常用于編譯不包含主程序的子程序文件。,-o output_filename,：確定輸出文件的名稱(chēng)為,output_filename,，同時(shí)這個(gè)名稱(chēng)不能和源文件同名。如果不給出這個(gè)選項(xiàng)，就給出預(yù)設(shè)的可執(zhí)行文件,a.out,-g,：產(chǎn)生符號(hào)調(diào)試工具所必要的符號(hào)資訊，要想對(duì)源代碼進(jìn)行調(diào)試，我們就必須加入這個(gè)選項(xiàng)。,-O,：對(duì)程序進(jìn)行優(yōu)化編譯、連接，采用這個(gè)選項(xiàng)，整個(gè)源代碼會(huì)在編譯、連接過(guò)程中進(jìn)行優(yōu)化處理，這樣產(chǎn)生的可執(zhí)行文件的執(zhí)行效率可以提高，但是，編譯、連接的速度就相應(yīng)地要慢一些。,-O2,、,-O3,、,-O4,：比,-O,更好的優(yōu)化編譯、連接，當(dāng)然整個(gè)編譯、連接過(guò)程會(huì)更慢。（具體和編譯器相關(guān)）,2004年4月22/149常用編譯參數(shù)-c：只編譯，不連接成,2004,年,4,月,23,/149,常用編譯參數(shù),-Idirname,：將,dirname,所指出的目錄加入到程序頭文件目錄列表中，是在預(yù)編譯過(guò)程中使用的參數(shù)。,C,程序中的頭文件包含兩種情況：,A)#include ,B)#include “myinc.h”,,其中，,A,類(lèi)使用尖括號(hào),(),，,B,類(lèi)使用雙引號(hào),(“ ”),。對(duì)于,A,類(lèi)，預(yù)處理程序,cpp,在系統(tǒng)預(yù)設(shè)包含文件目錄,(,如,/usr/include),中搜尋相應(yīng)的文件，而對(duì)于,B,類(lèi)，,cpp,在當(dāng)前目錄中搜尋頭文件，這個(gè)選項(xiàng)的作用是告訴,cpp,，如果在當(dāng)前目錄中沒(méi)有找到需要的文件，就到指定的,dirname,目錄中去尋找。在程序設(shè)計(jì)中，如果我們需要的這種包含文件分別分布在不同的目錄中，就需要逐個(gè)使用,-I,選項(xiàng)給出搜索路徑。,2004年4月23/149常用編譯參數(shù)-Idirname：將,2004,年,4,月,24,/149,常用編譯參數(shù),-Ldirname,：將,dirname,所指出的目錄加入到程序函數(shù)檔案庫(kù)文件的目錄列表中，是在連接過(guò)程中使用的參數(shù)。在預(yù)設(shè)狀態(tài)下，連接程序,ld,在系統(tǒng)的預(yù)設(shè)路徑中,(,如,/usr/lib),尋找所需要的檔案庫(kù)文件，這個(gè)選項(xiàng)告訴連接程序，首先到,-L,指定的目錄中去尋找，然后到系統(tǒng)預(yù)設(shè)路徑中尋找，如果函數(shù)庫(kù)存放在多個(gè)目錄下，就需要依次使用這個(gè)選項(xiàng)，給出相應(yīng)的存放目錄。,-lname,：在連接時(shí)，裝載名字為“,libname.a”,的函數(shù)庫(kù)，該函數(shù)庫(kù)位于系統(tǒng)預(yù)設(shè)的目錄或者由,-L,選項(xiàng)確定的目錄下。例如，,-lm,表示連接名為“,libm.a”,的數(shù)學(xué)函數(shù)庫(kù)。,,上面我們簡(jiǎn)要介紹了編譯器最常用的功能和主要參數(shù)選項(xiàng)，更為詳盡的資料可以參看,Linux,系統(tǒng)的聯(lián)機(jī)幫助。,,2004年4月24/149常用編譯參數(shù)-Ldirname：將,2004,年,4,月,25,/149,GCC,應(yīng)用舉例,1.,gcc hello.c,生成,a.out,2. gcc –o hello helo.c,生成,hello,3. gcc –O –o hello hello.c,生成,hello,4. gcc –O2 –o hello hello.c,生成,hello,5. gcc –c hello.c,生成,hello.o,gcc –o hello hello.o,生成,hello,6. gcc –c hello1.c,生成,hello1.o,gcc –c hello2.c,生成,hello2.o,gcc –o hello hello1.o hello2.o,生成,hello,7. gcc –o test test1.o –lm –I/home/czn/include,2004年4月25/149GCC應(yīng)用舉例1.gcc hel,2004,年,4,月,26,/149,Make,簡(jiǎn)介,在開(kāi)發(fā)大系統(tǒng)時(shí)，經(jīng)常要將程序劃分為許多模塊。各個(gè)模塊之間存在著各種各樣的依賴(lài)關(guān)系，在,Linux,中通常使用,Makefile,來(lái)管理,由于各個(gè)模塊間不可避免存在關(guān)聯(lián)，所以當(dāng)一個(gè)模塊改動(dòng)后，其他模塊也許會(huì)有所更新，當(dāng)然對(duì)小系統(tǒng)來(lái)說(shuō)，手工編譯連接是沒(méi)問(wèn)題，但是如果是一個(gè)大系統(tǒng)，存在很多個(gè)模塊，那么手工編譯的方法就不適用了。,為此，在,Linux,系統(tǒng)中，專(zhuān)門(mén)提供了一個(gè),make,命令來(lái)自動(dòng)維護(hù)目標(biāo)文件,。,與手工編譯和連接相比，,make,命令的優(yōu)點(diǎn)在于他只更新修改過(guò)的文件,，,而對(duì)沒(méi)修改的文件則置之不理，并且,make,命令不會(huì)漏掉一個(gè)需要更新的文件,2004年4月26/149Make簡(jiǎn)介在開(kāi)發(fā)大系統(tǒng)時(shí)，經(jīng)常要,2004,年,4,月,27,/149,一個(gè)簡(jiǎn)單的例子,先舉一個(gè)例子,: a.c b.c,兩個(gè)程序,,a.c extern void p(char *); main() { p("hello world"); },,b.c void p(char *str) {  printf("%sn",str); },Makefile hello: a.c b.c  gcc a.c b.c -o hello,?,注意這里是一個(gè),Tab,執(zhí)行,makegcc a.c b.c -o hello,,產(chǎn)生一個(gè)叫,hello,的可執(zhí)行程序,2004年4月27/149一個(gè)簡(jiǎn)單的例子先舉一個(gè)例子: a.,2004,年,4,月,28,/149,書(shū)寫(xiě),makefile,文件,Makefile,時(shí)由規(guī)則來(lái)組成的,,,每一條規(guī)則都有三部分組成,:,目標(biāo),(object),,依賴(lài),(dependency),和命令,(command).,在上面的例子中,, Makefile,只有一條規(guī)則,,,其目標(biāo)為,hello,,期依賴(lài)為,a.c b.c,,其命令為,gcc a.c b.c -o hello,,依賴(lài)可以是另一條規(guī)則的目標(biāo),,,也可以是文件,.,每一條規(guī)則被這樣處理,.,如目標(biāo)是一個(gè)文件是,:,當(dāng)它的依賴(lài)是文件時(shí),,,如果依賴(lài)的時(shí)間比目標(biāo)要新,,,則運(yùn)行規(guī)則所包含的命令來(lái)更新目標(biāo),;,如果依賴(lài)是另一個(gè)目標(biāo)則用同樣的方法先來(lái)處理這個(gè)目標(biāo),.,如目標(biāo)不是一個(gè)存在的文件時(shí),,,則一定執(zhí)行,.,2004年4月28/149書(shū)寫(xiě)makefile文件Makef,2004,年,4,月,29,/149,一個(gè)簡(jiǎn)單的,makefile,文件,例如,: Makefile,hello: a.o b.o  gcc a.o b.o -o hello a.o: a.c  gcc –c a.c,b.o: b.c  gcc –c b.c,當(dāng)運(yùn)行,make,時(shí)，可以接一目標(biāo)名,(eg:make hello),作為參數(shù)，表示要處理改目標(biāo)。如沒(méi)有參數(shù)，則處理第一個(gè)目標(biāo)。,對(duì)上述例子執(zhí)行,make,，則是處理,hello,這個(gè)目標(biāo)。,hello,依賴(lài)于文件目標(biāo),a.o,和,b.o,，則先去處理,a.o,,調(diào)用,gcc –c a.c,來(lái)更新,a.o,，之后更新,b.o,，最后調(diào)用,gcc a.c b.o -o hello,來(lái)更新,hello,2004年4月29/149一個(gè)簡(jiǎn)單的makefile文件例如,2004,年,4,月,30,/149,Make,中的宏,(macro),在,make,中是用宏，要先定義，然后在,makefile,中引用。宏的定義格式為：,宏名,=,宏的值,(,宏名一般習(xí)慣用大寫(xiě)字母,),例：,,CC = gcc,hello: a.o b.o  $(CC) a.o b.o -o hello,a.o: a.c  $(CC) –c a.c,b.o: b.c  $(CC) –c b.c,2004年4月30/149Make中的宏(macro)在ma,2004,年,4,月,31,/149,系統(tǒng)定義的宏,還有一些設(shè)定好的內(nèi)部變量，它們根據(jù)每一個(gè)規(guī)則內(nèi)容定義。,$@,當(dāng)前規(guī)則的目的文件名,$<,依靠列表中的第一個(gè)依靠文件,$^,整個(gè)依靠的列表（除掉了里面所有重復(fù)的文件名）。,$?,依賴(lài)中所有新于目標(biāo)的,以用變量做許多其它的事情，特別是當(dāng)你把它們和函數(shù)混合 使用的時(shí)候。如果需要更進(jìn)一步的了解，請(qǐng)參考,GNU Make,手冊(cè)。,('man make', 'man makefile'),2004年4月31/149系統(tǒng)定義的宏還有一些設(shè)定好的內(nèi)部變,2004,年,4,月,32,/149,修改原先的,makefile,,CC = gcc,CFLAGS = -O2,OBJS = a.o b.o,hello: $(OBJS),$(CC) $^ -o $@,a.o: a.c,$(CC) $(CFLAGS) -c $<,b.o: b.c,$(CC) $(CFLAGS) -c $<,clean:,rm –f *.o hello,2004年4月32/149修改原先的makefile CC,2004,年,4,月,33,/149,隱含規(guī)則,請(qǐng)注意在上面的例子里，幾個(gè)產(chǎn)生,.o,文件的命令都是一樣的，都是從,.c,文件和相關(guān)文件里產(chǎn)生,.o,文件，這是一個(gè)標(biāo)準(zhǔn)的步驟。,其實(shí),make,已經(jīng)知道怎么做,—,它有一些叫做隱含規(guī)則的內(nèi)置的規(guī)則，這些規(guī)則告訴它當(dāng)你沒(méi)有給出某些命令的時(shí)候，應(yīng)該怎么辦。,如果你把生成,a.o,和,b.o,的命令從它們的規(guī)則中刪除，,make,將會(huì)查找它的隱含規(guī)則，然后會(huì)找到一個(gè)適當(dāng)?shù)拿睢?,它的命令會(huì)使用一些變量，因此你可以按照你的想法來(lái)設(shè)定它：它使用變量,CC,做為編譯器，并且傳遞變量,CFLAGS,CPPFLAGS,TARGET_ARCH,，然后它加入 ‘,-c’,，后面跟變量,$<,，然后是 ‘,-o’,跟變量,$@,。一個(gè)Ｃ編譯的具體命令將會(huì)是：,,$(CC) $(CFLAGS) $(CPPFLAGS) $(TARGET_ARCH) -c $< -o $@,當(dāng)然你可以按照你自己的需要來(lái)定義這些變量。,2004年4月33/149隱含規(guī)則請(qǐng)注意在上面的例子里，幾個(gè),2004,年,4,月,34,/149,講座主要內(nèi)容提示,并行計(jì)算簡(jiǎn)介,編譯環(huán)境,數(shù)學(xué)庫(kù),BLAS,其它,并行計(jì)算機(jī)體系結(jié)構(gòu),并行軟件環(huán)境,并行計(jì)算機(jī)性能評(píng)測(cè),MPI,,2004年4月34/149講座主要內(nèi)容提示并行計(jì)算簡(jiǎn)介,2004,年,4,月,35,/149,BLAS,BLAS,基本線性代數(shù)庫(kù),(,Basic Linear Algebra Subroutines,）,提供最基本的線性代數(shù)函數(shù)接口,分為三級(jí),BLAS 1,（,Level 1,）：向量與向量操作,BLAS 2,（,Level 2,）：矩陣與向量操作,BLAS 3,（,Level 3,）：矩陣與矩陣操作,,2004年4月35/149BLASBLAS,2004,年,4,月,36,/149,LAPACK,LAPACK,：線性代數(shù)計(jì)算子程序包（,Linear Algebra Package,）,LAPACK,是建立在,BLAS 1,、,BLAS 2,和,BLAS 3,基礎(chǔ)之上,使用,Fortran 77,語(yǔ)言開(kāi)發(fā),使用了線性代數(shù)中最新、最精確的算法，同時(shí)采用了將大型矩陣分解成小塊矩陣的方法從而可以有效的使用存儲(chǔ)空間,開(kāi)放源碼，,lib.org/lapack/,,2004年4月36/149LAPACKLAPACK：線性代數(shù),2004,年,4,月,37,/149,ScaLAPACK,ScaLAPACK,：可擴(kuò)展線性代數(shù)庫(kù),(Scalable LAPACK),，是,LAPACK,的增強(qiáng)版本,是美國(guó)能源部,ODE2000,支持開(kāi)發(fā)的,20,多個(gè),ACTS,工具箱之一，由,Oak Ridge,國(guó)家實(shí)驗(yàn)室、加州大學(xué),Berkeley,分校和,Illinois,大學(xué)等聯(lián)合開(kāi)發(fā),分布式存儲(chǔ)環(huán)境運(yùn)行的線性代數(shù)庫(kù)，主要為可擴(kuò)放的、分布存儲(chǔ)的并行計(jì)算機(jī)而設(shè)計(jì)的,支持稠密和帶狀矩陣的各類(lèi)操作，如：乘法、轉(zhuǎn)置、分解等等,開(kāi)發(fā)源碼，,lib.org/scalapack,,,2004年4月37/149ScaLAPACKScaLAPAC,2004,年,4,月,38,/149,常用,BLAS,庫(kù),Linux,自帶,Blas,庫(kù),由,Linux,操作系統(tǒng)提供，在安裝,Linux,時(shí)可以選擇安裝,性能相對(duì)較差,/usr/lib,目錄下,,,2004年4月38/149常用BLAS庫(kù) Linux自帶Bl,2004,年,4,月,39,/149,常用,BLAS,庫(kù) －,ATLAS,ATLAS,開(kāi)放源代碼,(,免費(fèi),),，用戶(hù)可以下載源代碼，在自己的平臺(tái)上編譯,在編譯中調(diào)整性能，達(dá)到性能最優(yōu),包括全部,BLAS,函數(shù)和一部分,LAPACK,函數(shù),提供,C,和,Fortran 77,接口,最新版本：,3.7,http://math- －ATLASATL,2004,年,4,月,40,/149,常用,BLAS,庫(kù) －,GOTO,GOTO,免費(fèi)提供各種平臺(tái)二進(jìn)制代碼的下載,支持,Opteron,、,Xeon,、,Itanium,、,Power,、,Alpha,等平臺(tái),支持,Windows,平臺(tái)（,Xeon,、,Opteron,）,支持多線程,性能最優(yōu),最新版本：,0.9,下載網(wǎng)址：,http://www.cs.utexas.edu/users/kgoto/,,2004年4月40/149常用BLAS庫(kù) －GOTOGOTO,2004,年,4,月,41,/149,常用,BLAS,庫(kù) －,ACML,ACML,ACML,：,AMD Core Math Library,，基于,Opteron,處理器,AMD,公司公司與英國(guó),Numerical Algorithms Group,（,NAG,）共同開(kāi)發(fā),支持,32bit,和,64bit,的,Windows,平臺(tái)、,32bit,和,64bit,的,Linux,平臺(tái),提供一級(jí)、二級(jí)、三級(jí),BLAS,以及,LAPACK,、,FFT,通過(guò),PGI,編譯器同時(shí)支持面向,Linux,開(kāi)發(fā)的,OpenMP,和非,OpenMP,免費(fèi)下載，下載網(wǎng)址：, －ACMLACML,2004,年,4,月,42,/149,常用,BLAS,庫(kù) －,MKL,MKL,Intel,®,Math Kernel Library,Intel,公司開(kāi)發(fā)，針對(duì),Intel,處理器，,Pentium,、,Xeon,、,Itanium,包括諸如,BLAS,和,LAPACK,等線性代數(shù)功能，離散傅利葉變換（,DFT,）以及向量超越函數(shù)（向量數(shù)學(xué)庫(kù),/VML,），以及向量統(tǒng)計(jì)函數(shù)（,VSL,）,Linux,版本和,Windows,版本,需要購(gòu)買(mǎi)，但可以從網(wǎng)上得到,30,天試用版本, －MKLMKL,2004,年,4,月,43,/149,常用,BLAS,庫(kù) －,ESSL,ESSL,ESSL,庫(kù),(Engineering and Scientific Subroutine Library),是,IBM,提供的工程與科學(xué)計(jì)算優(yōu)化庫(kù)，針對(duì),IBM Power,系列處理器,包括：,線性代數(shù)子程序,，,矩陣運(yùn)算,，,線性代數(shù)方程,、,本征系統(tǒng)分析,，,傅立葉變換、卷積與對(duì)射變換及其它信號(hào)處理相關(guān)計(jì)算,，,排序與搜索,，,插值,，,數(shù)值積分,，,微分方程,，,隨機(jī)數(shù)生成,2004年4月43/149常用BLAS庫(kù) －ESSLESSL,2004,年,4,月,44,/149,PETSc,PETSc,：并行可擴(kuò)展科學(xué)計(jì)算工具箱（,Parallel Extensible Toolkits for Scientific Computing,）,核心人員：美國(guó)數(shù)學(xué)與計(jì)算機(jī)部、,Argonne,國(guó)家重點(diǎn)實(shí)驗(yàn)室等等,基于,MPI,、,BLAS,庫(kù)、,LAPACK,庫(kù),使用,Fortran,、,C/C++,開(kāi)發(fā),PETSc,軟件包含一個(gè)功能強(qiáng)大的工具集以在高性能計(jì)算機(jī)上數(shù)值求解偏微分方程及其相關(guān)問(wèn)題,可移植性：,CRAY T3D,，,T3E,，,Origin 2000, IBM SP, HP UX, ASCI Red, Blue Mountain, NOWs,，,LINUX,，,ALPHA,等,公開(kāi)源代碼，免費(fèi)下載,http://www.mcs.anl.gov/petsc,,2004年4月44/149PETScPETSc：并行可擴(kuò)展科,2004,年,4,月,45,/149,PETSc,2004年4月45/149PETSc,2004,年,4,月,46,/149,PETSc,PETSc,的一些模塊處理：,索引集，包括用于向量索引的置換，重新計(jì)數(shù)等,向量,矩陣（一般是,稀疏,的）,分布陣列（對(duì)正規(guī)的基于網(wǎng)格問(wèn)題的并行化有用）,Krylov,子空間方法,預(yù)條件子，包括多重網(wǎng)格和稀疏直接解法器,非線性解法器,解時(shí)間相關(guān)（非線性）,PDEs,的時(shí)間步進(jìn)解法器,,2004年4月46/149PETScPETSc 的一些模塊處,2004,年,4,月,47,/149,講座主要內(nèi)容提示,并行計(jì)算簡(jiǎn)介,編譯環(huán)境,數(shù)學(xué)庫(kù),并行計(jì)算機(jī)體系結(jié)構(gòu),并行軟件環(huán)境,并行計(jì)算機(jī)性能評(píng)測(cè),MPI,、,PVM,、,OpenMP,,2004年4月47/149講座主要內(nèi)容提示并行計(jì)算簡(jiǎn)介,2004,年,4,月,48,/149,并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu),Flynn,分類(lèi)：,SISD, SIMD, MIMD, MISD,,結(jié)構(gòu)模型：,PVP, SMP, MPP, DSM, COW,,訪存模型：,UMA, NUMA, COMA, CC-NUMA, NORMA,2004年4月48/149并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)Flynn分類(lèi)：,2004,年,4,月,49,/149,Flynn,分類(lèi),Flynn(1972),提出指令流、數(shù)據(jù)流和多倍性概念，把不同的計(jì)算機(jī)分為四大類(lèi)：,SISD,（,Single-Instruction Single-Data,）,SIMD,（,Single-Instruction Multi-Data,）,MISD,（,Multi-Instruction Single-Data,）,MIMD,（,Multi-Instruction Multi-Data,）,2004年4月49/149Flynn分類(lèi)Flynn(1972,2004,年,4,月,50,/149,結(jié)構(gòu)模型,2004年4月50/149結(jié)構(gòu)模型,2004,年,4,月,51,/149,共享存儲(chǔ)對(duì)稱(chēng)多處理機(jī)系統(tǒng),(SMP),SMP,:,對(duì)稱(chēng)式共享存儲(chǔ)：任意處理器可直接訪問(wèn)任意內(nèi)存地址,,,且訪問(wèn)延遲、帶寬、幾率都是等價(jià)的,;,系統(tǒng)是對(duì)稱(chēng)的；,微處理器,:,一般少于,64,個(gè),;,處理器不能太多,,,總線和交叉開(kāi)關(guān)的一旦作成難于擴(kuò)展；,例子,: IBM R50, SGI Power Challenge, SUN Enterprise,,曙光一號(hào),2004年4月51/149共享存儲(chǔ)對(duì)稱(chēng)多處理機(jī)系統(tǒng)(SMP),2004,年,4,月,52,/149,分布共享存儲(chǔ)多處理機(jī)系統(tǒng),(DSM),DSM:,分布共享存儲(chǔ),:,內(nèi)存模塊物理上局部于各個(gè)處理器內(nèi)部,,,但邏輯上,(,用戶(hù),),是共享存儲(chǔ)的,;,這種結(jié)構(gòu)也稱(chēng)為基于,Cache,目錄的非一致內(nèi)存訪問(wèn),(CC-NUMA),結(jié)構(gòu),;,局部與遠(yuǎn)程內(nèi)存訪問(wèn)的延遲和帶寬不一致,,3-10,倍,?,高性能并行程序設(shè)計(jì)注意,;,與,SMP,的主要區(qū)別：,DSM,在物理上有分布在各個(gè)節(jié)點(diǎn)的局部?jī)?nèi)存從而形成一個(gè)共享的存儲(chǔ)器；,微處理器,: 16-128,個(gè),,,幾百到千億次,;,代表,: SGI Origin 2000, Cray T3D;,2004年4月52/149分布共享存儲(chǔ)多處理機(jī)系統(tǒng)(DSM),2004,年,4,月,53,/149,大規(guī)模并行計(jì)算機(jī)系統(tǒng),(MPP),MPP:,物理和邏輯上均是分布內(nèi)存,能擴(kuò)展至成百上千個(gè)處理器,(,微處理器或向量處理器,),采用高通信帶寬和低延遲的互聯(lián)網(wǎng)絡(luò),(,專(zhuān)門(mén)設(shè)計(jì)和定制的,),一種異步的,MIMD,機(jī)器；程序系由多個(gè)進(jìn)程組成，每個(gè)都有其私有地址空間，進(jìn)程間采用傳遞消息相互作用；,代表,:CRAY T3E(2048), ASCI Red(3072), IBM SP2,,曙光,1000,；,2004年4月53/149大規(guī)模并行計(jì)算機(jī)系統(tǒng)(MPP)MP,2004,年,4,月,54,/149,機(jī)群系統(tǒng),(Cluster),Cluster:,每個(gè)節(jié)點(diǎn)都是一個(gè)完整的計(jì)算機(jī),各個(gè)節(jié)點(diǎn)通過(guò)高性能網(wǎng)絡(luò)相互連接,網(wǎng)絡(luò)接口和,I/O,總線松耦合連接,每個(gè)節(jié)點(diǎn)有完整的操作系統(tǒng),曙光,2000, 3000, ASCI Blue Mountain (48,臺(tái),128-way DSM Origin 2000,6144,個(gè)處理器,),2004年4月54/149機(jī)群系統(tǒng)(Cluster)Clus,2004,年,4,月,55,/149,訪存模型,UMA:,NORMA:,NUMA:,多處理機(jī)（單地址空間共享存儲(chǔ)器）,,UMA: Uniform Memory Access,NUMA: Nonuniform Memory Access,多計(jì)算機(jī)（多地址空間非共享存儲(chǔ)器）,,NORMA:No-Remote Memory Access,2004年4月55/149訪存模型UMA:NORMA:NUM,2004,年,4,月,56,/149,均勻存儲(chǔ)器存取,(UMA),均勻存儲(chǔ)器存?。?UMA,－,Uniform Memory Access,）,所有處理器,均勻共享,物理存儲(chǔ)器，這里所謂均勻是指所有處理器對(duì)所有存儲(chǔ)字具有相同的存取時(shí)間,每臺(tái)處理器可帶私有高速緩存,外圍設(shè)備也可以一定形式共享,各處理機(jī)之間的通信是通過(guò)共享存儲(chǔ)器的共享變量來(lái)實(shí)現(xiàn)的,這一類(lèi)多處理機(jī)由于對(duì)資源的高度共享,,,常稱(chēng),緊耦合,系統(tǒng),(tightly coupled system),UMA:,2004年4月56/149均勻存儲(chǔ)器存取 (UMA)均勻存儲(chǔ),2004,年,4,月,57,/149,均勻存儲(chǔ)器存取,(UMA),對(duì)稱(chēng)多處理機(jī)系統(tǒng),(symmetric multi-processor),所有處理機(jī)都能同樣訪問(wèn)所有外圍設(shè)備；所有處理機(jī)都能同樣運(yùn)行執(zhí)行程序，如操作系統(tǒng)的內(nèi)核、,I/O,服務(wù)程序,,不對(duì)稱(chēng)處理機(jī)系統(tǒng),(asymmtric multi-processor),只有一臺(tái)或一組處理機(jī)（,MP,主處理機(jī)）執(zhí)行操作系統(tǒng)并操縱,I/O,，其余處理機(jī)（,AP,附屬處理機(jī)）沒(méi)有,I/O,能力,2004年4月57/149均勻存儲(chǔ)器存取 (UMA)對(duì)稱(chēng)多處,2004,年,4,月,58,/149,非均勻存儲(chǔ)訪問(wèn),(NUMA),非均勻存儲(chǔ)訪問(wèn),(NUMA,—,Nonuniform Memory Access),被共享的存儲(chǔ)器在物理上是分布在所有的處理其中的，其所有本地存儲(chǔ)器的集合就組成了全局地址空間,處理器訪問(wèn)存儲(chǔ)器的時(shí)間是不一樣的：訪問(wèn)本地存儲(chǔ)器,(LM),較快，而訪問(wèn)外地的存儲(chǔ)器較慢（此即是非均勻存儲(chǔ)訪問(wèn)名稱(chēng)的由來(lái)）,每臺(tái)處理器可帶私有高速緩存，且外設(shè)也可以某種形式共享,NUMA:,2004年4月58/149非均勻存儲(chǔ)訪問(wèn)(NUMA)非均勻存,2004,年,4,月,59,/149,非遠(yuǎn)程存儲(chǔ)訪問(wèn),(NORMA),非遠(yuǎn)程存儲(chǔ)訪問(wèn),(NORMA,—,No-Remote Memory Access),所有存儲(chǔ)器都是私有的，僅能由其處理器所訪問(wèn),絕大都數(shù)都不支持遠(yuǎn)程存儲(chǔ)器的訪問(wèn),NORMA:,2004年4月59/149非遠(yuǎn)程存儲(chǔ)訪問(wèn)(NORMA)非遠(yuǎn)程,2004,年,4,月,60,/149,結(jié)構(gòu)模型,----,訪存模型,UMA:,NUMA:,NORMA:,2004年4月60/149結(jié)構(gòu)模型 ---- 訪存模型UMA,2004,年,4,月,61,/149,多處理機(jī) ＆ 多計(jì)算機(jī),UMA:,NUMA:,NORMA:,,多處理機(jī),（,共享存儲(chǔ),）,,多計(jì)算機(jī),（,分布式存儲(chǔ),）,2004年4月61/149多處理機(jī) ＆ 多計(jì)算機(jī)UMA:NU,2004,年,4,月,62,/149,幾種體系結(jié)構(gòu)特征比較,2004年4月62/149幾種體系結(jié)構(gòu)特征比較,2004,年,4,月,63,/149,曙光系列,曙光一號(hào),SMP (1993),曙光,1000 MPP (1995),曙光,2000I Cluster (1998),曙光,2000II Cluster (1999),曙光,3000 Cluster (2000),曙光,4000l Cluster (2002),曙光,4000A Cluster (2004),2004年4月63/149曙光系列曙光一號(hào) SMP (199,2004,年,4,月,64,/149,動(dòng)物食物鏈,2004年4月64/149動(dòng)物食物鏈,2004,年,4,月,65,/149,1984,年的計(jì)算機(jī)食物鏈,Mainframe,Vector Supercomputer,Mini Computer,Workstation,PC,2004年4月65/1491984年的計(jì)算機(jī)食物鏈Mainf,2004,年,4,月,66,/149,1994,年的計(jì)算機(jī)食物鏈,Mainframe,Vector Supercomputer,MPP,Workstation,PC,Mini Computer,(hitting wall soon),(future is bleak),2004年4月66/1491994年的計(jì)算機(jī)食物鏈Mainf,2004,年,4,月,67,/149,現(xiàn)在和未來(lái)的計(jì)算機(jī)食物鏈,2004年4月67/149現(xiàn)在和未來(lái)的計(jì)算機(jī)食物鏈,2004,年,4,月,68,/149,講座主要內(nèi)容提示,并行計(jì)算簡(jiǎn)介,編譯環(huán)境,數(shù)學(xué)庫(kù),并行計(jì)算機(jī)體系結(jié)構(gòu),并行軟件環(huán)境,并行計(jì)算機(jī)性能評(píng)測(cè),MPI,,2004年4月68/149講座主要內(nèi)容提示并行計(jì)算簡(jiǎn)介,2004,年,4,月,69,/149,并行計(jì)算軟件環(huán)境及現(xiàn)狀,操作系統(tǒng)：,UNIX,、,LINUX,、,Windows NT,在,SMP,DSM,并行機(jī)上編譯系統(tǒng)通常具有一定的對(duì)用戶(hù)程序,(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ā)展。缺少合適的并行軟件是阻礙主流用戶(hù)社會(huì)接納并行計(jì)算的原因。,?,:,與串行軟件相比，并行軟件數(shù)量少，功能原始。,2004年4月69/149并行計(jì)算軟件環(huán)境及現(xiàn)狀操作系統(tǒng)：U,2004,年,4,月,70,/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月70/149??編程環(huán)境,2004,年,4,月,71,/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ǔ)言?！皬氖虏⑿谐绦蛟O(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),2004年4月71/149一些途徑充分利用順序程序開(kāi)發(fā)的經(jīng)驗(yàn),2004,年,4,月,72,/149,并行軟件程序員的工作,,,,,,,,指令層，非常細(xì)的粒度,數(shù)據(jù)層，細(xì)粒度,控制層，中粒度,任務(wù)層，大粒度,,前兩層大都由硬件和編譯器負(fù)責(zé)處理，程序員通常處理后兩層的并行,,,2004年4月72/149并行軟件程序員的工作 指令層，非常,2004,年,4,月,73,/149,并行程序設(shè)計(jì)方法,隱式并行程序設(shè)計(jì)：,常用傳統(tǒng)的語(yǔ)言編程成順序源編碼，把“并行”交給編譯器實(shí)現(xiàn)自動(dòng)并行,程序的自動(dòng)并行化是一個(gè)理想目標(biāo)，存在難以克服的困難,語(yǔ)言容易，編譯器難,,顯式并行程序設(shè)計(jì)：,在用戶(hù)程序中出現(xiàn)“并行”的調(diào)度語(yǔ)句,顯式的并行程序開(kāi)發(fā)則是解決并行程序開(kāi)發(fā)困難的切實(shí)可行的,語(yǔ)言難，編譯器容易,2004年4月73/149并行程序設(shè)計(jì)方法隱式并行程序設(shè)計(jì)：,2004,年,4,月,74,/149,并行程序設(shè)計(jì)模型,隱式并行（,Implicit Parallel,）,數(shù)據(jù)并行（,Data Parallel,）,共享變量（,Shared Variable,）,消息傳遞（,Message Passing,）,2004年4月74/149并行程序設(shè)計(jì)模型隱式并行（Impl,2004,年,4,月,75,/149,隱式并行,(Implicit Parallel),概況：,程序員用熟悉的,串行語(yǔ)言,編程,(,未作明確的制定并行性,),編譯器,和,運(yùn)行支持系統(tǒng),自動(dòng)轉(zhuǎn)化為并行代碼,特點(diǎn)：,語(yǔ)義簡(jiǎn)單,可移植性好,單線程，易于調(diào)試和驗(yàn)證正確性,細(xì)粒度并行,效率很低,2004年4月75/149隱式并行(Implicit Par,2004,年,4,月,76,/149,數(shù)據(jù)并行（,Data Parallel,）,概況：,SIMD,的自然模型,局部計(jì)算和數(shù)據(jù)選路操作,特點(diǎn)：,單線程,并行操作于聚合數(shù)據(jù)結(jié)構(gòu)（數(shù)組）,松散同步,單一地址空間,隱式交互作用,顯式數(shù)據(jù)分布,優(yōu)點(diǎn),:,編程相對(duì)簡(jiǎn)單,,,串并行程序一致,.,缺點(diǎn),:,程序的性能在很大程度上依賴(lài)于所用的編譯系統(tǒng)及用戶(hù)對(duì)編譯系統(tǒng)的了解,.,并行粒度局限于,數(shù)據(jù)級(jí)并行,,,粒度較小,.,2004年4月76/149數(shù)據(jù)并行（Data Paralle,2004,年,4,月,77,/149,共享變量,(Shared Variable),概況：,PVP, SMP, DSM,的自然模型,特點(diǎn)：,多線程：,SPMD, MPMD,異步,單一地址空間,顯式同步,隱式數(shù)據(jù)分布,隱式通信,典型代表：,OpenMP,2004年4月77/149共享變量(Shared Varia,2004,年,4,月,78,/149,消息傳遞,(Message Passing),概況：,MPP,、,COW,的自然模型,特點(diǎn)：,多線程,異步,多地址空間,顯式同步,顯式數(shù)據(jù)映射和負(fù)載分配,顯式通信,典型代表,MPI,、,PVM,2004年4月78/149消息傳遞(Message Pass,2004,年,4,月,79,/149,并行編程標(biāo)準(zhǔn),數(shù)據(jù)并行語(yǔ)言標(biāo)準(zhǔn),Fortran90, HPF(1992), Fortran95/2001:,顯式數(shù)據(jù)分布描述,,,并行,DO,循環(huán),.,線程庫(kù),標(biāo)準(zhǔn),(Thread Library),– Win32 API.,– POSIX threads,線程模型,.,編譯制導(dǎo),(Compiler Directives),–,OpenMP,: portable shared memory parallelism,消息傳遞庫(kù)標(biāo)準(zhǔn),(Message Passing Libraries),–,MPI,,: Message Passing Interface,–,PVM,: Parallel Virtual Machine,共享變量編程,消息傳遞編程,數(shù)據(jù)并行編程,2004年4月79/149并行編程標(biāo)準(zhǔn)數(shù)據(jù)并行語(yǔ)言標(biāo)準(zhǔn)共享變,2004,年,4,月,80,/149,并行編程標(biāo)準(zhǔn)歸類(lèi),所有并行編程標(biāo)準(zhǔn)可分為以下三類(lèi),:,數(shù)據(jù)并行,HPF, Fortran90,用于,SMP, DSM,共享編程,OpenMP,用于,SMP, DSM,消息傳遞,MPI, PVM,用于所有并行計(jì)算機(jī),三者可混合使用,:,如對(duì)以,SMP,為節(jié)點(diǎn)的,Cluster,來(lái)說(shuō),,,可以在節(jié)點(diǎn)間進(jìn)行消息傳遞,,,在節(jié)點(diǎn)內(nèi)進(jìn)行共享變量編程,.,2004年4月80/149并行編程標(biāo)準(zhǔn)歸類(lèi)所有并行編程標(biāo)準(zhǔn)可,2004,年,4,月,81,/149,基本并行化方法,相并行（,Phase Parallel,）,流水線并行（,Pipeline Parallel,）,主從并行（,Master-Slave Parallel,）,分治并行（,Divide and Conquer Parallel,）,工作池并行（,Work Pool Parallel,）,2004年4月81/149基本并行化方法相并行（Phase,2004,年,4,月,82,/149,講座主要內(nèi)容提示,并行計(jì)算簡(jiǎn)介,編譯環(huán)境,數(shù)學(xué)庫(kù),并行計(jì)算機(jī)體系結(jié)構(gòu),并行軟件環(huán)境,并行計(jì)算機(jī)性能評(píng)測(cè),MPI,、,PVM,、,OpenMP,,2004年4月82/149講座主要內(nèi)容提示并行計(jì)算簡(jiǎn)介,2004,年,4,月,83,/149,并行計(jì)算性能評(píng)測(cè),機(jī)器的理論峰值速度,用戶(hù)能得到的實(shí)際速度,,Benchmark LINPACK,www.top500.org,加速比、效率,S,＝并行算法,(,程序,),性能,/,串行算法,(,程序,),性能,可擴(kuò)展性：體系結(jié)構(gòu)、軟件、算法,隨著計(jì)算負(fù)載的增加和機(jī)器規(guī)模的擴(kuò)大，計(jì)算系統(tǒng)的性能是否隨著處理器的數(shù)目的增加而按比例的增加,性能依賴(lài)因素：,算法設(shè)計(jì)：并行性、計(jì)算量,程序設(shè)計(jì)：體系結(jié)構(gòu)特點(diǎn)的利用,(,通信、存儲(chǔ)、,Cache),、負(fù)載平衡、并行粒度,2004年4月83/149并行計(jì)算性能評(píng)測(cè)機(jī)器的理論峰值速度,2004,年,4,月,84,/149,機(jī)器的理論峰值速度,理論峰值速度,=,CPU,主頻,,×,每個(gè)時(shí)鐘周期執(zhí)行浮點(diǎn)運(yùn)算的次數(shù),×,CPU,數(shù)目,每個(gè)時(shí)鐘周期執(zhí)行浮點(diǎn)運(yùn)算的次數(shù),是由處理器中浮點(diǎn)運(yùn)算單元的個(gè)數(shù)及每個(gè)浮點(diǎn)運(yùn)算單元在每個(gè)時(shí)鐘周期能處理幾條浮點(diǎn)運(yùn)算來(lái)決定的,2004年4月84/149機(jī)器的理論峰值速度理論峰值速度=C,2004,年,4,月,85,/149,基準(zhǔn)測(cè)試程序,(Benchmark),基本測(cè)試程序,SPEC,：原主要是測(cè)試,CPU,性能，現(xiàn)在強(qiáng)調(diào)開(kāi)發(fā)能反映真實(shí)應(yīng)用的基準(zhǔn)測(cè)試程序，并以推廣至客戶(hù),/,服務(wù)器計(jì)算、商業(yè)應(yīng)用、,I/O,子系統(tǒng)等等,,科學(xué)與工程計(jì)算性能,Linpack,：高斯消元法求解線性代數(shù)方程組,NPB(NAS Parallel Benchmark),：美國(guó),NAS,項(xiàng)目開(kāi)發(fā)，包含,8,個(gè)空氣動(dòng)力學(xué)計(jì)算類(lèi)應(yīng)用，測(cè)試范圍從整數(shù)排序到復(fù)雜的數(shù)值計(jì)算,LAPACK,、,ScalLAPACK,：稠密、帶狀矩陣上的各類(lèi)操作,Perfect,、,SPLASH,、,ParkBench,2004年4月85/149基準(zhǔn)測(cè)試程序(Benchmark),2004,年,4,月,86,/149,www.top500.org,2004年4月86/149www.top500.org,2004,年,4,月,87,/149,Linpack,Linpack,是,國(guó)際上流行的用于測(cè)試高性能計(jì)算機(jī)系統(tǒng)浮點(diǎn)性能的,benchmark,,通過(guò)對(duì)高性能計(jì)算機(jī)采用,LU,分解求解線性代數(shù)方程組能力的測(cè)試，評(píng)價(jià)高性能計(jì)算機(jī)的浮點(diǎn)處理性能,2004年4月87/149LinpackLinpack是國(guó)際,2004,年,4,月,88,/149,Linpack,由,J. Dongarra,編寫(xiě)的,Linpack,采用主元高斯消去法求解雙精度,(64bits),稠密線性代數(shù)方程組,結(jié)果按每秒浮點(diǎn)運(yùn)算次數(shù)（,flops,）表示,包含三類(lèi)測(cè)試（問(wèn)題規(guī)模與優(yōu)化選擇各不相同）,100×100,測(cè)試,不允許對(duì),Linpack,測(cè)試程序進(jìn)行任何修改（包括注釋行）。所有的優(yōu)化只能在編譯器里完成,,1000×1000,測(cè)試,允許對(duì)算法和軟件進(jìn)行修改或替換,并盡量利用系統(tǒng)的硬件特點(diǎn)，以達(dá)到盡可能高的性能,但是所有的優(yōu)化都必須保持和標(biāo)準(zhǔn)算法如高斯消去法相同的相對(duì)精度，而且必須使用,Linpack,的主程序進(jìn)行調(diào)用,2004年4月88/149Linpack由J. Dongar,2004,年,4,月,89,/149,HPL,高性能,Linpack,：,HPL,(High Performance Linpack),針對(duì)大規(guī)模的并行計(jì)算機(jī)系統(tǒng)的測(cè)試，,2000,年,9,月發(fā)布,1.0,版,是,TOP500,超級(jí)計(jì)算機(jī)排名的主要依據(jù),采用,MPI,實(shí)現(xiàn)，基于,BLAS,庫(kù)或,VSIPL,庫(kù),用戶(hù)可以選擇矩陣的大小,(,問(wèn)題規(guī)模,),、使用各種優(yōu)化方法來(lái)執(zhí)行測(cè)試程序，尋求最佳的測(cè)試結(jié)果,浮點(diǎn)峰值,＝,總計(jì)算量,,/,計(jì)算時(shí)間,總計(jì)算量＝,2/3 * N^3 – 2*N^2,計(jì)算時(shí)間：可通過(guò)系統(tǒng)時(shí)鐘獲得,2004年4月89/149HPL高性能Linpack：HPL,2004,年,4,月,90,/149,如何做,HPL,測(cè)試,所必須的軟件包,HPL,BLAS,庫(kù)：,GOTO,、,ATLAS,、,ACML,、,MKL,、,Linux,自帶的,BLAS,庫(kù) 等等,編譯器：需要,C,語(yǔ)言和,Fortran 77,編譯器。,eg,：,gcc/g77,、,icc/ifc,、,pgcc/pgf77,等等,并行環(huán)境：,MPI,安裝編譯器、,MPI,、,BLAS,庫(kù)，編譯,HPL,運(yùn)行,xhpl,eg: mpirun –np 4 xhpl,查看結(jié)果文件,2004年4月90/149如何做HPL測(cè)試所必須的軟件包,2004,年,4,月,91,/149,如何做,HPL,測(cè)試,HPL.out,文件或在