《并行計算簡介課件》由會員分享，可在線閱讀，更多相關《并行計算簡介課件（148頁珍藏版）》請在裝配圖網上搜索。

1、單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,單擊此處編輯母版標題樣式,2004,年,4,月,*,/149,2004,年,4,月,1,/149,講座主要內容提示,并行計算簡介,編譯環(huán)境,數(shù)學庫,并行計算機體系結構,并行軟件環(huán)境,并行計算機性能評測,MPI,、,PVM,、,OpenMP,,2004年4月1/149講座主要內容提示并行計算簡介,2004,年,4,月,2,/149,并行計算,--,高性能計算,并行計算,(Parallel Computing,）,,高端計算,(High-end Parallel Computing),,高性能計算,(High Performance Co

2、mputing),,超級計算,(Super Computing),,任何高性能計算和超級計算都離不開使用并行技術,,計算科學,與傳統(tǒng)的兩種科學，即,理論科學,和,實驗科學,，并立被認為是人類認識自然的三大支柱，他們彼此相輔相成地推動科學發(fā)展與社會進步。在許多情況下，或者是理論模型復雜甚至理論尚未建立，或者實驗費用昂貴甚至無法進行時，計算就成了求解問題的唯一或主要的手段。,2004年4月2/149并行計算--高性能計算并行計算(Pa,2004,年,4,月,3,/149,并行,:,古老的思想,!,“...,并行計算并不是什么新的思想,,,只是將它擴展應用于計算機而已”,.,作者也不認為這種擴展應用

3、會存在什么無法克服的困難,.,但也不要期待有效的并行編程方法與技術能夠在一夜之間誕生,.,期間還需要有許多的工作和實驗要做,.,畢竟,,,今天的編程技術,(,串行,),是若干年來艱苦的探索才取得的,.,現(xiàn)在編程工作似乎成了一種令人單調乏味的工作,,,事實上,,,并行編程的出現(xiàn)將會使重新恢復編程工作者們的探索精神,...”,(,Gill, S. (1958),,“Parallel Programming”,,The Computer Journal, vol. 1, April, pp. 2-10.),Parallel Programming with MPI,by Peter Pacheco(

4、2000),2004年4月3/149并行:古老的思想!“...并行計算并,2004,年,4,月,4,/149,什么是并行計算,?,并行計算,:,,由運行在多個部件上的小任務合作來求解一個規(guī)模很大的計算問題的一種方法,,例,:,在曙光,2000,上用,8,個節(jié)點計算的,Mandelbrot,集結果,(Mandelbrot,為分形理論創(chuàng)始人,),,2004年4月4/149什么是并行計算?并行計算: 由運行在,2004,年,4,月,5,/149,現(xiàn)代計算機的共同特點： 并行性,2004年4月5/149現(xiàn)代計算機的共同特點：,2004,年,4,月,6,/149

5、,現(xiàn)代計算機的共同特點： 并行性,2004年4月6/149現(xiàn)代計算機的共同特點：,2004,年,4,月,7,/149,為什么要做并行計算？ －－應用需求,2004年4月7/149為什么要做并行計算？,2004,年,4,月,8,/149,為什么要做并行計算？,人類對計算及性能的要求是無止境的,從系統(tǒng)的角度,：集成系統(tǒng)資源，以滿足不斷增長的對性能和功能的要求,從應用的角度,：適當分解應用，以實現(xiàn),更大規(guī)模,或,更細致,的計算,2004年4月8/149為什么要做并行計算？人類對計算及性能,2004,年,4,月,9,/149,為

6、什么要做并行計算？,問題,:,科學和工程問題的數(shù)值模擬與仿真,計算密集,數(shù)據(jù)密集,網絡密集,三種混合,,要求,:,在合理的時限內完成計算任務,秒級 制造業(yè),分鐘級 短時天氣預報,(,當天,),小時級 中期天氣預報,(3~10,日,),盡可能快 長期天氣預報,(,氣候,),可計算 湍流模擬,2004年4月9/149為什么要做并行計算？問題: 科學和工,2004,年,4,月,10,/149,2004年4月10/149,2004,年,4,月,11,/149,并行計算的功能,降低單個問題求解的時間,,增加問題求解規(guī)模、提高問題求解精度,,(,多機同時執(zhí)行多個串行程序,),容錯、更高的可用性、提

7、高吞吐率,2004年4月11/149并行計算的功能降低單個問題求解的時,2004,年,4,月,12,/149,如何實現(xiàn)并行計算,?,,分而治之,!,2004年4月12/149如何實現(xiàn)并行計算?分而治之!,2004,年,4,月,13,/149,分而治之,并行化的主要方法,:,分而治之,根據(jù)問題的求解過程，把任務分成若干子任務,(,任務級并行或功能并行,),根據(jù)處理數(shù)據(jù)的方式，形成多個相對獨立的數(shù)據(jù)區(qū)，由不同的處理器分別處理,(,數(shù)據(jù)并行,),2004年4月13/149分而治之并行化的主要方法:分而治之,2004,年,4,月,14,/149,講座主要內容提示,并行計算簡介,編譯環(huán)境,常用編譯器,編

8、譯優(yōu)化,如何編譯,數(shù)學庫,并行計算機體系結構,并行軟件環(huán)境,并行計算機性能評測,MPI,、,PVM,、,OpenMP,,2004年4月14/149講座主要內容提示并行計算簡介,2004,年,4,月,15,/149,GNU Compiler,GNU Compiler,自由軟件，一般操作系統(tǒng)都自帶,支持,C/C++,、,Fortran77,、,Java,、,COBAL,等等許多語言,支持大部分硬件平臺,高性能計算中常用的：,C/C++,：,GCC (GNU C/C++ Compiler),Fortran 77,：,G77,不支持,Fortran 90/ 95,不支持,OpenMP,是最常用的編譯器

9、，性能一般,(,相對于一些針對特定平臺優(yōu)化的編譯器,),由于缺少對,Fortran 90/ 95,，限制了其在高性能計算中的使用,2004年4月15/149GNU CompilerGNU C,2004,年,4,月,16,/149,PGI Compiler,PGI Compiler,由,Portland,公司開發(fā)的編譯器,支持,AMD Opteron/Althon,處理器、,Intel Xeon,處理器等，在,Opteron,上同時支持,32-bit,和,64-bit(),支持,Linux,、,Windows,支持,C/C++,（,pgcc,）、,Fortran77(pgf77),、,Fortr

10、an90/95,（,pgf90),、,HPF,（,High Performance Fortran,）,支持多線程和,OpenMP,最新版本：,5.1,需要購買，但可以從網上得到,15,天試用版本,,,2004年4月16/149PGI CompilerPGI C,2004,年,4,月,17,/149,Intel Compiler,Intel Compiler,由,Intel,公司針對,Intel,處理器開發(fā)（,Xeon,、,Pentium,）,支持,Linux,、,Windows,支持,C/C++,（,icc,：,Intel C/C++ Compiler,）、,Fortran77/90/95,

11、（,ifc,：,Intel Fortran Compiler),支持多線程和,OpenMP,最新版本：,8.0,需要購買，但可以從網上得到,30,天試用版本, CompilerInt,2004,年,4,月,18,/149,編譯優(yōu)化,編譯優(yōu)化對于計算密集型程序的性能提高非常幫助,優(yōu)化消耗,CPU,資源最多的那部分，即計算密集部分,一般采用,-O2,、,-O3,可以采用,SIMD,指令集，,eg: Intel,和,AMD,處理器的,MMX,、,SSE1,、,SSE2,具體編譯優(yōu)化的選項和編譯器以及,CPU,相關，參見編譯器手冊,對于有些應用程序，過分的優(yōu)化會導致計算結果錯誤,2004年4月18/1

