（计算机科学与技术专业论文）openmp+task调度算法实现及优化.pdf

国防科学技术火学研究生院硕十学位论文 摘要 o p e n m p 已经成为共享存储程序设计的事实标准。随着多核技术的发展，越来越多的 应用程序使用o p e n m p 并行编程以发挥多核c p u 的并行计算能力。为了支持不规则程序 的并行执行，o p e n m p3 0 规范中提出了t a s k 机制，标识独立工作的单元，支持递归并行、 动念任务创建等，拓宽了o p e n m p 应用领域。目前，各编译器厂商和研究机构都给出了各 自不同的t a s k 实现。 作为最广泛使用的丌源编译器，g c c 初步实现了o p e n m p 3 0 接1 3 。但是对于t a s k ， g c c 只实现了简单的f i f o 调度，导致t a s k 机制开销大。论文在研究分析了目前已有的 t a s k 调度算法和实现的基础上，在g c c 上实现了宽度优先和工作优先调度策略，优化了 t a s k w a i t 时线程空闲等待导致的负载不平衡，并提出了混合调度策略。主要工作和创新 包括： l 、分析比较了目前已有t a s k 调度算法和实现，尤其对g c c 中t a s k 实现进行了 详细分析，针对g c c 只实现了简单的f i f 0 调度的问题，在g c c 上实现了宽度 优先和工作优先调度，解决了g c ct a s k 并行效率低的问题，测试表明，f f i 递 归非绑定测试程序，在八个线程的深度优先调度中，性能提高了1 0 6 。 2 、针对g c c 本身的调度策略中任务遇到t a s k w a i t ，线程挂起等待的问题，通过 修改任务与子任务问通信机制对其进行优化，使得任务在等待子任务的同时可调 度执行就绪任务，提高程序的并行性能。 3 、针对宽度优先中线程提取性能差的任务缺点，和工作优先调度中线程可能挨饿缺 点，提出混合调度策略，通过宽度优先创建足够多的任务，工作优先提取性能好 的任务保证线程忙碌而高效，以提高程序的并行性能。 4 、利用t a s k 机制，实现了典型不规则并行的测试用例，例如f f t ，用以测试论文 提出并实现的调度策略。测试结果表明，论文实现的调度策略能较好的调度任务， 提高不规则并行程序的性能，与g c c 实现相比，程序平均获得了1 1 g l 速比。 主题词：o p e n m p ，t a s k ，任务调度，宽度优先调度，工作优先调度，混合调度 第i 页 国防科学技术大学研究生院硕十学位论文 a b s t r a c t t h eo p e n m ph a sb e e nt h es t a n d a r do fp a r a l l e lp r o g r a m m i n go nt h es h a r em e m o r y w i t ht h e d e v e l o p m e n to fm u l t i c o r e ，m o r ea n dm o r ea p p l i c a t i o n sm a k eu s eo fo p e n m pt oe x p l o r et h e i r p a r a l l e lc o m p u t a t i o n i no r d e r t od e v e l o pt h ei r r e g u l a rp a r a l l e lp r o g r a m ，t h eo p e n m p 3 0p r o p o s e t h et a s k ，w h i c hi su s e dt os p e c i f yi n d e p e n d e n tu n i t so fw o r k ，s u p p o r tr e c u r s i v ep a r a l l e l i z a t io n ， a n dt h ec r e a t i o no fd y n a m i ct a s k s ，t oa d d r e s st h el a n d s c a p e b yn o wt h em a i nc o m p i l e r sv e n d o r s a n do r g a n i z a t i o no fc o m p i l e r si m p l e m e n tt h et a s ks c h e d u l i n gs t r a t e g i e si nt h e i ro w l lw a y s g c c ，a sw i d e l yu s e do p e ns o u r c ec o m p i l e r ，h a sd e v e l o p e da l li m p l e m e n t a t i o no fo p e n m p 3 0a p ip r i m a r i l y h o w e v e r ，i to n l yju s tc o m p l e t e sas i m p l ef i f os c h e d u l e rf o rt h et a s k ， w h i c hi sr e s p o n s i b l ef o ri t si n e f f e c t i v ep e r f o r m a n c e r n l ep a p e ra n a l y s e st h et a s ks c h e d u l i n g s t r a t e g i e sa n di t si m p l e m e n t a t i o nw ek n o w ，a n dc o m p l e t et h eb r e a d t h f i r s ta n dw o r k f i r s to n g c c ，a n dp r o p o s em i x t a s ks c h e d u l i n gs t r a t e g i e s t h em a i nw o r kw ed o n ea sf o l l o w s ： 1 a n a l y z i n gt h et a s ks c h e d u l i n gs t r a t e g i e s ，e s p e c i a l l ya n a l y z et h et a s ks c h e d u l i n g s t r a t e g i e si m p l e m e n t e db yg c ca n di t si m p l e m e n t a t i o ni nd e t a i l f o rt a s ks c h e d u l i n g ju s to n l yi m p l e m e n tw i t hf i f o ，w ee x p l o r et h eb r e a d t h f i r s ta n dw o r k f i r s tt a s k s c h e d u l i n gs t r a t e g i e so ng c ct o d e a lw i t hl o ww o r s ep e r f o r m a n c eb yg c ct a s k s c h e d u l i n gs t r a t e g y b yt h et e s to ff f t ，t h er e s u l ts h o wt h ep e r f o r m a n c eo fa p p l i c a t i o n h a sb e e ni m p r o v e d1 0 6 2 t h e r ei sap r o b l e m ，w h e nat a s ke n c o u n t e rat a s k w a i t t h et h r e a dw i l ls u s p e n di t s e l ft o w a i ti nt h eo r i g i n a lo fi m p l e m e n t a t i o no ft a s ks c h e d u l i n go fg c c ，t os o l v et h ep r o b km ， w em o d if yt h ec o m m u n i c a t i o nm e c h a n i s mb e t w e e nt h et a s ka n di t sc h i l d r e n w h i c h m a k et h et a s kc a ns c h e d u l ea n o t h e rr e a d yt a s kt ol u l lw h e ni ti sw a i t i n gi t sc h i l d r e nt ob e c o m p l e t e d ，h e l p i n gt oi m p r o v et h ep e r f o r m a n c eo ft h ep a r a l l e la p p l i c a t i o n 3 t os o l v et h ep r o b l e mo ft h et h r e a dg e t st h ew o r s ep e r f o r m a n c eo fw o r ki nb r e a d t h f i r s t s c h e d u l e r sa n dt h et h r e a dm a y g e tt os t a r v ei nw o r k f i r s ts c h e d u l e r s ，w ep r o p o s et h em i x t a s ks c h e d u l i n gs t r a t e g y m a k i n gu s eo ft h eb r e a d t h f i r s ts c h e d u l i n gt oc r e a t em o r et a s k s t ok e e pt h et h r e a db u s ya n dt h ed e p t h f i r s tt og e tb e t t e rp e r f o r m a n c ew o r kt ok e e pt h e t h r e a de f f e c t i v e ，w h i c hi sh e l p f u lt oi m p r o v et h ep e r f o r m a n c eo ft h ea p p l i c a t i o n 4 w i t ht h em e c h a n i s mo ft a s k ，w ed e v e l o ps o m et y p i c a li 1 1 r e g u l a rp a r a l l e la p p l i c a t i o n s ， s u c ha sf f t ，t ot e s tt h et a s ks c h e d u l i n gs t r a t e g i e sw h i c ha r ei m p l e m e n t e db yt h ep a p e r t h er e s u l ts h o w st h a tt h ei m p l e m e n t a t i o no ft h et a s ks c h e d u l i n gi nt h ep a p e rc a l l s c h e d u l et h et a s kw e l l ，a n di m p r o v et h ep e r f o r m a n c eo ft h ea p p l i c a t i o n s c o m p a r e dt o t h eg c c s ，g e taa v e r a g e1 1 s p e e d u p k e yw o r d s ：o p e n m p ，t a s k ，t a s ks c h e d u l e r s ，b r e a d t h - f i r s ts c h e d u l e r s ，w o r k - f r s t s c h e d u l e r s ，m i xs c h e d u l e r s 第i i 页 围防科学技术火学研究生院硕十学位论文 表目录 表1 1 任务属性4 表2 1 g c c 4 5 中任务属性一1 8 表3 1协程属性2 5 表5 1调度器组合4 1 第l i i 页 国防科学技术大学研究生院硕十学位论文 图 图 图 图 图1 5 图1 6 图1 7 图1 8 图1 9 图2 1 图2 2 图2 3 图2 4 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图4 1 图4 2 图4 3 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 图5 8 图5 9 图目录 并行指针索引2 使用s i n g l en o w a i t 的并行指针索引2 并行深度优先遍历。3 延续传递形式5 阻塞模式。5 斐波那契任务图6 对应图1 6 中斐波那契任务图的线程就绪池7 任务完成后任务仍然可能存在9 任务构造9 g o m pt a s k 函数原型1 9 g o m pt a s k 的数据流图2 0 o m pb a r r i e rh a n d l et a s k s 函数原型2 l g o m pt a s k w a i t 函数原型2 1 协程的数据结构2 4 宽度优先的任务数据结构2 5 宽度优先任务池的数据结构及管理函数接口2 6 宽度优先任务创建流程图2 7 宽度优先的任务调度器2 8 工作优先的任务池3 0 工作优先任务调度策略流程图3 1 宽度优先分配任务3 3 任务构造图3 4 t a s k w a i t 任务等待子任务的优化前后对比3 5 基2 的串行递归f f t 算法3 9 基2 并行递归f f t 算法4 0 基s i z e 的c o m p u t ew o r k 并行算法4 0 t a s kf f t 加入并行区4 0 a l i g n m e n t 4 2 s p a s e l u 4 2 f f t 4 3 s o r t 4 3 nq u e e n s 4 4 第1 v 页 国防科学技术火学研究生院硕十学位论文 图5 10s t r a s s e n 4 4 图5 11 绑定任务的f f t 一4 5 第v 页 独创性声明 本人声明所星交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果口尽我所知。除了文中特另, j l l j 1 以标注和致谢的地方外，论文中不包舍 其他人已经发表和撰写过的研究成果。也不包舍为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：q 巳皇q 塑旦塑丛塑廑篡鎏塞塑垦垡! 竖 学位论文作者签名：毒溪良日期：川年f x 月知日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅：可以将学位论文的全部或部分内容编入有关数据 库进行检索可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 学位论文储签名：旦粤k 眺卟m 妒 作者指导教师签名：型江 日期：砷年堋湖 国防科学技术大学研究生院硕十学位论文 第一章引言 多核技术的快速发展，已经不仅仅局限于服务器，现在的p c 也已经全面进入多核阶 段。对今天的用户而言，就是要如何用好多核。在多核上进行编程，o p e n m p 是一个很好 的选择。它在串行程序中适当的位置加上编译制导指令，程序就可以并行执行，这对习惯 于编写串行程序的程序员非常简单，有效。然而o p e r d v i p 2 5 规范是基于数组式应用程序， 不适合编写不规则并行程序，但是应用程序中有大量的不规则的并行，o p e n m p 结构委员 会在基于其他编程语言的动态结构情况下，在o p e n m p 3 0 规范中提出了t a s k 机制，标识 独立的工作单元，使得o p e n m p 适合开发包含不规则并行的程序。 1 1 1 多核技术发展 1 1 课题背景 一直以来，各处理器生产厂商一直依靠提高时钟频率来提高处理器性能。但随着芯片 工艺的不断进步，传统处理器在性能提高和节能方面遇到了技术瓶颈，在这样的状况下， 各主流处理器的竞争焦点逐渐从主频转向了多线程、多内核。第一款采用多核设计的服务 器处理器是2 0 0 1 年i b m 发布双核r i s c 处理器p o w e r 4 ，它由两个p o w e r p c 处理器内核 集成在同一颗j 芭= 片上。随后，各主流处理器厂家先后推出双核，四核处理器等多核处理器， 争夺多核处理器市场。多核体系结构1 1 , 2 1 为性能提高和节能计算等领域开辟了新的方向，使 世界信息产业迈入多核时代，但同时，多核处理器需要提高程序的并行度，因为串行程序 是无法挖掘出多核处理器的性能的。为了发挥多核的最大性能，软件必须设计成为多线程 的。并行化、多核心等诸多技术为软件开发和应用行业提供了巨大的空间。全球的开发者 都已经丌始重视并行编程，开发人员也越来越感受到并行编程可以充分的获取多核处理器 的性能。 在多核上进行多线程编程，o p e n m p 是一种不错的选择，他以线程为基础，通过编译 制导语句显式制导并行化，可以方便的将一个串行程序改造成一个并行程序，减少程序员 负担，同时他也很简单，使得程序员容易上手。 1 1 2 o p e n m p 2 5 规范的缺点 o p e n m p 是一种面向共享内存的多处理器多线程并行编程语言。它是一种能够被用于 显式制导多线程，共享内存并行的应用程序接口。o p e n m p 的规范由s g i 发起，由一组主 要的计算机硬件和软件厂商共同制定并认可。 很多应用程序，如基于指针索引，自适应网格计算等，包含许多不规则的并行数据处 第1 页 国防科学技术火学研究生院硕七学位论文 理。4 i 舰则的并行常常以动态生成的工作单元，异步执行的形式存在。 在o p e n m p 2 5 规范中，没有提供一种简单有效的方式表示不规则的并行。因为o p e r l l v l p 原本是为基于大规模数组的应用程序设计1 3 j 的。在o p e n m p 2 5 规范中，线程间的工作分配 主要有两种机制，一是在循环结构中，工作分配就是迭代次数在线程间分配，而迭代次数 在进入循环时已经确定，并且在程序执行中不能改变。二是在s e c t i o n s 结构中，工作单元 是在编译期间静念分配的。 图1 1 并行指针索引 在o p e n m p 2 5 中并行遍历动态链表是很麻烦的。一种可能的实现方法是把指针存储在 数组中，如图1 1 所示。当所有的指针都存储到数组中，可以使用p a r a l l e lf o r 循环来并行 处理数组中的数据。p a r a l l e l f o ，指令创建一组线程，并在线程间分配迭代次数，线程并行 执行所分配的任务。这种存贮指针到数组中并行化遍历动态链表的方法，不仅有创建数组 的丌销，而且实现麻烦。 另一种可能的实现方法是在p a r a l l e l 区域使用s i n g l en o w a i t 4 结构，如图1 2 所示。 p a r a l l e l 指令创建一组线程，线程组中的所有线程并行执行w h i l e 循环，遍历链表中所有元 素，s i n g l e 指令保证线程组中只有一个线程实际处理了链表中某一元素。 图1 2 使州s i n g l en o w a i t 的并行指针索引 尽管这种方法看上去很好，但方法不直观且效率低效。因为s i n g l e 结构开销很大，而 且每一个线程都要去遍历整个链表和判断元素是否已经被另一个线程处理。 o p e n m p 2 5 规范还缺乏标识不同工作单元中独立结构的指令。o r d e r e d 结构强制了执行 的顺序。其它o p e n m p 同步结构，如栅栏，同步一个线程组，而不是工作单元。规范中的 诸多限制影响了具有层次结构的算法的程序( 如树结构的遍历，多区域网格求解f 5 】，自适 应网格加密【6 。8 l ，密集线程组) 性能。理论上，嵌套并行方式可以解决这类问题，如图1 3 所示。 第2 页 同防科学技术人学研究生院硕十学位论文 图1 3 并行深度优先遍历 在程序舭n ，p 瑚p p 中的p a r a l l e l 指令，创建一组线程，其中包含两个线程。s e c t i o n s 指令 指定其中的一个线程柬处理左子树，另一个线程处理右子树。每一个线程都会在子树上递 归调用t r a v e r s e o ，创建嵌套的并行区。但这种方法开销大。创建并行区，会过多使用系统 资源，导致负载不均衡，而且不同的应用程序有不同的实现方法。因而嵌套并行方式不适 合。 1 1 3t a s k 的提出 o p e n m p 2 5 规范的结构特性不适合开发不规则的并行程序。用户需要一种简单的方法 来标识独立的工作单元，并且不用关心这些工作单元的调度。这种模型称为“t a s k i n g ” 9 1 ， 它常常以动态生成的工作单元，异步执行的形式存在。在其它程序语言中，有几种方式 表示不规则的并行，我们列举如下： c o m p o s i t i o n a lc + + ( c c h ) 0 0 ，是对c + + 进行拓展，为开发任务并行的面向对象秸序 而设计的。c c h 语言引进p a r 块和p a r f o r 及s p a w n 语句。c c 抖的并行程序块用 p a r s t a t e m e n t so p t 表示。并行块内的语句按照随机公平交替的方式执行，在并行块中的语 句全部执行完毕之后，控制流转入并行块的后继语句。c c h 中用p a r l o r ( f o r i n i t s t a t e m e n t e x p r e s s i o no p t ；e x p r e s s i o no p t ) 标识一个并行循环。循环的后继迭代可以在当前迭代执行 完毕之后开始运行，并行循环中的迭代是公平交替执行的。全部迭代执行完毕之后，p a r f o r 的执行中止。s p a w n 语句生成一个新的线程来执行任意的c c + + 语句。 c i l k i l l j 是- - i 1 基于c 编程语言，能动态生成任务的多线程的语言。c i l k 语言提出的工 作优先原理和窃取任务策略，对动态任务的调度有启发意义。然而，c i 墩缺乏l o o p 和s e c t i o n s 等结构，这些结构可以高效地解决以计算为主问题。 i n t e l 的w o r k q u e u i n g 模型i l 引，是向o p e n m p 中添加生成动态任务的一次尝试。这种模 型使用t a s k q 结构定义任务。嵌套t a s k q 结构可以表示具有层次结构的任务。t a s k q 结构的 结尾有一个隐式的栅栏结构，实现任务同步。 n a n o s 小组在u p c 上提出动态s e c t i o n s 作为o p e n m ps e c t i o n s 结构的拓展生成动念任 务【l3 | 。s e c t i o n 块可以直接嵌套，但是任务的层次同步只能用嵌套的并行区来完成。他f f 还 用p r e d 和s u c c 结构静态指定s e c t i o n s 顺序关系。 第3 页 国防科学技术大学研究生院硕十学位论文 i n t e lb u i l d i n gb l o k s ( t b b ) 1 4 1 是一个c + + 运行库，不需要编译器特别的支持和语言拓 展。用户可以用任务( 代表了一个任务类对象) 编程。运行库负责任务的调度和负载均衡。 建立在任务调度器上的t b b 的高级循环模板负责把工作分解为任务。t b b 还提供了并发 容器类。这些并发容器类要么通过细粒度锁，要么通过无锁算法，可以并发访问不同的并 发容器( 如哈希图和哈希队列) 。 微软1 1 5 1 丌发的t a s kp a r a l l e ll i b r a r y ( t p l ) 库提供p a r a l l e l f o r 方法，该方法支持并行 结构，如p a r a l l e lf o r 等。t p l 还支持其它的结构，如任务和f u t u r e 。两个或多个任务可以 并发执行。f u t u r e 是一种特殊的任务，它返回在后台线程执行的用f u t u r e 对象的结果，这 个结果会缓存到下次使用。 在借鉴了上面编程语言中动态任务单元的表示，来自i n t e l ，u p c ，i b m ，s u n ，c a s p ! j r 和p g i 公司的代表组成了结构委员会【1 6 】，在o p e n m p 3 0 规范中推出t a s k 机制。任务能 显式标识独立的工作单元，能表示不规则的并行和动态任务的生成。但是o p e n m p 3 0 规范 中没有说明任务是如何调度及在运行时中何时运行。 1 2 研究现状 o p e n m p 3 。0 规范【1 7 】在2 0 0 8 年5 月提出，随后主流编译器厂家相继宣称对o p e n m p 3 0 规范提供了不同程度的支持。由于规范中没有说明t a s k 是如何调度及运行时何时运行， 且t a s k 的调度策略对程序的性能影响很大，各编译器厂家和编译器研究机构给出了自己 的任务调度策略实现。本文对他们的任务调度策略的实现进行了研究。 1 2 1i n t e lt b b i n t e l 线程构建模块( t h r e a d i n gb u i l d i n gb l o c k ) i s 】为c + + 程序提供了完备并且丰富的 方法来表达并行语义。 1 、任务 在i n t e l 的t b b 中，每个任务实例都有自己相应的属性，如表1 1 t 1 8 1 所示： 表1 1 任务属性 属性 描述 o w l l e r 目前管理任务的工作线程 p a r e n t要么是n u l l ，要么是分配这个任务的父任务延续任务 d e p t h任务在任务树中深度 r e f c o u n t 将t h i s 作为父任务的子任务数量。r e f c o u n t 的递增操作和递减操作都必须 是原子操作 2 、任务调度简介 任务的含义是计算的逻辑单元。调度器将这些任务以非抢先式的映射方式到物理线 第4 页 围防科学技术人学研究生院硕十学1 _ ) = 论文 程。在执行时，每个线程郜有且仅有一个e x e c u t e ( ) 方法。当线程肝始执行e x e c u t e ( ) 后，直 到e x e c u t e ( ) 返回前，这个任务都被绑定在这个线程上。在任务被绑定的时间里，只有当任 务在某个子任务上等待时，线程才能够执行其它的任务，此时它将会执行同一任务中的其 它子任务，如果没有就绪子任务的话，也可以执行在其它线程中创建的任务。 图1 4 延续传递形式 划分汇合( s p l i t j o i n ) 模式往往会产生潜在的并行。目前在所支持的两种基本的划舯 合并模式中，最有效的就是延续传递( c o n t i n u a t i o np a s s i n g ) 模式。在此模式中程序员将 构造一个显式的“延续”任务，而不是通过默认的调度器来决定下一个任务。相应的步骤 如图1 4 【i8 】所示，在每个步骤中的运行任务( 也就是说，这些任务的e x e c u t e 方法是活跃的) 在图中用阴影部分表示。 在步骤a 中创建的是父任务。在步骤b 中，父任务创建了子任务，并且制定了一个当 子任务完成时需要执行的将继承父任务的延续任务( c o n t i n u a t i o n t a s k ) 。然后，为了不阻 塞它的予任务，父任务将退出。在步骤c 中，子任务开始运行。在步骤d 中，当子任务或 者这些子任务的延续任务完成之后，延续任务将开始运行。 图1 5 阻塞模式 因为它将任务的堆栈与任务分离开来，因此显式的延续传递是高效的。然而，这种方 第5 页 国防科学技术人学研究生院硕十学位论文 式伍编写的过程中比较困难。第二种模式是使用了隐式的延续传递方式的阻塞模式。虽然 它有时候会降低性能但相对于第一种模式更容易编程实现。在阻塞模式中，父任务将一直 被阻塞到它的子任务完成，如图1 5 所示。 这种编程上的方便性是需要付出一定的代价的。由于父任务被阻塞，相应的堆栈就不 能够被弹出。因为持续的窃取和阻塞这个线程必须注意它所承担的工作如何不会导致蚱：栈 无限制地增长。为了解决这个问题，需要在调度器中对阻塞线程做一定的限制，这样阻塞 线程就不会执行比最深的阻塞任务要浅的任务。但是这个约束可能会影响程序的性能，因 为它将使线程选择更小( 更深的) 子树，并限制了可用的并行。 3 、任务调度的工作原理 任务图是一张有向图，如图1 6 所示。它通过调度器来进行计算，图中的每个节点表 示一个任务，都指向各自的父节点，根节点的父节点为正在等待根节点完成的其它任务或 者为n u l l 。通过t a s k ：p a r e n t o 方法可以访问父指针。 图1 6 斐波那契任务图 如图1 6 所示，在每个任务中都存在个用来计算其深度的深度变量d e p t h ，子任务的 深度通常比其父任务的深度大l 。在每个任务中还有个统计变量r e f c o u n t ，它是用来统计 将这个任务作为父任务的子任务的数量。在这张图中，叶节点表示正在运行的任务或名将 要运行的任务。引用计数不为零的任务( a ，b 和f ) 将等待它们的子任务执行完成。 第6 页 国防科学技术人学研究生院硕十学位论文 为了实现调度器在运行任务时将内存需求和跨线程的通信量降至最低的目标，需要在 深度优先和宽带优先这两种方法的执行中达到个平衡。我们假设这棵树的规模是有限 的，那么在串行执行时最好使用深度优先算法，理由如下： 1 内存空间最小化 如果采用以宽度优先的形式来执行上层任务将展开位于这个任务之下的树，并且由于 所有任务在等待线程的时候都将占据内存空间，这将使系统中同时存在的节点数量成指数 增长。相对而言，虽然深度优先的执行形式也会创建相同数量的节点，但是因为它并没有 展丌其它准备运行的任务( 在图中是e ，c 和g ) ，所以在系统中同时存在的节点数量只 是一个线性值。 2 当缓存为“热( h o t ) ”时，可以获得很好的效果 最深的任务是那些最新创建的任务，因此它们在缓存中也就是最“热”的。同样，如 果它们能够完成，那么任务f 可以继续执行；虽然它不是缓存中最热的任务，但仍然要好 于在它上层的任务。 虽然宽度优先形式在内存使用上有着严重的问题，但这种形式能够将拥有非常多的数 量的物理线程的情况下使并行最大化。在大多数情况下，物理线程的数量通常是有限的， 因此最好是通过有限的宽度优先来使处理器保持忙碌的状态。在调度器中实现宽带优先形 式的方式如下： 幻每个线程都有一个线程池，每个线程池中包含一组就绪任务。 b ) 当一个任务就绪时，它被加入到每个线程池。 c ) 在自己的线程池中没有就绪任务时，每个线程都可以从其它线程池中窃取任务。 最浅 r i i i 7 7 u 最深 7 l “”。 图1 7 对应图1 6 中斐波那契任务图的线程就绪池 对应于图1 6 中斐波那契任务图的线程就绪池如图1 7 所示。在这个就绪池中包括一 个链表数组，其中的链表相当于数组中的元素，而这个数组的下标为任务的深度。任务首 先被压入到链表的左侧，然后从左侧弹出。在每个就绪池( r e a d yp 0 0 1 ) 中都有两个相互交 叉的行为，一个是从池中获取任务并执行它们，另一个是将任务放入到池中。 当线程参与到任务图的计算过程并且需要一个新任务来运行时，它将按照线性顺序根 掘以下规则中第一个能够使用的规则提取任务： 第7 页 国防科学技术大学研究生院硕士学位论文 a )前一个任务的e x e c u t e 方法中返回的任务。如果e x e c u t e 返凹n u l l ，参考b ) ； b ) 线程自己任务池中最深的链表前端上的任务。如果池中所有链表都是空的，参考c ) ； c ) 随机选择一个线程，从他的任务池中最浅的链表前端窃取任务。如果所选择的池没有 任务，那么将随机再次选择其它池，直到最终成功。 提取任务的过程只是计算任务图的一部分，它通常是自动的；放置任务的操作则既可 以是手动的也可以是自动的。 当需要将任务放置到一个就绪池中时，它通常被放置到当前线程的池中，还允许从另 一个池中进行窃取，但不允许主动将任务放置到另一个池中。将任务放入到就绪池中总共 有3 种方式： a 1 任务是显式生成的 b ) 任务逻辑上被释放，物理空间分配给一个新任务； c ) 当子任务完成时，任务的引用计数在隐式的递减运算后将变成0 。 调度器中使用了任务窃取。每个线程中已经为运行做好了准备的任务都被放置到它所 维持的一个就绪任务池中。就绪池的结构为一组任务链表，这些链表是按照后进先出瞥顺 序末操作的，其中第i 个元素对应于树中第i 层的任务。在第二层的任务将在第i + l 层上创 建子任务。如果有非空的链表，线程将从数组中最深的非空链表中取出任务；如果没有的 话，线程将随机从另一个线程的最浅的链表中窃取一个任务。如果线程完成了最后一个任 务的话还可以隐式地进行窃取，在这种情况下，它将开始执行在子任务上进行等待的任务。 从总体上看，任务调度器的基本策略就是通过将深度优先和宽度优先结合起来使用来 保持线程高效和忙碌的执行。宽度优先规则带来了可以使线程保持忙碌的状态足够多的并 行。而深度优先则使得每个线程在又足够多工作的情况下能够高效地执行。 1 2 2i b mx lc c + + 编译器 i b mx lc c + + 编译器【一j 支持o p e n m p3 0 规范。t a s k 和t a s k w a i t 使用户能够 对包含不规则的并行算法( 例如，指针索引或递归算法) 进行并行化，但是也存在一些不 足，如线程没有私有数据。 l 、任务池 在并行区内生成的所有任务都是与并行区域绑定的。每个并行区都有一个任务池，任 务池中的任务是处于就绪状念的，故任务池也称作就绪池。任务池使用队列实现。当创建 新任务时，任务从队列尾部添加，当提取任务时，任务从队列的头部取出。在任务调度的 限制下，任务的调度顺序是伪f i f o 顺序。就绪池中的任务数量是有最大限制的，一旦就 绪池中任务数量达到上限，线程会立即执行新创建的任务，而不会继续向就绪池中添加任 务。只有那些一直处于等待状态且没有被调度过的任务保留在就绪池中，而已经被调度过 的任务则保留在的执行线程的栈帧中。 第8 页 国防科学技术大学研究生院硕十学位论文 并行区还有一个保存空节点( 逻辑上已经释放，但是物理空间保留的任务节点) 的池 子，简称为空池。空池可以降低任务创建和销毁的开销。当线程准备创建一个新任务时， 如果有可用的空节点，那么线程就会从空池中取出一个空节点而不是新分配一个空间给任 务。当一个任务完成且没有活跃的子任务时，可以把自己加入到到空池中来释放自己，或 者由子任务释放。所以当一个任务完成时，其空间可能仍然存在。 图1 8 任务完成后任务仍然可能存在 如图1 8 所示，任务3 是任务4 和任务的父任务。任务3 不需要等待它的子任务4 和 子任务5 完成。如果任务3 和任务5 完成，任务3 的结构继续保存在内存中，因为子任务 4 还没有完成。当子任务4 完成时，它要负责释放其父任务3 的空间。 2 、任务 任务有两种，一种是隐式的，一种是显式的。在并行区的线程组中的每一个线程，都 会创建一个隐式任务。当线程遇到隐式任务时，立即执行。当线程遇到任务构造时，会创 建一个显式任务，只有显式的任务才能被放入就绪池中。父任务负责初始化子任务。任务 图1 9 任务构造 是放在任务池中管理的。在任务池中，任务通过n e x t 指针与下一个任务链接。为保存任务 的层次和任务i 日j 的依赖关系，每个任务构造都有一个计数器，记录其活跃的子任务数量。 当任务创建一个新任务时，它的计数器会加一，而当它完成时，父任务的计数器会减一。 当任务遇到t a s k w a i t 时，查看自己的计数器是否等于零，如果是，表明子任务已经完成， 不需等待；否则，等待。任务构造如图1 9 所示。 第9 页 国防科学技术大学研究生院硕十学位论文 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = , - - z , i21z = = = = = = = = = = = = = = 在卜列三种情况下创建的任务是串行任务： ( 1 ) 任务在串行区内创建； ( 2 ) 与并行区绑定的线程组只有一个线程； ( 3 ) 用户程序要求任务是串行任务。 串行任务都是创建后立即执行。 3 、任务调度 任务切换是指线程挂起当前正在执行的任务而去调度执行另一任务。线程可以在任务 切换点( t s p ) 进行任务切换。绑定任务的任务切换点有三个：创建任务，遇到t a s k w a i t 等待，或栅栏( 隐式或显式的) ；非绑定任务的任务切换点可以在代码的任何地方。臼务 调度有两点限制： ( 1 )当任务有i f 从句且其表达式的值为假，线程会挂起父任务，立即执行该任务。 父任务要一直等到该任务完成时才能恢复执行。 ( 2 ) 一个绑定的任务会被调度，要么是任务集合为空，要么是任务是每一个任务的 后代。 绑定的任务在i b m 运行时中是存储在线程的栈帧中。当任务切换点是栅栏时，任务调 度是一个完全的f i f o 调度。 非绑定的任务在i b m 运行时中被实现为绑定的任务。在递归生成任务机制中，当生成 的任务是叶子节点时，所有的任务都绑定到一个线程，使线程负载不均衡。 1 2 3n a n o s 小组 n a n o s 小纠2 0 2 1 】在标准块结构( s t a n d a r ds e c t i o n sc o n s t r u c o 基础上拓展并提出动态块 ( d y n a m i cs e c t i o n s ) ，允许动态任务生成。巴塞罗那超算中心的a l e j a n d r od u r a n 等在n a n o s r u n t i m e 上拓展实现两种调度：宽度优先和工作优先2 2 , 2 3 】，还实现了两种剪枝策略。 ( 1 ) 宽度优先调度 在宽度优先调度中，新创建的任务放入到线程组的任务池中，父任务继续执行。初始 时，任务放入线程组内的任务池中，线程组内的任何线程都可以从任务池中获取任务。当 任务被挂起( 例如遇到了t a s k w a i t ) 时，如果是绑定任务，则将任务放入线程的私有池中， 否则，放入到线程组的任务池。线程总是先从私有池中调度任务，如果没有就绪的任务， 则从线程组的任务池中调度任务。任务池的访问策略可以是l i f o 或f i f o 。程序员可以根 据程序特征，通过环境变量或者参数，动态设簧访问策略，提高数据局部性，降低任务同 步丌销。例如，对于递归程序，访问策略应该是l i f o ，对于