untitled

Size: px

Start display at page:

Download "untitled"

たつぞううえや
5 years ago
Views:

1 OpenMP CPU CPU CPU CPU BUS CPU CPU MEM MEM Network CPU CPU MEM MEM Poorman s supercomputer Sun IPC cluster etlwiz Alpha cluster, 100 BASE-TX SWITCHATM beowulf class RWCP PC cluster MyrinetGigabit Ethernet, Fiber Channel, DEC Memory Channel, IBM SP2 network UCB CLUMPS, RWC COMPaS) ethernet : 10Mbps 100Mbps Gigabit either MyrinetSAN Network I/O PVM, P4, TCGMSGMPIMPI2 (Message Passing) (shared memory) DSMon MPI,PVM pthread, solaris thread, NT thread OpenMP annotation thread HPF annotation, distribution hint Fancy parallel programming languages 1

2 POSIX for(i=0;i<1000; i++) S += A[i] S Pthread, Solaris thread for(t=1;t<n_thd;t++) r=pthread_create(thd_main,t) thd_main(0); for(t=1; t<n_thd;t++) pthread_join(); PARAMCS For(t=1; t<n_thd;t++) CREATE(thd_main); thd_main(0) WAIT_FOR_END(n_thd-1); S POSIX int s; /* global */ int n_thd; /* number of threads */ int thd_main(int id) int c,b,e,i,ss; c=1000/n_thd; b=c*id; e=s+c; ss=0; for(i=b; i<e; i++) ss += a[i]; pthread_lock(); s += ss; pthread_unlock(); return s; OpenMP OK! #pragma omp parallel for reduction(+:s) for(i=0; i<1000;i++) s+= a[i]; OpenMP OpenMP OpenMP Parallel Regionwork sharing (for)(sections)single data scope orphan static extent dynamic extent OpenMP OpenMP OpenMP (Fortran/C/C++)directive ISV Oct Fortran ver.1.0 API Oct C/C++ ver.1.0 API (1999 F90 API?) URL 2

