任务并行编程模型

任务并行编程模型电信学部——任务并行编程模型概述传统的并行编程模型主要有数据并行和消息传递,数据并行编程模型的编程级别比较高,编程相对简单,但它仅适用于数据并行问题;消息传递编程模型的编程级别相对较低,但消息传递编程模型可以有更广泛的应用范围。任务并行编程模型把任务作为并行的基本单位,提供任务划分和同步的编程接口,把任务划分和同步工作交给程序员完成,用户可以把应用程序划分出大量细粒度任务.然而,具体到每个任务到底是并行执行还是串行执行、在哪个物理核上执行以及如何实现任务之间的同步则由运行时系统完成.运行时系统通过基于有向无环图(DAG)的任务窃取调度算法来管理任务的执行。任务并行编程模型优点为程序员提供了两类并行控制结构,分别是支持规则并行的循环并行控制结构和支持非规则并行的嵌套并行控制结构.逻辑任务与物理线程分离,程序员只需考虑如何划分逻辑任务,使用合适的并行控制结构并行逻辑任务运行时系统负责任务调度,采用任务窃取调度算法获得负载平衡,提高多核的使用效率内容提纲1.关键技术挑战并行性表达数据管理任务调度2.针对挑战的最新研究成果并行性表达数据管理任务调度3.未来的展望1.关键技术挑战1.1该模型的编程接口能支持的并行模式有限,需要丰富编程接口,表达多种多样的并行性嵌套并行控制结构循环级并行无条件原子块结构有条件原子块结构1.2该模型把数据分为共享和私有两种,通过共享数据进行通信.但有些数据是部分任务共享,或者一个线程内执行的所有任务共享,因此需要对数据进一步区分共享范围,需要研究如何高效实现不同级别的共享数据;1.3降低运行时系统开销2.最新研究成果2.1并行性表达尾端严格的特性循环级并行表达原子块结构移相器2.1.1尾端严格的特性尾端严格的特性任务同步对应的依赖关系在任务之间产生join边,DAG任务图中每条join边都是从一个任务的最后一条指令指向其派生树的某祖先完全严格的join边总是从派生树的某节点指向父亲节点依赖图满足的严格特性2.1.2循环级并行表达Cilk++cilk_for关键词支持循环级并行,任务图采用DFS(深度优先搜索)具体实现方法采用分治法切分迭代空间,把循环并行转换为嵌套并行,从而把任务压入或弹出任务队列OpenUH任务图采用BFS(广度优先搜索)TBB(ThreadingBuildingBlocks)一个C++并行模板库,通过parallel_for、parallel_do等关键词表达并行,底层实现运用了Cilk的任务窃取调度算法2.1.3原子块结构X10语言支持无条件原子块结构atomicS和有条件原子块结构when(E)S.当条件E不为真时,有条件原子块结构when(E)S只能被挂起具体方法是:每一个库所(通常指一个缓存一致性的计算单元)共享一个额外队列存放被挂起的有条件的原子块;当执行到when结构时,E为假,就把这个原子块放入额外队列中,挂起该原子块,成为空闲线程.当线程执行完某个原子块时,把共享的额外队列中所有原子块放入自己的任务队列中,这样,每一个被挂起的原子块的条件都会重新再计算一遍.2.1.4移相器2008年,Rice大学借鉴X10的任务并行结构提出HabaneroJava任务并行语言,引入了移相器(phaser)及其累加器(accumulator)这两个概念,目的是降低栅障和规约的开销移相器是X10中同步钟的一个扩展,它是一个同步对象,支持4种操作:创建、注册、退出和推进.移相器与其累加器相结合把集合操作划分为数据发送、计算、结果取回和同步,支持计算和通信的重叠2.2数据管理数据属性表达并发数据结构锁外协助2.2.1数据属性表达基于共享存储的任务并行编程模型用全局变量进行通信和同步.全局变量在串行程序中用于简化编程,但在并行程序中会导致数据竞争.用锁避免对共享数据的竞争会影响并行度,从而不能获得高性能Cilk++提供超级对象(hyperobjects)来描述数据属性.运行时系统保证每个线程有全局变量的私有拷贝,线程访问私有拷贝,这样,在不需要锁的情况下消除了线程间竞争的可能性2.2.2并发数据结构一个并发数据结构允许多个线程并发访问和更新数据结构中的元素,它往往使用细粒度锁或lock-free技术等方法加以实现,在保证线程安全的同时得到并行加速比,但是复杂,难理解,而且有明显的实现开销.Cilk++利用reducer超级对象实现了这样一个快速访问的并发集合bag,多个线程可以同时向集合bag中增加或删除数据2.2.2并发集合这个并发集合是一个指针数组,每个数组元素是一棵二叉树.指针数组相当于一个二进制数,表明集合中元素的个数.例如,指针数组A[]是010111,表示有23个节点,A[0]是有1个节点的二叉树,A[1]是有2个节点的二叉树,A[2]是有4个节点的二叉树,A[3]和A[5]没有节点,A[4]是有16个节点的二叉树.当有两个线程需要共同访问这个并发集合时,这个指针数组A能够快速分裂成两个大小相同的指针数组,两个线程分别访问不同的数组;sync之后,也能快速地把两个指针数组合并成一个数组.这种无锁的并发集合比基于锁的并发集合性能好很多.2.2.3锁外协助临界区是用于防止多个线程同时执行一段特定代码的机制,常用锁对临界区进行保护,每次只能有一个线程执行临界区内的代码.假设线程1获得锁L,开始执行临界区A.这时,线程2也想获得锁L,它只能被阻塞helplock:当线程2不能获得锁L时,线程2不是阻塞,而是挂起自己的任务,帮助线程1去执行临界区A的任务.这样,线程2没有忙等,充分利用了计算资源.这种helplock非常适合临界区较大的程序2.3任务调度任务并行编程模型提供隐式的任务映射机制,运行时系统采用任务窃取调度算法,把逻辑任务映射到物理线程上去执行.提高执行效率是运行时系统的核心任务任务窃取调度算法局部性敏感的调度算法异构系统调度算法控制任务粒度2.3.1任务窃取调度算法任务窃取调度算法的实现方法是每个处理器核对应一个线程,每个线程维护一个双端队列存放任务状态信息,这个状态信息包括任务中的局部变量、PC值、子任务的个数等,用于恢复被挂起任务或执行被窃取的任务.每个线程从自己双端队列的尾部压入准备好的任务或弹出已经执行完的任务;当自己双端队列为空时,从其他线程的双端队列头部窃取任务,首先恢复窃取的任务状态,然后根据状态跳转到相应的的指令开始执行2.3.2局部性敏感的调度算法任务窃取采用最早任务优先窃取策略,该策略的“深度优先执行”能够提高cache的利用率.但随机选择线程进行任务窃取,而没有考虑处理器架构特点,对于局部性敏感的应用会有影响.局部性敏感的调度算法主要关注如何选择要窃取的线程.Cache亲密性调度每个线程除了任务队列外还有一个邮箱(mailbox),用于存放与该线程亲密的任务.当线程1产生一个与线程2有亲密性的任务时,线程1把指向该任务的指针放入线程2的邮箱中.当线程2完成自己任务队列中的任务时,先检查自己的邮箱,执行邮箱中的任务,最后再窃取任务.多路多核处理器架构上的局部性敏感调度目前,服务器基本上都是多路多核架构,处理器包含多个多核芯片,片内多核共享L3cache,片间多核共享内存,提供cache一致性.任务窃取调度策略是随机选择一个线程进行任务窃取,没有区分片内和片间的线程,而对于局部性敏感的应用,这种随机任务窃取调度策略降低了cache利用率,从而也导致性能下降.根据硬件结构对线程进行分组,片内的线程分为一组,每个线程有一个组内任务队列,每个组有一个组间任务队列.运行时系统顺着调用树把任务分成组内任务和组间任务,然后放入相应的任务队列中.线程执行完自己的组内任务队列中的任务后,随机选取同组其他线程进行任务窃取;当一个组的所有组内任务队列为空时,从本组的组间任务队列中窃取任务;当一个组的所有组内任务队列和组间任务队列都为空时,就从其他组的组间任务队列中窃取任务.2.3.3异构系统调度算法假设共享存储系统中各个处理器的执行速度不同,在这种异构系统中,执行速度快的处理器可以打断执行速度慢的处理器,并把它正在执行的任务窃取过来执行2.3.4控制任务粒度运行时系统用软件实现任务窃取调度算法是有代价的,产生大量的细粒度任务会加重系统开销;相反地,产生少量的粗粒度任务会造成负载不平衡,从而使性能下降.由此可见,系统开销与任务数量成正比,而负载平衡与任务数量成反比,合适的任务粒度是在系统开销和负载平衡两个因素之间加以权衡.如何获得合适的任务粒度是任务并行编程模型的一个重要问题.控制任务粒度的调度算法自适应任务粒度自适应任务粒度的核心思想是,当所有线程都繁忙时就不产生任务,直到有线程空闲需要任务时,繁忙线程再产生任务Cut-Off策略Cut-Off策略通常指定在派生树(或函数调用树)上的一个递归深度,当超过这个深度时,不产生任务Cut-Off策略的5种实现方法方法1.程序员提供一个cut-off递归深度,或运行时系统设置一个缺省的深度.这种方法简单,但不能适应环境变化.方法2.运行时系统根据当前任务队列的大小设置cut-off深度,从而控制任务粒度.但是这种方法需要程序员设置串行程序的阈值,并且进行手动的性能调优Cut-Off策略的5种实现方法方法3.首先进行工作集轮廓信息收集,然后用收集后的信息执行cut-off方法4.运行时系统支持的自适应cut-off技术运行时系统收集每一层产生的任务数,如果任务数大于两倍的线程数,就cut-off,不再产生新任务方法5.用户制导的自适应cut-off技术，希望能够预测每个分支的大小,直到这个分支不太大时就cut-off3.未来研究方向针对NUMA(non-uniformmemoryaccess)结构的多路多核处理器,任务并行编程模型需要考虑提供合适的数据分布接口针对异构平台CPU+GPU针对新兴的非规则应用,任务并行编程模型需要提供更丰富的数据管理组件提高可编程性谢谢！