中科大多核并行計(jì)算課件2439569.ppt

1、多核并行計(jì)算Multicore Parallel Computing,主講人 徐 云,國家高性能計(jì)算中心（合肥）,第十三章 共享存儲(chǔ)系統(tǒng)編程,國家高性能計(jì)算中心（合肥）,共享存儲(chǔ)系統(tǒng)編程,13.1 ANSI X3H5共享存儲(chǔ)模型 13.2 POSIX 線程模型 13.3 OpenMP模型,國家高性能計(jì)算中心（合肥）,編程標(biāo)準(zhǔn)的作用,規(guī)定程序的執(zhí)行模型 SPMD, SMP 等 如何表達(dá)并行性 DOACROSS, FORALL, PARALLEL, INDEPENDENT 如何表達(dá)同步 Lock, Barrier, Semaphore, Condition Variables 如何獲得運(yùn)行時(shí)的環(huán)境

2、變量 threadid, num of processes,國家高性能計(jì)算中心（合肥）,ANSI X3H5共享存儲(chǔ)器模型,Started in the mid-80s with the emergence of shared memory parallel computers with proprietary directive driven programming environments 更早的標(biāo)準(zhǔn)化結(jié)果PCF共享存儲(chǔ)器并行Fortran 1993年制定的概念性編程模型 Language Binding C Fortran 77 Fortran 90,國家高性能計(jì)算中心（合肥）,并行塊（工

3、作共享構(gòu)造） 并行塊(psections . end psections) 并行循環(huán)(pdo . Endo pdo) 單進(jìn)程(psingle . End psingle) 可嵌套 非共享塊重復(fù)執(zhí)行 隱式路障(nowait)，顯式路障和阻擋操作 共享/私有變量 線程同步 門插銷(latch)：臨界區(qū) 鎖：test,lock,unlock 事件:wait,post,clear 序數(shù)(ordinal):順序,國家高性能計(jì)算中心（合肥）,X3H5:并行性構(gòu)造,Program main!程序以順序模式開始,此時(shí)只有一個(gè) A!A只由基本線程執(zhí)行，稱為主線程 parallel!轉(zhuǎn)換為并行模式，派生出多個(gè)子線

4、程（一個(gè)組） B!B為每個(gè)組員所復(fù)制 psections!并行塊開始 section C!一個(gè)組員執(zhí)行C section D!一個(gè)組員執(zhí)行D end psections!等待C和D都結(jié)束 psingle!暫時(shí)轉(zhuǎn)換成順序模式 E!E由一個(gè)組員執(zhí)行 end psingle!轉(zhuǎn)回并行模式 pdo i=1,6!pdo構(gòu)造開始 F(i)!組員共享F的六次迭代 end pdo no wait!無隱式路障同步 G!更多的復(fù)制代碼 end parallel!轉(zhuǎn)為順序模式 H!初始化進(jìn)程單獨(dú)執(zhí)行H .!可能有更多的并行構(gòu)造 End,國家高性能計(jì)算中心（合肥）,線程,隱式路障同步,P,Q,R,A,B,C,E,F(

5、1:2),G,H,G,G,F(3:4),F(5:6),D,B,B,隱式路障同步,隱式路障同步,無隱式路障同步,隱式路障同步,國家高性能計(jì)算中心（合肥）,共享存儲(chǔ)系統(tǒng)編程,13.1 ANSI X3H5共享存儲(chǔ)模型 13.2 POSIX 線程模型 13.3 OpenMP模型,國家高性能計(jì)算中心（合肥）,POSIX線程模型,IEEE/ANSI標(biāo)準(zhǔn)IEEE POSIX 1003.1c-1995線程標(biāo)準(zhǔn)Unix/NT操作系統(tǒng)層上的，SMP Chorus, Topaz, Mach Cthreads Win32 Thread GetThreadHandle,SetThreadPriority,Suspend