12、49編譯優(yōu)化編譯優(yōu)化對于計算密集型程序,2004,年,4,月,19,/149,編譯優(yōu)化,在雙路,Intel Xeon,平臺上，采用,SSE2,優(yōu)化和不采用,SSE2,優(yōu)化，所獲得的,HPL,性能。,在這種情況下，,采用,SSE2,技術得到的性能高出近,90,％,,,2004年4月19/149編譯優(yōu)化在雙路Intel Xeon,2004,年,4,月,20,/149,編譯簡介,在,Linux,系統(tǒng)中，可執(zhí)行文件沒有統(tǒng)一的后綴，系統(tǒng)從文件的屬性來區(qū)分可執(zhí)行文件和不可執(zhí)行文件,大部分編譯器通過后綴來區(qū)別輸入文件的類別，下面來介紹常用的一些后綴,.c,：,C,語言源代碼文件,.f,：,Fortran 7

13、7,語言源代碼文件,.o,：編譯后的目標文件,.a,：由目標文件構成的檔案庫文件,.C,、,.cc,、,.cxx,：,C++,源代碼文件,.f90,：,Fortran 90,語言源代碼文件,.h,：程序所包含的頭文件,2004年4月20/149編譯簡介在Linux系統(tǒng)中，可執(zhí)行,2004,年,4,月,21,/149,基本的用法,,cc/f77/f90 [options] [filenames],,編譯器名 編譯參數(shù) 編譯文件,,其中,options,就是編譯器所需要的參數(shù)，,filenames,給出相關的文件名稱,,2004年4月21/149基本的用法,2004,年,4,月,22,/14

14、9,常用編譯參數(shù),-c,：只編譯，不連接成為可執(zhí)行文件，編譯器只是由輸入的,.c/.f,等源代碼文件生成,.o,為后綴的目標文件，通常用于編譯不包含主程序的子程序文件。,-o output_filename,：確定輸出文件的名稱為,output_filename,，同時這個名稱不能和源文件同名。如果不給出這個選項，就給出預設的可執(zhí)行文件,a.out,-g,：產生符號調試工具所必要的符號資訊，要想對源代碼進行調試，我們就必須加入這個選項。,-O,：對程序進行優(yōu)化編譯、連接，采用這個選項，整個源代碼會在編譯、連接過程中進行優(yōu)化處理，這樣產生的可執(zhí)行文件的執(zhí)行效率可以提高，但是，編譯、連接的速度就相

15、應地要慢一些。,-O2,、,-O3,、,-O4,：比,-O,更好的優(yōu)化編譯、連接，當然整個編譯、連接過程會更慢。（具體和編譯器相關）,2004年4月22/149常用編譯參數(shù)-c：只編譯，不連接成,2004,年,4,月,23,/149,常用編譯參數(shù),-Idirname,：將,dirname,所指出的目錄加入到程序頭文件目錄列表中，是在預編譯過程中使用的參數(shù)。,C,程序中的頭文件包含兩種情況：,A)#include ,B)#include “myinc.h”,,其中，,A,類使用尖括號,(),，,B,類使用雙引號,(“ ”),。對于,A,類，預處理程序,cpp,在系統(tǒng)預設包含文件目錄,(,如,/u

