（计算机科学与技术专业论文）异构多核系统中面向细粒度任务集的调度算法研究.pdf

l l i | i l ll p ir li il liil il tiil y 19 0 6 2 7 0 t h er e s e a r c ho fs c h e d u l i n ga l g o r i t h mf o rf i n eg r a n u l a r i t yt a s ks e ti n h e t e r o g e n e o u ss y s t e m b y l ix u e h u i b e ( z a o z h u a n gu n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g c o m p u t e rs c i e n c ea n dt e c h n o l o g y i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rz h a 0h u a n m a y ，2 0 1 1 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：专髻卿 日期：矽，年，月多7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名： 导师签名： 毒专嬲 吨 妙 e l 期：即j 年岁月工7e l e l 期：刃t 年上月玷e l 异构多核系统中面向细粒度任务集的调度算法研究 摘要 随着异构多核处理器的快速发展，异构多核系统中的任务调度成为研究热点。 目前，适用于普通任务集调度的算法在调度细粒度任务集时，存在处理器负载失 衡，处理器空闲时间多，并行性差和冗余任务等诸多缺陷，严重影响了多核系统 的性能。本文针对这些问题展开研究。 结合聚簇、列表和复制算法各自的优势，本文提出了一种高效的适合细粒度 任务集的调度算法h c d u l ，h c d u l 分为聚簇、优先级计算和就绪任务列表建立、 任务调度、复制上层节点四个阶段。通过聚簇降低了通信开销，调度过程中动态 更新就绪列表，并实时对其排序，关键任务有最高的优先级；每次取列表头节点， 并调度到完成时间最小的处理器核上；利用当前节点之前的空闲时间段复制上层 节点，进一步减小通信开销，提前子任务的开始时间，从而缩短整个任务集的完 成时间。 针对复制算法存在冗余任务问题，本文提出了一种优化算法h d o 。首先，查 找并删除冗余任务，然后计算冗余任务后继节点的开始时间，最后调整后继节点。 通过消除冗余任务，提前了后续节点开始时间，节省了处理器资源，并进一步缩 短了调度长度。 本文使用随机生成图进行了大量实验，在调度细粒度任务集时，与h e f t 和 h c n f 算法比较，h c d u l 算法的调度长度率s l r 更小，加速比s p e e d u p 更大。 同样，使用大量的随机生成图对h d o 算法验证，h c n f 和h c d u l 算法的调度结 果经h d o 算法优化之后，总执行时间比率s e t r 更小，并且在一定程度上，调 度长度率s l r 减小，加速比s p e e d u p 增加。 关键词：异构多核系统：细粒度任务集；冗余任务；优化算法；随机生成图 a b s t r a c t a st h ed e v e l o p m e n to fh e t e r o g e n e o u sm u l t i c o r ep r o c e s s o r ，t h et a s ks c h e d u l l n g 0 nh e t e r o g e n e o u sm u l i t c o r es y s t e mh a sb e c o m eah o ts p o t w h e ns c ：h e d u l i n g f i n e g r a n u l a r i t vt a s ks e t s ，t h es c h e d u l i n ga l g o r i t h m sa d j u s t i n g t on o r m a lt a s ks e t sh a v e m n vd e f e c t ss u c ha su n b a l a n c e dl o a d ，t o o m u c hi d l et i m e ，l o wp a r a l l e l i s ma n d r e d u n d a n tt a s k sc o t a l lo ft h ep r o b l e m si n f e c tt h ep e r f o r m a n c e o fm u l t l c o r es y s t e m t h er e s e a r c ho ft h i sp a p e ri st os o l v et h e s ep r o b l e m s f i r s t l y ，t h i sp a p e rp r o p o s e dan e wa l g o r i t h mc a l l e dh c d u l t os c h e d u l ef i n e g r a n u l a r i t vt a s ks e t s h c d u lh a sf o u rp h a s e s ：c l u s t e rp h a s e ，p r i o r i t yc a l c u l a t l o n 蛐d r e a d vn o d e sl i s tb u i l d i n gp h a s e ，t a s ks c h e d u l i n g p h a s e a n du p p e fl e v e rn o d e s d u p l i c a t i o np h a s e t h r o u g hc l u s t e rp h a s e ，t h ee x p e n s e s o fc o m m u n i c a t l o nb e c o m e i o w e r i nt h cp r o c e s so fs c h e d u l i n g ，h c d u lu p d a t er e a d y n o d e sl i s td y n a m i c a l l ya n d r e s o r tt h el i s ti nr e a lt i m e w h e ns o r t i n gt h el i s t ，t h e c pn o d e sh a v et h eh l g h e s t p r i o r i t y t h r o u g hd u p l i c a t i n gt h eu p p e rl e v e ln o d e s ，t h ee x p e n s e so fc o m m u n l c a t l o n b e c o m e1 0 w c rf u r t h e r a n dt h u sm a k et h ec h i l dn o d e s e a r l i e s ts t a r tt i m es m a l l e r a n d t h u sc o m et oa b r i d g et h ee n dt i m eo ft h ew h o l et a s ks e t i no r d e rt os o l v et h ep r o b l e mo fr e d u n d a n tt a s k s ，w ep r o p o s ea n o t h e ra l g o r i t h m c a l l e dh d oi nt h i sp a p e r f i r s t l y ，h d ol o o k sf o rr e d u n d a n tt a s k sa n dd e l e t e t h e m s e c o n d l y ，h d oc a l c u l a t et h ee a r l i e s ts t a r tt i m eo fr e d u n d a n tt a s k s c h i l dn o d e s ，a n d f i n a i i y ，h d or e v i s e t h en o d e s t h r o u g he l i m i n a t i n gr e d u n d a n tt a s k s ，t h el a s t m g n o d e s e a r l i e s ts t a r tt i m e sa r ea h e a d e l i m i n a t i n gr e d u n d a n tt a s k sn o to n l y s a v et n e p r o c c s s o i sr e s o u r c e ，b u ta l s oa b r i d g et h es c h e d u l i n gl o n g t h r a n d o m l yg e n e r a t e dg r a p h sa r eu s e di n t h ee x p e r i m e n t w h e ns c h e d u l i n gf i n e g r a n u l a r i t yg r a p h s ，c o m p a r e dw i t hh e f t a n dh c n fa l g o r i t h m s ，h c d u lh a sl o w e r s l ra n dh i g h e rs p e e d u p a st h es a m e ，al a r d g en u m b e r o fr a n d o m l yg e n e r a t e dg r a p h s a r cu s e di nv e r i f y i n gh d o t h er e s u l t so fh c n fa n dh c d u l o p t i m i z e db yh d o h a v es m a l l e rs e t r k e yw 。r d s ：h e t e r o g e n e 。u sm u l t i - c 。r es y s t e m ；f i n eg r a n u l a r i t y t a s ks e t ；r e d u n d a n t t a s k s ；o p t i m i z i n ga l g o r i t h m ；r a n d o m l yg e n e r a t e d g r a p h m ! 异构多核系统中面向细粒度任务集的调度算法研究 目录 学位论文原创性声明及学位论文版权使用说明书i 摘要i i a b s t r a c t i i i 目录j i v 插图索引v i 附表索引v i i i 第1 章绪论1 1 1 选题背景与意义1 1 2 调度算法研究的状况2 1 2 1 国外研究状况2 1 2 2 国内研究状况。3 1 3 本文主要研究内容4 1 4 论文组织结构5 1 5 本章小结5 第2 章异构多核系统与调度模型6 2 1 多核系统6 2 1 1 多核系统硬件环境研究：6 2 1 2 异构多核平台的软件系统设计8 2 2 任务调度模型1 0 。2 2 1 运行系统的数学模型1 0 2 2 2 任务的数学模型1 0 2 2 3 调度的约束条件分析1 2 2 3 任务调度的n p 完全性综述1 3 2 3 1 静态调度的n p 完全问题1 3 2 3 2 静态调度算法的复杂性分析1 3 2 4 本章小结1 4 第3 章多核系统中的调度算法分析1 5 3 1 多核系统中调度算法分类1 5 3 1 1 按调度思想分类1 5 3 1 2 按调度环境分类1 6 3 2 启发式算法1 7 i v 硕卜学位论文 3 2 1 聚簇算法1 7 3 2 2 列表算法1 8 3 2 3 复制算法。1 9 3 3 异构多核系统中经典算法分析2 0 3 3 1h e f t 算法2 0 3 3 2h c n f 算法2 2 3 4 本章小结2 5 第4 章针对细粒度任务集的调度方法设计2 6 4 1 算法缺陷分析2 6 4 2h c d u li 章法2 7 4 2 1h c d u l 算法原理一2 8 4 2 2h c d u l 算法实例分析一3 1 4 2 3 算法复杂度分析。3 3 4 3 复制算法的缺陷3 4 4 4h d o 算法3 5 4 4 1h d o 算法原理3 5 4 4 2h d o 算法实例分析。3 7 4 4 3 算法复杂度分析3 9 4 5 本章小结。3 9 第5 章实验仿真及性能分析4 0 5 1h c d u l 性能测试设计4 0 5 1 1 性能测试参考标准4 0 5 1 2 性能测试方案设计4 1 5 2 测试结果分析4 2 5 3 三种算法时间复杂度比较4 4 5 4h d o 性能测试方案设计4 5 5 5 测试结果分析4 5 5 6 本章小结4 8 结论4 9 参考文献51 致谢5 6 附录a 攻读学位期间发表的学术论文5 7 附录b 攻读学位期间参与的科研项目5 8 v 异构多核系统中面向细粒度任务集的调度算法研究 插图索引 图2 1h y d r a 处理器体系结构7 图2 2c e l l 处理器体系结构8 图2 3 并行程序设计。9 图2 4 任务调度模型1 0 图2 5 任务模型图。1 1 图3 1 静态调度算法分类图。1 5 图3 2 不同环境下调度算法分类1 6 图3 3d a g 与两种聚簇方法1 7 图3 4 任务复制实例图2 0 图3 5 空闲时间段实例图2 1 图3 6 区间插入技术实例图2 2 图3 7 随机d a g 2 4 图3 8 使用h e f t 算法的调度结果2 4 图3 9 使用h c n f 算法的调度结果2 5 图4 1 处理器负载失衡情况2 6 图4 2 简单的d a g 任务图2 7 图4 3 处理器存在较大空闲时间2 7 图4 4d a g 的串行执行图。2 7 图4 5h c d u l 算法设计原理图2 8 图4 6 聚簇原理图2 8 图4 7h c d u l 算法流程图3 0 图4 8 复制策略流程图3 1 图4 9 随机生成的d a g 任务图3 2 图4 1 0h c d u l 算法对图4 9 的调度结果3 3 图4 1 1 简单d a g 任务图3 4 图4 1 2 复制节点b 前后的调度情况3 5 图4 1 3h d o 算法的作用( 在调度中的位置) 。3 5 图4 1 4h d o 算法原理图及流程图3 6 图4 1 5 随机任务集3 7 图4 1 6 使用h c n f 调度结果3 7 图4 1 7h d o 算法优化后结果3 8 图5 1c c r 不同时三种算法的s l r 和s p e e d u p 对比一4 3 硕士学位论文 图5 2 节点数不同时三种算法的s l r 和s p e e d u p 对比4 3 图5 3h e f t 、h c n f 和h c d u l 平均运行时间比较4 4 图5 4c c r 不同时优化前后s l r 、s p e e d u p 和s e t r 比较4 6 图5 5 节点数c c r 不同时优化前后s l r 、s p e e d u p 和s e t r 比较4 7 i 异构多核系统中面向细粒度任务集的调度算法研究 附表索引 表3 1 各节点在处理器上的执行时间2 4 表4 1 各任务的执行时间及r a n k u 值和p r o p c p 值3 3 表4 2 节点在各处理器执行时间、平均执行时间、r a n k u 值和路径长度3 8 表5 1c c r 不同时与h e f t 和h c n f 的对比实验数据4 3 表5 2 节点数不同时三种算法平均运行时间比较4 4 表5 3c c r 不同时和h c n f 和h c d u l 调度结果优化前后的对比实验数据4 6 i l 硕士学位论文 1 1 选题背景与意义 第1 章绪论 随着半导体技术及集成电路制造工艺的迅猛发展，集成在芯片上的晶体管密 度不断提高，使得越来越多的元件可以集成到一块单一芯片上。但是由于晶体管 数量增加使芯片发热量越来越大，晶体管的电流泄露问题也随之越来越严重；然 而，晶体管数目增加一倍，所得到性的能提升却只有原来的3 0 【1 1 。过去几十年， 人们使用传统的超标量和超流水线技术来提高单个微处理器性能的方法遇到了瓶 颈，其发展走到了尽头i z 】。 基于以上原因，多核处理器系统c m p s ( c h i pm u l t i p r o c e s s o rs y s t e m ) 应运而 生。多核处理器系统主要分为两类：同构多核系统和异构多核系统。同构多核系 统是指各个处理器核结构相同，性能相同，在系统中的地位也相同。而异构系统 中，各内核的结构、性能和地位等不相同；在实际应用中，同构并行计算机存在 着不足，不能满足具有多种并行性的计算任务需求，大量时间花费在执行很不适 合它的代码上；不同的应用需求对处理器核要求不同，在处理复杂任务集时，异 构多核系统比同构系统有更大的优势。目前在通用计算机和高端计算机上，多核 已经有了相当广泛的应用，例如a m d so p t e r o n ( 皓龙) ，i n t e l si t a n i u m ( 安腾) s u n 公司的u l t r a s p a r c l v 等。 在一个计算机系统中，硬件和软件相互协同、平衡的发展，其整体性能才能 得到最大限度的提高。在多核系统中，多核的硬件环境给程序并行执行提供了良 好平台，而要实现任务良好的并行性，需要解决并行算法的设计、任务的划分、 通信的协调、任务的调度等问题，一组存在并列关系的任务集，需要将他们合理 分配到各个处理器核才能达到良好的并行性。否则，若调度不当，则会抹煞并行 的优点，效果甚至比串行执行还差，因此任务调度是并行分布计算需要解决的瓶 颈问题之一p ，4 j 。 在异构多核系统中，相同任务在不同处理器核上的运行时间不同，部分任务 之间存在约束条件，任务调度的目的就是在满足约束的前提下，将所有任务按照 一定的分配策略分配到处理器核，使任务有序的并行运行，以达到最大时间消耗 最小。要同时满足总任务完成时间最小和任务优先级约束的要求，不可能将所有 任务都分配到执行时间最短的处理器核上，一个良好的调度策略，就是在保证任 务优先级约束的基础上，尽可能增加任务执行的并行性，从而最大限度减少最大 时间消耗，在整体上提高多核处理器的性能。 任务间的通信、外部事件的处理以及中断处理等都离不开任务调度，并且随 异构多核系统中面向细粒度任务集的调度算法研究 着系统功能的完善与增强，任务间的关系变得更加复杂，任务之间的通信量增大【5 1 。 在异构多核系统中，处理核之间通信时的通信启动时间也增加了任务集的完成时 间。为了减小大任务对系统的影响，常把大任务分割成多个小的任务i 引，这同样 也增加了处理核之间的通信。随着处理核的增多，任务分得更细，细粒度图扮演 着越来越重要的角色【7 1 。 细粒度任务图在实际中的应用越来越多，因此对细粒度任务集调度算法展开 研究，对异构多核系统中任务调度具有重要的意义。本课题来源于湖南省科技计 划项目“嵌入式异构多核体系任务调度机制的研究与实现 ( 2 0 0 9 g k 3 0 8 7 ) 。 1 2 调度算法研究的状况 。调度问题从提出到现在已有近4 0 年的历史，特别近年来多核系统的发展，该 领域成为了计算机科学研究热点。并且其它许多领域：如人工智能、神经网络和 基因算法的研究等把各自领域研究成果应用于任务调度【8 】。国内外许多大学和科 研机构都进行了积极探索，并取得一定成效。 1 2 1 国外研究状况 1 9 7 3 年l i u 和l a y l a n d 最先提出任务调度的概念，他们提出的周期任务模型 成为许多实时任务模型基础【9 1 ，在多核系统环境下，用于任务调度可行性分析和 算法设计；该模型忽略某些实现细节，抽象层次高。最早截止期限优先e d f ( e a r l i e s td e a d l i n ef i r s t ) 和速率单调调度r m s ( r a t em o n o t o n i cs c h e d u l i n g ) 是两个 经典的基于周期任务模型的调度算法。r m s 算法中，执行频率最高的任务拥有最 高优先级，该算法可以满足一定系统要求，且实现简单。但是任务之间的数据依 赖、任务通信等限制，使周期任务模型不能很好的描述实际系统。 1 9 9 4 年t a oy 和g e r a s o u l i sa 针对无限数目处理器并行系统任务调度提出了 d s c 聚簇任务调度算法【| 7 1 。该算法主要对f o r k 、j o i n 类型任务图实现优化调度， 具有较低的时间复杂度和较高的任务调度效率，但对细粒度任务图的调度效果却 不理想。之后，m o u r a dh 和f r a n c kb 针对d s c 算法的缺点进行改进，提出了d c p s 算法1 1 0 l 。该算法分成两个阶段：( 1 ) 任务聚簇，( 2 ) 聚簇好的簇分配到各处理器上。 算法由下向上聚簇，动态计算关键路径长度，并且在不增加关键路径长度的前提 下增加约束条件，使算法时间复杂度降到o ( v + e l o g v ) ，使用的处理器数目较d s c 算法少，对细粒度任务图有好的效果，并且任务图的粒度越小，效果越好。 t o p c u o g l uh 和h a r i r is 于1 9 9 9 年提出了公认的调度效率较高的两种启发式 表调度算法：h e f t ( h e t e r o g e n e o u s e a r l i e s t f i n i s h t i m e ) 和c p o p ( c r i t i c a l p a t h o nap r o c e s s o r ) 算法【1 1 ，12 1 ，其基本思想是：首先根据任务的优先级建立任务 就绪列表，然后把任务分配到各个处理器核以追求最优调度。 2 硕十学位论文 m a h e s w a r a nm 和a l is 对异构多核系统中独立任务调度问题进行深入研究， 详细论述了m i n m i n 、m a x m i n 和s u f f r a g e 三种经典算法。m i n m i n 每次选择就 绪的最小任务分配到执行它最快的处理器；m a x m i n 每次选择大任务分配到执行 该任务最快的处理器核上；s u f f r a g e 每次选择最早完成时间与次早完成时间之差 最大的任务，并把其分配到执行时间最小的处理器核上。 列表和复制结合，可以取得更小的最大时间消耗。2 0 0 6 年p r a s h a n t hc r a n g a s 和s a n j e e vb 等提出了一种关键路径任务优先调度，非关键路径任务大任务优先 算法h c n f ( h e t e r o g e n e o u sc r i t i c a ln o d ef i r s t ) 1 1 3 l 。算法整个过程，关键路径任务 具有最高优先级，任务执行时间为次优先级，同时，引入复制技术将低计算成本 任务复制到多个处理器核，减小任务间通信开销，从而降低了任务集的最大时间 消耗。该算法对存在先后依赖关系的任务集调度有良好效果。 r a n a w e e r as 和a g r a w a ld p 提出了基于任务重叠的可扩展调度算法【1 4 】。 b a r u a hs k 提出了全局任务动态调度算法，实现任务运行过程中的动态迁移【1 5 】， 且迁移代价近似为零。e d w i nsh 和n i r w a na s 等采用遗传算法研究多核系统中 的任务调度，通过完善交叉算子提高了任务调度的效率1 1 6 l 。k r z y s z t o fr 和 f r a n c i s z e ks 使用d a g 作系统模型【1 7 l ，采用遗传算法对异构多核系统中的任务调 度分析，优化任务优先级，使调度效率进一步提升。 1 2 2 国内研究状况 相对于国外，国内对于任务调度的研究起步较晚，但发展快速，取得相当大 的成就。湖南大学的李仁发等教授从调度算法分析和实现框架两方面着重探讨了 了多处理器片上系统的研究概况，分析了当前亟待解决的问题与下一步的研究方 向，为多处理器片上系统相关研究提供了参考1 1 8 l 。徐成教授针对周期任务引入多 帧的概念，建立了新任务模型描述异构多核系统中多帧任务的特性，并证明了新 模型的n p 完全性，新模型上采用遗传算法对任务调度，为异构多核系统任务调 度提供了新的解决思路【1 9 】。李肯立教授对异构系统中的动态调度和负载平衡问 题，提出了新的任务模型，对抢占式任务调度算法改进，建立负载平衡的探测机 制，使可用性与响应能力达到良好平衡，优化了调度结果卜。 清华大学郑纬民、石威等教授针对现有表调度算法的不足，提出了均衡动态 关键路径算法【2 1 1 ，综合考虑任务集关键路径节点和非关键路径节点的优先级，调 度过程动态计算关键路径长度，对调度长度影响最大的任务予以优先调度。该算 法把基于表调度的算法与动态计算关键路径结合，缩短了整个任务集的总调度长 度。 国防科学技术大学钟求喜博士结合遗传算法，提出了一种基于异构系统的任 务调度优化算法。在初始种群构造过程中，采用节点的高度值均衡构造初始种群【2 引， 3 异构多核系统中面向细粒度任务集的调度算法研究 通过设计改进的杂交算子和迁移算子等对算子完善，优化任务调度的结果。 华中科技大学赵勇等提出了一种关系演化算法，通过模拟人类社会演化过程， 对簇的优先级重新定义，将复制、聚簇与列表相结合，提出了一种动态关键前驱 ( d c p ) 算法【2 3 1 。算法重新定义了粒度的概念，改变了聚簇任务条件，优化了调 度结果，对粗粒度任务图具有十分良好的调度结果。李庆华、韩建军等对同构多 核环境中静态调度提出了新模型，并设计了适应该模型的调度算法，提高了任务 调度性能，降低了算法的时间复杂度【2 引。 中国科学院计算技术研究所的张兆庆等对多核多线程处理器任务调度技术进 行研究，在任务间有通信限制的条件下，对典型的f o r k j o i n 任务图采用复制算法 优化【2 5 1 ，将任务尽可能调度到已处在工作的处理器上，来减少处理器的使用数目， 以便降低处理器的功耗；针对调度结果中存在冗余任务的问题，提出了一种优化 策略减少冗余任务数，最大程度的利用处理器资源，降低了处理器的功耗。 北京航空航天大学与西安交通大学的刘轶、张昕等对多核处理器并行系统上 的启发式任务调度算法进行研究，提出两轮操作调度算法，多次迭代使任务调度 结果更优，一定程度上减少了算法的求解时间【2 6 1 。 浙江大学陈天洲教授在嵌入式异构多核系统上，采用软硬件协同任务调度的 方法，提高了系统反应时间，减小了系统功耗，为以后嵌入式异构多核系统任务 调度研究提供了新的思想方法【2 7 1 。 1 3 本文主要研究内容 目前任务调度的研究主要集中在对粗粒度图即执行密集型任务集研究，对于 细粒度图的研究比较少，特别是对于细粒度图在异构多核系统上调度的研究更少。 现有的算法应用到异构多核系统中细粒度图调度存在许多缺陷，本文主要对异构 多核系统中细粒度任务集的调度进行研究，主要研究内容包括以下几个方面： ( 1 ) 对现有任务调度算法展开研究，对比普通调度算法与适合通信密集型任 务集的调度算法之间的区别，并总结算法的各自特点，筛选高效调度算法，将其 应用到细粒度图的调度。 ( 2 ) 建立任务模型，通过建立任务模型，把任务调度抽象成一个数学问题， 从而简化问题的复杂性。并对比通信密集型任务集和执行密集型任务集的不同， 以便针对通信密集型任务集设计特定算法。 ( 3 ) 把经典算法应用于通信密集型任务集的调度，统计出现的问题，并分析 问题出现的原因，针对这些原因设计解决方法，从而设计出适合通信密集型任务 集调度的算法。 ( 4 ) 对提出的算法进行实验验证，通过大量实验可以准确、公平的验证算法 的效果。并与其它算法对比，总结新算法的优缺点，对不足进行优化，以便达到 4 硕士学位论文 最佳效果。 1 4 论文组织结构 本文按照研究内容的先后秩序，共分成5 章，具体组织结构如下： 第1 章绪论，共分成三部分，首先介绍了论文的选题背景与意义，然后详细 介绍了国内外研究现状，最后大概陈述了本文的主要研究内容。 第2 章异构多核系统与调度模型，首先介绍多核系统的定义及软硬件环境， 其次对运行环境和任务集建模，并对模型进行了详细介绍，最后对静态任务调度 的n p 完全问题进行详细描述和复杂性进行分析。 第3 章多核系统中的调度算法分析，对静态任务调度算法进行细致分析。该 章也分成三大部分，首先对调度算法分类，然后对基于启发式算法的三种算法详 细分析，最后详细阐述了两种经典算法。 第4 章针对细粒度任务集的调度方法设计，该章是本文的主要内容，分成四 部分，首先分析现有调度算法对细粒度任务图调度的不足，其次详细介绍适合细 粒度图的调度算法h c d u l 算法，再次分析基于复制算法存在的缺陷，最后对复 制算法进行优化，即h d o 算法进行详细阐述。 第5 章实验仿真及性能分析，对提出的两种算法进行模拟实验，统计实验结 果并分析实验数据，陈述实验结论。 文章最后是总结与展望，对全文工作进行了总结，并且简要分析本文工作的 不足和待改善之处，为以后继续研究确定方向。 1 5 本章小结 本章是整篇论文的绪论部分，首先介绍了选题的背景与意义，然后详细介绍 了该领域的研究现状，包括国内和国外的研究状况。通过研究现状，可以查找相 关资料，也是继续研究该领域的基础。分析研究现状后，发现目前对细粒度图的 调度研究较少，引入了本文的研究工作一一异构多核系统中针对细粒度图的任务 调度算法研究。最后介绍了论文的组织结构。 5 异构多核系统中面向细粒度任务集的调度算法研究 第2 章异构多核系统与调度模型 相对于单核系统，多核系统有处理速度快，系统反应时间短和功耗低等优点。 任务调度是高性能多核系统的重要组成部分，对系统性能的提升起着至关重要的 作用，良好的调度算法能够使系统达到最佳性能。 2 1 多核系统 流水线技术已经发展到了极限，单处理器系统很难满足高吞吐量的需求，并 行处理技术应运而生。最开始是在一个计算机上汇集多个处理器，各个处理器之 间共享内存系统和i 0 系统，称为对称多处理器s m p ( s y m m e t r i c a l m u l t i p r o c e s s i n g ) ，这在一定程度上提升了计算机系统的并行性和计算能力【2 引，但 是该方式需要把多个通用处理器构建成集群，存在很大的技术难题。后来出现了 在一个芯片上集成多个处理器核心的技术即：c m p ( c h i pm u l t i p r o c e s s o r s ) ，为处理 器性能的继续提升提供了一种方式。 2 1 1 多核系统硬件环境研究 c m p 技术又称为多核技术( m u l t i c o r e ) ，芯片上每个处理器核都是一个结构相 对简单、功能独立的单线程处理器，这些处理器之间联系十分紧密，共享二级c a c h e 甚至一级c a c h e 和f s b 总线接口。c m p 拥有硬件多线程处理能力 s m t ( s i m u l t a n e o u sm u l t i t h r e a d i n g ) ，并在设计上同s m p 有很多像似之处。 s m t 技术是乱序执行处理技术的一种扩展技术，目的是增加可供处理器执行 的指令序列。该技术忽略高层的数据共享，不同线程在数据上没有依赖性，增加 了可供处理器运行指令级并行的独立指令序列，并且可以使不同指令序列利用处 理器来响应不同资源器件，使处理器在同一时间从不同的线程选取指令序列来执 行。s m t 技术处理器可以在同一时间里运行多个线程，当某一个线程等待外部资 源而阻塞时，另外的线程共享利用处理器，使之继续运行。理论上只对一个线程 来讲，运行在s m t 处理器比运行在非s m t 技术的处理器慢，但s m t 技术的c p u 计算资源利用率高，运行效率更快【2 9 4 1 1 。 c m p 与s m t 一样，努力挖掘线程级并行性，但是c m p 上每个处理器核心都 是独立的，他们各自执行自己的指令级序列【3 2 , 3 3 】。 相对于单处理器系统，多核系统有控制逻辑简单、开发和验证周期短、功耗 低、主频高和可扩展性高等优势，许多科研机构和商业机构对多核系统进行了深 入研究，如a m d 、i b m 、i n t e l 等都推出了自己的多核处理器。目前多核处理器 的差别主要在于核心数目不同，核心类型不同。根据芯片上处理器核心的类型是 6 硕“仁学位论文 否相同和处理器核心是否对称，分为同构多核处理器和异构多核处理器。 同构多核处理器大多由相同的通用处理器组成，对同一任务，各处理器的执 行速度相同。典型代表是1 9 9 6 年斯坦福大学开发的h y d r a 处理器1 3 引，该处理器 集成四个m i p s 微处理器到同一芯片。每个处理器核拥有一个独立的l i c a c h e ， 共享一个l 2 c a c h e ，通过读总线、写总线、地址总线和控制总线与l 2 c a c h e 相连。 私有l i c a c h e 由一个指令c a c h e 和一个数据c a c h e 组成，读总线作为通用系统总 线，实现了处理器核心、l 2 c a c h e 和外部接口与片外存储器之间的数据传送。同 时，多个内核共享l 2 c a c h e 的结构，降低了内核间的通信延迟，利于处理器性能 的提升【3 5 1 。图2 1 为h y d r a 处理器体系结构。 d r a mm a i nm m o r yi od e v i c e s 图2 1h y d r a 处理器体系结构 一般情况下，在处理器执行的多个任务性质不同，同构多核系统在处理这些 任务时，往往浪费处理器资源，相比较而言异构多核系统有更大优势。i b m 和索 尼、东芝联合推出的c e l l 处理器采用了异构多核处理器结构【3 6 j ，其主频可达 4 g h z ，包含一个p p e 主处理器核和8 个专用的s p e 协处理器核，通过高宽带元 件互联总线e i b ( h i g h b a n d w i d t he l e m e n