3 SGI Cray Origin ASCI Blue Mountain System SUN Enterprise PC-based SMP SGI Power Fortran/C SUN Impact KAI/KAP OpenMP OpenMP 5%95%(?) 5% small-scale(16medium-scale (64 pthreados-oriented, general-purpose OpenMPAPI OpenMP directives/pragma Fortran77, f90, C, C++ Fortran!$OMP C: #pragma omp pragma incremental Fork-join parallel region A... #pragma omp parallel foo(); /*..B... */ C. #pragma omp parallel D E... Call foo() fork A Call foo() Call foo() B join C D E Call foo() OpenMP OpenMP OpenMPAPI Fortran $OMP,C$OMP,*$OMPsentinel!$OMP directive_name [clause, clause, ] directive_name: clause:, C/C++ #pragma omp pragma #pragma omp directive_name [clause, clause, ] #pragma omp parallel 3

4 Parallel Region (team) Parallel Parallel regionteam regionteam Fortran: C:!$OMP PARALLEL #pragma omp parallel parallel region Parallel region...!$omp END PARALLEL... Parallel region (contd.) ID omp_get_thread_num() IDTeam ID=0 ID omp_set_num_threads(nthreads) OMP_NUM_THREADS parallel regionjoin critical, atomic, barrier for(i=0;i<1000; i++) S += A[i] S S OpenMP #pragma omp parallel int c,b,e,i,ss; c=1000/omp_get_num_threads(); b=c*omp_get_thread_num();e=s+c;ss=0; for(i=b; i<e; i++) ss += a[i]; #pragma omp atomic s += ss; OpenMP #pragma omp parallel for reduction(+:s) for(i=0; i<1000;i++) s+= a[i]; OpenMP : (data-parallel) (task-parallel) tuning : SPMD omp_get_thread_num()id SPLASH 2PARMACS Macro backend: OpenMP e.g. Polaris Compiler OpenMP Pthread, Solaris thread for(t=1;t<n_thd;t++) r=pthread_create(thd_main,t) thd_main(0); for(t=1; t<n_thd;t++) pthread_join(); PARAMCS For(t=1; t<n_thd;t++) CREATE(thd_main); thd_main(0) WAIT_FOR_END(n_thd-1); OpenMP omp_set_num_threads(n_thd); #pragma omp parallel thd_main(omp_get_thread_num()); 4

5 Work sharing Team parallel region for sections single parallel parallel for parallel sections For ForDO forcanonical shape #pragma omp for [clause] for(var=lb; var logical-op ub; incr-expr) body varprivate incr-expr ++var,var++,--var,var--,var+=incr,var-=incr logical-op break clause For schedule(kind[,chunk_size]) schedule(static,chunk_size) chunk_sizeround-roubin chunk_size=1:cyclic schedule(dynamic,chunk_size) chunk_size chunk_size=1 schedule(guided,chunk_size) chunk_size schedule(runtime) OMP_SCHEDULE implementation n schedule(static,n) Schedule(static) Schedule(dynamic,n) Schedule(guided,n) Iteration space Sections single Matvec(double a[],int row_start,int col_idx[], double x[],double y[],int n) int i,j,start,end; double t; #pragma omp parallel for private(j,t,start,end) for(i=0; i<n;i++) start=row_start[i]; end=row_start[i+1]; t = 0.0; for(j=start;j<end;j++) t += a[j]*x[col_idx[j]]; y[i]=t; Section #pragma omp sections #pragma omp section section1 #pragma omp section section2 #pragma omp single statements 5

6 Work sharingnowait barrier Critical section critical Atomic atomic Barrier flush work sharingnowait #pragma omp barrier Atomic Atomic #pragma omp atomic statement x binop= expr x++,++x, x--, --xx xexpr Atomic Critical Critical section #pragma omp critical[(name)] statements critical section critical section conditional wait master Master ordered #pragma omp master block statements ordered #pragma omp ordered block statements fordynamic extent forordered Data scope parallelwork sharing shared(var_list) private(var_list) private firstprivate(var_list) private lastprivate(var_list) private reduction(op:var_list) reduction private 6

7 Threadprivate file-scope #pragma omp threadprivate(var_list) parallel region persistent parallelcopyin(var_list) Data scope work sharing Parallel private,firstprivate,shared,reduction,copyin default(shared none) defaultnone for private,firstprivate,lastprivate,reduction sections private,firstprivate,lastprivate,reduction single private,firstprivate Orphan directiveextent extent (orphan directive) Static extent lexical dynamic extent orphan directive Static extentdynamic extent dynamic extent dynamic extentdata scope autoprivate shared main() for(it=0;it<niter;i++) resid=cgsol() printf(,resid); cgsol() #pragma omp parallel for for(i=0;i<cols;i+) p[i]=r[i]=x[i]; for(it=0;it<nitcg;i++) matvec(); #pragma omp parallel for for(i=0;i<cols;i++) z[i]+=alpha*p[i]; main() #pragma omp parallel for(it=0;it<niter;i++) resid=cgsol() #pragma omp master printf(,resid); cgsol() #pragma omp for for(i=0;i<cols;i+) p[i]=r[i]=x[i]; for(it=0;it<nitcg;i++) matvec(); #pragma omp for for(i=0;i<cols;i++) z[i]+=alpha*p[i]; Directive binding for, sections, single,master, barrier directivedynamic extentbind dynamic extent work sharingnest master, critical nested parallelism parallel directivenest Nested parallelismenableparallel Disablethread Nested parallelism Nested parallelism in FAQ ``What about nested parallelism? Nested parallelism is permitted by the OpenMP specification. Supporting nested parallelism effectively can be difficult, and we expect most vendors will start out by executing nested parallel constructs on a single thread. In ``OpenMP Fortran Interpretations Version 1.0 In Note that an OpenMP-compliant implementation is permitted to serialize a nested parallel region. Nested parallelismserialize sectionserialize serialize 7

8 OpenMPmemory consistency OpenMPweak consistency Parallel region volatile nowaitwork sharing flush flush #pragma omp flush[(var_list)] consistency omp_get_num_threads, omp_set_num_threads team omp_get_thread_num id omp_get_max_threads omp_get_num_procs omp_set_dynamic, omp_get_dynamic omp_set_nested, omp_get_nested parallel regionnest lock omp_lock_t omp_nest_lock_t OMP_NUM_THREADS Parallel region OMP_SCHEDULE schedule(runtime) OMP_DYNAMIC SGI origin OMP_NESTED nested parallelism nestparallel region OpenMP incremental Work sharing orphan directive data mapping Iteration mapping locality reduction pragma OpenMP --- (Fortran,C/C++) fork-join incremental Fortraninterpretation publish SC 99Fortransecond version locality MPI,HPF Commercial products KAI Guide compiler(fortran,c,c++) Digital UNIX/NT alpha, HPUX,IBM AIX,Intel Solaris/NT,SGI,SUN Solaris PGI SGI MIPSpro (Fortran,C) Gray UNICOS SUN COMPaQ/Digital Fortran IBM SR8000(?) NEC SX-4(?) 8

9 Performance tuning tools performance tuning KAI Assure/Guide view TAU (OGI) Polaris Omni tlogview Omni OpenMPdirective (tlog file) barrier Omni tlogview KAI Guide Tools Performance Viewer KAI Assure Tools Program verifier check racing condition,..etc.. OpenMP-NOW(Rice) WS TradeMarkOpenMP OpenMP+MPI(ASCI) OpenMP+HPF(Vienna Univ.) 2 SPEC HPGOpenMP(MPI OpenMP(RWCP) 9

10 Omni OpenMP SMP (Solaris Thread or POSIX Threads) Solaris 5.6 (SPARC,x86), linux (x86 SMP) Fortran77 C-front: Cparser exc-tools-java: Java download RWC Omni OpenMP Compiler A translator from an OpenMP program to the multithreaded C program with the runtime library calls. Omni Exc toolkit Toolkit for compiler research C-front : OpenMP C parser to generate Xobject code Xobject code: AST (Abstract Syntax Tree) and data type informations Exc java toolkit : Java class libraries to analyze and transform Xobject code. OpenMP transformation and optimization are written in Java using Exc java toolkit. Omni OpenMP compiler for SMP Solaris Thread or POSIX Threads. (Stack/Threads at U. of Tokyo) Solaris 5.6 (SPARC,x86), linux (x86 SMP), (O2K pthread) C and Fortran77. F90 is under development. Overview of Omni OpenMP Compiler OpenMP (1) C++ OpenMP COpenMP F77+OpenMP C++frontend C-Front Xobject code Exc Java toolkit F77 frontend Omni Exc Toolkit Multithreaded C code +Runtime library calls OpenMP Compiled by native cc runtime library executable link S1 #pragma omp parallel for for(i=0; i<n; i++) x[i]=; S2 OpenMP (2) void ompc_func_1(void ** ompc_args) auto int *_pp_n; _pp_n=(int *)*( ompc_args+0); auto int _p_i, _p_i_0, _p_i_1, _p_i_2; _p_i_0=; _ompc_static_sched(&_p_i_0,...); for(_p_i=)... Parallel S1 auto void * ompc_argv[1]; *( ompc_argv+0)=(void *)&n; ompc_do_parallel( ompc_func_1, ompc_argv); S2 RWCP Omni OpenMP Compiler/C NPB1 CG,BT,SP (Class A) in C orphan directive overhead SUN S1000(8CPU) Speedup 10

(RWC OpenMP NPB1 CG(Class A) in OpenMP and Multithread(solaris thread) NPB1 CG (Class A) in OpenMP and Multithread (solaris thread) SMP SMP PC MPP SMP SMP SMP COMPaS: a PC-based SMP Cluster SMP CPUs

11 (RWC OpenMP NPB1 CG(Class A) in OpenMP and Multithread(solaris thread) NPB1 CG (Class A) in OpenMP and Multithread (solaris thread) SMP SMP PC MPP SMP SMP SMP COMPaS: a PC-based SMP Cluster SMP CPUs MEM SMP node network Middle scale Server ASCI Blue Mountain, O2K ASCI Blue Pacific, SP2 vector supercomputer Hitachi SR8000 SX-5 PC-based SMP COMPaS Clumps SMP SMP) SMP SMP hardware shared memory + DSM DSM MPI/shmemMPI? Hybrid MPI+OpenMP MPIOpenMP OpenMP MPI Cyclic Shift for(iter=0;iter<n_pe; iter++) #pragma for(i=0; ompi<blkn;i++) parallel for private(j,k,t) firstprivate(blkn) for(i=0; t=0; i<blkn;i++) t=0; for(j=0;j<blkn; j++) t+=a[k][i]*b[j][k]; for(j=0;j<blkn; C[j][i]=t; j++) t+=a[k][i]*b[j][k]; C[j][i]=t; r=mpi_sendrecv(,b,bb,); r=mpi_sendrecv(,b,bb,); update matrix, B <- BB, update matrix, B <- BB, 11

12 MPIOpenMP OpenMP MPI+OpenMP MPI SMP Cyclic Shift OpenMP+MPI OpenMP singlemastercritical thread-safempi MPI OpenMPthreadprivate SMP OpenMP --- (Fortran,C/C++) fork-join incremental SMP MPIOpenMP SPEC HPGOpenMP(MPI OpenMP(RWCP) OpenMPSMP OpenMP for SMP Cluster OpenMP on SDSM OpenMP(SIF) on TreadMarks (at Rice Univ.) Omni OpenMP Compiler for SCASH (RWCP and TITECH) This approach cannot exploit application-specific data access pattern. Compiler-directed SDSM The compiler generates memory coherence check codes to keep memory consistency (e.g. Shasta SDSM). The compiler analyzes the memory access pattern to optimize communication between nodes. OpenMP structured parallelism description enables more high-level optimization The data-parallel computation in work sharing directives can be compiled into efficient and explicit communication by compiler analysis. OpenMP SMP OpenMP+MPI SMPOpenMP HPF 12

untitled

untitled OpenMP (Message Passing) (shared memory) DSMon MPI,PVM pthread, solaris thread, NT thread OpenMP annotation thread HPF annotation, distribution hint Fancy parallel programming languages for(i=0;i