并行程序设计Chapter-2H

第二章共享存储程序设计,刘轶北京航空航天大学计算机学院,从程序员视角看，并行体系结构主要分为两类：共享存储(shared-memory)系统典型平台：-基于多核处理器的计算机-SMP及NUMA体系结构计算机消息传递(message-passing)系统-机群系统,本章内容,几种主流的并行编程接口,2.1OpenMP,2.1OpenMP,一、概述20世纪90年代后期开发通过使用嵌入编译器命令来建立并行，由一个小型的编译器命令集构成支持C/C+、Fortran在C/C+中，OpenMP命令包含在#pragma语句中#pragmaompdirective_name在Fortran中，OpenMP命令包含在comment语句中OpenMP的构成CompilerdirectivesRuntimeroutinesEnvironmentvariablesOpenMP的编译支持Linux/Unix平台：gcc支持OpenMPWindows平台：Microsoftvisualstudio编译选项：/openmp,2.1OpenMP,MicrosoftVisualStudio编译选项,2.1OpenMP,使用OpenMP并行化,一段for循环的串行代码,OpenMP的并行执行模型,OpenMP的优点之一：在支持并行的编译和运行平台上，可通过并行获得性能提升，在不支持的编译平台上，#pragma被忽略，编译出的程序顺序执行,以上仅为示例，实际运行时可能因并行粒度过小导致无法提升性能(每个线程仅200次加法),进程与线程进程(process)程序在数据集合上的一次运行是系统资源分配和调度的单位进程与程序之间有关联又有区别，进程是动态概念，程序是静态概念线程(thread)又称为轻量级进程(LWPlightweightprocess)线程是进程中的一个实体，是操作系统调度的基本单位进程与线程比较进程是资源分配的单位，线程是处理器调度的单位不同进程拥有独立的内存地址空间由操作系统和处理器的虚拟存储机制实现避免进程间相互干扰，保证系统稳定性和安全性进程之间的交互需要通过操作系统提供的进程间通信机制进行属于一个进程的多个线程共享该进程的资源内存地址空间(变量)、文件、,主流通用操作系统的线程调度基于优先级的时间片轮转调度当有处理器空闲时，操作系统从就绪(Runnable)线程队列中选择线程运行线程按时间片(timeslot)轮流调度执行当线程运行时间片满时，转入就绪状态线程运行过程中，执行I/O、加锁等操作时，转入阻塞状态当线程等待的事件发生时，由阻塞状态转入就绪状态，等待调度执行运行(Running)、阻塞(Blocked)和就绪(Runnable)状态的线程处于就绪状态的线程按优先级排入不同队列，操作系统优先从优先级队列中调度线程执行,嵌入式操作系统、实时操作系统等的线程调度机制可能有所不同,2.1OpenMP,二、Parallel命令Parallel：OpenMP的基本命令#pragmaompparallelstructured_block命令将创建多个线程，每个线程都执行指定的structured_blockstructured_block可以是一条语句或，但只能有一个入口和出口在结束处有一个隐含的barrier线程个数由下列方法之一设定(按顺序)：在paralllel命令之后用num_threads子句#pragmaompparallelnum_threads(8)调用omp_set_num_threads()用环境变量OMP_NUM_THREADS定义如果未指定线程数，则由系统自行确定可通过环境变量OMP_DYNAMIC或函数omp_set_num_dynamic()控制动态调整机制,三、工作共享有三种构造：sections、for和singlesections构造(construct)#pragmaompsections#pragmaompsectionstructured_block#pragmaompsectionstructured_block各结构块将在组内的线程间共享，每个结构块执行1次，结构块可并行并不创建线程组，线程组在parallel时创建在结束处有一个隐含的barrier，除非该构造包含nowait子句,2.1OpenMP,三、工作共享for构造#pragmaompforfor_loop循环将被分成若干部分，由组内线程并行执行循环的分割方法可由schedule子句说明，如schedule(static,chunk_size)将使循环按chunk_size指定的大小分割，并以轮转方式分配给线程并不创建线程组，线程组在parallel时创建在结束处有一个隐含的barrier，除非该构造包含nowait子句single构造#pragmaompsinglestructured_block结构块将仅由一个线程执行,2.1OpenMP,四、并行工作共享的组合如parallel命令后跟随单个for，则可组合成：#pragmaompparallelforfor_loop类似地，sections可组合成：#pragmaompparallelsections#pragmaompsectionstructured_block#pragmaompsectionstructured_blockmaster命令#pragmaompmasterstructured_block指定主线程执行结构块,五、同步(1/2)critical#pragmaompcriticalnamestructured_block一次只允许一个线程执行structured_block一个线程执行过程中，其他要执行该块的线程将等待直到其退出该块atomic#pragmaompatomicexpression_statement高效地实现临界区，它要求是一个表达式语句，如更新一个共享变量,五、同步(2/2)barrier#pragmaompbarrier线程到达时将等待直到所有线程都到达,多线程工作共享Barrier多线程工作共享,2.1OpenMP,六、常用子句(clauses)nowait子句作用：使线程忽略命令结束处的隐含barrier可用于for、sections、single命令例：#pragmaompparallel#pragmaompfornowaitfor(i=0;i处理器个数，性能也可能受影响,2.3新型编程语言/接口,2.3新型编程语言/接口,一、Cilk一种针对多核处理器的编程语言扩展最初支持C语言，后扩展至C+首先由MIT开发(1994)，后产品化(CilkArtsInc.)，2009年被Intel收购有开源软件包GCC、VisualStudio均可支持cilk编程Cilk包含若干关键字,2.3新型编程语言/接口,Cilk的关键字cilk:用于标示一个函数是cilk代码spawn:标示一个函数调用可以和其他代码并行执行sync:等待之前spawn的代码都执行完毕且返回结果后，当前的过程调用才可继续(类似于barrier)inlet:用于控制多个spawn的函数修改变量的原子性abort:inlet内使用，表示spawn的函数可以安全地abort,Cilk示例代码：求Fibonacci数列,cilkintfib(intn)if(n2)return(n);elseintx,y;x=spawnfib(n-1);y=spawnfib(n-2);sync;return(x+y);,将一个函数标示为Cilk过程，能够被并行化,标示该函数调用可以和其他代码并行执行,等待之前所有spawned代码执行完毕,Fibonacci数列：F(0)=0F(1)=1F(n)=F(n-1)+F(n-2),Cilk的特点：程序员只需指出并行性，当程序运行时，由运行时环境根据硬件状况进行动态调度,2.3新型编程语言/接口,多核/众核处理器上的任务调度现有操作系统任务调度存在的问题处理器核数和任务数都很多，集中式的任务调度易产生性能瓶颈在众核环境下，任务可能相对较小(执行时间短)，集中式的任务调度难以适应解决办法：使用多条任务队列(如每核一条)，但可能导致负载不平衡(运行过程中有些核的队列很长，有些核的队列为空)针对多核/众核的任务调度方法任务共享(Worksharing)每当创建新的任务时，调度器(scheduler)就试着将其中一部分迁移到其他处理器上，以便将工作分布到低利用率的处理器上任务窃取(Workstealing)空闲处理器核主动从其他处理器上“窃取”任务运行线程迁移次数比任务共享调度方式少,线程迁移可能产生较大开销,Cilk运行时环境的任务窃取调度每个处理器(核)维护一条就绪队列，队列中一项对应一层，包含一个链表当一个处理器的就绪队列为空时，它就变为thief，从现有处理器中随机选择一个victim，从该处理器就绪队列尾部(最浅层)窃取一个线程执行从最浅层窃取任务的理由：最浅层线程的任务