（计算机应用技术专业论文）多处理器系统任务调度研究.pdf

a 南京邮电大学 硕士学位论文摘要 作 者：巡级硕士研究生奎握 指导教师：姚放吾教授 题目：多处理器系统任务调度研究 英文题目：r e s e a r c ho ft a s ks c h e d u l i n gi nm u l t i p r o c e s s o rs y s t e m 主题词：多处理器系统，任务调度，蚁群算法，截止期，异构 k e y w o r d s ：m u l t i p r o c e s s o rs y s t e m ，t a s ks c h e d u l i n g ，a c o ，d e a d l i n e ， h e t e r o g e n e o u s 南京t 1 1 ：1 u 人学坝t ： o i 究生学位论义 摘复 摘要 目自，j ，多处理器系统己成为计算机领域中的研究热点，随着它的应用领域越来越广泛， 其复杂性也在不断增加，所处理的任务也越来越复杂，在这样的环境下，对任务调度提出了 更高的要求。 多处理器系统任务调度是n p 完全问题，改进算法的效率并构建任务调度实现机制成 为研究重点。大多数实时多处理器系统的动态调度算法都是针对同构系统提出的，对实时 异构系统的动态调度算法研究的比较少。 本文研究了最初用于处理组合优化问题的蚁群算法( a n tc o l o n yo p t i m i z a t i o n a l g o r i t h m ，a c o ) ，并用其解决多处理器系统的任务调度问题。在基本蚁群算法的基础上， 考虑了带截止期的多处理器实时异构系统的特点，结合任务和处理器各个属性，设计新的 任务选择和处理器分配策略，以及信息素更新策略。该算法能够满足任务问的优先约束关 系以及截_ l e 期的限制，取得较短的调度长度，并且具有较好的收敛性。 为了验证该蚁群算法解决调度问题的优点，本文用m i c r o s o f tv i s u a lc + + 6 0 对任务模 型进行实验，将得到的数据同其它的调度算法进行比较，实验证明本文的算法是一种求解 多处理器系统任务调度问题的有效算法。 关键词：多处理器系统，任务调度，蚁群算法，截止期，异构 a b s t r a c t n o w a d a y s ，m u l t i p r o c e s s o rs y s t e mb e c o m e sah o tr e s e a r c ha r e ai nt h ef i e l do fc o m p u t e r s a si t sa p p l i c a t i o nf i e l d sb e c o m em o r ea n dm o r ew i d e s p r e a d ，i t sc o m p l e x i t yi sr a i s i n ga n di t s t a s k st ob ep r o c e s s e db e c o m em o r ea n dm o r ec o m p l i c a t e d u n d e rs u c hac o n d i t i o n ，t h em u c h h i g h e rr e q u e s ti sb r o u g h tu pf o rt a s ks c h e d u l i n g i ti san pc o m p l e t ep r o b l e mt od e a lw i t ht a s k s c h e d u l i n gi nm u l t i p r o c e s s o rs y s t e m i m p r o v i n gt h ee f f i c i e n c yo ft h ea l g o r i t h ma n dc o n s t r u c t i n gt h ei m p l e m e n t a t i o nm e c h a n i s m b e c o m e st h er e s e a r c hi s s u e m a n yd y n a m i cs c h e d u l i n ga l g o r i t h m si nm u l t i p r o c e s s o rr e a l t i m e s y s t e ma r ep r o p o s e df o rt h ei s o m o r p h i cs y s t e m ，h o w e v e rt h e r ea r ef e w e rr e s e a r c h e sa b o u tt h e d y n a m i cs c h e d u l i n ga l g o r i t h m si nr e a l t i m eh e t e r o g e n e o u ss y s t e m s t h i st h e s i ss t u d i e sa b o u tt h ea n tc o l o n yo p t i m i z a t i o na l g o r i t h m ( a c o ) w h i c hi sa p p l i e dt o ， r e s o l v ec o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s f i r s t ，a n du s ei tt or e s o l v et a s ks c h e d u l i n gi n m u l t i p r o c e s s o r c o n s i d e r i n g t h ef e a t u r eo ft h e m u l t i p r o c e s s o r r e a l t i m e h e t e r o g e n e o u s s y s t e m sw h i c hh a v ed e a d l i n e sa n dc o m b i n i n ga t t r i b u t e so ft h et a s k sa n dt h ep r o c e s s o r s ，t h i s t h e s i sd e s i g n san e wp o l i c yo ft a s k s e l e c t i n g ，p r o c e s s o ra s s i g n i n ga n dp h e r o m o n eu p d a t i n g b a s e do nt h eb a s i ca c o t h en e wa l g o r i t h mc a nm e e tt h ep r i o rc o n s t r a i n ta m o n gt h et a s k sa n d t h ed e a d l i n e s ，g e t sas h o r t e rs c h e d u l i n gl e n g t h ，a n dh a v eab e t t e rc o n v e r g e n c e i no r d e rt ov e r i f yt h ea d v a n t a g eo ft h ea c ot or e s o l v et h es c h e d u l i n gp r o b l e m s ，t h i st h e s i s a p p l i e sm i c r o s o f tv i s u a lc + + 6 0t o t e s tt h et a s k sm o d e la n dc o m p a r e st h er e s u l t sw i t ho t h e r a l g o r i t h m s t h et e s ts h o w st h a tt h ea l g o r i t h mp r o p o s e di nt h i st h e s i si sa ne f f e c t i v ea l g o r i t h mt o r e s o l v et h et a s ks c h e d u l i n gi nm u l t i p r o c e s s o rs y s t e m k e y w o r d s ：m u l t i p r o c e s s o rs y s t e m ，t a s ks c h e d u l i n g ，a c o ，d e a d l i n e ，h e t e r o g e n e o u s 南京i f | | ；i u 人学顺i j 州，生学位论义 日录 目录 第一章绪论1 1 1 研究背景：1 1 2 论文所要做的工作：2 1 3 论文的组织结构3 第二章多处理器任务调度问题一4 2 1 多处理器系统的发展及存在问题4 2 2 多处理器任务凋度问题6 2 2 1 调度问题的定义6 2 2 2 调度问题的模型6 2 2 3 调度求解过程的分析9 2 7 4 调度算法的评价9 2 2 5 调度方法的分类1 0 2 2 6 调度问题的研究发展及成果1 l 2 2 7 新的算法和理论1 2 2 3 本章小结1 5 第三章蚁群算法的起源及其原理1 6 3 1 大自然中蚁群的觅食行为及特征1 6 3 2 蚁群算法的思想及其发展1 9 3 3 蚁群算法的描述2l 3 4 蚁群算法的实现步骤2 3 3 5 蚁群算法参数讨论2 5 3 6 蚁群算法的优缺点及改进2 6 3 7 蚁群算法的研究现状及应用2 9 3 8 本章小结2 9 第四章蚁群算法用于解决调度问题3 0 4 1 带截止期的多处理器实时异构系统3 0 4 2 用蚁群算法解决多处理器调度问题3 3 4 2 1 任务的选择概率公式设计3 3 i i i 南京邮i u 人学f 嗍i j 研究生学位论义 4 2 2 处理器的选择概率公式设计 4 2 3 任务信息、素的更新 4 2 4 处理器信息素的更新 4 2 5 算法的实现步骤和i 流程图 。： 4 2 6 算法参数的讨论 4 3 实验4 0 4 3 1 实验一：任务调度的求解一4 0 4 3 2 实验二：各个参数对算法性能的影响4 1 4 3 3 实验三：算法参数的确定一4 6 4 3 4 实验四：与其它算法的比较一4 7 4 。4 本章小结4 9 第五章总结和展望5 0 5 1 研究总结5 0 5 2 研究展望5 0 致谢5 2 参考文献5 3 作者在硕士研究生期| 日j 发表的论文一5 6 南京l l | | ；l u 入学顾i j 川：究生学位论文第一章绪论 第一章绪论 本文针对当前多处理器系统任务调度算法的现状，分析其局限性，研究了正在发展的 几种智能优化算法，将蚁群算法应用于实时异构的多处理器系统，并对其进行改进以求得 更优秀的调度性能。本章将简要描述解决组合优化问题的几种智能算法，说明蚁群算法解 决调度问题的可行性，在本章最后列出了本文的组织结构。 1 1 研究背景 组合优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 问题的目标是从组合问题的可行解集中求出最 优解，通常可描述为：令q = “，s ：j 。 为所有状态构成的解空间，c ( s ，) 为状态s j 对应 的目标函数值，要求寻找最优解j 木q ，使得对于所有的s ，q ，有c 幸) = m i n c ( s ，) 或 者m a x c ( s ，) 。由此可以看出最优解的定义，即使某线性规划的目标函数达到最优值( 最 小值或最大值) 的任一可行解，都称为该线性规划的一个最优解。线性规划的最优解不一 定唯一，若其有多个最优解，则所有最优解所构成的集合称为该线性规划的最优解域。组 合优化往往涉及排序、分类、筛选等问题，它是运筹学的一个重要分支。 典型的组合优化问题有旅行商问题t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) 、加工调度问题 ( s c h e d u l i n gp r o b l e m ，如f l o w s h o p ，j o b s h o p ) 、0 一l 背包问题( k n a p s a c kp r o b l e m ) 、装箱 问题( b i np a c k i n gp r o b l e m ) 、图着色问题( g r a p hc o l o r i n gp r o b l e m ) 、聚类问题( c l u s t e r i n g p r o b l e m ) 等。这些问题描述非常简单，并且有很强的工程代表性，但最优化求解很困难， 其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致根本不可 能在现有计算机上实现，即所谓的“组合爆炸”。正是这些问题的代表性和复杂性激起了 人们对组合优化理论与算法的研究兴趣。自然界的许多自适应优化现象不断给人类以隐 喻：生物体和自然生态系统可以通过自身的演化就使许多在人类看来高度复杂的优化问题 得到令人满意的解决，这种能力让最好的计算机程序也相形见绌。伴随着模拟自然与生物 机理为特征的仿生优化算法时代的悄然兴起，一些仿生优化算法已在经典n p 完全问题的 求解和实际应用中显示出了强大的生命力和进一步发展的潜力。 智能算法是求解组合优化问题的比较新的方法，智能优化算法要解决的一般是最优化 问题。优化算法有很多，经典算法包括线性规划，动念规划等；改进型局部搜索算法包括 ! 要塞些! ! 叁兰丝坐丛! ! 竺兰丝堡墨笙二至堑堡 爬山法、最速下降法等；指导性搜索法包括模拟退火、遗传算法以及禁忌搜索等；系统动 态演化方法包括神经网络，混沌搜索等。优化思想罩面经常提到邻域函数，它的作用足指 出如何由当日，j 解得到一个( 组) 新解。其具体实现方式要根据具体问题分析来定。一般而 言，局部搜索就是基于贪婪思想利用邻域函数进行搜索，若找到一个比现有值更优的解就 弃i 寸者而耳义后者。但是，它一般只可以得到“局部极小解”，而模拟退火、遗传算法、禁 忌搜索、神经网络等从不同的角度和策略实现了改进，取得较好的“全局最小解”。 模拟退火、遗传算法、禁忌搜索、神经网络在解决全局最优解的问题上有着独到的优 点，并且它们有一个共同的特点：都是模拟了自然过程。模拟退火思路源于物理学中固体 物质的退火过程，遗传算法借鉴了自然界优胜劣汰的进化思想，禁忌搜索模拟了人类有记 忆的智力过程，神经网络更是直接模拟了人脑。它们之间的联系也非常紧密，比如模拟退 火和遗传算法为神经网络使用更优良的学习算法提供了思路。把它们有机地综合在一起， 取长补短，性能将更加优良。这几种智能算法有别于一般的精确计算的程序，尤其是人工 神经网络，是对计算机模型的一种新的诠释，按照这种思想来设计的计算机有着广阔的发 展前景。 蚁群算法a c o ( a n tc o l o n yo p t i m i z a t i o n ) ，又称蚂蚁算法，是一种用来在图中寻找优 化路径的机率型算法。它由m d o r i g o 等人提出【1 j 【列，其灵感来源于蚂蚁在寻找食物过程 中发现路径的行为。它是一种求解组合最优化问题的新型通用启发式方法，是一种模拟进 化算法，初步的研究表明该算法具有许多优良的性质。将蚁群算法设计的结果与遗传算法 设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的 有效性和应用价值。该方法具有j 下反馈、分布式计算和富于建设性的贪婪启发式搜索的特 点。 本文要研究的多处理器调度问题属于组合最优化问题，在计算机科学领域虽说不是一 个很新的课题，但它还一直是个远远没有得到很好解决的问题，m o k 和d e r t o u z o s 在1 9 8 3 年指出m s p ( m u l t i p r o c e s s o rs c h e d u l i n gp r o b l e m ) 是：- - 个n p 完全问题f 3 】不存在一个理想的 调度算法。因此，可以用蚁群算法来求解多处理器调度问题，并期望可以耳义得较为优秀的 可行解。 1 2 论文所要做的工作 ( 1 ) 分析了多处理器系统的复杂性，以及任务调度的过程，研究了现有理论成果的优 点和不足。 南京l | l i i l u 人学顺i ：研究生学位论文 第一章绪论 ( 2 ) 分析了蚁群算法，将蚁群算法引入多处理器任务调度问题，尤其是用来解决目前 研究较少的实时异构多处理器系统中的任务凋度问题，结合实际问题建立模型，设计了算 法的公式； ( 3 ) 通过仿真实验分析算法参数的取值，以求得具有更高效率和更好性能的算法。 1 3 论文的组织结构 第一章介绍了论文的研究背景，分析了课题的可行性； 第二章介绍了多处理器系统的发展及其任务调度算法的研究现状，给出了一些相关的 定义和概念，为蚁群算法的引出奠定了基础； 第三章介绍了蚁群算法的思想起源，并且结合旅行商问题对蚁群算法进行了具体的叙 述，讨论了该算法的优点和局限性； 第四章将蚁群算法应用于带截至期限的实时异构多处理器系统中，用来解决其任务调 度问题，为其设计了可行的公式，并通过仿真实验讨论了参数的取值，最后同其它算法做 出比较； 第五章是总结和展望。 南京l | j i j 也人学顺一i ：仞f 究生学位论义第二章多处理器任务调度问题 第二章多处理器任务调度问题 本章将介绍多处理器任务调度问题的发展，给出它的一些基本的相关知识，介绍一些 主要的定义和概念，提出本文所要解决的目标，为说明本文的工作做好铺垫。 2 1 多处理器系统的发展及存在问题 随着计算机的发展，半导体集成电路芯片制造工艺先后经历从单处理器片上系统 ( s o c ) ，多处理器片上系统( m p s o c ) ，到片上网络( n o c ) 的发展过程。s o c 计算能力不强， 一般只用于控制，很难适应复杂的工程计算。m p s o c 具体来讲指的是在单一芯片上集成 多个处理器的复杂s o c ，一般由多个处理器单元、专用功能模块甚至混和信号电路组成， 构建一个复杂的集成计算系统，实现处理器在计算性能、功耗、实时性、成本之间的协调 【4 j 。它的结构如图2 1 ，m p s o c 不是简单的处理器的集合，它更注重处理器之i i b j 的结构和 平衡应用的需求。 p r o c e s s o ra s i cd s pa s i c iili i n t e r c o n n e c t i o nn c t w o r k i ili p r o c e s s o r m e m o r y a s i cp r o c e s s o r 图2 1m p s o c 的一般组成 n o c 实际是基于网络通信的m p s o c ，它把计算机网络技术移植到芯片系统中来，用 路由和报文交换技术代替传统的总线技术完成通信任务。 本文要研究的对象是多处理器系统( m p s ) ，它是随着微处理机的性能迅速增强，新的 快速网络不断出现，可移植的高可靠性通信软件的产生而出现的种新的计算机系统。通 过高速网络，将许多处理单元连接起来构成个计算系统的做法变得可行，并且非常容易。 图2 2 是一个s u n 公司的多处理器系统。本文研究的内容不仅仅局限于一个芯片上，它 具有较普遍的应用，也适用于m p s o c 和n o c ，主要区别是路由机制的差别。 4 南京邮l u 人学帧i - g f 究生学位论文第二章多处埋器任务调度问题 图2 2s p a r cv 9 多处理器系统 目前，多处理器系统己成为计算机领域中的研究热点。处理器的拓扑结构、并行算法 的设计、任务的划分和同步、任务的调度是多处理器系统研究的几个主要问题。这些问题 中，多处理器任务调度问题m s p ( m u l t i p r o c e s s o rt a s ks c h e d u l i n gp r o b l e m ) 是一个重要的 问题，它是限制分布计算效率的瓶颈，是多处理器系统设计的关键问题之一，也是本文所 要研究的问题。在这样的多处理器环境下，进程调度的复杂性增加了，调度算法除了需要 满足系统的实时要求以外，还需要利用多处理器平台的性能。任务调度是将一组映射到多 处理器上，满足实时性、功耗与成本等条件的约束。很多任务调度的研究是基于抽象模型 给出任务的形式化定义，然后进行调度策略与算法的设计。各种因素决定了多处理器任务 调度问题属于复杂优化问题，是n p 完全问题。因此寻求一种在有限时间内求得可行解的 优化算法是进行处理器实时调度的需要，改进算法的效率并构建任务调度实现机制成为研 究重点。良好的调度算法可以充分运用系统中每个处理器的计算能力，提高并行分布计算 的效率。同时，体系结构上的异构性使得多处理器任务调度特别需要关注任务在不同体系 结构的处理单元上执行时的特点，并在调度实现上提出了很多新的挑战。任务调度这一步 骤对发挥系统的并行计算能力、提高系统吞吐量具有非常重要的影响。 在一个多处理器系统中，大部分处理器在大部分时徊j 内都处于低利用率状态【川。加州 大学b e r k e l e yn o w 研究小组的研究结果表明：即使在每天下午最繁忙的时候，平均也有 近6 0 的结点处于空闲可利用状念。多处理器系统中这些闲置结点，如果不加以合理的 利用的话，其c p u 等计算资源就白白的浪费了。而实际上在一个局域网或高速网络内， 5 堕窒! ! ! ! ! ! 垫叁兰堡生丛塑圭兰垡堡兰笙三至童竺墅堡箜塑些塑望 在适当的任务调度机制的控制与管理下，可以充分利用这些闲置结点来执行大规模并行计 算，充分利用系统资源。另外很可能出现负载不平衡的现象，当一些处理器处于重载时， 另一些处理器却处于轻载或闲置状态，这种负载的不平衡将直接影响多处理器系统的整体 性能。良好的调度算法可以充分运用系统中每个处理器的计算能力，极大的提高处理器的 利用率，避免有的处理器没有可执行的任务，而有的处理器等待执行的任务排起了长队， 致使总任务的执行时i 白j 较长。这就有必要在多处理器系统中，按任务的静态分配和动态调 度要求做到负载平衡，以提高系统性能。还有的多处理器系统中，任务调度机制不合理， 致使许多任务不能够被成功调度，调度成功率较低，或者调度长度较长。可见，任务调度 策略是影响多处理器系统性能的关键问题之一，为了最大限度的提高系统的资源利用率和 减少任务的平均响应时阳j ，必须采取有效的任务调度策略，合理地分配子任务到各个处理 器上，保证总任务在最短的时问内完成。 2 2 多处理器任务调度问题 2 2 1 调度问题的定义 在多处理器系统中，一个程序可以看作一个任务集，这些任务可以并行或串行，任务 之间有一定的优先次序约束关系。任务调度主要是对建立的抽象任务模型进行分析，设计 合理有效的算法，调度问题的目标是在满足一定的指标和优先约束关系的前提下，将可并 行的任务按适当的分配策略确定一种执行顺序，合理分配到各处理器上有序执行，以达到 减少总的执行时日j 的目标。因此提高算法的执行效率和计算性能是一个重要问题。 2 2 2 调度问题的模型 多处理器任务调度问题常用有两种模型： 1 周期类相关模型 ” 最早对任务调度进行研究的是l i u 和l a y l a n d ，他们提出的周期任务模型【6 1 抽象层次 较高，可扩展至多处理器环境下的实时异构任务模型，被很多文章改进使用。b a r u a h 描 述了一种多处理器周期任务调度模型【7 1 ，其主要内容如下： ( 1 ) 处理器集合用兀表示，任务集合用r 表示： ( 2 ) 用一个( 1fl 1 f 1f ) 大小的实数矩阵 “， 来表两处理器用于执行第f 个任务所需 6 南京l l l | j l u 人学f 砚，j j f 卅歹生学位论文第二章多处理器任务调度问题 要的执行能力比例，如果i 任务不能在处理器上执行，则“u = ； ( 3 ) 任务在处理器上执行的速度用速率矩阵 表示，一，表示处理器执行任务i 的速度，如果i 任务被分配到处理器上执行，则其每个作业将执行( e ，1 ，) 时间单位； ( 4 ) 计算平台的异构性通过任务在不同处理器上执行时问的不同来描述多处理器。 上述的任务形式化模型有一些重要的假设，即任务的独立性、任务划分执行和无通信 开销等，在此不再赘述。 在本文中将要用到的模型是基于文献【8 j 中的模型建立的，文献【8 1 中的模型如下： 设系统中有m 个处理器( m 1 ) ，记为p 。，p ：p 。，f 表示任务集，于是，任务的调度 模型可以表示为如下形式： ( 1 ) v t f ，均可表示成一个多元组啡，且 钟2 ( 口t ，厂t ，d t ，v t ，e t t ) 其中口t ：任务t 的到达时f 刚，口t o ： 厂t ：任务t 就绪时l 日j ，y t a t ； d 。：任务的截止期，d 。o ； v t ：任务所具有的不同逻辑版本的数目，同时也表示了任务的服务等级数； e t r ：任务的运行时l 日j 。 ( 2 ) 任务是不可抢占的，且相互问是独立的； ( 3 ) 任务不具有并行性： ( 4 ) 除了处理器以外，任务还可能需要其他一些资源，如某些数据结构、变量及缓冲 区等，每个任务对资源的访问方式包括互斥访问和共享访问两种。 2 d a g 类相关模型 实时系统中可用一个有向无环图d a g ( v ，毋对任务进行建模，其中v 是节点的集合， 用于表示分配的任务，而e 是一组有向边，用于表示节点问的优先约束或通信丌销。 以下为一个d a g 模型【9 】： 用一个有向无环图d a g ( v ，e ，s o u r c e n o d e ，s i n k n o d e ) 对任务进行建模，其中矿是 顶点的集合，每一个顶点表示一个待调度的任务( 1 明= 门) ，e 是有向边的集合，用于表示任 务间的优先约束关系和通信丌销，边( 甩，门，) 限定任务的数据依赖关系，任务，z ，是前驱， 7 南京i u 人学坝i 州歹c 生学位论文 第- 二辛多处理器任务训发问题 任务门是后继，只有f j ，j 驱任务执行完毕，后继任务爿川以执行。边上的权值表示两个任 务j 丑j 的估计通信量。s o u r c e n o d e 是没有自，j 驱的任务，s i n k n o d e 是没有后继的任务，它们 分别被称为入口和出口任务，任务图中必须只包含惟一的入口和出口任务。运行环境包含 多个处理单元以及处理单元之l 日j 的拓扑连接。 处理单元集q ( 蚓= 腕) 中的处理单元可以足通用的处理器c p u s 或硬件a s i c s 等，任 务集v 在处理器单元q 上的执行矩阵w = v xq ，w i j 表示任务胛，在处理器单元p ，的估 计执行时问。处王里单元之f n j 的拓扑连接支持处理单元f s j 的通信，假定系统中通信设备是专 用通信硬件，即通信和计算可以并行进行。设通信设备集合为b ，处理单元集q 中处理 单元之l 、日j 的通信设备映剩函数为，( p ，只) ，规定在尸= e 时，尸，e ) = 0 ，任务分配 在不同处理器上时通信时l 日j 为c 一其值由处理单元之l l 目j 的拓扑连接决定。基于d a g 任 务调度问题可以描述为将任务分配到处理器并协调执行，使得在满足实时性约束条件下， 任务的整体执行时间、功耗或其他指标最优，它同样是n p 完全问题。 在上述的d a g 模型中有如下定义： ( 1 ) 在为任务分配处理器之前，需要用到任务的执行时i 日j ，其初始值等于该任务在所 有处理器上的平均执行时阳j ，计算方法如公式( 2 1 ) ： i n i ( r f ) = a v e r a g e w ( 2 1 ) q q 当任务门，调度后被分配到处理器p 。时，r ，= w l 2 ； ( 2 ) t l e v e l ( n ，) 是从任务图的入口任务到任务疗，的最长路径的长度( 不包含任务门，本身 的执行时f l 百j ) ，设p r e d ( n ，) 是任务刀，的酊驱集，t l e v e l ( n ，) 的计算方法如公式( 2 2 ) ： ( 2 2 ) ( 3 ) b l e n g t h ( n ，) 是从任务，z ，到出口任务的最长路径的长度( 包含任务船，本身的执行时 间) ，设s u c c ( 门，) 是任务门，的后继集，b l e n g t h ( n ，) 的计算方法如公式( 2 3 ) ： ( 4 ) 关键路径( c r i t i c a lp a t h ) ：任务图中的最长路径，是组成图中最大的执行代价和通 荔 = 蓉 跏 w 此 ， 、 赫 箸 馏馏 i 订京i l l l ：i u 人学f 映i j 究生学位沦义 筇二章多处理； 任务训度问题 信代价的任务集和边集，关键路径长度i “， 计算方法如公式( 2 4 ) ： l 。，i = m a x t l e v e l ( n ，) + b l e v e l ( n ) ) 一r ( 2 4 ) ( 5 ) 就绪任务( r e a d yt a s k s ) ：如果任务_ 的所有i ，j 驱任务都已经执行完毕或者没有i n 驱任务，则任务刀，属于就绪任务。任务图调度f j 的就绪任务集合中仅包含入口任务 s o u r c e n o d e 。 ( 6 ) 调度长度( s c h e d u l el e n g t h ) ：任务图中的所有任务凋度完毕后，出口任务的调度完 成i t 寸i h j 。 基于d a g 的任务调度问题可以描述为将任务分配到处理器并协调执行，使得在满足 实时性约束条件f 任务的整体执行时间、功耗或其他指标最优，它同样是n p 完全问题。 2 2 3 调度求解过程的分析 多处理器系统的求解过程大体可分为以下步骤【5 1 ： ( 1 ) 任务分解，是指把一个大任务划分为可并行执行的相关任务的过程； ( 2 ) 任务调度，是指将这些子任务分配到各个并行处理器上，并安排处理器上任务的 执行次序的过程： ( 3 ) 并行运算，是指这些任务在被分配的处理器上进行并行运算； ( 4 ) 解的合成，是指将任务的运行结果合成为整个大任务的运行结果。 其中最重要的就是调度算法的设计，需要满足不同的要求，提高任务调度成功率和处 理器利用率，减少调度时间等，本文主要研究的是任务调度。 2 2 4 调度算法的评价 评价一个算法的性能主要有算法的效率、调度成功率、调度长度等。 ( 1 ) 算法的效率：主要以算法的时间复杂度来衡量： ( 2 ) 调度成功率：定义为可被算法成功调度的任务集数目与总共待调度任务集数目的 比值； ( 3 ) 调度长度( s c h e d u l el e n g t h ) ：定义为所有任务调度完毕后，最后一个结束的任务的 完成时间。 9 南, t ! i i t l , i 也人学顺i j 研究生学位论文 笫- 二章多处理器任务调度问题 2 2 5 调度方法的分类 从不同的考虑因素出发，多处理器系统中的任务调度有不同的分类方法。 ( 1 ) 静态调度和动念调度 按照任务是确定还是非确定的可以将调度分为静念调度和动念调度。静念调度是指在 程序编泽时，调度的任务和它们之问的相关关系已经完全确定，如：任务的处理时间、通 信和同步要求、数据依赖等，因此任务的执行处理器及执行时序也可以确定；动态调度是 指在程序运行前，只有部分任务是已知的，随着系统的执行，任务会动态增减，需要根据 当自，j 任务调度及系统执行情况，临时决定每个任务的执行处理器及执行时序，它的丌销通 常比静态调度要大。静态调度又叫做确定性调度，而动态调度又叫做负载平衡。 ( 2 ) 集中式调度和分布式调度 按照调度程序的结构或调度程序所收集调度信息的范围可以将调度分为集中式调度 和分布式调度。集中式调度是指由一个处理器专门负责调度，它被称为中心调度器，其它 处理器把它们的状态信息传送给中，1 5 , 调度器，并由中心调度器做出调度决定，集中式凋度 实现比较简单，但是结点多的情况下，中心调度器会比较繁忙，而且它与各结点的通信会 成为瓶颈；分布式调度是指各个处理器根据局部范围内的一些调度信息来进行任务调度， 其最大优点在于具有良好的可扩展性，这种方式一般是动念的。 ( 3 ) 自适应调度和非自适应调度 按照调度程序的调度策略是否随系统状念信息变化而自动调整，可以将调度分为白适 应调度和非自适应调度。自适应调度是指程序可以根据前一段时间内的执行结果和当前系 统的信息自动修f 调度策略，它一般是动态的；非自适应调度是指一旦确定调度策略，那 么在并行程序执行过程中就固定地按照这些调度策略来进行任务调度，即使有新的任务产 生，也必须等到非执行状念时再修正调度策略，因此它的效率比较低。 ( 4 ) 抢占式调度和非抢占式调度 按照调度程序执行调度操作时是否允许任务抢占执行，可以将调度分为抢占式调度和 非抢占式调度。抢占式调度是指允许任务被中断执行而把它所在的处理器让给其它任务执 行，即改变了任务的执行时序：非抢占式调度是指不允许任务被中断，必须等到运行完毕 后刁释放该处理器。 ( 5 ) 最优调度和次优调度 按照任务调度目标的实现程度，可以将调度分为最优调度和次优调度。最优调度是指 以系统的最优调度为目标，获取系统的最高并行度：次优调度是指以达到用户要求为目标， 1 0 南京| | l | j 电人学坝l 研究生学位论文 第_ 二章多处理器任务训发问题 获取较高的并行度。所谓的最优和次优通常采用启发式算法得到问题的近似解。 ( 6 ) 迁移调度和非迁移调度 按照任务是否允许迁移执行可以将调度分为非迁移调度和迁移分配调度。非迁移调度 是指任务被分配到一个处理器上后就一直在那台处理器上运行直至完成，无论它所在的机、 器负载有多重，也无论有多少其它的处理器空闲，它都不能移动；迁移分配调度是指可以 。 更换任务的执行处理器，这种迁移调度策略能更好地平衡负载，但实现起来非常复杂。 ( 7 ) 基于共享存储的调度和基于分析i 存储的调度- 按照并行分布计算模型的存储器结构可以将调度分为基于共享存储的调度和基于分 稚存储的调度。基于共享存储的调度是指各个处理器共享存储区，一般不需要考虑通信延 迟：基于分佃存储的调度是指各个处理器分别拥有自己的存储区，它们之间的通信延迟使 得调度更为复杂，不过新的高速网络的不断出现；基于分布存储的调度显得越来越重。 2 2 6 调度问题的研究发展及成果 多处理器调度问题( m s p ) 是个n p 完全的组合优化问题，是计算机科学的一个热门的 研究领域。有许多专著和期刊专题讨论调度问题，大量的论文在许多计算机科学方面的期 刊上发表。长期以来对该问题的研究侧重于在满足时间复杂度的前提下获得近似最优解的 启发式算法，其中比较典型的有基于表调度技术的算法和基于遗传算法的算法。表调度算 法包含两个步骤：第1 步是根据优先级进行任务选择，第2 步是分配处理器，即将第l 步选择的任务调度到启发函数最小的处理器上去。不过这些算法大多集中在同构系统上， 已有的同构多处理器系统的列表调度算法有m c p ( m o d i f i e dc r i t i c a lp a t h ) t l o l ，d c p ( d y n a m i c c r i t i c a lp a t h ) i j 等，基于表调度技术的启发式算法尽管h , - t n 复杂度和空间复杂度都很好， 但是它的致命缺点是无法保证解的质量。基于遗传算法的启发式调度算法克服了表调度算 法的缺点，但遗传算法操作复杂，难以实现，实用性较差。所以寻求新的更加有效的调度 算法一直是广大学者关注的问题。 k r a m a m r i t h a 等人提出了针对动态实时多处理器调度的近视算法【1 2 】。它在传统的基 于启发式搜索的基础上，限定了在一次调度中被考虑的任务数，从而降低了算法的复杂度。 同时，该算法首次考虑了任务除了处理器以外还需其他资源的情况。在近视算法的基础上， g m a n i m a r a n 等人又提出了一种新的动态实b , - t 多处理器系统的调度算法【1 3 1 ，它利用了任务 的并行性来提高调度算法的性能。a m i t t a l 等人提出的实时多处理器系统中的集成动态调 度算法【1 4 】也是基于近视算法的，它是针对在实时多处理器系统中硬实时与软实时任务并 堕塞些! ! 叁兰丝! ! 竺壅竺堂垡堡苎丝三翌童竺些登堡箜塑堡囹望 存的情7 兄而提出的。在以上这些算法中，为任务分配处理器的策略是选择最早可运行的处 理器，这种处理器的选择方法将延迟未被渊度任务的可开始运行时间，从而可能会造成对 这些任务调度的失败，因此算法调度成功率不高。 在文献【8 】中考虑了任务的资源需求和处理器需求，提出了实时多处理器系统的节约算 法。文献【| 5 】对节约算法进行了扩展，使之能够用于异构多处理器系统和具有强实时和弱 实时任务的多处理器系统。文献6 】对近视算法和节约算法进行了改进，提出了分组适度 算法。其它的调度算法还有最早任务期限优先算法e d f ( e a r l i e s td e a d l i n ef i r s t ) 、最小剩余 时间优先算法l l f ( l e a s tl a x i t yf i r s t ) 、最迟丌| 始时间算法l s t ( t h el a t e s ts t a r tt i m e ) 和多 处理器截止期优先算法d o o m ( t h ed e a d l i n eo r d e r i n go v e rm u l t i p r o c e s s o r s ) 等。这些算法 各有优缺点，很难找到一个可以普遍应用并且具有较高性能的算法。 2 2 7 新的算法和理论 许多新兴学科都把各自领域的研究成果应用于解决调度问题，用以提高算法的性能、 可扩展性和可应用性，降低时l 自j 复杂度。为了应对这种挑战，人们提出了一些新的调度思 想，例如随机化方法和并行调度技术等，解决组合优化问题的一些比较新颖的算法或者理 论，也用来解决任务调度问题。比如模拟退火，遗传算法，禁忌搜索，蚁群算法等。这些 算法或理论都有一些共同的特性( 比如模拟自然过程) ，通称为“智能算法”。它们在解决 一些复杂的工程问题时大有用武之地。 下面概括介绍一下模拟退火，遗传算法，禁忌搜索这几种算法【1 7 】，蚁群算法将在下 章详细的介绍。 1 模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 1 8 】 模拟退火算法的依据是固体物质退火过程和组合优化问题之间的相似性。物质在加热 的时候，粒子问的布朗运动增强，到达一定强度后，固体物质转化为液态，这个时候再进 行退火，粒子热运动减弱，并逐渐趋于有序，最后达到稳定。 模拟退火的解不再像局部搜索那样最后的结果依赖初始点。它引入了一个接受概率 p 。如果新的解s 的目标函数f ( s ) l g n - 前i ns 的目标函数厂( s ) 更好，则p = l ，表示接受s 作 为新的当前解：否则，以概率p 接受s 为新的当前解。也就是说，模拟退火没有像局部搜 索那样每次都贪婪地寻找比现在好的点，目标函数差一点的解也有可能接受进来。随着算 法的执行，系统温度t 逐渐降低，最后终止于某个低温，在该温度下，系统不再接受变 化。值得注意的是，当t 为0 时，模