6、Thread,ResumeThread TLS(線程局部存儲(chǔ))TlsAlloc, TlsSetValue LinuxThreads:_clone and sys_clone 用戶線程和內(nèi)核線程(LWP)(一到一，一到多，多到多),國家高性能計(jì)算中心（合肥）,What Are Threads?,General-purpose solution for managing concurrency. Multiple independent execution streams. Shared state. Preemptive scheduling. Synchronization (e.g. loc

7、ks, conditions).,Shared state (memory, files, etc.),Threads,國家高性能計(jì)算中心（合肥）,線程共享相同的內(nèi)存空間。 與標(biāo)準(zhǔn) fork() 相比，線程帶來的開銷很小。內(nèi)核無需為各個(gè)線程單獨(dú)復(fù)制進(jìn)程的內(nèi)存空間或文件描述符等等。這就節(jié)省了大量的 CPU 時(shí)間。 和進(jìn)程一樣，線程將利用多 CPU。 支持內(nèi)存共享無需使用繁瑣的 IPC (Inter Process Communication)和其它復(fù)雜的通信機(jī)制。 Linux _clone不可移植，Pthread可移植。 POSIX 線程標(biāo)準(zhǔn)不記錄任何“家族”信息。無父無子。如果要等待一個(gè)線程終

8、止，就必須將線程的 tid 傳遞給 pthread_join()。線程庫無法為您斷定 tid。,國家高性能計(jì)算中心（合肥）,POSIX Threads: Basics and Examples by Uday Kamath /abw/parallel/pthreads/pthreads.html POSIX 線程詳解: 一種支持內(nèi)存共享的簡(jiǎn)單和快捷的工具 by Daniel Robbins ,國家高性能計(jì)算中心（合肥）,線程調(diào)用線程管理,POSIXSolaris 2 pthread_create thr_create pthread_exitthr_

9、exit pthread_kill thr_kill pthread_jointhr_join pthread_selfthr_self,國家高性能計(jì)算中心（合肥）,線程調(diào)用線程同步和互斥,POSIXSolaris 2 pthread_mutex_initmutex_init pthread_ mutex_destroy mutex_destroy pthread_ mutex_lock mutex_lock pthread_ mutex_trylock mutex_trylock pthread_ mutex_unlock mutex_unlock pthread_cond_init pth

10、read_cond_destroy pthread_cond_wait pthread_cond_timedwait pthread_cond_signal pthread_cond_broadcast,國家高性能計(jì)算中心（合肥）,Pthreads實(shí)現(xiàn)計(jì)算的實(shí)例(1),國家高性能計(jì)算中心（合肥）,Pthreads實(shí)現(xiàn)計(jì)算的實(shí)例(2),國家高性能計(jì)算中心（合肥）,共享存儲(chǔ)系統(tǒng)編程,13.1 ANSI X3H5共享存儲(chǔ)模型 13.2 POSIX 線程模型 13.3 OpenMP模型 OpenMP概述 OpenMP編程風(fēng)絡(luò) OpenMP編程簡(jiǎn)介 運(yùn)行庫例程與環(huán)境變量 OpenMP計(jì)算實(shí)例,OpenM

11、P概述,OpenMP應(yīng)用編程接口API是在共享存儲(chǔ)體系結(jié)構(gòu)上的一個(gè)編程模型 包含編譯制導(dǎo)(Compiler Directive)、運(yùn)行庫例程(Runtime Library)和環(huán)境變量(Environment Variables) 支持增量并行化(Incremental Parallelization),OpenMP體系結(jié)構(gòu),什么是OpenMP,什么是OpenMP 應(yīng)用編程接口API（Application Programming Interface ） 由三個(gè)基本API部分（編譯指令、運(yùn)行部分和環(huán)境變量）構(gòu)成 是C/C+ 和Fortan等的應(yīng)用編程接口 已經(jīng)被大多數(shù)計(jì)算機(jī)硬件和軟件廠家所標(biāo)準(zhǔn)

