（计算机科学与技术专业论文）基于周期任务的异构多核多帧任务分配算法研究.pdf

基于周期任务的异构多核多帧任务分醚算法研究 摘要 任务调度问题是计算机科学研究的基本课题，多核系统的出现为任务调度问 题带来了新的变化。多核系统的任务调度问题首先考虑能否在保证任务得以完成 情况下，寻求分配方案使得处理器繁忙程度平均，这也称为任务的分配问题。该 问题在异构多核系统中更为复杂。在异构系统的任务分配问题中需要综合考虑处 理器的异构特性，使得各处理器各尽所能，任务各取所需。 当前在异构多核任务分配的研究中对经典的周期任务研究较为深入，但这些 研究并没有关注具有多帧性质的任务，导致在分析中使用任务的单一最大处理时 间，悲观的误判某些可以分配的任务集不能分配。 本文从经典的周期任务入手，在研究当前异构多核任务分配的流行算法基础 上，将多帧性质应用于异构多核系统，建立新的任务模型：异构多核多帧任务模 型。该模型具有更全面的描述能力，集中体现了计算系统的异构性和任务的多帧 性。利用非线性规划的描述方法证明新模型的优势，并借助遗传算法进行验证。 首先对于具有a m ( 累积单调) 性质的异构多核多帧任务，从理论上分析新 模型的优势，即能分配更多任务，其后设计遗传算法进行解决。为验证理论结果 和算法性能，同时针对异构多核研究没有统一平台的问题，本文设计了一个易于 扩展的异构多核任务分配评估系统，实现文中使用的两种方法：遗传算法和m a t l a b 两步法。本文基于该系统进行a m 异构多核多帧任务的模拟实验。 在此基础上，对一般异构多核实时任务进行了讨论，使得模型具有更广泛的 应用范围。给出了一般异构多核任务的相似理论分析和遗传算法设计，通过模拟 实验证实模型的可用性，以及更全面的体现任务。 理论分析和实验结果表明，考虑了多帧特性的异构多核任务模型较悲观的使 用最大处理时间的任务分配方法可以成功分配更多任务，更全面的表现任务性质。 遗传算法的设计简单实用，在较短的时问内即能获得很好的结果，移植性好，具 有一定的应用价值。 关键词：周期任务；异构多核系统；多帧；任务模型；分配问题；遗传算法 l l a b s t r a c t t h ep r o b l e mo ft a s k ss c h e d u l i n gi s o n eo ft h eb a s i cr e s e a r c h i nc o m p u t e f s c i e n c e w i t ht h ea p p e a r a n c eo fm u l t i p r o c e s s o rs y s t e m s ，an e wc h a n g ew a sp r o p o s e d i nt h et r a d i t i o n a lc o n l p u t e rt a s k ss c h e d u l i n g t h ep a r t i t i o n i n gi s s u ei s c o n s l d e r e d f i r s t l yi nm u l t i p r o c e s s o rs y s t e m s ，w h i c hd e t e r m i n e sh o wt op a r t i t i o n as e to f9 1 v e n t a s k jt oac o n e c t i o no fp r o c e s s e s ，m a k i n gs u r ee v e r yt a s ki se x e c u t e da n db a l a n c l n g t h eb u s y n e s s 锄o n gp r o c e s s e s t h i sp r o b l e mi sm o r ec o m p l i c a t e di nt h es i t u a t i o no f h e t e r o g e n e o u sm u l t i p r o c e s s o rs y s t e m s ， b e c a u s eo ft a k i n ga c c o u n to fd i f f e r e n c e p r o c e s sc a p a b i l i t ya n l o n gp r o c e s s o r s ，s ot h a te v e r yp r o c e s sc a n d ol t sb e s ta c c o r d l n g t oi t sa b i l i t i e sa n de v e r yt a s kc a nt a k ew h a t i t sn e e d c u r r e n t l y ；t h o u g h t h e r ea r ep l e n t y o fr e s e a r c ha i b o u tt h eh e t e r o g e n e o u s m u l t i p r o c e s s o rt a s k sp a r t i t i o n i n gb a s e do nc l a s s i c a lp e r i o d i c t a s k sm o d e l ，f e ws t u d y t a k e sn o t i c eo ft h em u l t i 行a m ec h a r a c t e fo ft a s k s ，w h i c hr e s u l t si n 觚a l y z i n g w l t ha s i n g l ew o r s t c a s ee x e c u t i o nt i m e ，p e s s i m i s t i c a l l yt a k i n gf o rs o m et a s k ss e t c a n tb e p a r t i t i o nw h i c h c a np a n i t i o na c t u a l l y f r o mt h ec l a s s i cp e r i o d i ct a s k s ，b a s e do nt h es t u d yo fc u r r e n th e t e r o g e n e o u s m u l t i p r o c e s s o rt a s k sp a r t i t i o n i n gp o p u l a ra l g o r i t h m s ，t h i sp a p e r t o o kt h em u l t l t r a m e c h a r a c t e ri n t oh e t e r o g e n e o u sm u l t i p r o c e s s o rs y s t e m ， b u i l tan e wt a s km o d e l ： h c t e r o g e n e o u sm u l t i p r o c e s s o rm u l t i f - r 锄ep e r i o d i cr e a l t i m et a s k sm o d e l t h em o d e i i sm o r eg e n e r a l i z e dt h a np r e v i o u sm o d e l s ， r e n e c t i n g t h es y s t e mc a p a b l l l t y o t h e t e r o g e n e o u sm u l t i p r o c e s s o ra n dt h em u l t i - f r a m ec h a r a c t e ro ft a s k se 仃e c t i v e l y i n v i r t u eo fd e s c r i b i n gi nn o n 1 i n e a rp r o g r a m m i n g ，t h ea d v a n t a g eo fn e wm o d e lw a s p r o v e di nt h e o r e t i c as i m u l a t i o ne x p e r i m e n ta p p l i e di ng e n e t i ca l g o r i t h m sw a s 9 1 v e n a sw e l l f i r s t ly ， f o r t h eh e t e r o g e n e o u sm u l t i p r o c e s s o r m u l t i f r a m et a s k sw i t ha m ( a c c m u l a t i v e ly m o n o t o n i c ) p r o p e r t y t h e o r e t i c a la n a l y s i s s h o w e dn e wt a s k sm o d e l 7 s a d v a n t a g e ：p a r t i t i o n i n gm o r et a s k ss e t st h a nt h ep e s s i m i s t i cw a y a n dd e s l g nag e n e t l c a l g o r i t h mt os l o v e t ov e r i f yt h e o r e t i c a lc o n c l u s i o na n d t h ep e r f o 咖a n c eo fa l g o r i t h m a n df o rt h ep r o b l e mo fn ou n i f o 珊p l a t f o r mi nh e t e r o g e n e o u sm u l t i p r o c e s s o rt a s k s p a r t i t i o n i n gs t u dy ，a ne a s i l ye x t e n d e d h e t e r o g e n e o u sm u l t i p r o c e s s o rt a s k sp a n l t l o n l n g e v a l u a t i n gs y s t e mw a si m p l e m e n t e d t w om e t h o d si nt h i sp a p e r ：g e n e t l ca l g o r l t h m a n dm a t l a bt w o s t e p sw a yw e r ea p p l i e di nt h es y s t e mf o re t c s i m u l a t i o ne x p e r l m e n t t t t ：兰：芏些墼型些塑丝型丝丝些墅丝丝一 ! = e = = ! = = = = = = ! = = l ! ! | ! ! = = ! = j ! ! ! = = = ! = = = = ! ! = = = = ! = = = = = = = = = = ；。一 a b o u ta mh e t e r o g e n e o u sm u l t i p r o c e s s o rm u l t i f r a m e t a s k sw a st e s t e do nt n e e v a l u a t i n gs y s t e m b a s e do nt h ea mh e t e r o g e n e o u sm u l t i p r o c e s s o rm u l t i f r a m et a s k s ，t oe n l a r g et h e r a n g eo fn e wm o d e l ，t h eg e n e r a lh e t e r o g e n e o u sm u l t i p r o c e s s o rr e a i - t i m et a s k sm o d e t w a sd i s c u s s e d s i m i l a rt h e o r e t i c a la n a l y s i sa n dg e n e t i ca l g o r i t h md e s l g nw a s9 1 v e n a s w e l l t h eu s a b i l i t ya n du n i v e r s a l i t yw a sc o n f i r m e dt h r o u g hs i m u l a t i o ne x p e r l m e n t b o t ht h e o r e t i ca n de x p e r i m e n ts h o w e dt h em o d e lc o n s i d e r i n gm u l t i - 蜀a m e 1 n h e t e r og e n e o u sm u l t i p r o c e s s o rc a np a n i t i o n i n gm o r et a s k ss e t st h a nu s l n g aw o r s t - c a s e e x e c u t i o nt i m ep e s s i m i s t i c a l l y ； m o r eg e n e r a l i z e dp i c t u r er e a ls y s t e mt a s k s t h e g e n e t i ca l g o r i t h mw a ss i m p l ea n de a s yt oa p p l i e d ，a c h i e v e sr e l i a b l er e s u l t s i nl o w e r t i m et h a nt r a d i t i o n a lw a y s ，c a nb ew i d e l yu s e d k e y w o r d s ： p e r i o d i ct a s k s ； h e t e r o g e n e o u sm u l t i p r o c e s s o rs y s t e m s ； m u t i f r a m e ； t a s k sm o d e l ；p a r t i t i o n i n gp r o b l e m ；g e n e t i ca l g o r i t h m s l v 顾i j 学位论文 插图索引 图1 1 论文结构图6 图2 1 追踪系统调度示意图。l o 图2 2 遗传算法流程图1 3 图3 1 异构多核多帧任务模型1 5 图3 2 异构多核任务模型。1 6 图3 3 任务集分配和调度图1 7 图3 4 选择算子2 3 图3 5 交叉算子2 3 图3 6 变异算子2 4 图3 7 遗传算法流程2 4 图4 1h t e s 主界面2 7 图4 2r d o 流程图2 8 图4 3r d m 流程图2 8 图4 4f r o 流程图3 0 图4 5f r m 流程图31 图4 6m t s 求解3 3 图4 7 掰= 2 相对分配成功率3 5 图4 8m = 4 ，6 ，8 ，1 0 相对分配成功率3 6 图4 9 随机产生利用率矩阵3 6 图5 1 遗传算法流程。4 4 图5 2 聊= 4 相对分配成功率4 6 图5 3 ，l = = 2 ，6 ，8 ，1 0 相对分配成功率图。4 7 图5 4 随机生成的任务集第一帧周期情况4 8 v i l 幕于周期任务的异构多核多帧任务分配算法研究 附表索引 表2 1m p e g 视频片段统计9 表4 1 引擎操作指令简介3 2 表4 2m x 矩阵操作指令简介3 2 表4 3m = 2 时任务集分配情况对比3 4 表4 4m a t l a b 两步算法时间结果3 7 表4 5 遗传算法时间和结果3 7 表5 1m ：4 时任务集分配情况对比4 6 表5 2 遗传算法时间结果4 8 v i l i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名： 。刁锑日期：砰r 月吖日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：黾乞氛 刷磁辄静 日期： 日期： 1 1 研究背景和意义 第1 章绪论 任务调度算法是一组用于决定特定时刻执行特定任务的规则集合，是计算机 科学研究的经典问题。多核处理器的出现给任务调度相关研究带来了新的变化。 在多核处理器计算平台中，首先需要考虑任务的分配问题，并且保证分配到每个 处理器的各个任务可调度。从单核处理器发展到多核处理器，以及现在新一代的 异构多核处理器系统，计算能力越来越强，但在这样的新兴计算系统上论证一组 任务的可分配性以及在可分配的前提下寻求最优( 次优) 分配策略的难度却大大 增加。 现有的异构多核处理器上任务分配分析方法大多考虑任务执行的单一性，因 而在分配研究中只考虑任务的最差情况。实际上，任务执行时间随周期变化的情 况在现实系统中很常见( 如视频处理) ，这样的任务执行时间并不单一为一个最差 时间。研究异构多核多帧系统上的任务分配和调度问题，充分利用计算系统的处 理器具有的多核和异构特性，并深入分析周期多帧任务在新计算平台上的性质， 对于加强对计算机任务调度的理解，更合理的完成这些任务，提高实际异构多核 处理器系统性能有着深刻的理论意义。 从实际角度来说，目前以异构多核处理器为计算核心、主要应用任务又具有 多帧性质的高性能计算平台己得到了广泛应用。如德州仪器推出了基于达芬奇技 术框架的t m s 3 2 0 d m 6 4 4 6 多媒体异构片上多处理器，即是最为典型的代表。此 类高性能平台的主要应用领域：网络视频应用开发，其任务具有明显的多帧性质。 因此，基于异构多核处理器系统研究异构多核多帧任务的分配问题，具有十分广 阔的应用前景。 1 2 异构多核任务分配问题研究概况 1 2 1 研究现状和发展趋势介绍 计算机任务调度的研究早在上世纪6 0 年代就已开始。1 9 6 7 年m a n a c h e rg k 第一次提出了“任务 的概念，并利用列表法进行了基本的调度研究，同时文章 对于软硬实时系统也给出了说明【。l i u c 和l a y l a n d j 在上述基础上提出了著名 的周期任务集，主要有如下假设： l 、所有任务的硬期限要求是周期出现的，其间有常量的问隔； 2 、最终期限只包括了运行能力约束，例如：每个任务必须在下一次要求出现 之前完成； 基十周期任务的异构多核多帧任务分配算法研究 3 、任务之间是独立的，所以特定任务的要求不会依赖于其他任务请求的开始 或是完成； 4 、每个任务的运行时间是一个与该任务有关的常量，并不因时间而改变。这 里的运行时间是指一个处理器无中断执行该任务所用的时间； 5 、系统的非周期任务是特别的，执行例行的初始化或是失败一重启，在运行 时取代周期任务，而且没有硬的、严格的最终期限。 基于以上假设，作者认为可以用二元组来描述一个周期任务t ：任务周期z 和 执行时间e 【2 1 。而且文中也对这样的模型进行了分析，提出了三个算法用于在单 处理器上调度周期任务：单调速率算法r m ( r a t em o n o t o n i ca l g o r i t h m ) 、最早结 束优先e d f ( e a r l i e s td e a d l i n ef i r s t ) 算法以及二者综合的算法。在r m 算法中， 根据任务的需求速度赋予其一定的优先级，即所谓的固定优先级。在e d f 算法中， 任务最终期限值较小的赋予更高的优先级，即动态调整任务的优先级。而综合的 算法将任务分开对待，分别使用上述的算法。在固定优先级的分析中作者指出， 此种情况下处理利用率上界如公式1 1 所示： u = 聊( 2 1 加一1 ) ( 1 1 ) 其中肌为任务个数，当朋专，【，h 1 2 。 l i u c 和l a y l a n d j 将计算机的任务使用上述二元组( 以下简称l & l 周期任务 模型) 进行描述，为研究任务调度问题提供了良好的数学途径。后来的学者对任 务调度以及分配问题的研究几乎都基于这个模型。然而，认为任务总是一成不变 的表现出一个最差执行时间并不适用于所有情况。 a l o y s i u sk m o k 和d e j ic h e n 在1 9 9 6 、1 9 9 7 年在周期任务模型的基础上提 出了多帧任务( m u l t i f r a m et a s k s ) 模型1 3 】【4 】。作者指出，同一任务并不是在任何 情况( 特别是在多媒体系统) 下都具有相同的执行时间( 文中以多媒体任务m p e g 的伊b 帧为例说明) ，而l & l 的周期任务模型悲观的考虑最坏情况下的执行时 间，来分析任务的可调度性以及调度方案，致使一部分可调度的任务被错误的归 结为不可调度。于是作者用这样的元组表示一个多帧任务：( r ，p 1 ，其中 r ：f c o ，c 1 ，c - 11 为元组( 1 1 ，表示了种执行时间，而p 为最小的时 间间隔，相当于l & l 中的任务周期。可以看出帧之间的差别就表现了任务之间的 执行时间区别。在这样的模型和假设下，作者得到了更高的处理器利用率上界。 多帧周期任务集的研究成果十分丰硕。h i r o a k it a k a d a 和k e ns a k a m a r a 在上 述模型上给出了多帧任务可调度性的另一个判断方法，提出使用m i f ( m a x i m u m i n t e r f a c ef u n c t i o n ) 为基础的多项式算法进行可调度性判断【5 l 。1 9 9 8 年，c h i n g c h i h h a n 将自己和h u n g y i n gt y a n 在不考虑多帧实时任务调度的算法基础上加入任务 多帧特性的考虑，在m o k 的关键时刻测试的基础上讨论了更为准确的可调度性测 试条件，并据此给出了s r ( s p e c i a l i z a t i o no p e r a t i o n ) 和d c t 两个算法，它们都具 2 硕 ：学位论文 有d ( 刀2 ( + m a x f ) ) 的时间复杂度，其中，l 为任务个数，m 为任务帧数引6 儿7 。而 作为多帧任务模型提出者的a l o y s i u sk m o k 和d e i ic h e n 也在1 9 9 9 年与s a n j o y b a r u a h 以及s e r g e yg o r i n s k y 共同将多帧任务的形式进一步一般化【8 j 。使用三元组 来表示一个任务：( 雷，西，声) ，其中云，西，声均为维向量，云为执行时间，西为最 终期限，尸为最小时间间隔。这种任务模型不仅表示出任务的执行时间是可变的， 其最终期限和周期也是可变的。这样的任务被称为一般化多帧任务( g e n r e r a l i z e d m u l t i f r a m et a s k s ) 。文章使用需求上限函数来分析任务的可调度性，并给出了寻 找优化调度的算法。 近年来，多帧任务的研究也有了新的进展。2 0 0 7 年w a n c h e nl u 和k w e i j a y l i n 等人利用任务间的相对周期比率提出了新的可调度性条件，借助系统的最大 和最小周期提高了r m 的调度成功率【9 1 。2 0 0 8 年，a z u h i l y 和b u m s 研究了具有 a m ( a c c u m u l a t i v e l ym o n o t o n i c ) 性质的多帧任务，他们通过响应时间找到了多 帧任务可调度性的充要条件，完善了多帧任务的研究【l0 1 。 随着多核计算的出现，在同构以及异构多核系统上对任务集进行建模以及研 究该情况下的分配与调度问题也成为科学界的重大课题，引起人们的关注。 b jo r na n d e r s s o n 和j a nj o n s s o n 以及p a o l ov a l e n t e 和g i u s e p p el i p a r i 分别从 静态优先级和e d f 算法出发，对相应条件下的同构多核处理器上任务调度问题进 行了研究，并说明该问题是一个n p 完全问题【川f 1 甜。北卡大学的s a n j o yb a r u a h 小组对异构多核处理器上任务分配相关研究贡献显著，发表了大量论文。2 0 0 4 年， s a n j o yb a r u a h 以经典的l & l 周期任务模型为基础，在异构多核计算系统上进行 扩展，使用利用率材，的差异来反映不同处理器处理相同任务的不同能力，给出了 一个两步算法【i3 1 。将任务分配问题建模到一个线性规划问题，首先使用工具( 如 m a t l a b ) 解决该规划，获取一部分解，再利用穷举法获取剩余的解，得到了在每 个处理器利用率不超过5 0 的情况下的可行性与分配结果。文章也证明了异构多 核处理器上的任务分配与调度是一个n p 完全问题。同年后期，s a n i o yb r a u a h 又 对全局调度进行了研究【i 引。在该文的模型下，不同于分配后固定每个任务在特定 的处理器上运行，作者在假设迁移是无代价的条件下，允许其在运行过程中动态 迁移到其它处理器上继续运行。文中给出了判断可行性以及分配的具体算法。 s a c h i s hg o p a l a k r i s h n a n 和m a r c oc a c c a m o 在s a n io yb r a u a h 模型基础上增加任务 复制的条件，对新模型进行了类似研究f ”】。 对于n p 完全问题使用遗传算法可以防止组合爆炸问题，很多学者在任务分 配与调度问题上利用遗传算法进行了尝试。e d w i ns h h o u 和h i r w a na n s a r i 等人 对同构多核任务调度问题进行了分析，文章利用任务完成时间作为适应度函数， 完善了交叉算子【1 引。k r z y s z t o fr z a d c a 和f r a n c i s z e ks e r e d y n s k i 也采用遗传算法分 析异构多核的分配问题【1 7 】。两篇文章都使用d a g ( d i r e c t e da c y c l i cg r a p h ) 图进 皋f 周期任务的异构多核多帧任务分配算法研究 行任务集建模，利用d a g 的先天优势更直观的表现任务间的时间约束关系【1 8 】。 任务分配与调度方面的研究也引起了国内专家的广泛关注。中国科学院软件 研究所的戴国忠、王宏安小组发表了【19 2 l 】等一系列的文章，研究了实时多处理 器系统的动态调度算法。在多帧任务调度问题的研究上，黄文广等讨论了周期多 帧任务的固定优先级调度算法，证明对于周期多帧任务的d m 算法不是最优的 同时也证明对于累积单调周期多帧任务d m 算法是最优的【2 2 1 。在改进的模型中作 者还对一般多帧任务进行了定义f 2 3 1 。宾雪莲等从响应时间入手分析了周期多帧实 时任务的可调度性【2 4 1 。 2 5 2 7 】讨论了嵌入式系统的任务调度问题。f 2 8 3 1 】也对 单处理器的任务调度问题给出了自己的见解。 对于多核处理器上的任务分配与调度，湖南大学的李仁发教授等分析了异构 多核系统的研究概况【3 2 1 。国防科学技术大学的钟求喜博士基于遗传算法对多核处 理器上任务的分配与调度进行了研究，文章通过算子的完善，进一步优化了 1 6 】 的结果【3 3 j 。 1 2 2 涉及的关键问题 1 、任务模型 从上述文献的分析中不难发现，任务模型的选取决定了研究的方法与最后的 结果，任务分配与调度模型的相关研究是实时任务研究中具有挑战性的课题f 3 4 1 。 任务模型反映了系统任务特性，解决分配与调度问题的首要问题就是建立合理的 任务模型。“优秀”的模型不仅可以更好的反映系统的特质，更能起到简化问题的 作用，使研究结果更具说服力。 目前在异构多核处理器任务分配问题的研究中，占主导地位的是s a n j o y 对 l & l 周期任务模型的在异构多核处理器计算平台上的扩展，而l & l 模型在任务 多帧特性上的缺陷却没能引起人们的注意。 本文从该问题入手，尝试建立综合考虑异构多核优势和多帧实际的新模型， 更一般的表现计算机的任务，并讨论分配问题。 2 、近似算法 上述文献分析可以明显看到，作为n p 完全问题的( 异构) 多核处理器系统 上的任务分配问题将使传统算法面临组合爆炸的窘境。用什么样的近似算法来解 决这个问题，同时获得令人信服的结果也是富有挑战性的。 遗传算法的应用给我们提供了思路，本文利用遗传算法的优势在相对可以接 受的时间内尝试解决异构多核任务分配问题。 s a n j o y 教授将问题转化为线性规划，为我们提供了研究的新思路，文中给出 的m a t l a b 和穷举两步算法也值得学习【1 3 】【14 1 。不过从固定优先级实时任务的角度， 该方法主要存在以下四点不足。 ( 1 ) 实时任务未考虑多帧特性。这样的悲观考虑会导致一些本来可以分配的 4 硕l ：学位论文 任务误认为不能分配。 ( 2 ) 算法最后需要d 沏”) ( 所为处理器个数) 的穷举完成。这个时间代价会 随着系统规模的扩大成为算法的瓶颈，可以预见在一定系统规模情况下，如此等 待会让人难以忍受。 ( 3 ) 第一步使用工具( m a t l a b ) 的算法不易于移植。虽然m a t l a b 方便模拟 仿真，但从实际应用的角度看，该方法难于扩大使用范围。 ( 4 ) 任务的处理器利用率不能超过5 0 。这主要是因为该方法后期需要穷 举求解，如果存在超过5 0 的利用率，会使得穷举出现不可行的解，导致算法失 败。 本文借鉴文献【1 3 】【1 4 】的方法，增加任务多帧性质的考虑，并结合异构多核处 理器计算平台，以遗传算法作为突破口，旨在设计更为高效的分配算法。 1 3 论文的主要工作和论文结构 本文在分析国内外任务分配与调度的相关研究和发展动态，以及对异构多核 处理器上任务分配的算法做深入了解的基础上，发现已有的异构多核处理器上任 务分配算法的诸多问题。本文认为，当前异构多核处理器上任务分配研究存在着 表现任务性质不足，周期任务分配的算法应用范围不广以及移植困难等缺点。因 此，必须充分考虑实时任务的性质，使用新的模型进行表达，并寻找基于新模型 的易用算法，完善该方面的研究。 本文首先提出了一种基于周期任务的异构多核多帧实时任务模型，并在固定 优先级调度的前提下，利用非线性规划对新模型进行数学上的描述。同时从非线 性规划的性质入手，在理论上证明新模型的优势，提出了基于该模型的异构多核 周期多帧任务分配算法。本文的主要工作内容如下： 1 、对基本理论进行研究和分析。对单核处理器任务调度、同构多核处理器任 务分配与调度以及异构多核处理器任务分配与调度的概念进行研究，分析上述系 统的模型建立目的、方法和算法设计，总结模型的不足和算法的缺陷。 2 、建立新的任务研究模型。异构多核多帧任务模型。该模型充分考虑计算系 统的多核处理器异构特征、任务多帧的事实，更全面的展现了任务的性质。对具 有a m ( a c c u m u l a t i v e l ym o n o t o n i c ) 性质的异构多核多帧任务模型，利用非线性 规划描述任务分配问题，并通过非线性规划的性质证明了新模型的全面性与一般 性。利用文献 3 】 4 1 在单核处理器上多帧实时任务调度结果，针对异构多核多帧任 务设计具体的遗传算法。 3 、建立异构多核任务分配评估系统及仿真实验。针对目前异构多核处理器任 务分配问题研究未有统一的平台和度量标准，旨在建立一种易扩展、易使用的评 估系统，为日后相关研究提供帮助。同时为验证理论结果和算法性能，参考文献 5 幕于岗期任务的异构多核多帧任务分配算法研究 6 1 7 1 的任务生成方法模拟实际任务集，进行可分配性仿真实验。 4 、一般异构多核任务模型的建立与分配算法研究。对不能确定任务的全部先 验知识，以及不满足a m 性质的任务进行分析，通过非线性规划进行描述，并设 计遗传算法解决，最后通过仿真实验验证理论分析的结果和算法性能。 据此，本文结构安排如图1 1 所示，分5 章展开。 厂翮鎏缀芬吣 模型发展与研究基础 相关研究 “2 “”一” 模型与分配算法研究模型与分配算法研究伏2 ”“ i7 7 一 异构多核任务分配、 评估系统 验证 、- 、， 图1 1 论文结构图 第l 章绪论。阐述本论文研究的背景和意义，异构多核处理器上任务分配的 研究历史与动态、当前流行的算法及存在的主要问题，最后指出论文的主要工作 和总体结构。 第2 章异构多核任务分配相关研究。介绍本文的研究基础，包括异构多核处 理器上任务分配相关的任务模型，非线性规划的基本理论以及遗传算法的简介。 其中任务模型以经典的周期任务为出发点，讲述该模型在两方面的扩展：考虑异 构系统实际的异构多核实时任务模型和引入多帧性质的多帧实时任务模型，从不 同的角度扩大了周期任务的描述范围，体现了计算机任务的更多性质，提高了实 际系统分配与调度能力的提高。 第3 章异构多核周期多帧任务模型与分配算法研究。建立综合考虑异构实际 系统和多帧现实性质的异构多核多帧任务模型，给出形式化定义，对具有a m 性 质的异构多核多帧任务，通过实际例子说明新模型更全面的描述能力，利用非线 性规划的描述证明新模型的优势，得到可以分配更多任务集的结论。之后设计遗 6 硕f j 学位论文 传算法，为解决以该模型为基础的异构多核多帧任务问题提供思路。 第4 章异构多核任务分配评估系统。为验证第3 章的结论，同时为推广异构 多核任务分配问题评估平台，建立异构多核任务分配评估系统。详细讲述系统框 架和关键模块，实现文中提及的遗传算法和m a t l a b 两步法，作为评估系统扩展的 尝试。同时，利用该系统通过仿真实验对第3 章的结论进行验证，并分析遗传算 法的性能。 第5 章非a m 异构多核多帧任务模型与分配算法研究。给出不能确定任务先 验知识和不满足a m 性质的异构多核多帧任务的建模方法，给出模型的形式化分 析和可分配性研究，是第3 章的扩展。并通过理论和实验证明考虑多帧的异构多 核任务更全面的体现了任务性质，为实际系统带来了更高的分配成功率。 之后是全文的总结。总结本文的研究成果和存在的问题，并对将来研究的方 向进行展望。 最后附上参考文献和致谢。 1 4 ，j 、结 本章阐述了异构多核多帧任务分配算法的研究背景和意义，对课题研究趋势 和现状进行了介绍。在此基础上总结了课题研究的关键问题，并对现有算法的不 足进行说明。之后给出论文主要工作和章节结构。 7 基f 周期任务的异构多核多帧任务分配算法研究 第2 章异构多核任务分配相关研究 上一章介绍了任务分配与调度研究的现状和趋势，异构多核处理器系统上的 任务分配问题是异构计算系统任务调度的首要问题，目前的研究方法多样，得到 了广大学者的关注。本章介绍异构多核处理器上任务分配的相关研究。以经典的 周期任务为基础介绍现有的任务模型，通过多媒体任务的特征引出多帧实时任务， 给出多帧任务的实例。利用非线性规划形式，对在周期任务基础上扩展出来的异 构多核任务模型进行描述。最后对遗传算法的要素和基本流程进行介绍。 2 1 任务分配问题的数学描述 2 1 1 异构多核任务分配 定义2 1 ：在上述( 见1 2 1 ) 假设下的计算机任务称为周期任务，可以用二 元组表示( c ，丁) ，其中c 表示该任务的执行时间，丁为周期【2 1 。 对于在单处理器上的朋个周期任务f ，( e ，z ) ，o f 玎一1 ，它们对处理器的穷 尽程度称为处理器利用率，如式2 1 所示【2 】： j ，一i ，1 u ：y 蔓 ( 2 1 ) 备7 = 定理2 1 ：对于固定优先级的刀个周期任务，在单处理器上利用率上界如式 2 2 所示1 2 j ： 刀( 2 1 抽一1 ) ( 2 2 ) 定理2 1 说明，在单处理器下的疗个任务，其利用率小于该界时是可以调度 的。 在异构多核处理器平台上讨论的任务分配问题，是将上述周期任务推广到异 构多核平台。 定义2 2 ：异构多核实时系统是指给定一组周期任务和组异构处理器，并 确定每个任务在每个处理器上的相应利用率。任务分配是确定是否可以将这些任 务指定在相应处理器上执行，使得每个任务得以完成，每个处理器均可调度分配 在其上的若干任务，同时在可分配的基础上寻求最优( 较优) 分配方案【1 3 】1 1 4 1 。使 用下面的三个参数对上述系统进行描述。 处理器：一组处理单元，我们均作为异构处理器，个数为脚； 任务：在上述处理器上运行的任务，个数为”； 利用率矩阵：利用率矩阵是一个疗聊矩阵，记为刁，其中巩就表示任务f 在 处理器，上的处理器利用率( o s f 玎一1 ，o m 一1 ) ，【o ，1 】u o o ) ，若f 任务不 能在处理器上运行则仉卜。 r 硕i j 学位论文 这个模型中，异构的性质是通过同一任务在不同处理器上的执行时间( 利用 率) 不同来体现的。 异构多核任务分配问题已经被证明为n p 完全问题f 1 3 】【14 1 。 2 1 2 多帧实时任务 定义2 1 的周期任务是任务调度相关研究的基础，然而认为任务执行始终是 最差运行时间未免过于悲观。事实上，一些任务的执行时间并不是一成不变。最 为典型的为多媒体任务，如一个m p e g 数据流一般由三种帧( 帧，b 帧，p 帧) 组成：佃召p b b ，而且一般情况下二帧的数据量远大于尸帧，而 帧或p 帧 的数量又远大于b 帧【3 】【4 】f 2 2 1 。文献【3 】对电影终结者1 的主演施瓦辛格一个骑 摩托车的视频片段进行统计，如表2 1 所示。 表2 1m p e g 视频片段统计 n a m e b i k e m p e g 根据这种情况，假设任务的执行时问不再是一个单一的最大执行时间，而是 由几个执行时间值组成的一个执行时间向量，代表了该任务的固有执行模式。周 期性执行的这种实时任务模型称为周期多帧任务模型。 定义2 3 ：多帧实时任务为一个元组( c ，尸) ，其中c 为任务的固定执行模式， 个执行时间( c o ，c 1 ，c - 1 ) ，p 为任务的执行周期f 3 】【4 】【2 2 1 。任务的第f 帧执行时间 为c ( 卜1 ) “o d ，f l 。 当= l 时，该模型就是一般( 定义2 1 ) 的实时任务。 定义2 4 ：对于一组执行时间数组为( c o ，c 1 ，c _ 1 ) 的周期多帧实时任务，如 果j 朋【o ，一1 】，使得v f ，【o ，一1 】式2 3 成立【3 ，4 ，2 2 】： m + ii + i y c ( 删y c ( m 甜 ( 2 3 ) j-