16、sr/include),中搜尋相應的文件，而對于,B,類，,cpp,在當前目錄中搜尋頭文件，這個選項的作用是告訴,cpp,，如果在當前目錄中沒有找到需要的文件，就到指定的,dirname,目錄中去尋找。在程序設計中，如果我們需要的這種包含文件分別分布在不同的目錄中，就需要逐個使用,-I,選項給出搜索路徑。,2004年4月23/149常用編譯參數(shù)-Idirname：將,2004,年,4,月,24,/149,常用編譯參數(shù),-Ldirname,：將,dirname,所指出的目錄加入到程序函數(shù)檔案庫文件的目錄列表中，是在連接過程中使用的參數(shù)。在預設狀態(tài)下，連接程序,ld,在系統(tǒng)的預設路徑中,(,如,/

17、usr/lib),尋找所需要的檔案庫文件，這個選項告訴連接程序，首先到,-L,指定的目錄中去尋找，然后到系統(tǒng)預設路徑中尋找，如果函數(shù)庫存放在多個目錄下，就需要依次使用這個選項，給出相應的存放目錄。,-lname,：在連接時，裝載名字為“,libname.a”,的函數(shù)庫，該函數(shù)庫位于系統(tǒng)預設的目錄或者由,-L,選項確定的目錄下。例如，,-lm,表示連接名為“,libm.a”,的數(shù)學函數(shù)庫。,,上面我們簡要介紹了編譯器最常用的功能和主要參數(shù)選項，更為詳盡的資料可以參看,Linux,系統(tǒng)的聯(lián)機幫助。,,2004年4月24/149常用編譯參數(shù)-Ldirname：將,2004,年,4,月,25,/149

18、,GCC,應用舉例,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.

19、 gcc –o test test1.o –lm –I/home/czn/include,2004年4月25/149GCC應用舉例1.gcc hel,2004,年,4,月,26,/149,Make,簡介,在開發(fā)大系統(tǒng)時，經常要將程序劃分為許多模塊。各個模塊之間存在著各種各樣的依賴關系，在,Linux,中通常使用,Makefile,來管理,由于各個模塊間不可避免存在關聯(lián)，所以當一個模塊改動后，其他模塊也許會有所更新，當然對小系統(tǒng)來說，手工編譯連接是沒問題，但是如果是一個大系統(tǒng)，存在很多個模塊，那么手工編譯的方法就不適用了。,為此，在,Linux,系統(tǒng)中，專門提供了一個,make,命令來自動維護

20、目標文件,。,與手工編譯和連接相比，,make,命令的優(yōu)點在于他只更新修改過的文件,，,而對沒修改的文件則置之不理，并且,make,命令不會漏掉一個需要更新的文件,2004年4月26/149Make簡介在開發(fā)大系統(tǒng)時，經常要,2004,年,4,月,27,/149,一個簡單的例子,先舉一個例子,: a.c b.c,兩個程序,,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

21、  gcc a.c b.c -o hello,?,注意這里是一個,Tab,執(zhí)行,makegcc a.c b.c -o hello,,產生一個叫,hello,的可執(zhí)行程序,2004年4月27/149一個簡單的例子先舉一個例子: a.,2004,年,4,月,28,/149,書寫,makefile,文件,Makefile,時由規(guī)則來組成的,,,每一條規(guī)則都有三部分組成,:,目標,(object),,依賴,(dependency),和命令,(command).,在上面的例子中,, Makefile,只有一條規(guī)則,,,其目標為,hello,,期依賴為,a.c b.c,,其命令為,gcc a.

22、c b.c -o hello,,依賴可以是另一條規(guī)則的目標,,,也可以是文件,.,每一條規(guī)則被這樣處理,.,如目標是一個文件是,:,當它的依賴是文件時,,,如果依賴的時間比目標要新,,,則運行規(guī)則所包含的命令來更新目標,;,如果依賴是另一個目標則用同樣的方法先來處理這個目標,.,如目標不是一個存在的文件時,,,則一定執(zhí)行,.,2004年4月28/149書寫makefile文件Makef,2004,年,4,月,29,/149,一個簡單的,makefile,文件,例如,: Makefile,hello: a.o b.o  gcc a.o b.o -o hello a.o: a.c 

23、 gcc –c a.c,b.o: b.c  gcc –c b.c,當運行,make,時，可以接一目標名,(eg:make hello),作為參數(shù)，表示要處理改目標。如沒有參數(shù)，則處理第一個目標。,對上述例子執(zhí)行,make,，則是處理,hello,這個目標。,hello,依賴于文件目標,a.o,和,b.o,，則先去處理,a.o,,調用,gcc –c a.c,來更新,a.o,，之后更新,b.o,，最后調用,gcc a.c b.o -o hello,來更新,hello,2004年4月29/149一個簡單的makefile文件例如,2004,年,4,月,30,/149,Make,中的宏,(m

24、acro),在,make,中是用宏，要先定義，然后在,makefile,中引用。宏的定義格式為：,宏名,=,宏的值,(,宏名一般習慣用大寫字母,),例：,,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)定義的宏,還有一些設定好的內部變量，它們根據(jù)每一個規(guī)則內容定義。,$@,當前規(guī)則的目的文件名,$<,依靠列表中的第一個依靠

25、文件,$^,整個依靠的列表（除掉了里面所有重復的文件名）。,$?,依賴中所有新于目標的,以用變量做許多其它的事情，特別是當你把它們和函數(shù)混合 使用的時候。如果需要更進一步的了解，請參考,GNU Make,手冊。,('man make', 'man makefile'),2004年4月31/149系統(tǒng)定義的宏還有一些設定好的內部變,2004,年,4,月,32,/149,修改原先的,makefile,,CC = gcc,CFLAGS = -O2,OBJS = a.o b.o,hello: $(OBJS),$(CC) $^ -o $@,a.o: a.c,$(CC) $(CFLAGS

26、) -c $<,b.o: b.c,$(CC) $(CFLAGS) -c $<,clean:,rm –f *.o hello,2004年4月32/149修改原先的makefile CC,2004,年,4,月,33,/149,隱含規(guī)則,請注意在上面的例子里，幾個產生,.o,文件的命令都是一樣的，都是從,.c,文件和相關文件里產生,.o,文件，這是一個標準的步驟。,其實,make,已經知道怎么做,—,它有一些叫做隱含規(guī)則的內置的規(guī)則，這些規(guī)則告訴它當你沒有給出某些命令的時候，應該怎么辦。,如果你把生成,a.o,和,b.o,的命令從它們的規(guī)則中刪除，,make,將會查找它的隱含規(guī)則，然后會找到一個適當