12、化 OpenMP不包含的性質(zhì) 不是建立在分布式存儲(chǔ)系統(tǒng)上的 不是在所有的環(huán)境下都是一樣的 不是能保證讓多數(shù)共享存儲(chǔ)器均能有效的利用,OpenMP的歷史,1994年，第一個(gè)ANSI X3H5草案提出，被否決 1997年，OpenMP標(biāo)準(zhǔn)規(guī)范代替原先被否決的ANSI X3H5，被人們認(rèn)可 1997年10月公布了與Fortran語言捆綁的第一個(gè)標(biāo)準(zhǔn)規(guī)范 1998年11月9日公布了支持C和C+的標(biāo)準(zhǔn)規(guī)范 目前Fortran77、Fortran90、C、C+語言的實(shí)現(xiàn)規(guī)范已經(jīng)完成。 資源網(wǎng)站： http:/phase.hpcc.jp/Omni/,OpenMP的目標(biāo)

13、,標(biāo)準(zhǔn)性 簡(jiǎn)潔實(shí)用 使用方便 可移植性,OpenMP并行編程模型,基于線程的并行編程模型(Programming Model) OpenMP使用Fork-Join并行執(zhí)行模型,OpenMP程序結(jié)構(gòu),基于Fortran語言的OpenMP程序的結(jié)構(gòu) PROGRAM HELLOINTEGER VAR1, VAR2, VAR3 !Serial code !Beginning of parallel section. Fork a team of threads. !Specify variable scoping !$OMP PARALLEL PRIVATE(VAR1, VAR2) SHARED(VA

14、R3) !Parallel section executed by all threads !All threads join master thread and disband!$OMP END PARALLEL !Resume serial codeEND,OpenMP程序結(jié)構(gòu),基于c/c+語言的OpenMP程序的結(jié)構(gòu) #include main () int var1, var2, var3; /*Serial code*/ /*Beginning of parallel section. Fork a team of threads*/ /*Specify variable scopi

15、ng */ #pragma omp parallel private(var1, var2) shared(var3) /*Parallel section executed by all threads*/ /*All threads join master thread and disband*/ /*Resume serial code */ ,一個(gè)簡(jiǎn)單的OpenMP程序?qū)嵗?基于C/C+語言的OpenMP程序結(jié)構(gòu)的一個(gè)具體實(shí)現(xiàn) #include omp.h int main(int argc, char* argv) int nthreads, tid; int nprocs; cha

16、r buf32; /* Fork a team of threads */ #pragma omp parallel private(nthreads, tid) /* Obtain and print thread id */ tid = omp_get_thread_num(); printf(Hello World from OMP thread %dn, tid); /* Only master thread does this */ if (tid=0) nthreads = omp_get_num_threads(); printf(Number of threads %dn, n

17、threads); return 0; ,一個(gè)簡(jiǎn)單的OpenMP程序?qū)嵗?運(yùn)行結(jié)果 (setenv OMP_NUM_THREADS 8) Hello World from OMP thread 0 Number of threads 8 Hello World from OMP thread 4 Hello World from OMP thread 5 Hello World from OMP thread 6 Hello World from OMP thread 7 Hello World from OMP thread 2 Hello World from OMP thread 1 H

18、ello World from OMP thread 3,OpenMP程序性能舉例,void test() int a=0; clock_t t1=clock(); for ( int i=0; i100000000; i+ ) a=i+1; clock_t t2=clock(); printf(Test Time=%dn, t2-t1); int main(int argc, char *argv) clock_t t1=clock(); #pragma omp parallel for for ( int j=0; j2; j+) test(); clock_t t2=clock(); p

19、rintf(Test Time=%dn, t2-t1); test(); return(); ,運(yùn)行結(jié)果如下： Test Time=297 Test Time=297 Test Time=297 Test Time=297,編譯制導(dǎo),語句格式,編譯制導(dǎo),作用域 靜態(tài)擴(kuò)展 文本代碼在一個(gè)編譯制導(dǎo)語句之后，被封裝到一個(gè)結(jié)構(gòu)塊中 孤立語句 一個(gè)OpenMP的編譯制導(dǎo)語句不依賴于其它的語句 動(dòng)態(tài)擴(kuò)展 包括靜態(tài)范圍和孤立語句,作用域,并行域結(jié)構(gòu),并行域中的代碼被所有的線程執(zhí)行 具體格式 #pragma omp parallel clause,clausenewline clause= if (scala

