并行计算 结构 算法 编程 主讲教师 : 谢磊
第十三章共享存储系统编程
为什么要共享存储编程标准? 1 并行技术的再发展主要在于拓宽应用领域, 这其中编程方式至关重要 很多厂商和研究单位的支持, 各有特色, 无统一标准 消息传递的特点 用户需要考虑数据和计算的划分, 编程困难 现状 共享存储与消息传递 共享存储的特点 (1) 继承性 (2) 无须考虑数据的分布 (3) 指针的支持 (4) 进程迁移 一开始就着手制订标准, 如 MPI 有人质疑 MPP 中共享存储与消息传递究竟谁更好? 特别的, MPI 标准的成熟使得 MPI 的继承性更好
为什么要共享存储编程标准? 2 可扩展性 (Scalability) 硬件 --- 可扩展的互连网络构成的分布式存储系统 软件 --- 消息传递模型, 其他的模型都只能架构在它的上面. 长期以来, 形成一种错觉 : HPC 中并行软件的可扩展性只能通过消息传递编程模型来达到 (MPI, PVM) 可扩展共享存储多处理机 (SSMP) 的迅速崛起 共享存储编程 (SMP) 模型是基本的, 并且是可扩展的 共享存储编程模型简单, 并且非常适合于描述并行性 缺少可移植性是 SMP 一直不受青睐的根本原因 共享存储编程标准的诞生 目标就是与 MPI 进行抗衡
编程标准的作用 规定程序的执行模型 SPMD, SMP 等 如何表达并行性 DOACROSS, FORALL, PARALLEL,INDEPENDENT 如何表达同步 Lock, Barrier, Semaphore, Condition Variables 如何获得运行时的环境变量 threadid, num of processes
共享存储编程的基本问题 任务划分 域分解法 : 数据并行 (SPMD) 功能分解法 : 控制并行 (MPMD) 任务调度 静态调度 确定模式 非确定模式 动态调度 任务同步 任务通信
共享存储编程环境 纯共享编程环境 SMP 结构, 访存模型 UMA 系统中存在一个集中的 公共的共享存储器 ; 系统中集中的存储器对程序员而言是全局统一编址的 ; 系统不提供对非一致存储访问应用程序的任何支持 虚拟共享存储环境 DSM 结构, 访存模型 NUMA 系统中分布的局部存储器组成了系统的全局共享虚拟存储器 ; 系统中的虚拟共享存储器对程序员而言是全局可寻址的
共享存储系统编程 13.1 ANSI X3H5 共享存储模型 13.2 POSIX 线程模型 13.3 OpenMP 模型
ANSI X3H5 共享存储器模型 更早的标准化结果 PCF 共享存储器并行 Fortran 1993 年制定的概念性编程模型 Language Binding C Fortran 77 Fortran 90
并行块 ( 工作共享构造 ) 并行块 (psections... end psections) 并行循环 (pdo... Endo pdo) 单进程 (psingle... End psingle) 可嵌套 非共享块重复执行 隐式路障 (nowait), 显式路障和阻挡操作 共享 / 私有变量 线程同步 门插销 (latch): 临界区 锁 :test,lock,unlock 事件 :wait,post,clear 序数 (ordinal): 顺序
X3H5: 并行性构造 Program main! 程序以顺序模式开始, 此时只有一个 A!A 只由基本线程执行, 称为主线程 parallel! 转换为并行模式, 派生出多个子线程 ( 一个组 ) B!B 为每个组员所复制 psections! 并行块开始 section C! 一个组员执行 C section D! 一个组员执行 D end psections! 等待 C 和 D 都结束 psingle! 暂时转换成顺序模式 E! 已由一个组员执行 end psingle! 转回并行模式 pdo i=1,6!pdo 构造开始 F(i)! 组员共享 F 的六次迭代 end pdo no wait! 无隐式路障同步 G! 更多的复制代码 end parallel! 转为顺序模式 H! 初始化进程单独执行 H...! 可能有更多的并行构造 End
线程 P Q R A 隐式路障同步 B B B C D 隐式路障同步隐式路障同步无隐式路障同步 F(1:2) G E F(3:4) G F(5:6) G 隐式路障同步 H
共享存储系统编程 13.1 ANSI X3H5 共享存储模型 13.2 POSIX 线程模型 13.3 OpenMP 模型
POSIX 线程模型 IEEE/ANSI 标准 IEEE POSIX 1003.1c 1995 线程标准 Unix/NT 操作系统层上的,SMP Chorus, Topaz, Mach Cthreads Win32 Thread GetThreadHandle,SetThreadPriority,SuspendThread,ResumeThread TLS( 线程局部存储 ) TlsAlloc, TlsSetValue LinuxThreads: clone and sys_clone 用户线程和内核线程 (LWP)( 一到一, 一到多, 多到多 )
What Are Threads? Shared state (memory, files, etc.) Threads General purpose solution for managing concurrency. Multiple independent execution streams. Shared state. Preemptive scheduling. Synchronization (e.g. locks, conditions).
线程共享相同的内存空间 与标准 fork() 相比, 线程带来的开销很小 内核无需单独复制进程的内存空间或文件描述符等等 这就节省了大量的 CPU 时间 和进程一样, 线程将利用多 CPU 如果软件是针对多处理器系统设计的, 计算密集型应用 支持内存共享无需使用繁琐的 IPC 和其它复杂的通信机制 Linux clone 不可移植,Pthread 可移植 POSIX 线程标准不记录任何 家族 信息 无父无子 如果要等待一个线程终止, 就必须将线程的 tid 传递给 pthread_join() 线程库无法为您断定 tid
国家高性能计算中心 ( 合肥 ) POSIX Threads: Basics and Examples by Uday Kamath http://www.coe.uncc.edu/~abw/parallel /pthreads/pthreads.html POSIX 线程详解 : 一种支持内存共享的简单和快捷的工具 by Daniel Robbins http://www.cn.ibm.com/developerwor ks/linux/thread/posix_thread1/index.sht ml
国家高性能计算中心 ( 合肥 )
线程调用 线程管理 POSIX Solaris 2 pthread_create thr_create pthread_exit thr_exit pthread_kill thr_kill pthread_join thr_join pthread_self thr_self
线程调用 线程同步和互斥 POSIX Solaris 2 pthread_mutex_init mutex_init pthread_ mutex_destroy mutex_destroy pthread_ mutex_lock mutex_lock pthread_ mutex_trylock mutex_trylock pthread_ mutex_unlock mutex_unlock pthread_cond_init pthread_cond_destroy pthread_cond_wait pthread_cond_timedwait pthread_cond_signal pthread_cond_broadcast
Pthreads 实现计算 的实例 1
Pthreads 实现计算 的实例 2
对生产者驱动的有界缓冲区问题的 Pthread 条件变量解 void *consumer(void *arg2){ void *producer(void *arg1){ int i; for (i=1;i<=sumsize;i++){ pthread_mutex_lock(&slot_lock); while(nslots<=0) pthread_cond_wait(&slots,&slot_lock); nslots--; pthread_mutex_unlock(&slot_lock); put_item(i*i); pthread_mutex_lock(&item_lock); nitems++; pthread_cond_signal(&items); pthread_mutex_unlock(&item_lock); } pthread_mutex_lock(&item_lock); producer_done=1; pthread_cond_broadcast(&items); pthread_mutex_unlock(&item_lock); return NULL;} int i,myitem; for (;;){ pthread_mutex_lock(&item_lock); while ((nitems<=0)&&!producer_done) pthread_cond_wait(&items,&item_lock); if ((nitems<=0)&&producer_done){ ptherad_mutex_unlock(&item_lock); break; } nitems--; pthread_mutex_unlock(&item_lock); get_item(&myitem); sum+=myitem; pthread_mutex_lock(&slot_lock nslots++; cond_signal(&slots); pthread_mutex_unlock(&slot_lock); } return NULL; }
共享存储系统编程 13.1 ANSI X3H5 共享存储模型 13.2 POSIX 线程模型 13.3 OpenMP 模型
The History of OpenMP What is directive/pragma? Directive-based general purpose parallel programming API with emphasis on the ability to parallelize existing serial programs Why a new standard? Who s Involved? Parallelism model and basic directives Fortran77, Fortran90 C, C++ OpenMP 标准
The History of OpenMP A key intermediate step was X3H5 in the late 80 s. An official standards effort to agree on a parallel dialect of Fortran for shared memory computers. The X3H5 effort failed. It was too big and too late. OpenMP is born: In 1996 a group formed to create an industry standard set of directives for SMP programming This group called itself the OpenMP Architecture Review Board(the ARB) who takes care of OpenMP
The History of OpenMP(cont.) The ARB has released the following specifications: OpenMP 1.0 for Fortran, Nov. 1997 OpenMP 1.0 for C/C++, Nov. 1998 OpenMP Fortran Interpretations, Spring 1999 OpenMP 2.0(soon) OpenMP is an evolving standard. Send comments over the feedback link on the OpenMP web site(http://www.openmp.org)
为什么要建立新标准? ANSI X3H5, 1994 时机不好, 分布式机器流行 只支持循环级并行性, 粒度太细 Pthreads(IEEE Posix 1003.4a ) 是为低端 (low end) 的共享机器 ( 如 SMP) 的标准 对 FORTRAN 的支持不够 适合任务并行, 而不适合数据并行 MPI 消息传递的编程标准, 对程序员要求高 HPF 主要用于分布式存储机器 大量已有的科学应用程序需要很好地被继承和移植 OpenMP 标准的产生
In a Nutshell A set of directives(library routines, and environment variables) used to annotate a sequential program to indicate how it should be executed in parallel 继承 X3H5 的许多概念 Portable, Simple and Scalable Shared Memory Multiprocessing API not a new language not automatic parallelization extend base languages: Fortran77, Fortran90, C and C++ Multi-vendor Support, for both UNIX and NT Standardizes Fine Grained(Loop) Parallelism, also Supports Coarse Grained Algorithms
OpenMP 是什么? 一组编译制导语句和可调用的运行 (run-time) 库函数, 扩充到基本语言中用来表达程序中的并行性 编译制导语句包括 : 在串行程序中加入下列结构 SPMD(Single Program Multiple Data) constructs work-sharing constructs synchronization constructs data environment constructs 运行库函数包括 : execution environment routines lock routines 另外, 在 FORTRAN 标准中, 还包括对环境变量的描述
国家高性能计算中心 ( 合肥 )
OpenMP 当前的状况 1997 年 10 月 28 日, DEC, IBM, Intel, SGI, 和 Kuch & Associates 等公司的代表们决定制定一种适用于多种硬件平台的共享存储编程的新的工业应用标准 接着, 全球很多的组织和 ISV 决定支持这一标准, 如 DOE/ASCI, Livermore Software Technology Corp., Fluent Inc., Absoft Corp., Ansys Inc. Etc. 目前支持 FORTRAN 语言, C 和 C, 并建有专门的网址 http://www.openmp.org 在科研机构中, 也引起了足够的重视, 被认为是 21 世纪最受欢迎的并行编程标准 OpenMP on NOWs (SC98, Nov. 1998) Integrated OpenMP and MPI on Clusters
国家高性能计算中心 ( 合肥 )
OpenMP 并行编程模型 OpenMP 使用 Fork join 并行执行模型 所有的 OpenMP 程序开始于一个单独的主线程 (Master Thread) 主线程会一直串行的执行, 直到遇见第一个并行域 (Parallel Region) 才开始并行执行 接下来的过程如下 : Fork: 主线程创建一队并行的线程, 然后, 并行域中的代码在不同的线程队中并行执行 Join: 当主线程在并行域中执行完之后, 他们或被同步或被中断, 最后只有主线程在执行 所有 OpenMP 的并行化, 都是通过使用嵌入到源代码中的编译制导语句来达到的
Parallel and work sharing directives data environment directives synchronization directives
编译制导语句 (1) Work-sharing constructs 将结构内的任务分配到处理机中, 必须动态地放在 Parallel region construct 中, 进入这种结构之前并不隐含 BARRIER 操作 DO( 最常用 ) 有 SCHEDULE 选项, 可以指定采用什么调度算法 SECTIONS( 可以流水线执行之 ) SINGLE( 只有一个处理机执行之 )
Parallel Region and Work Sharing Directives Parallel Region: parallel, end parallel Work Sharing: do, sections, single(parallel do, nowait) Fork-Join model of parallel execution(static,dynamic,orphaned)
编译制导语句 (2) 指令格式 固定形式!$OMP 自由形式!$OMP, *$OMP, C$OMP Parallel Region Construct!$OMP Parallel [clause[[,] clause]...] Do I = 1, 20 A(I) = A(I) + B(I)!$OMP End Parallel ( 隐含 BARRIER 操作 ) 其中 Clause 可以为 :PRIVATE(list), SHARED(list),COPYIN(list), FIRSTPRIVATE(list), DEFAULT(PRIVATE SHARED NONE), REDUCTION({operation intrinsic}:list), IF(logical_expression)
DO 编译制导语句!$OMP DO [clause[[,] clause]...] do_loop [!$OMP END DO [NOWAIT]] 例子 :!$OMP PARALLEL DO DO I = 2, N B(I) = ( A(I) + A(I-1)) /2.0 ENDDO!$OMP END DO NOWAIT!$OMP END PARALLEL
SECTIONS 编译制导语句!$OMP SECTIONS!$OMP SECTION block1!$omp SECTION block2!$omp SECTION block3!$omp END SECTIONS
编译制导语句 (3) Data environment constructs THREADPRIVATE Data scope attribute clauses PRIVATE SHARED DEFAULT FIRSTPRIVATE LASTPRIVATE REDUCTION COPYIN
Data Environment Directives Data Scope attribute clauses: Private, Shared, Default, Firstprivate, Lastprivate, Reduction and Copyin/Copyout(value undefined entering/exiting parallel region) Threadprivate directives:private to a thread but global within the thread(smp) Fortran:COMMON blocks/ C:file scope and static variables
编译制导语句 (4) Synchronization constructs MASTER CRITICAL BARRIER ATOMIC FLUSH ORDERED
例子 (ORDERED) 规定了各个线程执行的顺序!$OMP PARALLEL!$OMP DO ORDERED SCHEDULE(DYNAMIC) DO I = LowBound, UpBound, Step CALL WORK(I) END DO!$OMP END PARALLEL SUBROUTINE WORK(K)!$OMP ORDERED WRITE(*,*) K!$OMP END ORDERED END
Synchronization Directives master, barrier, critical, atomic, flush, ordered
OpenMP 的 Orphan 新特性 1 为了便于支持粗粒度的任务级并行, OpenMP 提供了 Orphan 制导语句 Orphan 制导语句是指那些在并行区域 (Parallel Region, 如 PARALLEL) 之外的制导语句 在 OpenMP 中提供了一种绑定规则使得这些 Orphan 制导语句与调用它们的并行区域产生联系, 这样大大地增加了程序的模块性 X3H5 中不支持这一特点, 所有的同步和控制语句都必须依次出现在并行区域内, 无模块性
OpenMP 的 Orphan 特性 2
运行库函数 (1) Execution Environment Routines OMP_SET_NUM_THREADS OMP_GET_NUM_THREADS OMP_GET_MAX_THREADS OMP_GET_THREAD_NUM OMP_GET_NUM_PROCS OMP_IN_PARALLEL OMP_SET_DYNAMIC OMP_GET_DYNAMIC OMP_SET _NESTED OMP_GET_NESTED
运行库函数 (2) Lock Routines OMP_INIT_LOCK OMP_DESTROY_LOCK OMP_SET_LOCK OMP_UNSET_LOCK OMP_TEST_LOCK
OpenMP implementations are not required to check dependencies, conflicts, deadlocks, race conditions or other problems that result in incorrect program execution. The user is responsible for ensuring that the application using the OpenMP constructs execute correctly. Compiler do not ignore user directives even if wrong(semantic). ARB: Compaq HP IBM SGI Intel KAI Sun Research Compiler: Polaris/OpenMP(Purdue Univ.) Can be run on the Web at http://punch.purdue.edu.cn:8000/parhub/ Compiler/Translator Debugger profiler Translates sequential Fortran programs into OpenMP
OpenMP 计算 的实例
MPI 计算 的实例
OpenMP 与其他标准的比较 1
OpenMP 与其他标准的比较 2
OpenMP 与其他标准的比较 3 X3H5 OpenMP SGI
OpenMP 的优点与缺点 优点 提供了一个可用的编程标准 可移植性, 简单, 可扩展性 灵活支持多线程, 具有负载平衡的潜在能力 支持 Orphan Scope, 使程序更具有模块化 缺点 只适用于硬件共享存储型的机器 动态可变的线程数使得支持起来困难
Conclusion 为什么共享存储编程模型得不到应用领域科学家的青睐? (1) 性能的考虑 (2) 最大问题是缺乏广为接受的标准 ANSI X3H5 标准委员会现已停止活动,X3H5 标准也不为工业界广泛接受 目前使用的是 专用的并行编程语言 (SGI Power C or Cray Craft) 线程库 (Solaris Threads or Pthreads) OpenMP 标准可能统一共享存储器标准