27、的命令。,,它的命令會使用一些變量，因此你可以按照你的想法來設定它：它使用變量,CC,做為編譯器，并且傳遞變量,CFLAGS,CPPFLAGS,TARGET_ARCH,，然后它加入 ‘,-c’,，后面跟變量,$<,，然后是 ‘,-o’,跟變量,$@,。一個Ｃ編譯的具體命令將會是：,,$(CC) $(CFLAGS) $(CPPFLAGS) $(TARGET_ARCH) -c $< -o $@,當然你可以按照你自己的需要來定義這些變量。,2004年4月33/149隱含規(guī)則請注意在上面的例子里，幾個,2004,年,4,月,34,/149,講座主要內容提示,并行計算簡介,編譯環(huán)境,數(shù)學庫,BLAS,其

28、它,并行計算機體系結構,并行軟件環(huán)境,并行計算機性能評測,MPI,,2004年4月34/149講座主要內容提示并行計算簡介,2004,年,4,月,35,/149,BLAS,BLAS,基本線性代數(shù)庫,(,Basic Linear Algebra Subroutines,）,提供最基本的線性代數(shù)函數(shù)接口,分為三級,BLAS 1,（,Level 1,）：向量與向量操作,BLAS 2,（,Level 2,）：矩陣與向量操作,BLAS 3,（,Level 3,）：矩陣與矩陣操作,,2004年4月35/149BLASBLAS,2004,年,4,月,36,/149,LAPACK,LAPACK,：線性代數(shù)計算

29、子程序包（,Linear Algebra Package,）,LAPACK,是建立在,BLAS 1,、,BLAS 2,和,BLAS 3,基礎之上,使用,Fortran 77,語言開發(fā),使用了線性代數(shù)中最新、最精確的算法，同時采用了將大型矩陣分解成小塊矩陣的方法從而可以有效的使用存儲空間,開放源碼，,lib.org/lapack/,,2004年4月36/149LAPACKLAPACK：線性代數(shù),2004,年,4,月,37,/149,ScaLAPACK,ScaLAPACK,：可擴展線性代數(shù)庫,(Scalable LAPACK),，是,LAPACK,的增強版本,是美國能源部,ODE2000,支持開發(fā)

30、的,20,多個,ACTS,工具箱之一，由,Oak Ridge,國家實驗室、加州大學,Berkeley,分校和,Illinois,大學等聯(lián)合開發(fā),分布式存儲環(huán)境運行的線性代數(shù)庫，主要為可擴放的、分布存儲的并行計算機而設計的,支持稠密和帶狀矩陣的各類操作，如：乘法、轉置、分解等等,開發(fā)源碼，,lib.org/scalapack,,,2004年4月37/149ScaLAPACKScaLAPAC,2004,年,4,月,38,/149,常用,BLAS,庫,Linux,自帶,Blas,庫,由,Linux,操作系統(tǒng)提供，在安裝,Linux,時可以選擇安裝,性能相對較差,/usr/lib,目錄下,,,2004

31、年4月38/149常用BLAS庫 Linux自帶Bl,2004,年,4,月,39,/149,常用,BLAS,庫 －,ATLAS,ATLAS,開放源代碼,(,免費,),，用戶可以下載源代碼，在自己的平臺上編譯,在編譯中調整性能，達到性能最優(yōu),包括全部,BLAS,函數(shù)和一部分,LAPACK,函數(shù),提供,C,和,Fortran 77,接口,最新版本：,3.7,http://math- －ATLASATL,2004,年,4,月,40,/149,常用,BLAS,庫 －,GOTO,GOTO,免費提供各種平臺二進制代碼的下載,支持,Opteron,、,Xeon,、,Itanium,、,Power,、,Alp

32、ha,等平臺,支持,Windows,平臺（,Xeon,、,Opteron,）,支持多線程,性能最優(yōu),最新版本：,0.9,下載網址：,http://www.cs.utexas.edu/users/kgoto/,,2004年4月40/149常用BLAS庫 －GOTOGOTO,2004,年,4,月,41,/149,常用,BLAS,庫 －,ACML,ACML,ACML,：,AMD Core Math Library,，基于,Opteron,處理器,AMD,公司公司與英國,Numerical Algorithms Group,（,NAG,）共同開發(fā),支持,32bit,和,64bit,的,Windows,

33、平臺、,32bit,和,64bit,的,Linux,平臺,提供一級、二級、三級,BLAS,以及,LAPACK,、,FFT,通過,PGI,編譯器同時支持面向,Linux,開發(fā)的,OpenMP,和非,OpenMP,免費下載，下載網址：, －ACMLACML,2004,年,4,月,42,/149,常用,BLAS,庫 －,MKL,MKL,Intel,?,Math Kernel Library,Intel,公司開發(fā)，針對,Intel,處理器，,Pentium,、,Xeon,、,Itanium,包括諸如,BLAS,和,LAPACK,等線性代數(shù)功能，離散傅利葉變換（,DFT,）以及向量超越函數(shù)（向量數(shù)學庫,

34、/VML,），以及向量統(tǒng)計函數(shù)（,VSL,）,Linux,版本和,Windows,版本,需要購買，但可以從網上得到,30,天試用版本, －MKLMKL,2004,年,4,月,43,/149,常用,BLAS,庫 －,ESSL,ESSL,ESSL,庫,(Engineering and Scientific Subroutine Library),是,IBM,提供的工程與科學計算優(yōu)化庫，針對,IBM Power,系列處理器,包括：,線性代數(shù)子程序,，,矩陣運算,，,線性代數(shù)方程,、,本征系統(tǒng)分析,，,傅立葉變換、卷積與對射變換及其它信號處理相關計算,，,排序與搜索,，,插值,，,數(shù)值積分,，,微分方

35、程,，,隨機數(shù)生成,2004年4月43/149常用BLAS庫 －ESSLESSL,2004,年,4,月,44,/149,PETSc,PETSc,：并行可擴展科學計算工具箱（,Parallel Extensible Toolkits for Scientific Computing,）,核心人員：美國數(shù)學與計算機部、,Argonne,國家重點實驗室等等,基于,MPI,、,BLAS,庫、,LAPACK,庫,使用,Fortran,、,C/C++,開發(fā),PETSc,軟件包含一個功能強大的工具集以在高性能計算機上數(shù)值求解偏微分方程及其相關問題,可移植性：,CRAY T3D,，,T3E,，,Origin

36、2000, IBM SP, HP UX, ASCI Red, Blue Mountain, NOWs,，,LINUX,，,ALPHA,等,公開源代碼，免費下載,http://www.mcs.anl.gov/petsc,,2004年4月44/149PETScPETSc：并行可擴展科,2004,年,4,月,45,/149,PETSc,2004年4月45/149PETSc,2004,年,4,月,46,/149,PETSc,PETSc,的一些模塊處理：,索引集，包括用于向量索引的置換，重新計數(shù)等,向量,矩陣（一般是,稀疏,的）,分布陣列（對正規(guī)的基于網格問題的并行化有用）,Krylov,子空間方法,預

37、條件子，包括多重網格和稀疏直接解法器,非線性解法器,解時間相關（非線性）,PDEs,的時間步進解法器,,2004年4月46/149PETScPETSc 的一些模塊處,2004,年,4,月,47,/149,講座主要內容提示,并行計算簡介,編譯環(huán)境,數(shù)學庫,并行計算機體系結構,并行軟件環(huán)境,并行計算機性能評測,MPI,、,PVM,、,OpenMP,,2004年4月47/149講座主要內容提示并行計算簡介,2004,年,4,月,48,/149,并行計算機系統(tǒng)結構,Flynn,分類：,SISD, SIMD, MIMD, MISD,,結構模型：,PVP, SMP, MPP, DSM, COW,,訪存模型

38、：,UMA, NUMA, COMA, CC-NUMA, NORMA,2004年4月48/149并行計算機系統(tǒng)結構Flynn分類：,2004,年,4,月,49,/149,Flynn,分類,Flynn(1972),提出指令流、數(shù)據(jù)流和多倍性概念，把不同的計算機分為四大類：,SISD,（,Single-Instruction Single-Data,）,SIMD,（,Single-Instruction Multi-Data,）,MISD,（,Multi-Instruction Single-Data,）,MIMD,（,Multi-Instruction Multi-Data,）,2004年4月49

39、/149Flynn分類Flynn(1972,2004,年,4,月,50,/149,結構模型,2004年4月50/149結構模型,2004,年,4,月,51,/149,共享存儲對稱多處理機系統(tǒng),(SMP),SMP,:,對稱式共享存儲：任意處理器可直接訪問任意內存地址,,,且訪問延遲、帶寬、幾率都是等價的,;,系統(tǒng)是對稱的；,微處理器,:,一般少于,64,個,;,處理器不能太多,,,總線和交叉開關的一旦作成難于擴展；,例子,: IBM R50, SGI Power Challenge, SUN Enterprise,,曙光一號,2004年4月51/149共享存儲對稱多處理機系統(tǒng)(SMP),2004

40、,年,4,月,52,/149,分布共享存儲多處理機系統(tǒng),(DSM),DSM:,分布共享存儲,:,內存模塊物理上局部于各個處理器內部,,,但邏輯上,(,用戶,),是共享存儲的,;,這種結構也稱為基于,Cache,目錄的非一致內存訪問,(CC-NUMA),結構,;,局部與遠程內存訪問的延遲和帶寬不一致,,3-10,倍,?,高性能并行程序設計注意,;,與,SMP,的主要區(qū)別：,DSM,在物理上有分布在各個節(jié)點的局部內存從而形成一個共享的存儲器；,微處理器,: 16-128,個,,,幾百到千億次,;,代表,: SGI Origin 2000, Cray T3D;,2004年4月52/149分布共享存儲

41、多處理機系統(tǒng)(DSM),2004,年,4,月,53,/149,大規(guī)模并行計算機系統(tǒng),(MPP),MPP:,物理和邏輯上均是分布內存,能擴展至成百上千個處理器,(,微處理器或向量處理器,),采用高通信帶寬和低延遲的互聯(lián)網絡,(,專門設計和定制的,),一種異步的,MIMD,機器；程序系由多個進程組成，每個都有其私有地址空間，進程間采用傳遞消息相互作用；,代表,:CRAY T3E(2048), ASCI Red(3072), IBM SP2,,曙光,1000,；,2004年4月53/149大規(guī)模并行計算機系統(tǒng)(MPP)MP,2004,年,4,月,54,/149,機群系統(tǒng),(Cluster),Clus

42、ter:,每個節(jié)點都是一個完整的計算機,各個節(jié)點通過高性能網絡相互連接,網絡接口和,I/O,總線松耦合連接,每個節(jié)點有完整的操作系統(tǒng),曙光,2000, 3000, ASCI Blue Mountain (48,臺,128-way DSM Origin 2000,6144,個處理器,),2004年4月54/149機群系統(tǒng)(Cluster)Clus,2004,年,4,月,55,/149,訪存模型,UMA:,NORMA:,NUMA:,多處理機（單地址空間共享存儲器）,,UMA: Uniform Memory Access,NUMA: Nonuniform Memory Access,多計算機（多地

43、址空間非共享存儲器）,,NORMA:No-Remote Memory Access,2004年4月55/149訪存模型UMA:NORMA:NUM,2004,年,4,月,56,/149,均勻存儲器存取,(UMA),均勻存儲器存?。?UMA,－,Uniform Memory Access,）,所有處理器,均勻共享,物理存儲器，這里所謂均勻是指所有處理器對所有存儲字具有相同的存取時間,每臺處理器可帶私有高速緩存,外圍設備也可以一定形式共享,各處理機之間的通信是通過共享存儲器的共享變量來實現(xiàn)的,這一類多處理機由于對資源的高度共享,,,常稱,緊耦合,系統(tǒng),(tightly coupled system)

44、,UMA:,2004年4月56/149均勻存儲器存取 (UMA)均勻存儲,2004,年,4,月,57,/149,均勻存儲器存取,(UMA),對稱多處理機系統(tǒng),(symmetric multi-processor),所有處理機都能同樣訪問所有外圍設備；所有處理機都能同樣運行執(zhí)行程序，如操作系統(tǒng)的內核、,I/O,服務程序,,不對稱處理機系統(tǒng),(asymmtric multi-processor),只有一臺或一組處理機（,MP,主處理機）執(zhí)行操作系統(tǒng)并操縱,I/O,，其余處理機（,AP,附屬處理機）沒有,I/O,能力,2004年4月57/149均勻存儲器存取 (UMA)對稱多處,2004,年,4,月

45、,58,/149,非均勻存儲訪問,(NUMA),非均勻存儲訪問,(NUMA,—,Nonuniform Memory Access),被共享的存儲器在物理上是分布在所有的處理其中的，其所有本地存儲器的集合就組成了全局地址空間,處理器訪問存儲器的時間是不一樣的：訪問本地存儲器,(LM),較快，而訪問外地的存儲器較慢（此即是非均勻存儲訪問名稱的由來）,每臺處理器可帶私有高速緩存，且外設也可以某種形式共享,NUMA:,2004年4月58/149非均勻存儲訪問(NUMA)非均勻存,2004,年,4,月,59,/149,非遠程存儲訪問,(NORMA),非遠程存儲訪問,(NORMA,—,No-Remote

46、Memory Access),所有存儲器都是私有的，僅能由其處理器所訪問,絕大都數(shù)都不支持遠程存儲器的訪問,NORMA:,2004年4月59/149非遠程存儲訪問(NORMA)非遠程,2004,年,4,月,60,/149,結構模型,----,訪存模型,UMA:,NUMA:,NORMA:,2004年4月60/149結構模型 ---- 訪存模型UMA,2004,年,4,月,61,/149,多處理機 ＆ 多計算機,UMA:,NUMA:,NORMA:,,多處理機,（,共享存儲,）,,多計算機,（,分布式存儲,）,2004年4月61/149多處理機 ＆ 多計算機UMA:NU,2004,年,4,月,62,

47、/149,幾種體系結構特征比較,2004年4月62/149幾種體系結構特征比較,2004,年,4,月,63,/149,曙光系列,曙光一號,SMP (1993),曙光,1000 MPP (1995),曙光,2000I Cluster (1998),曙光,2000II Cluster (1999),曙光,3000 Cluster (2000),曙光,4000l Cluster (2002),曙光,4000A Cluster (2004),2004年4月63/149曙光系列曙光一號 SMP (199,2004,年,4,月,64,/149,動物食物鏈,2004年4月64/149動

48、物食物鏈,2004,年,4,月,65,/149,1984,年的計算機食物鏈,Mainframe,Vector Supercomputer,Mini Computer,Workstation,PC,2004年4月65/1491984年的計算機食物鏈Mainf,2004,年,4,月,66,/149,1994,年的計算機食物鏈,Mainframe,Vector Supercomputer,MPP,Workstation,PC,Mini Computer,(hitting wall soon),(future is bleak),2004年4月66/1491994年的計算機食物鏈Mainf,2004,

49、年,4,月,67,/149,現(xiàn)在和未來的計算機食物鏈,2004年4月67/149現(xiàn)在和未來的計算機食物鏈,2004,年,4,月,68,/149,講座主要內容提示,并行計算簡介,編譯環(huán)境,數(shù)學庫,并行計算機體系結構,并行軟件環(huán)境,并行計算機性能評測,MPI,,2004年4月68/149講座主要內容提示并行計算簡介,2004,年,4,月,69,/149,并行計算軟件環(huán)境及現(xiàn)狀,操作系統(tǒng)：,UNIX,、,LINUX,、,Windows NT,在,SMP,DSM,并行機上編譯系統(tǒng)通常具有一定的對用戶程序,(C/Fortran),進程自動并行化的能力,,,但經常需要人工干預,(,通過編譯制導,,,命令行

50、選項等,),以達到理想的并行效率,.,且并行主要針對循環(huán)進行,(,屬于細粒度并行,);,在分布式內存并行機上尚無通過高效的自動并行工具,,,主要依靠人工編寫并行程序,;,并行算法的設計及并行程序的編制已成為目前特約大規(guī)模并行計算機應用的主要障礙,.,,并行編程現(xiàn)狀,?,:,并行軟件開發(fā)遠遠落后于并行系統(tǒng)體系結構的發(fā)展。缺少合適的并行軟件是阻礙主流用戶社會接納并行計算的原因。,?,:,與串行軟件相比，并行軟件數(shù)量少，功能原始。,2004年4月69/149并行計算軟件環(huán)境及現(xiàn)狀操作系統(tǒng)：U,2004,年,4,月,70,/149,??,編程環(huán)境,落后的并行編譯器、調試器,vs.,通用先進的串行編程環(huán)

51、境,.,自動并行編譯器遠遠滿足不了程序并行化的要求,.,,3,算法,并行模型的多樣化,(,并行計算機系統(tǒng)結構的多樣性,) vs.,串行編程中的唯一模型,:,馮,.,諾依曼模型,問題的并行求解的困難在于問題的多樣性和求解過程中所需的創(chuàng)造性勞動，使得這一過程難以進行自動化,對串行機而言,,,解法,=,唯一串行算法,+,計算程序,(,通用,),對并行機而言,,,解法,=,某種并行算法,+,有針對性的計算程序,(,很難通用,),,J,人,稀少而初級的并行編程人員,vs.,成熟而經驗豐富的串行程序員,2004年4月70/149??編程環(huán)境,2004,年,4,月,71,/149,一些途徑,充分,利用順序程

52、序開發(fā)的經驗、方法和工具,，特別是順序領域中的問題求解、算法設計方法，這是簡化并行程序開發(fā)的重要手段。,并行程序開發(fā)的困難主要在于,問題的并行求解,，而不是并行程序設計語言。“從事并行程序設計實踐的人往往把精力耗費在為變量分配內存、為循環(huán)體尋求并行上，卻忽略對問題本身的分析。其實能否并行的決定因素是應用問題本身。”,在并行算法的設計階段,最大限度地開發(fā)出問題本身固有的并行性,才是提高計算效率的根本手段。只有,粗粒度的并行,，才能具有高的計算通信比，而粗粒度的并行只能在算法設計階段開發(fā)出來,2004年4月71/149一些途徑充分利用順序程序開發(fā)的經驗,2004,年,4,月,72,/149,并行軟

53、件程序員的工作,,,,,,,,指令層，非常細的粒度,數(shù)據(jù)層，細粒度,控制層，中粒度,任務層，大粒度,,前兩層大都由硬件和編譯器負責處理，程序員通常處理后兩層的并行,,,2004年4月72/149并行軟件程序員的工作?指令層，非常,2004,年,4,月,73,/149,并行程序設計方法,隱式并行程序設計：,常用傳統(tǒng)的語言編程成順序源編碼，把“并行”交給編譯器實現(xiàn)自動并行,程序的自動并行化是一個理想目標，存在難以克服的困難,語言容易，編譯器難,,顯式并行程序設計：,在用戶程序中出現(xiàn)“并行”的調度語句,顯式的并行程序開發(fā)則是解決并行程序開發(fā)困難的切實可行的,語言難，編譯器容易,2004年4月73/1

54、49并行程序設計方法隱式并行程序設計：,2004,年,4,月,74,/149,并行程序設計模型,隱式并行（,Implicit Parallel,）,數(shù)據(jù)并行（,Data Parallel,）,共享變量（,Shared Variable,）,消息傳遞（,Message Passing,）,2004年4月74/149并行程序設計模型隱式并行（Impl,2004,年,4,月,75,/149,隱式并行,(Implicit Parallel),概況：,程序員用熟悉的,串行語言,編程,(,未作明確的制定并行性,),編譯器,和,運行支持系統(tǒng),自動轉化為并行代碼,特點：,語義簡單,可移植性好,單線程，易于調試

55、和驗證正確性,細粒度并行,效率很低,2004年4月75/149隱式并行(Implicit Par,2004,年,4,月,76,/149,數(shù)據(jù)并行（,Data Parallel,）,概況：,SIMD,的自然模型,局部計算和數(shù)據(jù)選路操作,特點：,單線程,并行操作于聚合數(shù)據(jù)結構（數(shù)組）,松散同步,單一地址空間,隱式交互作用,顯式數(shù)據(jù)分布,優(yōu)點,:,編程相對簡單,,,串并行程序一致,.,缺點,:,程序的性能在很大程度上依賴于所用的編譯系統(tǒng)及用戶對編譯系統(tǒng)的了解,.,并行粒度局限于,數(shù)據(jù)級并行,,,粒度較小,.,2004年4月76/149數(shù)據(jù)并行（Data Paralle,2004,年,4,月,77,/

56、149,共享變量,(Shared Variable),概況：,PVP, SMP, DSM,的自然模型,特點：,多線程：,SPMD, MPMD,異步,單一地址空間,顯式同步,隱式數(shù)據(jù)分布,隱式通信,典型代表：,OpenMP,2004年4月77/149共享變量(Shared Varia,2004,年,4,月,78,/149,消息傳遞,(Message Passing),概況：,MPP,、,COW,的自然模型,特點：,多線程,異步,多地址空間,顯式同步,顯式數(shù)據(jù)映射和負載分配,顯式通信,典型代表,MPI,、,PVM,2004年4月78/149消息傳遞(Message Pass,2004,年,4,月,

57、79,/149,并行編程標準,數(shù)據(jù)并行語言標準,Fortran90, HPF(1992), Fortran95/2001:,顯式數(shù)據(jù)分布描述,,,并行,DO,循環(huán),.,線程庫,標準,(Thread Library),– Win32 API.,– POSIX threads,線程模型,.,編譯制導,(Compiler Directives),–,OpenMP,: portable shared memory parallelism,消息傳遞庫標準,(Message Passing Libraries),–,MPI,,: Message Passing Interface,–,PVM,: Par

58、allel Virtual Machine,共享變量編程,消息傳遞編程,數(shù)據(jù)并行編程,2004年4月79/149并行編程標準數(shù)據(jù)并行語言標準共享變,2004,年,4,月,80,/149,并行編程標準歸類,所有并行編程標準可分為以下三類,:,數(shù)據(jù)并行,HPF, Fortran90,用于,SMP, DSM,共享編程,OpenMP,用于,SMP, DSM,消息傳遞,MPI, PVM,用于所有并行計算機,三者可混合使用,:,如對以,SMP,為節(jié)點的,Cluster,來說,,,可以在節(jié)點間進行消息傳遞,,,在節(jié)點內進行共享變量編程,.,2004年4月80/149并行編程標準歸類所有并行編程標準可,200

59、4,年,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,講座主要內容提示,并行計算簡介,編譯環(huán)境,數(shù)學庫,并行計算機體系結構,并行軟件環(huán)境,并行計算機性能評測,MPI,、,PVM,、,OpenMP,,2004年4月82/14

60、9講座主要內容提示并行計算簡介,2004,年,4,月,83,/149,并行計算性能評測,機器的理論峰值速度,用戶能得到的實際速度,,Benchmark LINPACK,www.top500.org,加速比、效率,S,＝并行算法,(,程序,),性能,/,串行算法,(,程序,),性能,可擴展性：體系結構、軟件、算法,隨著計算負載的增加和機器規(guī)模的擴大，計算系統(tǒng)的性能是否隨著處理器的數(shù)目的增加而按比例的增加,性能依賴因素：,算法設計：并行性、計算量,程序設計：體系結構特點的利用,(,通信、存儲、,Cache),、負載平衡、并行粒度,2004年4月83/149并行計算性能評測機器的理論峰值速度,200

61、4,年,4,月,84,/149,機器的理論峰值速度,理論峰值速度,=,CPU,主頻,,×,每個時鐘周期執(zhí)行浮點運算的次數(shù),×,CPU,數(shù)目,每個時鐘周期執(zhí)行浮點運算的次數(shù),是由處理器中浮點運算單元的個數(shù)及每個浮點運算單元在每個時鐘周期能處理幾條浮點運算來決定的,2004年4月84/149機器的理論峰值速度理論峰值速度=C,2004,年,4,月,85,/149,基準測試程序,(Benchmark),基本測試程序,SPEC,：原主要是測試,CPU,性能，現(xiàn)在強調開發(fā)能反映真實應用的基準測試程序，并以推廣至客戶,/,服務器計算、商業(yè)應用、,I/O,子系統(tǒng)等等,,科學與工程計算性能,Linpack,：

62、高斯消元法求解線性代數(shù)方程組,NPB(NAS Parallel Benchmark),：美國,NAS,項目開發(fā)，包含,8,個空氣動力學計算類應用，測試范圍從整數(shù)排序到復雜的數(shù)值計算,LAPACK,、,ScalLAPACK,：稠密、帶狀矩陣上的各類操作,Perfect,、,SPLASH,、,ParkBench,2004年4月85/149基準測試程序(Benchmark),2004,年,4,月,86,/149,www.top500.org,2004年4月86/149www.top500.org,2004,年,4,月,87,/149,Linpack,Linpack,是,國際上流行的用于測試高性能計算

63、機系統(tǒng)浮點性能的,benchmark,,通過對高性能計算機采用,LU,分解求解線性代數(shù)方程組能力的測試，評價高性能計算機的浮點處理性能,2004年4月87/149LinpackLinpack是國際,2004,年,4,月,88,/149,Linpack,由,J. Dongarra,編寫的,Linpack,采用主元高斯消去法求解雙精度,(64bits),稠密線性代數(shù)方程組,結果按每秒浮點運算次數(shù)（,flops,）表示,包含三類測試（問題規(guī)模與優(yōu)化選擇各不相同）,100×100,測試,不允許對,Linpack,測試程序進行任何修改（包括注釋行）。所有的優(yōu)化只能在編譯器里完成,,1000×1000,測

64、試,允許對算法和軟件進行修改或替換,并盡量利用系統(tǒng)的硬件特點，以達到盡可能高的性能,但是所有的優(yōu)化都必須保持和標準算法如高斯消去法相同的相對精度，而且必須使用,Linpack,的主程序進行調用,2004年4月88/149Linpack由J. Dongar,2004,年,4,月,89,/149,HPL,高性能,Linpack,：,HPL,(High Performance Linpack),針對大規(guī)模的并行計算機系統(tǒng)的測試，,2000,年,9,月發(fā)布,1.0,版,是,TOP500,超級計算機排名的主要依據(jù),采用,MPI,實現(xiàn)，基于,BLAS,庫或,VSIPL,庫,用戶可以選擇矩陣的大小,(,問題

65、規(guī)模,),、使用各種優(yōu)化方法來執(zhí)行測試程序，尋求最佳的測試結果,浮點峰值,＝,總計算量,,/,計算時間,總計算量＝,2/3 * N^3 – 2*N^2,計算時間：可通過系統(tǒng)時鐘獲得,2004年4月89/149HPL高性能Linpack：HPL,2004,年,4,月,90,/149,如何做,HPL,測試,所必須的軟件包,HPL,BLAS,庫：,GOTO,、,ATLAS,、,ACML,、,MKL,、,Linux,自帶的,BLAS,庫 等等,編譯器：需要,C,語言和,Fortran 77,編譯器。,eg,：,gcc/g77,、,icc/ifc,、,pgcc/pgf77,等等,并行環(huán)境：,MPI,安裝編譯器、,MPI,、,BLAS,庫，編譯,HPL,運行,xhpl,eg: mpirun –np 4 xhpl,查看結果文件,2004年4月90/149如何做HPL測試所必須的軟件包,2004,年,4,月,91,/149,如何做,HPL,測試,HPL.out,文件或在