20、r_expression) private (list) shared (list) default (shared | none) firstprivate (list) reduction (operator: list) copyin (list),共享任務(wù)結(jié)構(gòu),共享任務(wù)結(jié)構(gòu)將它所包含的代碼劃分給線程組的各成員來執(zhí)行 并行for循環(huán) 并行sections 串行執(zhí)行,for編譯制導(dǎo)語句,for語句指定緊隨它的循環(huán)語句必須由線程組并行執(zhí)行； 語句格式 #pragma omp for clause,clause newline clause= Schedule(type ,chunk) ord

21、ered private (list) firstprivate (list) lastprivate (list) shared (list) reduction (operator: list) nowait,for編譯制導(dǎo)語句,示例： int j=0; #pragma omp parallel #pragma omp for for (j=0; j4; j+) printf(j=%d, ThreadId=%dn, omp_get_thread_num(); ,運(yùn)行結(jié)果： j=1, ThreadId=1 j=3, ThreadId=3 j=2, ThreadId=2 j=0, Thread

22、Id=0,for編譯制導(dǎo)語句,schedule子句描述如何將循環(huán)的迭代劃分給線程組中的線程 如果沒有指定chunk大小，迭代會(huì)盡可能的平均分配給每個(gè)線程 type為static，循環(huán)被分成大小為 chunk的塊，靜態(tài)分配給線程 type為dynamic,循環(huán)被動(dòng)態(tài)劃分為大小為chunk的塊，動(dòng)態(tài)分配給線程,Sections編譯制導(dǎo)語句,sections編譯制導(dǎo)語句指定內(nèi)部的代碼被劃分給線程組中的各線程 不同的section由不同的線程執(zhí)行 Section語句格式： #pragma omp sections clause,clause newline #pragma omp section ne

23、wline #pragma omp section newline ,Sections編譯制導(dǎo)語句,clause= private (list) firstprivate (list) lastprivate (list) reduction (operator: list) nowait 在sections語句結(jié)束處有一個(gè)隱含的路障，使用了nowait子句除外,Sections編譯制導(dǎo)語句,#include #define N 1000 int main () int i; float aN, bN, cN; /* Some initializations */ for (i=0; i N;

24、 i+) ai = bi = i * 1.0; #pragma omp parallel shared(a,b,c) private(i) #pragma omp sections nowait #pragma omp section for (i=0; i N/2; i+) ci = ai + bi; #pragma omp section for (i=N/2; i N; i+) ci = ai + bi; /* end of sections */ /* end of parallel section */ ,single編譯制導(dǎo)語句,single編譯制導(dǎo)語句指定內(nèi)部代碼只有線程組中的一

25、個(gè)線程執(zhí)行。 線程組中沒有執(zhí)行single語句的線程會(huì)一直等待代碼塊的結(jié)束，使用nowait子句除外 語句格式： #pragma omp single clause,clause newline clause= private(list) firstprivate(list) nowait,組合的并行共享任務(wù)結(jié)構(gòu),parallel for編譯制導(dǎo)語句 parallel sections編譯制導(dǎo)語句,parallel for編譯制導(dǎo)語句,Parallel for編譯制導(dǎo)語句表明一個(gè)并行域包含一個(gè)獨(dú)立的for語句 語句格式 #pragma omp parallel for clause newli

26、ne clause= if (scalar_logical_expression) default (shared | none) schedule (type ,chunk) shared (list) private (list) firstprivate (list) lastprivate (list) reduction (operator: list) copyin (list),parallel for編譯制導(dǎo)語句,#include #define N 1000 #define CHUNKSIZE 100 int main () int i, chunk; float aN, b

27、N, cN; /* Some initializations */ for (i=0; i N; i+) ai = bi = i * 1.0; chunk = CHUNKSIZE; #pragma omp parallel for shared(a,b,c,chunk) private(i) schedule(static,chunk) for (i=0; i n; i+) ci = ai + bi; ,parallel sections編譯制導(dǎo)語句,parallel sections編譯制導(dǎo)語句表明一個(gè)并行域包含單獨(dú)的一個(gè)sections語句 語句格式 #pragma omp paralle

