（计算机系统结构专业论文）多核多线程处理器上任务调度技术研究.pdf

摘要 论文着重于多核多线程处理器上的任务调度相关的研究。首先是从理论角度提出了 3 种与基于复制的任务调度相关的算法，这3 种算法都表现出了较好性能。然后结合一 种实际的多核多线程处理器( 网络处理器i x p ) 展开了对任务调度实例化研究，并且运 用地址转换和迭代编译等技术构建了新型统一网络编程环境，又结合实际网络应用提出 了吞吐量与延迟相结合的网络任务调度算法。本文主要贡献如下： 提出了满足通信限制的基于复制的优化f o r k - j o i n 调度算法t d c _ f j ，t d cf j 利 用基于复制的f o r k - j o i n 最优化调度结果来对f o r k - j o i n 任务图进行调度，并且在 调度过程中加入处理器之间的通信限制，也就是一条通信信道不能同时被两个 通信事件占用。 r o e _ f j 算法在调度时力求减少需要的处理器数目，尽量调度任 务到已占用处理器上，在保证性能的同时减少处理器的消耗量。 给出针对普通任务图带通信限制的基于复制调度算法t d m s c l 。该算法把普通 任务图转换为i o i n 与f o r k 等基本形状，然后运用对j o i n 图与f o r k 图的优化调度 研究结果对这些基本形状进行任务调度。相对于传统任务调度中找关键路径或 者计算权值逐步调度的方式，t d m s c l 算法把调度过程转变为按照拓扑序列逐 步求优的过程。算法力求保证每个节点的最早开始时间，通过这种调度方式获 得整个任务的优化调度结果。合并过程采用贪婪策略力求在较小时间开销内提 高合并的耦合度，并且考虑了通信信道的独占性制止了同一通信信道的通信重 叠。最后与其他几种常见的任务调度算法进行了对比测试，结果显示，) m s c l 在算法时间复杂度处理器消耗与调度长度上有性能优势。 提出了一种新的冗余任务消除算法r t e 解决了基于复制的任务调度生成的冗余 任务问题。大多数基于复制的算法调度后的任务存在部分冗余。这种冗余的任 务会导致处理器计算资源的浪费。r t e 可以作为一种辅助手段用于提高已有基 于复制的任务调度算法的效能，具有很好的通用性。任何一种基于复制的调度 算法都可以和它结合使用。测试表明该算法可以使已有的基于复制的调度算法 都不同程度的获得效能提升。 针对异构多核处理器i x p 构建编译器s h a n g d - l a 的统一编译后端框架。采用地址 转换方法来解决异构内核使用不同寻址方式的指针共享问题。提出了收敛的迭 代编译框架来控制最终代码生成大小。这些技术的运用使s h a n g r i 1 a 很好整合了 两种不同处理器核的编译工作。这种统一的编译平台掩盖了复杂的网络处理器 结构特征，使得网络程序编写和传统模式的程序编写一样简单方便。 提出针对网络应用特性的任务调度算法l i t s 。网络程序不同于普通程序，网络 应用具有较高的并行性，但是网络应用中的并行性是数据并行性。而且网络程 多核多线程处理器上任务调度技术研究，摘要 序评价性能指标的延迟时间与吞吐量也和普通任务调度追求的调度长度不同。 本文按照网络应用以及p 处理器架构特点建立代价模型，并且以网络应用需 求为导向提出了网络任务调度算法u _ r s 。该算法兼顾网络程序的吞吐量与延迟 需求自动完成网络任务的调度工作，并且在这两项评价网络程序性能的重要指 标上得到了满意的结果。 关键词： 编译器，多核多线程处理器，任务调度，网络处理器 a b s t r a c t w hj i a j u n ( c o m p u t e r a r c h i t e c t u r e l t l l i sp a p e rf o c u s e so nt a s ks c h e d u l i n gf o rm u l t i - c o r ea n dm u l t i t h r e a dp r o c e s s o r m c e d u p l i c a t i o nb a s e dt a s ks c h e d u l i n ga l g o r i t h m sa r ep r e s e n t e d t h e s ea l g o r i t h m sh a v eg o o d p e r f o r m a n c e ，a n di t sa p p l i c a t i o no nar e a lm u l t i - c o r ea n dm u l t i - t h r e a dp r o c e s s o r ( n e t w o r k p r o c e s s o rt x e ) a r ed e m o n s t r a t e d i ta l s os h o wt h a th o wau n i f o r mn e t w o r kp r o g r a m m i n g e n v i r o n m e n tc o u l db eb u i l tt h r o u g ha d d r e s st r a n s l a t i o na n di t e r a f i v ec o m p i l a t i o nt e c h n i q u e s f i n a l l yi td e s c r i b e san e wn e t w o r kt a s ks c h e d u l i n ga l g o r i t h n aw h i c hc o n s i d e r sb o mt h r o u g h p u t a n dl a t e n c y 耽ec o n t r i b u t i o n so f t h i sp a p e ra r ea sb e l o w ： p r o p o s e dan e wd u p l i c a t i o nb a s e dt a s ks c h e d u l i n ga l g o r i t h mf o rf o r k - j o i ng r a p h c o n s i d e r i n gt h ec o m m u n i c a t i o nl i m i t sb e t w e e nd i f f e r e n tp r o c e s s o r s ，n a m e dt d c _ r j n et e s tr e s u l t ss h o wt h a tt d c _ f ji sf l e x m l ea n de f f e c t i v ef o rf o r k - j o i ng r a p ha n di t a c h i e v e sg o o dp e r f o r m a n c ea n dr e d u c e st h er e q u i r e m e n t so f p r o c e s s o r s p r o p o s e dad u p l i c a t i o nb a s e dt a s ks c h e d u l i n ga l g o r i t h mw i t hc o m m u n i c a t i o nl i m i t sf o r g e n e r a lt a s kg r a p h , t d m s c l i tc o n v e r t st h eo r d i n a r yt a s kg r a p hi n t of o r ka n dj o i n g r a p h , t h e na p p l yt h eo p t i m i z e dr e s u l to ff o r ka n dj o i ng r a p ht ot h es c h e d u l i n go f g e n e r a lt a s kg r a p h t d m s c lc o n v e r t st a s ks c h e d u l i n gp r o c e s si n t ot h ep r o c e s so f o p t i m i z i n gat o p o l o g i c a ls e q u e n c e n ea l g o r i t h mt r i e st os c h e d u l ee a c ht a s kn o d ea ti t s e a r l i e s ts t a r tt i m et oo b t a i ng o o dp e r f o r m a n c eo ft h ew h o l et a s k 1 h em e r g i n gi sb a s e d o ng r e e d yp o l i c yt oo b t a i nd e e pc o u p l i n gw i t hl o wt i m ec o m p l e x i t y n i ea l g o r i t h m c o n s i d e r st h eo c c u p a t i o no fc o m m u n i c a t i o nc h a n n e l c o m p a r et oo t h e rt a s ks c h e d u l i n g a l g o r i t h m s ，t d m s lh a sb e t t e rp e r f o r m a n c e , w h i c hh a sl e s sp r o c e s s o ! c o n s u m p t i o n a n dl o w e rt i m ec o m p l e x i t y p r o p o s e da na l g o r i t h mn a m e dr = i et oe l i m i n a t er e d u n d a n tt a s k s w h i c hr e s o l v e st h e r e d u n d a n tt a s kp r o b l e mo ft a s ks c h e d u l i n gb a s eo nd u p l i c a t i o n 1 1 l er e d u n d a n tt a s k s w a s t ec o m p u t i n gr e s o u r c e s r t ec a na c ta sa na s s i s t a n tm e t h o dt oi m p r o v et h e p e r f o r m a n c eo fd u p l i c a t i o nb a s e dt a s ks c h e d u l i n ga l g o r i t h m a n yd u p l i c a t i o nb a s e d t a s ks c h e d u l i n ga l g o r i t h mc a ni n t e g r a t ei te a s i l y n et e s tr e s u l t ss h o wi tc a ni n c r e a s e t h ep e r f o r m a n c eo fe x i s t i n gd u p l i c a t i o nb a s e dt a s ks c h e d u l i n ga l g o r i t h mi nd i f f e r e n t d e g r e e b u i l tau n i f o r mc o m p i l e rb a c k - e n db a s e do nw h i r l 2 cf o rn e t w o r kp r o g r a m m i n g e n v i r o n m e n ts h a n g d - l a b ya d d r e s st r a n s l a t i o ni tr e s o l v e dt h ep r o b l e mo fp o i n t e r s h a r i n gp r o b l e ma r o s eb yt h ed i f f e r e n c eo fm e m o r ya c c e s sm e t h o d s b yai t e r a t i v e c o m p i l a t i o nf r a m e w o r ki tm a d et h ec o d es i z eu n d e rc o n t r 0 1 b yt h e s et e c h n i q u e s s h a n g r i - l ai n t e g r a t e dt w oc o m p i l e r sf o rt w od i f f e r e n tk i n d so fp r o c e s s o r sa n dh i d et h e c o m p l i c a t e dn e t w o r kp r o c e s s o ra r c h i t e c t u r et on e t w o r kp r o g r a m m e r s 佻u n i f o r m p r o g r a m m i n g e n v i r o n m e n t s i m p l i f i e s t h ew o r ko f p r o g r a m m i n gn o w a d a y s c o m p l i c a t e dn e t w o r kp r o c e s s o r s 。p r o p o s e dat a s ks c h e d u l i n ga l g o r i t h ml 1 t sf o rn e t w o r ka p p l i c a t i o n n e t w o r k a p p l i c a t i o ni sd i f f e r e n tf r o mn o r m a lp a r a l l e lp r o g r a m ，w h i c hm o s t l yi sd a t ap a r a l l e l a n dn e t w o r ka p p l i c a t i o n s p e r f o r m a n c e sa r em e a s u r e db yt h r o u g h p u ta n dl a t e n c y w h i l et h en o r m a lo n e sm e a s u r e db ys c h e d u l i n gl e n g t h t h i sp a p e rp r e s e n t sac o s t m o d e lb a s e do nn e t w o r ka p p l i c a t i o na n dd a r c h i t e c t u r e , a n dd e s i g n e dan e t w o r kt a s k s c h e d u l i n ga l g o r i t h m l t i sf o rn e t w o r ka p p l i c a t i o n t h i s a l g o r i t h mc o n s i d e r s i 多核多线程处理器上任务调度技术研究ta b s t r a c t t h r o u g h p u ta n dl a t e n c ya n dc o m p l e t en e t w o r kt a s ks c h e d u l i n ga u t o m a t i c a l l y , w h i c h h a sg o o dp e r f o r m a n c eo nb o t ht h r o u g h p u ta n d l a t e n c y k e y w o r d s ：c o m p i l e r , m u l t i - c o r e m u l t i - t h r e a d p r o c e s s o r , t a s ks c h e d u l i n g , n e t w o r k p r o c e s s o r i v 图 图 图 图图图图图 图 图 图 图 图 图 图 图 图 图 图图 图 图 图 多核多线程处理器上任务调度技术研究t图目录 图5 1 1 不同任务规模的处理器消耗量 图5 1 2 不同c c r 的调度性能 图5 1 3 不同c c r 对处理器的消耗 图5 1 4 不同分支数的调度性能 图5 1 5 不同分支数的处理器消耗量 4 9 图5 1 6p y 算法调度结果。 图5 1 7l w b 算法调度结果 图5 1 8 不同规模任务的冗余计算开销减少量 图5 1 9 不同任务规模去除处理器百分比 图5 2 0 不同c c r 下的冗余计算量消除 5 0 5 1 。5 3 图5 2 1 不同c c r 的冗余处理器消除 图6 1i x p 2 4 0 0 处理器结构图 图6 2 网络程序数据并行性 图6 - 3s h a n g r i l a 架构图。 图6 - 4x s c a l ec g 构成。 。5 9 。5 9 图6 - 5w h i r l 2 c 基本框架 图6 - 6w n 2 c 基本结构 图6 7s t 2 c 结构示意 图6 - 8 t y 2 c 基本结构 图6 - 9 迭代编译框架 图6 1 0 反馈文件格式 图6 - 1 1 复合驱动模型示例 7 2 7 6 图6 - 1 2 网络测试环境 图6 1 31 3 _ s w i t h 程序结构图。 图6 1 4m p l s 程序结构图。 x 图6 1 5 图6 - 1 6 图6 1 7 图6 - 1 8 x i 表9 分组数据吞吐量测试结果 表表表表表表表表 声明 我声明本论文是我本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致 翕 的地方外，本论文中不包含 其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：哭锫袋 日期：御，形 论文版权使用授权书 本人授权中国科学院计算技术研究所可以保留并向国家有关部门或机 构送交本论文的复印件和电子文档，允许本论文被查阅和借阅，可以将本 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编本论文。 ( 保密论文在解密后适用本授权书。) 作者签名：徽导师签名：7 及此及日期：己力，歹，肜 第1 章引言 1 1 多核多线程处理器结构 多年来微处理器性能的提升大都基于提高单个处理器主频或者指令级并行度进 行的。但是随着单个处理器的发展，处理器结构越来越复杂，单处理器主频的提升 也变得举步维艰。但集成电路制造技术的快速发展使得芯片上的晶体管集成度不断 提高，为了有效的利用这些晶体管，各种复杂的技术被加入到处理器中，这些技术 大都着眼于提高单个处理的指令级并行执行能力。比如超标量技术就是让处理器在 同一时钟周期中发射多条指令，来提高并行执行能力。例如m i p sr 1 0 0 0 0 1 ， p o w e r p c i 2 ，s u nu l t r a s p a r c 3 等。但是这种技术依然没有摆脱传统处理器上应用程 序的串行模式。处理器要使用各种复杂技术来从串行程序中找出可以并行执行的指 令，比如乱序执行、猜测执行和硬件分支预测等。这种技术已经很难进一步地提高 单处理器的并行能力，晶体管数目的进一步增加也只能得到有限的性能提升。转而 一些新的低复杂度高并行度的技术被提出，其中多核技术以及多线程技术是提高单 处理器性能运用最为广泛的两种技术。借助多核多线程技术提升处理器性能成为如 今处理器发展的主流。最近著名的处理器公司i n t e l 就对它的产品路线图进行了大幅 修改，放弃了4 g h zp e n t i u m4 开发计划，转而推出多核处理器。多核多线程技术将 成倍地提高计算机的运算能力，它是对以往业界单纯以时钟频率衡量芯片性能做法 的重要变革，对整个r r 工业都具有重要意义：利用多核多线程技术，就有可能继续 使计算机业朝着速度更快、价格更便宜、耗能更小的方向前进。 多线程技术主要是为了提高处理器功能部件的利用率，减少执行长时钟周期指 令对处理器效率的影响，例如减少c a c h e 不命中和执行时间长的指令对处理器效率 的影响。在多线程处理器中当处理器执行到长延迟指令的时候处理器就进行线程切 换通过调用线程来保证处理器部件的持续运行。多线程处理器通常为每个线程维护 独立的处理器状态，包括寄存器与程序计数器p c 页表等，一般而言多线程处理器 中各个线程拥有自己独立的取指、发射部件。 多线程处理器按照线程划分的颗粒度大小又分为细粒度多线程( f i n e - g r a i n e d m u l f i t h r e a d i n g ) 和粗粒度多线程( c o a r s e - g r a i n e dm u l t i t h r e a d i n g ) 处理器。细粒度多线 程处理器一般采用r o u n d r o b i n 算法每个时钟周期发射不同线程的指令，碰到正在阻 塞( s t a ) 的线程就跳过。在细粒度多线程处理器中往往对于线程切换的开销要求非常 的高。细粒度多线程每个时钟周期只执行该线程的单条指令，所以如果处理器有较 长延迟指令就需要进行大量的线程切换，以期获得足够多的指令以掩藏该延迟。粗 粒度多线程处理器( 也称为b l o c k e dm u l t i t h r e a d i n g 【5 】) 是在遇到长延迟操作时才进行 中目科学院博士学位论文一多核多线程处理器上任务调度技术研究 线程切换，否则一直执行当日口线程的指令。粗粒度多线程处理器并不需要进行频繁 的线程切换，因此对线程切换的开销要求也没有细粒度多线程处理器那么高。也不 需要太多的线程数目。但是粗粒度多线程处理器在进行线程切换的时候需要排空流 水线然后再进行流水线填充。所以相对细粒度多线程粗粒度的线程切换开销较大。 多线程技术现在运用得非常广泛，超线程技术就是其中的一种。图1 1 给出了 s u p e r t h r e a d i n g 处理器【4 】的结构示意图。 1h r t “lp r “t ”i n gt h r e a dp r o a - n g t h i n a dp r o c e i n g 1 1 1 r e a dp m c m g u l l i t l e c l i t i o n x e c t l t a l l l e x 斟i l t l c l r lf e c 埘i n l l l0 + j l 毒 耄 ：0 。：| 嚣 l b m m u c o m m l 黑鼍l ：n i t 糟 掣 i l 一 掣”f 掣9 牺 。霸悃 1 一恻 “ b u 疵il i _ j il w a e - t 量a c k w r l t e - 啪c k w r l t e - b a c e愧一t 舢8 n c = 8 u f l e e h u l t e r h n 讯r8 u 凰f 1 r i d a t ac a t h e 图1 - 1s u p e r t h r e a d i n g 结构示熏图 多核处理器又叫单片多处理器( c m bc h i pm u l t i - p r o c e s s o r ) 6 也就是在同一个芯 片上集成多个处理器内核。多核处理器相对于传统超标量和超长指令字( 删) 的指令级并行具有更高的并行度，在多核处理器上可以达到线程级并行，也就是同 一时刻处理器上有多个线程在并行执行。与超标量和超长指令字处理器相比多核处 理器主要有两个优点： 1 1 由于不需要依赖复杂的功能部件，所以多核处理器的逻辑结构比较简单，易 于实现以及验证。晶体管的利用率高，同等规模的集成电路，多核处理器可以得到 更大的并行度。 多核处理可以达到较高的主频。由于多核处理的逻辑结构简单，所以在同等 2 第一章引言 集成电路工艺水平下多核处理器可以达到较高主频。 多核处理器又可以按照芯片上内核的组织结构分为异构多核处理器与同构多核 处理器两种。 异构多核处理器就是在同一芯片上集成两种以上的处理器核，像m m 和s o n y 最新推出的c e l l t t i 芯f i - 就属于异构多核处理器。这种方式的处理器通常由一个或 多个通用处理器内核与多个针对某些特定应用的高性能处理器构成。与同构多核处 理器相比它的针对性更强，可以用较小的晶体管开销在某些特定应用上得到高性能， 缺点就是通用性较差。图1 2 展示了异构多核处理器c e l l 的结构。c e l l 包含一个 p o w e r 处理器( p p e ，p o w e rp r o c e s s o re l e m e n t ) 和八个协处理单元( s p e ，s y n e r g i s t i c p r o c e s s o r ) 。 o m1 2 s p es e ps e ps e p i 卜 c lr c d w 0 0 a ) y x d r 口 翟 p p eme m 盟 兰 b o s e ps e ps e ps e p l 图1 - 2c e l l 处理器结构 同构多核处理器就是在一个芯片上以对等方式集成多个相同处理器核。可以把 同构多核处理器看作是传统s m p ( s y m m e t r i cs h a r e d m e m o r ym u l t i p r o c e s s o r ) 机器的 单芯片实现，它们的逻辑组成结构并没有太大的差异。但是由于同构多核处理器上 的核之间的通信是通过片内总线实现，所以与s m p 机器相比它大大降低了处理器 问通信开销。并且利用c a c h e 共享等方式可以进一步的提高处理器间通信速度。与 异构多核处理器相比实现同样并行度的同构多核处理器所需的晶体管开销更大，但 它的通用性更强。现在最新的高性能通用处理器大都采用同构多核处理器的组织方 式，比如像a m d 的a 6 4 x 2m m 的p o w e rp c 等都是这种结构。图1 3 图展示了 p o w e r 5 的结构。 3 中国科学院博士学位论文一多核多线程处理器上任务调度技术研究 f p u f p u委委f p un u 匕c t d u l s ul s ud u i f u i f u 一- l 2l 2l 2m c i - 3d k e c t o r y c o n t r o l 图1 - 3p o w e r 5 结构示意图 多核多线程处理器( m u l t i c o r em u l t i - t h r e a dp r o c e s s o r ) ，它是多核处理器与多线程 处理器的结合体。这种处理器结合了多核处理器与多线程处理器的优点。具有多核 处理器结构简单高并行性的特点，又可以利用多线程技术来消除内核之间的通信延 迟以及过长的指令执行延迟。多核多线程技术是未来处理器发展的方向，像i n t e l 最新的处理器就使用多核多线程技术。 1 2 任务调度问题的提出 多核多线程处理器的发展对传统的编译技术提出了挑战。目前大多数应用程序 都是基于串行模式编写的，如果直接运行于多核处理器，不能发挥多核处理器的高 并行处理能力。为了适应多核多线程处理器，传统的并行编译技术被引入。在并行 编译中为了充分利用多处理器资源来运行并行程序需要面临许多问题：程序划分问 题，也就是将原先完整的程序划分成多个可以并行执行的任务；任务调度问题，既 将通过程序划分后的子任务调度分配到合适的核上执行使得程序的整体执行时间最 短；还有就是任务之间的通信同步，及保持不同内核上的数据一致性问题。 程序划分可以按照划分的方式分为手工划分，人机交互划分以及自动划分。计 算机自动划分通常都是在编译阶段进行的，通过编译器分析程序的数据依赖以及程 序结构然后进行程序切分。通常手工划分可以获得较好的性能，但对程序员的要求 较高。程序员必须进行大量低级繁琐的划分工作，易出错且不利于大型程序的并行 化。自动划分可以把程序员从烦琐的划分工作中解放出来，易于实现大型程序的并 4 第一章引言 行化。但目前自动划分的局限性较大，性能还有待改进。人机交互划分结合了手工 划分和自动划分的优点，非关键部分由计算机自动完成，程序员可以对关键部分加 特殊制导优化机器划分的结果。从长远来看自动划分是程序划分的发展方向。 任务调度的好坏直接影响系统的性能【1 l 】，如果调度不当，则很可能将并行的 优点完全给抹煞掉，甚至比串行的效果还差。从调度的时机来看，可以分为静态和 动态的。静态调度指的是完全由编译器在编译时决定，程序行为( 包括各个任务运 行时间、通信、数据依赖以及同步等) 必须是编译时就己知的，通常将任务或线程 之间的关系用d a g 图表示，其中节点表示任务或线程，节点权重表示任务运行时 间，边则代表通信，边权重代表通信量 1 2 1 ；动态调度则指由调度程序根据运行时 情况动态的分配不同的任务到各个处理器上，以求尽量降低总运行时间，同时减少 调度程序本身带来的开销【1 3 】【1 4 】。 在我们研究的对象中，由于各个任务是一开始就加载而且不会终止，所以就不 存在动态调度的问题，故本文只关注静态调度问题。 1 3 论文研究贡献 论文着重于多核多线程处理器上的任务调度相关的研究。首先是从理论角度提 出了3 种与基于复制任务调度相关的算法，这3 种算法都表现出了较好的性能结果。 然后结合实际的多核多线程处理器也就是网络处理器i x p 展开了对任务调度实例化 研究，并且运用地址转换迭代编译等技术构建了新型统一网络编程环境。又结合实 际网络应用提出了吞吐量与延迟相结合的网络任务调度算法。具体贡献如下： 提出了t d cf j 算法, t d c _ f j 利用基于复制的f o r k - j o i n 最优化调度结果来 对f o r k - j o i n 任务图进行调度，并且在调度过程中加入处理器之间的通信限 制，也就是一条通信信道不能同时被两个通信事件占用。t d c _ f j 算法在调 度时力求减少需要的处理器数目，尽量调度任务到已占用处理器上，在保 证性能的同时减少处理器的消耗量。 给出针对普通任务图带通信限制的基于复制调度算法t d m s c l 。该算法把 普通任务图转换为j o i n 与f o r k 等基本形状，然后运用对j o i n 图与f o r k 图的 优化调度研究结果对这些基本形状进行任务调度。相对于传统任务调度中 找关键路径或者计算权值逐步调度的方式，t d m s c l 算法把调度过程转变 为按照拓扑序列逐步求优的过程。算法力求保证每个节点的最早开始时间， 通过这种调度方式获得整个任务的优化调度结果。合并过程采用贪婪策略 力求在较小时间开销内提高合并的耦合度，并且考虑了通信信道的独占性 制止了同一通信信道的通信重叠。最后与其他几种常见的任务调度算法进 行了对比测试，结果显示t d m s c l 在算法时间复杂度处理器消耗与调度长 度上有性能优势。 5 中国科学院博士学位论文多核多线程处理器上任务调度技术研究 在基于复制的任务调度算法中，为了减少节点之间的通信开销往往会复制 部分任务。大多数基于复制的算法调度后的任务存在部分冗余。这种冗余 的任务会导致处理器计算资源的浪费。本文提出了一种新的冗余任务消除 算法r t e 解决了基于复制的任务调度生成的冗余任务问题。这种算法可以 作为一种辅助手段用于提高已有基于复制的任务调度算法的效能，具有很 好的通用性。任何一种基于复制的调度算法都可以和它结合使用。测试表 明该算法可以使已有的基于复制的调度算法都不同程度的获得效能提升。 针对异构多核处理器i x p 构建编译器s h a n g r i - l a 的统一编译后端框架。采用 地址转换方法来解决异构内核使用不同寻址方式的指针共享问题。提出了 收敛的迭代编译框架来控制最终代码生成大小。这些技术的运用使 s h a n g r i - l a 很好整合了两种不同处理器核的编译工作。这种统一的编译平台 掩盖了复杂的网络处理器结构特征，使得网络程序编写和传统模式的程序 编写一样简单方便。 提出针对网络应用特性的任务调度算法l t t s 。网络程序不同于普通程序， 网络应用具有较高的并行性，但是网络应用中的并行性是数据并行性。而 且网络程序评价性能指标的延迟时问与吞吐量也和普通任务调度追求的调 度长度不同。本文按照网络应用以及i x p 处理器架构特点建立代价模型， 并且以网络应用需求为导向提出了网络任务调度算法l t r s 。该算法兼顾网 络程序的吞吐量与延迟需求自动完成网络任务的调度工作，并且在这两项 评价网络程序性能的重要指标上得到了较好的结果。 1 4 论文组织结构 本文是关于多核处理器上的静态任务调度的研究，文章共分为七个章节，具体 结构如下： 第一章介绍多核处理器上的任务调度技术的起源以及背景，给出了论文的个 简要预览。 第二章描述任务调度技术的研究现状，主要介绍了任务调度技术的基本背景知 识。其中包含任务调度模型介绍，任务调度问题本身复杂性研究情况，任务调度的 分类和各种分类下任务调度的算法现状。 第三章给出论文中对任务调度算法的性能测试方案。分为测试环境和性能评价 标准两部分。 第四章介绍基于复制的调度算法研究现状。详细描述了c p f d , t s a _ f j t d s 这 三种算法。并且介绍了其他基于复制调度算法的研究现状。 第五章介绍本文提出的3 种与基于复制相关的任务调度的算法，首先是对 f o r k - j o i n 图的调度算法t d cf j 。然后是对通用图形的t d m s c l 调度算法。最后是 6 7 第2 章任务调度研究现状 在并行计算中任务调度问题是一个古老持久的话题。任务调度的主要目的是合理调 度任务到各个处理器上以使得最后程序执行时间最短。任务调度算法的好坏直接影响程 序的最终执行效果，所以任务调度算法以及相关的研究工作在并行计算领域显得尤为重 要。并行程序的任务调度分为两种类型，一种是独立的没有依赖关系的任务的调度，另 外一种是任务之间有通信和依赖关系的，这时一般要牵涉到任务或线程划分，即将原先 完整的程序划分成多个可以并行执行的任务。 对于有依赖关系的任务调度又可以按照调度的时机分为静态任务调度( s t a t i c s c h e d u l i n g ) 与动态任务调度： 静态任务调度大都是在编译时就通过静态估计或者p r o f i l i n g 技术得到程序的计 算量、通信开销、以及任务之间的依赖等信息，各个处理单元之间连接和处理 能力都是已经知道的，然后编译器通过这些信息分配任务到各个处理器上。并 且一旦任务分配到处理单元就只能在该处理单元上执行。 动态的任务调度是在执行程序时候调度器实时监控获取程序执行情况，然后按 照动态的运行情况来分配任务到处理器单元上。典型的情况就是操作系统中的 任务调度就是通过动态调度来实现处理器负载均衡，实时把任务从负载较重的 处理器转移到轻负载的处理器。但是动态调度的开销较大，还涉及动态任务迁 移时数据一致性和通信同步等问题。 本文不对动态调度作进一步的讨论。在未声明的情况下本文讨论的都是静态的任务 调度。具体的分类如图2 - 1 所示： 图2 - 1 调度分类 9 中国 学院博士学位论文一多核多线程处理器上任务调度技术研究 在静态任务调度中又可以按照调度方法进行分类。目前有四种比较常见的类型： 有向无环图( d a gd i r e c t e da c y c l i cg r a p h ) ：通过有向无环图来表示程序结构，节点 表示任务，边表示任务之间的依赖以及通信关系。处理器系统也被抽象为处理机 模型，通常使用无向图来表示，节点即为处理节点，边表示处理节点之间的拓扑 结构和通信通道。 分级任务图h t g ，h i e r a r c h i c a lt a s kg r a p h ) ：一个分级任务图( 【3 3 】可以有复合节 点，复合节点由另外的一个分级任务图构成。h t g 是在另外一个叫做”自动调度 ”技术里面被提出来的。它需要编译器显式的插入驱动代码。 t a s ki n t e r a c t i o ng r a p h ：节点表示并行任务，边表示任务间通信。通常用在静态调 度松散的通信处理方式( 任务都是同时独立执行，相互之间没有时间上的先后关 系) 。该领域工作最早是b o h k a r i 和s t o n e 开创的【4 9 】【5 0 】 p e t r i 网：p e t r i 网作为经典的数学模型被用于展示并行系统【3 4 】。对于控制数据流 图，它对高层任务并行信息提供了有力的支持。它被广泛的用在硬件上，并且也 被用来建模解决对多处理器的任务分配问题。但是它过于复杂，所以很少真正用 来解决多处理器的调度问题。 正规计算模型：m e s c a l 项目提出了一个规则去设计和实施片上网络系统，它 用计算的方法刻画了并行通讯形式 3 5 1 。这个关键点是分割计算模型的功能为通 信端口( 它是由一个库函数的集合所构成) 与控制端口( 由控制器表示) 。这些 组件用虚拟方式描述，大多时候足以容纳常用应用程序的特征。它们提供了一个 图形化的开发环境帮助设计者通过虚拟组件描述n o c ( n e t w o r k - o n - c h i p ) 的应用 模式，然后代码生成可由前面预定义的通信组件和用户定义的软件对象或设备驱 动协同完成。它们仅展示了一个简单路由应用程序的设计，而任务分割和映射是 用手动方式进行的，它并没有清楚展示他们的实际工作怎么进行的。 2 1 任务调度系统 调度系统主要是由任务模型，系统模型，以及调度算法三大部分构成。任务模型用 形式化的方法来表示等待调度的任务，模型上附载了进行调度所需要的所有相关信息。 系统模型表示处理器拓扑结构和处理能力等信息。调度算法接受任务模型和系统模型然 后给调度结果，也就是任务映射图。 1 0 第二章任务调度研究现状 图2 - 2 任务调度系统结构 2 1 。1 任务图的d a g 模型 在任务调度中任务通常可以用图论里面的有向无环图d a g 来表示。如图2 - 3 所示 有向无环图g 可以表示为一个二元组，g = f v , e ) 这里v = v l ，v 2 ，, v i ) 表示图中顶点v 的集合，节点v 在任务图中用来代表单 个任务。v i 表示第i 个任务，i v i 表示任务的个数。 e = e l ，e 2 ，c i , ) 表示图中有向边e 的集合，e 在任务图中表示任务之间的通信 和依赖关系。e i 表示第i 条边，吲表示边的个数。 v i 的权重表示任务i 的计算开销，可以用w ( v j 来表示。图中任务i 和j 之间的 边也可以使用v j ) 表示，( v 棚) 的权重电v j ) 表示i 和j 顶点之间的通信开销，也表 示任务到人物的依赖关系。如果存在( v i ，v j ) 那么就可以说v i 是v j 的父节点，v j 是v i 的子节点。 v i 的前驱节点集合定义为e r e d ( v i ) = l “ v i ) o ) v i 的后继节点集合定义为s u c c ( v i ) = v j i ( v b v 】) o ) s t ( i , p ) 表示任务i 在处理器p 上的开始执行时间 嘶，p ) 表示任务i 在p 处理器上的完成时间 c s t ( l p ) 表示任务i 如果调度到p 处理器最早可能开始执行的时间 l f t ( i , p ) 表示任务i 如果调度到p 处理器最晚可能开始的时间 本文假定所有任务节点都按照拓扑序列排列，也就是如果研那么v i 一定不是v j 的前驱节点。如果p r e d ) - 妒那么v i 是入口节点，入口节点集合 e n t r y 一“i p a r e n t ( ) - 升如果c 姒( b ) - 妒那么v i 就是出口节点，出口节点的集 合e x t - “i c h i m “) l 升 l l 中周科学院博士学位论文多核多线程处理器上任务调度技术研究 为了反映d a g 图侧重点是计算还是通信开销，引入通信计算比 ( c c r 舢u 1 1 i c a t i o n - t 蝴p u t a t i o n - r a t i o ) 来量化任务的通信与计算基本特性。 l - 纠 w ) c c r 一司万焉丁 c “，v j ) 白厶、” 。j 。 如果节点、，i 和q 之间不存在一条可以连通的路径，那么我们就说v i 与v i 是相 互独立的。两个相互独立的节点可以被分配到不同处理单元上并行执行。一个任务 图的最大并行度就