28、l sections clause newline clause= default (shared | none) shared (list) private (list) firstprivate (list) lastprivate (list) reduction (operator: list) copyin (list) ordered,同步結(jié)構(gòu),master 制導(dǎo)語句 critical制導(dǎo)語句 barrier制導(dǎo)語句 atomic制導(dǎo)語句 flush制導(dǎo)語句 ordered制導(dǎo)語句,master 制導(dǎo)語句,master制導(dǎo)語句指定代碼段只有主線程執(zhí)行 語句格式 #pragma om

29、p master newline,critical制導(dǎo)語句,critical制導(dǎo)語句表明域中的代碼一次只能執(zhí)行一個(gè)線程 其他線程被阻塞在臨界區(qū) 語句格式： #pragma omp critical name newline,critical制導(dǎo)語句,#include main() int x; x = 0; #pragma omp parallel shared(x) #pragma omp critical x = x + 1; /* end of parallel section */ ,barrier制導(dǎo)語句,barrier制導(dǎo)語句用來同步一個(gè)線程組中所有的線程 先到達(dá)的線程在此阻塞，等

30、待其他線程 barrier語句最小代碼必須是一個(gè)結(jié)構(gòu)化的塊 語句格式 #pragma omp barrier newline,barrier制導(dǎo)語句,barrier正確與錯(cuò)誤使用比較,atomic制導(dǎo)語句,atomic制導(dǎo)語句指定特定的存儲(chǔ)單元將被原子更新 語句格式 #pragma omp atomic newline atomic使用的格式,x binop = expr x+ +x x- -x,x是一個(gè)標(biāo)量 expr是一個(gè)不含對(duì)x引用的標(biāo)量表達(dá)式，且不被重載 binop是+,*,-,/, #pragma omp parallel for shared(nVar) for (i=0; i100

31、0; i+) #pragma omp atomic nVar+=1; 注：比較一下和臨界區(qū)方法的性能,flush制導(dǎo)語句,flush制導(dǎo)語句用以標(biāo)識(shí)一個(gè)同步點(diǎn)，用以確保所有的線程看到一致的存儲(chǔ)器視圖 語句格式 #pragma omp flush (list) newline flush將在下面幾種情形下隱含運(yùn)行，nowait子句除外,barrier critical:進(jìn)入與退出部分 ordered:進(jìn)入與退出部分 parallel:退出部分 for:退出部分 sections:退出部分 single:退出部分,ordered制導(dǎo)語句,ordered制導(dǎo)語句指出其所包含循環(huán)的執(zhí)行 任何時(shí)候只能有

32、一個(gè)線程執(zhí)行被ordered所限定部分 只能出現(xiàn)在for或者parallel for語句的動(dòng)態(tài)范圍中 語句格式： #pragma omp ordered newline 示例 #pragma omp parallel for ordered schdule(static, 2) for (i=0; i10; i+) #pragma omp ordered printf(i=%ldn, i);,threadprivate編譯制導(dǎo)語句,threadprivate語句使一個(gè)全局文件作用域的變量在并行域內(nèi)變成每個(gè)線程私有 每個(gè)線程對(duì)該變量復(fù)制一份私有拷貝 語句格式: #pragma omp threa

33、dprivate (list) newline,threadprivate編譯制導(dǎo)語句,復(fù)制全局變量為各自線程私有 int counter=0; #pragma omp threadprivate(counter) int increment_counter() counter+; return(counter+); 復(fù)制靜態(tài)變量為各自線程私有 int increment_counter() static int counter=0; #pragma omp threadprivate(counter) counter+; return(counter+); ,數(shù)據(jù)域?qū)傩宰泳?變量作用域范圍

34、數(shù)據(jù)域?qū)傩宰泳?private子句 shared子句 default子句 firstprivate子句 lastprivate子句 copyin子句 reduction子句,private子句,private子句表示它列出的變量對(duì)于每個(gè)線程是局部的 。 語句格式 private(list) private和threadprivate區(qū)別,private和threadprivate區(qū)別,#include int alpha10, beta10, i; #pragma omp threadprivate(alpha) int main () /* First parallel region */

35、#pragma omp parallel private(i,beta) for (i=0; i 10; i+) alphai = betai = i; /* Second parallel region */ #pragma omp parallel printf(alpha3= %d and beta3=%dn,alpha3,beta3); 思考: 上機(jī)運(yùn)行結(jié)果，并分析。,private和threadprivate區(qū)別,int global=111; #pragma omp threadprivate(global) int main() global=222; #pragma omp p

36、arallel copyin(global) / printf(Thread number %d global=%dn, omp_get_thread_num(),global); global=omp_get_thread_num()+10; printf(global=%dn,global); printf(parallel againn); #pragma omp parallel printf(Thread number %d global=%dn, omp_get_thread_num(),global); printf(global=%dn,global); return 0;,運(yùn)

37、行結(jié)果： Thread number 0 global=222 Thread number 3 global=222 Thread number 1 global=222 Thread number 2 global=222 global=10 parallel again Thread number 0 global=10 Thread number 3 global=13 Thread number 1 global=11 Thread number 2 global=12 global=10,shared子句,shared子句表示它所列出的變量被線程組中所有的線程共享 所有線程都能對(duì)它進(jìn)

38、行讀寫訪問 語句格式 shared (list),default子句,default子句讓用戶自行規(guī)定在一個(gè)并行域的靜態(tài)范圍中所定義的變量的缺省作用范圍 語句格式 default (shared | none),firstprivate子句,firstprivate子句是private子句的超集 對(duì)變量做原子初始化 語句格式： firstprivate (list),lastprivate子句,lastprivate子句是private子句的超集 將變量從最后的循環(huán)迭代或段復(fù)制給原始的變量 語句格式 lastprivate (list),copyin子句,copyin子句用來為線程組中所有線程

39、的threadprivate變量賦相同的值 主線程該變量的值作為初始值 語句格式 copyin(list),reduction子句,reduction子句使用指定的操作對(duì)其列表中出現(xiàn)的變量進(jìn)行歸約 初始時(shí)，每個(gè)線程都保留一份私有拷貝 在結(jié)構(gòu)尾部根據(jù)指定的操作對(duì)線程中的相應(yīng)變量進(jìn)行歸約，并更新該變量的全局值 語句格式 reduction (operator: list),reduction子句,#include int main () int i, n, chunk; float a100, b100, result; /* Some initializations */ n = 100; ch

40、unk = 10; result = 0.0; for (i=0; i n; i+) ai = i * 1.0; bi = i * 2.0; #pragma omp parallel for default(shared) private(i) schedule(static,chunk) reduction(+:result) for (i=0; i n; i+) result = result + (ai * bi); printf(Final result= %fn,result); ,reduction子句,Reduction子句的格式,x=x op expr x = expr op

41、x (except subtraction) x binop = expr x+ +x x- -x,x是一個(gè)標(biāo)量 expr是一個(gè)不含對(duì)x引用的標(biāo)量表達(dá)式，且不被重載 binop是+,*,-,/, double step; #define NUM_THREADS 2 void main () int i; double x, pi, sumNUM_THREADS; step = 1.0/(double) num_steps; omp_set_num_threads(NUM_THREADS); #pragma omp parallel double x; int id; id = omp_get_thread_num(); for (i=id, sumid=0.0;i num_steps; i=i+NUM_THREADS) x = (i+0.5)*step; sumid += 4.0/(1.0+x*x); for(i=0, pi=0.0;iNUM_THREADS;i+) pi += sumi * step; ,使用并行域并行化的程序 假設(shè)有2個(gè)線程參加計(jì)算：,線程0：,線程1：,迭代0,迭代2,迭代4,迭代6,迭代1,迭代3,迭代5,迭代7,OpenMP計(jì)算實(shí)例,使用共享任務(wù)結(jié)構(gòu)并行化的程序 #inclu