第10卷第2期 智能系统学报 Vol.10 No.2 2015年4月 CAAI Transactions on Intelligent Systems Apr.2015 D0:10.3969/j.issn.1673-4785.201503013 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150413.1505.001.html 基于动态任务调度的STDS算法设计研究 刘正 (哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001) 摘要：任务调度是计算机多核处理器系统获得高性能的关键，而现有的多核任务调度算法研究，大多侧重于静态 调度下的算法优化和负载均衡，对动态调度及动态负载均衡研究较少。针对动态调度，并结合异构多核的特点，提 出一种基于核负载均衡的动态任务调度算法STDS。算法通过合理设定调度粒度，降低调度频率，从而减少调度消耗 时间：根据异构多核处理器各核处理性能的差异，设置内核负载上下限值，控制内核负载保持在同一水平，以达到负 载均衡效果。算法依据等待时间长短、任务间通信大小和内核负载轻重因素对任务进行实时调度，并可通过实时因 子、负载因子等参数设置3种因素的影响比重，以满足系统的不同需求。仿真实验显示，在内核数目较多的系统中， STDS算法更加高效，在保证任务处理速度的同时有较好负载均衡。 关键词：动态任务调度：负载均衡：调度粒度：等待时间：异构多核系统 中图分类号：TP316.4文献标志码：A文章编号：1673-4785(2015)02-0324-09 中文引用格式：刘正.基于动态任务调度的STDS算法设计研究[J].智能系统学报，2015,10(2)：324-332. 英文引用格式：LIU Zheng.Research on STDS algorithm designing based on dynamic task scheduling[J].CAAI Transactions on In- telligent Systems,2015,10(2):324-332. Research on STDS algorithm designing based on dynamic task scheduling LIU Zheng (College of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China) Abstract:Efficient task scheduling is the key for multi-core systems to achieve high performance.However,most of the existing multi-core researches on task scheduling algorithms focus on algorithm optimization and load balancing under the static scheduling rather than dynamic scheduling and dynamic load balancing.Scalable task duplication based scheduling (STDS)is a new dynamic-balanced algorithm based on core load balancing.STDS was put for- ward specifically for dynamic scheduling and integrating the characteristics of heterogeneous multi-core.It shortens scheduling time by reasonably setting the scheduling granularity and reducing the frequency of scheduling.STDS sets the maximum and minimum ranges of the kernel load according to the different processing performance of each core of the heterogeneous multi-core processor,therefore controlling the core load at the same level and achieving the effect of load balance.The wait time of task and communications between tasks and kemnel load will be consid- ered together to pick up the most appropriate task during scheduling.The importance of each element can be adjus- ted by assigning another value to the real-time factor and load factor enabling it to adapt to various environment.The experimental results verified that the STDS algorithm is more efficient in the system with the most kernels.It also keeps a good load balance while maintaining the speed of task execution processing. Keywords:dynamic task scheduling;load balancing;scheduling granularity;waiting time;heterogeneous multi- core system 动态任务调度可以根据运行的时情况动态 收稿日期：2015-03-09.网络出版日期：2015-04-13. 基金项目：国家自然科学基金资助项目(61003036)：中央高校基本科研 地将任务分配到各个内核上，由于需要实时地收 业务费专项资金资助项目(HEUCF100606). 集、存储并分析状态信息，动态调度的实施有一 通信作者：刘正.E-mail:liuzheng528@hrbeu.cdu.cn
第 １０ 卷第 ２ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．２ ２０１５ 年 ４ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｐｒ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１５０３０１３ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１５０４１３．１５０５．００１．ｈｔｍｌ 基于动态任务调度的 ＳＴＤＳ 算法设计研究 刘正 （哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 １５０００１） 摘 要：任务调度是计算机多核处理器系统获得高性能的关键，而现有的多核任务调度算法研究，大多侧重于静态 调度下的算法优化和负载均衡，对动态调度及动态负载均衡研究较少。 针对动态调度，并结合异构多核的特点，提 出一种基于核负载均衡的动态任务调度算法 ＳＴＤＳ。 算法通过合理设定调度粒度，降低调度频率，从而减少调度消耗 时间；根据异构多核处理器各核处理性能的差异，设置内核负载上下限值，控制内核负载保持在同一水平，以达到负 载均衡效果。 算法依据等待时间长短、任务间通信大小和内核负载轻重因素对任务进行实时调度，并可通过实时因 子、负载因子等参数设置 ３ 种因素的影响比重，以满足系统的不同需求。 仿真实验显示，在内核数目较多的系统中， ＳＴＤＳ 算法更加高效，在保证任务处理速度的同时有较好负载均衡。 关键词：动态任务调度；负载均衡；调度粒度；等待时间；异构多核系统 中图分类号：ＴＰ３１６．４ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０２⁃０３２４⁃０９ 中文引用格式：刘正． 基于动态任务调度的 ＳＴＤＳ 算法设计研究［Ｊ］． 智能系统学报， ２０１５， １０（２）： ３２４⁃３３２． 英文引用格式：ＬＩＵ Ｚｈｅｎｇ． Ｒｅｓｅａｒｃｈ ｏｎ ＳＴＤＳ ａｌｇｏｒｉｔｈｍ ｄｅｓｉｇｎｉｎｇ ｂａｓｅｄ ｏｎ ｄｙｎａｍｉｃ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎ⁃ ｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（２）： ３２４⁃３３２． Ｒｅｓｅａｒｃｈ ｏｎ ＳＴＤＳ ａｌｇｏｒｉｔｈｍ ｄｅｓｉｇｎｉｎｇ ｂａｓｅｄ ｏｎ ｄｙｎａｍｉｃ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ＬＩＵ Ｚｈｅｎｇ （Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｈａｒｂｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｈａｒｂｉｎ １５０００１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｅｆｆｉｃｉｅｎｔ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ｉｓ ｔｈｅ ｋｅｙ ｆｏｒ ｍｕｌｔｉ⁃ｃｏｒｅ ｓｙｓｔｅｍｓ ｔｏ ａｃｈｉｅｖｅ ｈｉｇｈ ｐｅｒｆｏｒｍａｎｃｅ． Ｈｏｗｅｖｅｒ， ｍｏｓｔ ｏｆ ｔｈｅ ｅｘｉｓｔｉｎｇ ｍｕｌｔｉ⁃ｃｏｒｅ ｒｅｓｅａｒｃｈｅｓ ｏｎ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｆｏｃｕｓ ｏｎ ａｌｇｏｒｉｔｈｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ｌｏａｄ ｂａｌａｎｃｉｎｇ ｕｎｄｅｒ ｔｈｅ ｓｔａｔｉｃ ｓｃｈｅｄｕｌｉｎｇ ｒａｔｈｅｒ ｔｈａｎ ｄｙｎａｍｉｃ ｓｃｈｅｄｕｌｉｎｇ ａｎｄ ｄｙｎａｍｉｃ ｌｏａｄ ｂａｌａｎｃｉｎｇ． Ｓｃａｌａｂｌｅ ｔａｓｋ ｄｕｐｌｉｃａｔｉｏｎ ｂａｓｅｄ ｓｃｈｅｄｕｌｉｎｇ （ＳＴＤＳ） ｉｓ ａ ｎｅｗ ｄｙｎａｍｉｃ⁃ｂａｌａｎｃｅｄ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｏｒｅ ｌｏａｄ ｂａｌａｎｃｉｎｇ． ＳＴＤＳ ｗａｓ ｐｕｔ ｆｏｒ⁃ ｗａｒｄ ｓｐｅｃｉｆｉｃａｌｌｙ ｆｏｒ ｄｙｎａｍｉｃ ｓｃｈｅｄｕｌｉｎｇ ａｎｄ ｉｎｔｅｇｒａｔｉｎｇ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｍｕｌｔｉ⁃ｃｏｒｅ． Ｉｔ ｓｈｏｒｔｅｎｓ ｓｃｈｅｄｕｌｉｎｇ ｔｉｍｅ ｂｙ ｒｅａｓｏｎａｂｌｙ ｓｅｔｔｉｎｇ ｔｈｅ ｓｃｈｅｄｕｌｉｎｇ ｇｒａｎｕｌａｒｉｔｙ ａｎｄ ｒｅｄｕｃｉｎｇ ｔｈｅ ｆｒｅｑｕｅｎｃｙ ｏｆ ｓｃｈｅｄｕｌｉｎｇ． ＳＴＤＳ ｓｅｔｓ ｔｈｅ ｍａｘｉｍｕｍ ａｎｄ ｍｉｎｉｍｕｍ ｒａｎｇｅｓ ｏｆ ｔｈｅ ｋｅｒｎｅｌ ｌｏａｄ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｄｉｆｆｅｒｅｎｔ ｐｒｏｃｅｓｓｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｅａｃｈ ｃｏｒｅ ｏｆ ｔｈｅ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｍｕｌｔｉ⁃ｃｏｒｅ ｐｒｏｃｅｓｓｏｒ， ｔｈｅｒｅｆｏｒｅ ｃｏｎｔｒｏｌｌｉｎｇ ｔｈｅ ｃｏｒｅ ｌｏａｄ ａｔ ｔｈｅ ｓａｍｅ ｌｅｖｅｌ ａｎｄ ａｃｈｉｅｖｉｎｇ ｔｈｅ ｅｆｆｅｃｔ ｏｆ ｌｏａｄ ｂａｌａｎｃｅ． Ｔｈｅ ｗａｉｔ ｔｉｍｅ ｏｆ ｔａｓｋ ａｎｄ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｂｅｔｗｅｅｎ ｔａｓｋｓ ａｎｄ ｋｅｒｎｅｌ ｌｏａｄ ｗｉｌｌ ｂｅ ｃｏｎｓｉｄ⁃ ｅｒｅｄ ｔｏｇｅｔｈｅｒ ｔｏ ｐｉｃｋ ｕｐ ｔｈｅ ｍｏｓｔ ａｐｐｒｏｐｒｉａｔｅ ｔａｓｋ ｄｕｒｉｎｇ ｓｃｈｅｄｕｌｉｎｇ． Ｔｈｅ ｉｍｐｏｒｔａｎｃｅ ｏｆ ｅａｃｈ ｅｌｅｍｅｎｔ ｃａｎ ｂｅ ａｄｊｕｓ⁃ ｔｅｄ ｂｙ ａｓｓｉｇｎｉｎｇ ａｎｏｔｈｅｒ ｖａｌｕｅ ｔｏ ｔｈｅ ｒｅａｌ⁃ｔｉｍｅ ｆａｃｔｏｒ ａｎｄ ｌｏａｄ ｆａｃｔｏｒ ｅｎａｂｌｉｎｇ ｉｔ ｔｏ ａｄａｐｔ ｔｏ ｖａｒｉｏｕｓ ｅｎｖｉｒｏｎｍｅｎｔ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｖｅｒｉｆｉｅｄ ｔｈａｔ ｔｈｅ ＳＴＤＳ ａｌｇｏｒｉｔｈｍ ｉｓ ｍｏｒｅ ｅｆｆｉｃｉｅｎｔ ｉｎ ｔｈｅ ｓｙｓｔｅｍ ｗｉｔｈ ｔｈｅ ｍｏｓｔ ｋｅｒｎｅｌｓ． Ｉｔ ａｌｓｏ ｋｅｅｐｓ ａ ｇｏｏｄ ｌｏａｄ ｂａｌａｎｃｅ ｗｈｉｌｅ ｍａｉｎｔａｉｎｉｎｇ ｔｈｅ ｓｐｅｅｄ ｏｆ ｔａｓｋ ｅｘｅｃｕｔｉｏｎ ｐｒｏｃｅｓｓｉｎｇ． Ｋｅｙｗｏｒｄｓ： ｄｙｎａｍｉｃ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ； ｌｏａｄ ｂａｌａｎｃｉｎｇ； ｓｃｈｅｄｕｌｉｎｇ ｇｒａｎｕｌａｒｉｔｙ； ｗａｉｔｉｎｇ ｔｉｍｅ； ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｍｕｌｔｉ⁃ ｃｏｒｅ ｓｙｓｔｅｍ 收稿日期：２０１５⁃０３⁃０９． 网络出版日期：２０１５⁃０４⁃１３． 基金项目：国家自然科学基金资助项目（６１００３０３６）；中央高校基本科研 业务费专项资金资助项目（ＨＥＵＣＦ１００６０６）． 通信作者：刘正．Ｅ⁃ｍａｉｌ：ｌｉｕｚｈｅｎｇ５２８＠ ｈｒｂｅｕ．ｅｄｕ．ｃｎ． 动态任务调度可以根据运行的时情况动态 地将任务分配到各个内核上，由于需要实时地收 集、存储并分析状态信息，动态调度的实施有一
第2期 刘正：基于动态任务调度的STDS算法设计研究 ·325· 定的系统开销，但这种开销和付出通常是有回报 负载平衡研究提供了理论指导：徐雨明等将遗传 的山。多核处理器系统中的任务调度已被证明 算法和启发式方法有机地结合，根据染色体双螺旋 是NP问题2)，除个别特殊情况外，目前尚未有一 结构模型，提出了一种异构系统中依赖任务调度的 种多项式时间算法可以求得最优解，只能得到一 双螺旋结构遗传算法。该算法首先采用启发式方 个最大限度接近最优解的解，因此改进算法的效 法，产生较佳的任务调度优先队列，然后模仿碱基互 率并构建任务调度实现机制成为研究重点，很多 补配对方法，提高算法的有效性和收敛速度；Vinay 学者在这方面做了大量工作。 等]提出一种多核处理器动态任务调度策略，调度 比较经典的调度算法有Min-Min)、Max- 思想是依据任务的执行时间和依赖此任务的任务数 Mim[4、MCT)、MET算法。Min-Min算法实现简 量确定此任务优先级，当某个内核空闲时，选择一个 单、执行速度快。算法首先通过计算待调度任务在 优先级最高且为就绪状态的任务分配给该内核。此 任一可用内核上的最早完成时间，取最小值作为该 策略结构简洁，算法复杂度低，但每个内核上只分配 任务的最早完成时间，然后选取所有待调度任务中 一个任务，且调度时需要对数据段加锁以保证数据 最早完成时间最小的一个任务进行调度。缺点是如 一致性，当内核数目较多时，经常发生多个内核同时 果任务集中存在过多的执行时间比较小的任务，那 申请分配任务的情况，所以不可避免出现内核空闲 么大任务将无法得到及时的执行。Max-Min算法同 等待现象，不能完全发挥多核处理器优势。 Min-Min算法类似，同样需要计算每一任务的最早 文中对文献[11]的动态调度策略进行改进，克 完成时间，不同的是Max-Min算法首先调度最早完 服内核可能空闲等待问题，并综合负载均衡策略，提 成时间最大的任务，将其分配到对应的内核上。缺 出多核动态任务调度算法(shared task data struc- 点是小任务等待时间过长、影响执行效率，也可能造 ture,STDS)。算法通过分析任务等待时间、任务间 成负载不均衡。MCT算法以任务完成时间最早为 通信开销和内核负载等因素，确定任务优先级，并据 目标进行调度，每次将到达的任务分配到完成时间 此分配任务。通过仿真实验验证，该算法在保证任 最早的内核上，但该算法忽略了任务的执行时间，可 务处理速度的同时有较好负载均衡，比较适用于内 能将任务分配到执行时间较长的处理机上运行。 核数目较多的系统。 MET算法以任务执行时间最短为目标进行调度，每 1 模型 次将到达的任务分配到执行时间最短的内核上，其 缺点是易造成较强内核负载过多任务，导致内核间 在多核任务调度研究中，为便于研究理解，通常 负载不均衡，降低系统性能。 用抽象的任务调度模型描述任务调度系统。多核任 清华大学的石威等)提出了一种相关任务图 务调度模型通常由系统模型、任务模型、任务调度算 的均衡动态关键路径调度算法，采用动态关键路径 法和任务映射图组成。 技术并均衡考虑关键路径结点和非关键路径结点， 1.1系统模型 优先调度对相关任务图调度长度影响最大的就绪结 系统模型是指依据系统硬件环境构建出可 点，从而极大地缩短任务图的调度长度。李仁发) 进行数学量化分析的数学模型，文中用二元组 对多核处理器系统任务调度研究进展进行讨论，对 SM(system model)={P,Rate}表示，其中：SM表 不同模型下的多核系统任务调度算法相关研究进行 示系统模型；P={P。,P,…,P,…,P-1}为处 了分析总结，从调度算法分析和调度实现框架2个 理器内核集合，P表示第k个处理器内核，P= 方面探讨了近年来多核任务调度的国内外研究进展 m为处理器中内核的总个数。多核处理器根据 情况。文中对任务分配、任务模型优化、调度器实现 内核在执行能力方面的差别可划分为同构和异 和任务迁移等当前亟待解决的问题，进行了深入探 构2类，同构多核处理器通过增加同种处理器内 讨，并指出了下一步主要的研究方向，为多核处理器 核数量提升性能，而异构多核处理器通过集成不 相关研究提供参考。吉林大学的耿晓中提出了一种 同计算能力的内核来优化处理器，实现多核处理 动态负载均衡模型[⑨，将影响多核处理器负载均衡 器性能发挥的最大化，在能耗、面积等方面有着 的因素分为5类：多核系统的负载均衡环境、用户提 巨大的优势【2)。文中以有限数目的异构多核处 交的任务属性、系统的负载评价、系统所采用的调度 理器为研究基础，集合P中处理器内核速度并不 策略以及系统的调度评价指标，为多核动态调度的 完全相同，用sP4表示内核P的处理速度
定的系统开销，但这种开销和付出通常是有回报 的［ １］ 。 多核处理器系统中的任务调度已被证明 是 ＮＰ 问题［ ２］ ，除个别特殊情况外，目前尚未有一 种多项式时间算法可以求得最优解，只能得到一 个最大限度接近最优解的解，因此改进算法的效 率并构建任务调度实现机制成为研究重点，很多 学者在这方面做了大量工作。 比 较 经 典 的 调 度 算 法 有 Ｍｉｎ⁃Ｍｉｎ ［３］ 、 Ｍａｘ⁃ Ｍｉｎ ［４］ 、ＭＣＴ ［５］ 、ＭＥＴ ［６］ 算法。 Ｍｉｎ⁃Ｍｉｎ 算法实现简 单、执行速度快。 算法首先通过计算待调度任务在 任一可用内核上的最早完成时间，取最小值作为该 任务的最早完成时间，然后选取所有待调度任务中 最早完成时间最小的一个任务进行调度。 缺点是如 果任务集中存在过多的执行时间比较小的任务，那 么大任务将无法得到及时的执行。 Ｍａｘ⁃Ｍｉｎ 算法同 Ｍｉｎ⁃Ｍｉｎ 算法类似，同样需要计算每一任务的最早 完成时间，不同的是 Ｍａｘ⁃Ｍｉｎ 算法首先调度最早完 成时间最大的任务，将其分配到对应的内核上。 缺 点是小任务等待时间过长、影响执行效率，也可能造 成负载不均衡。 ＭＣＴ 算法以任务完成时间最早为 目标进行调度，每次将到达的任务分配到完成时间 最早的内核上，但该算法忽略了任务的执行时间，可 能将任务分配到执行时间较长的处理机上运行。 ＭＥＴ 算法以任务执行时间最短为目标进行调度，每 次将到达的任务分配到执行时间最短的内核上，其 缺点是易造成较强内核负载过多任务，导致内核间 负载不均衡，降低系统性能。 清华大学的石威等［７］ 提出了一种相关任务图 的均衡动态关键路径调度算法，采用动态关键路径 技术并均衡考虑关键路径结点和非关键路径结点， 优先调度对相关任务图调度长度影响最大的就绪结 点，从而极大地缩短任务图的调度长度。 李仁发［８］ 对多核处理器系统任务调度研究进展进行讨论，对 不同模型下的多核系统任务调度算法相关研究进行 了分析总结，从调度算法分析和调度实现框架 ２ 个 方面探讨了近年来多核任务调度的国内外研究进展 情况。 文中对任务分配、任务模型优化、调度器实现 和任务迁移等当前亟待解决的问题，进行了深入探 讨，并指出了下一步主要的研究方向，为多核处理器 相关研究提供参考。 吉林大学的耿晓中提出了一种 动态负载均衡模型［９］ ，将影响多核处理器负载均衡 的因素分为 ５ 类：多核系统的负载均衡环境、用户提 交的任务属性、系统的负载评价、系统所采用的调度 策略以及系统的调度评价指标，为多核动态调度的 负载平衡研究提供了理论指导；徐雨明等［１０］ 将遗传 算法和启发式方法有机地结合，根据染色体双螺旋 结构模型，提出了一种异构系统中依赖任务调度的 双螺旋结构遗传算法。 该算法首先采用启发式方 法，产生较佳的任务调度优先队列，然后模仿碱基互 补配对方法，提高算法的有效性和收敛速度；Ｖｉｎａｙ 等［１１］提出一种多核处理器动态任务调度策略，调度 思想是依据任务的执行时间和依赖此任务的任务数 量确定此任务优先级，当某个内核空闲时，选择一个 优先级最高且为就绪状态的任务分配给该内核。 此 策略结构简洁，算法复杂度低，但每个内核上只分配 一个任务，且调度时需要对数据段加锁以保证数据 一致性，当内核数目较多时，经常发生多个内核同时 申请分配任务的情况，所以不可避免出现内核空闲 等待现象，不能完全发挥多核处理器优势。 文中对文献［１１］的动态调度策略进行改进，克 服内核可能空闲等待问题，并综合负载均衡策略，提 出多核动态任务调度算法（ ｓｈａｒｅｄ ｔａｓｋ ｄａｔａ ｓｔｒｕｃ⁃ ｔｕｒｅ，ＳＴＤＳ）。 算法通过分析任务等待时间、任务间 通信开销和内核负载等因素，确定任务优先级，并据 此分配任务。 通过仿真实验验证，该算法在保证任 务处理速度的同时有较好负载均衡，比较适用于内 核数目较多的系统。 １ 模型 在多核任务调度研究中，为便于研究理解，通常 用抽象的任务调度模型描述任务调度系统。 多核任 务调度模型通常由系统模型、任务模型、任务调度算 法和任务映射图组成。 １．１ 系统模型 系统模型是指依据系统硬件环境构建出可 进行数学量化分析的数学模型，文 中 用 二 元 组 ＳＭ（ ｓｙｓｔｅｍ ｍｏｄｅｌ） ＝ ｛ Ｐ， Ｒａｔｅ｝表示，其中：ＳＭ 表 示系统模型； Ｐ ＝ ｛ Ｐ０ ，Ｐ１ ，…，Ｐｋ，…， Ｐ ｍ － １ ｝为处 理器内核集合，Ｐｋ表示第 ｋ 个处理器内核， ｜ Ｐ ｜ ＝ ｍ 为处理器中内核的总个数。 多核处理器根据 内核在执行能力方面的差别可划分为同构和异 构 ２ 类，同构多核处理器通过增加同种处理器内 核数量提升性能，而异构多核处理器通过集成不 同计算能力的内核来优化处理器，实现多核处理 器性能发挥的最大化，在能耗、面积等方面有着 巨大的优势［ １２］ 。 文中以有限数目的异构多核处 理器为研究基础，集合 Ｐ 中处理器内核速度并不 完全相同，用 ｓｐｋ表示内核 Ｐｋ的处理速度。 第 ２ 期 刘正：基于动态任务调度的 ＳＴＤＳ 算法设计研究 ·３２５·
·326· 智能系统学报 第10卷 Rate={…,Rate,…}表示处理器内核间数据 务T,与T的通信时间就可用Data:,/Rate,表示； 传输速率集合，元素Rate,表示处理器内核P,与P, T。={…,T,…}:依赖任务T:的任务集合，也 间的数据传输速率。 叫后继任务集合，只有T执行完成后，其后继任务 核间互连技术是多核处理器设计的关键，当前多 才有机会变为就绪状态，从而调度执行。当T:完成 核处理器核间互连方式主要有总线共享、交叉开关互 后，需要将集合T。中所有任务的T属性值减一； 连和片上网络3种。文中对多核处理器核间互连技 T。:任务优先级，表示任务优先调度程度，任务 术不做具体研究，默认任意2个处理器内核间均存在 优先级越高，被优先调度的可能性越大。任务优先 数据通信通路，即对于任意的s(0≤s≤m-1)和 级取决于任务就绪时间、通信开销以及内核负载等 t(0≤s≤m-1),Rate≠0。为简化环境模型，假 因素。系统运行过程中，就绪时间和内核负载等是 设同一时刻，内核P只能与一个内核进行通信。 动态变化的，所以任务优先级不是某一定值，它随着 1.2任务模型 系统状态的改变而动态变化： 任务模型是描述任务属性和特征的一种数学模 T:任务就绪时间，即任务满足调度条件变为 型，它包含任务调度过程中的状态和控制等信息。 就绪状态的时间。如果用t表示现在时间，则等待 STDS算法构建了一个可以共享访问的TDS(ask 时间就是(t-T),为避免存在长时间未能调度执 data structure)结构，TDS由若千数据项构成，每个数 行的就绪任务，算法应优先调度等待时间长的任务； 据项唯一对应一个任务，数据项记录该任务的相关 T:任务映射，表示任务和内核的对应关系，即 信息，其定义如图1所示。 任务T:分配到哪个内核上执行。STDS算法用-1 表示任务尚未分配内核资源，用整数0,1，…，m-1 分别表示在内核P。,P,…,Pm-1上执行。 图1数据项定义 1.3调度器模型 Fig.I Definition of data element 文中设计的调度器模型采用集中式调度模式， 图1中，T为任务编号，唯一标识任务；T为任务状 如图2所示。图中指定了一个内核专门执行调度程 态，STDS算法将任务状态分为等待、就绪和已执行 序，称为中心调度器，中心调度器负责收集调度信息 3种，用1表示等待，0表示就绪，2表示已执行。如 和执行任务调度，其余内核只负责执行任务。 果任务处于就绪态，说明已分配除CPU外所有必要 TDS 资源，允许调度程序将其调度分配：等待状态的任务 就绪队列 等待队列 因需要等待某一事件的发生，比如等待其前驱任务 执行完毕，而暂不能被调度程序调度：任务执行完毕 后的状态为已执行状态，此状态下，如果其他所有任 中心调度器 信息更新 务都不再需要此任务信息，就将其对应的数据项删 除，以节省内存空间： Ta={…,T,…:依赖任务集合，也叫前驱任 P 务集合，任务T必须在其依赖任务全部执行完成之 后执行： T：依赖任务剩余数量，表示任务T,的依赖任 务队列 务队列 务队 务集合中尚未执行完毕的任务数量，即依赖任务集 图2调度器模型 合T中，还有多少依赖任务没有执行完成。其初值 Fig.2 Scheduler model 是集合Ta的长度，即T=Tal,每当一个依赖任 建立维护等待队列和就绪队列2个全局任务列 务执行完毕，T油值减1，直到T=0,而T血=0是 表，调度器在任务调度时只需要检索就绪任务队列， T.=0(就绪)的必要条件： 节省了调度时间开销，等待队列中的任务满足就绪 Ta={…,Data,…}:与依赖任务通信数据量 条件时可以变为就绪态等待调度。每个内核都有一 集合，记录任务T:与其依赖任务T通信的数据大 个可以缓存一定数目任务的局部队列，当内核需要 小，Data,表示任务T:与依赖任务T通信的数据大 调度任务时直接从缓存中获取：而当局部队列中的 小，如果任务T:、T分别分配到内核P,、P上，则任 任务过少时开始请求调度器为局部队列分配任务
Ｒａｔｅ ＝ ｛…，Ｒａｔｅｓ，ｔ，…｝表示处理器内核间数据 传输速率集合，元素 Ｒａｔｅｓ，ｔ表示处理器内核 Ｐｓ 与 Ｐｔ 间的数据传输速率。 核间互连技术是多核处理器设计的关键，当前多 核处理器核间互连方式主要有总线共享、交叉开关互 连和片上网络 ３ 种。 文中对多核处理器核间互连技 术不做具体研究，默认任意 ２ 个处理器内核间均存在 数据通信通路，即对于任意的 ｓ（ ０ ≤ ｓ ≤ ｍ － １）和 ｔ（０ ≤ ｓ ≤ ｍ － １）， Ｒａｔｅｓ，ｔ ≠ ０。 为简化环境模型，假 设同一时刻，内核 Ｐｋ只能与一个内核进行通信。 １．２ 任务模型 任务模型是描述任务属性和特征的一种数学模 型，它包含任务调度过程中的状态和控制等信息。 ＳＴＤＳ 算法构建了一个可以共享访问的 ＴＤＳ （ ｔａｓｋ ｄａｔａ ｓｔｒｕｃｔｕｒｅ）结构，ＴＤＳ 由若干数据项构成，每个数 据项唯一对应一个任务，数据项记录该任务的相关 信息，其定义如图 １ 所示。 图 １ 数据项定义 Ｆｉｇ．１ Ｄｅｆｉｎｉｔｉｏｎ ｏｆ ｄａｔａ ｅｌｅｍｅｎｔ 图 １ 中，Ｔｉ为任务编号，唯一标识任务； Ｔｉｓ 为任务状 态，ＳＴＤＳ 算法将任务状态分为等待、就绪和已执行 ３ 种，用 １ 表示等待，０ 表示就绪，２ 表示已执行。 如 果任务处于就绪态，说明已分配除 ＣＰＵ 外所有必要 资源，允许调度程序将其调度分配；等待状态的任务 因需要等待某一事件的发生，比如等待其前驱任务 执行完毕，而暂不能被调度程序调度；任务执行完毕 后的状态为已执行状态，此状态下，如果其他所有任 务都不再需要此任务信息，就将其对应的数据项删 除，以节省内存空间； Ｔｉｄ ＝ ｛…，Ｔｊ，…｝： 依赖任务集合，也叫前驱任 务集合，任务 Ｔｉ 必须在其依赖任务全部执行完成之 后执行； Ｔｉｄｎ ： 依赖任务剩余数量，表示任务 Ｔｉ的依赖任 务集合中尚未执行完毕的任务数量，即依赖任务集 合 Ｔｉｄ 中，还有多少依赖任务没有执行完成。 其初值 是集合 Ｔｉｄ 的长度，即 Ｔｉｄｎ ＝｜ Ｔｉｄ ｜ ， 每当一个依赖任 务执行完毕， Ｔｉｄｎ 值减 １， 直到 Ｔｉｄｎ ＝ ０， 而 Ｔｉｄｎ ＝ ０ 是 Ｔｉｓ ＝ ０（就绪）的必要条件； Ｔｉｄｄ ＝ ｛…，Ｄａｔａｉ，ｊ，…｝：与依赖任务通信数据量 集合，记录任务 Ｔｉ 与其依赖任务 Ｔｉｄ通信的数据大 小， Ｄａｔａｉ，ｊ 表示任务 Ｔｉ 与依赖任务 Ｔｊ 通信的数据大 小，如果任务 Ｔｉ、Ｔｊ 分别分配到内核 Ｐｓ、Ｐｔ 上，则任 务 Ｔｉ 与 Ｔｊ 的通信时间就可用 Ｄａｔａｉ，ｊ ／ Ｒａｔｅｓ，ｔ 表示； Ｔｉａ ＝ ｛…，Ｔｊ，…｝：依赖任务 Ｔｉ 的任务集合，也 叫后继任务集合，只有 Ｔｉ 执行完成后，其后继任务 才有机会变为就绪状态，从而调度执行。 当 Ｔｉ 完成 后， 需要将集合 Ｔｉａ 中所有任务的 Ｔｉｄｎ 属性值减一； Ｔｉｐ ：任务优先级，表示任务优先调度程度，任务 优先级越高，被优先调度的可能性越大。 任务优先 级取决于任务就绪时间、通信开销以及内核负载等 因素。 系统运行过程中，就绪时间和内核负载等是 动态变化的，所以任务优先级不是某一定值，它随着 系统状态的改变而动态变化； Ｔｉｔ： 任务就绪时间，即任务满足调度条件变为 就绪状态的时间。 如果用 ｔ 表示现在时间，则等待 时间就是（ｔ － Ｔｉｔ）， 为避免存在长时间未能调度执 行的就绪任务，算法应优先调度等待时间长的任务； Ｔｉｃ：任务映射，表示任务和内核的对应关系，即 任务 Ｔｉ 分配到哪个内核上执行。 ＳＴＤＳ 算法用 － １ 表示任务尚未分配内核资源，用整数 ０，１，…，ｍ － １ 分别表示在内核 Ｐ０ ， Ｐ１ ，…， Ｐｍ－１ 上执行。 １．３ 调度器模型 文中设计的调度器模型采用集中式调度模式， 如图 ２ 所示。 图中指定了一个内核专门执行调度程 序，称为中心调度器，中心调度器负责收集调度信息 和执行任务调度，其余内核只负责执行任务。 图 ２ 调度器模型 Ｆｉｇ．２ Ｓｃｈｅｄｕｌｅｒ ｍｏｄｅｌ 建立维护等待队列和就绪队列 ２ 个全局任务列 表，调度器在任务调度时只需要检索就绪任务队列， 节省了调度时间开销，等待队列中的任务满足就绪 条件时可以变为就绪态等待调度。 每个内核都有一 个可以缓存一定数目任务的局部队列，当内核需要 调度任务时直接从缓存中获取；而当局部队列中的 任务过少时开始请求调度器为局部队列分配任务， ·３２６· 智 能 系 统 学 报 第 １０ 卷
第2期 刘正：基于动态任务调度的STDS算法设计研究 ·327. 降低了调度器调度频率，而且中心调度器与各内核 式中：表示内核P的调度粒度，l表示粒度因子， 可以并行地运行。全局调度队列和局部调度队列结 sP表示内核P的处理速度。对于一个实际的处理 合的方式在整体上是全局队列方式，与集中式调度 器系统，内核速度是确定的已知量，调度粒度1的大 策略配合使用易于实现负载均衡：在底层实现上是 小，可以通过粒度因子1调节，粒度因子与具体的运 局部队列方式，降低了系统对队列共享性要求，克服 行状况有关，它起到将内核的计算速度转换为内核 了集中式调度模式的性能瓶颈问题。 调度任务数量功能。 文中通过重载和轻载阀值确定调度时机，当内 STDS算法通过限制内核任务队列长度实现负 核处于轻载状态时请求任务调度，处于重载时不允 载均衡，为有效发挥调度队列作用，算法引入2个负 许再向内核分配任务，这种策略在保证一定负载均 载因子，分别确定队列的上限和下限，具体定义如式 衡效果的同时提高了内核执行效率。 (3)~(5): l4-max=l,(1+6,) (3) 2任务优先级 l4-min=l(1-82) (4) 将任务分配到最合适的内核上是任务调度的核 61+62=1 (5) 心问题，而任务优先级计算是任务分配的关键，任务 0≤k≤m-1 优先级表明任务被优先调度程度。在多核环境下， 式中：δ，是负载上限因子，lk-max表示内核P的任 各内核的状态不尽相同，STDS算法为评价任务与内 务队列长度上限，δ，是负载下限因子，lmin表示 核的适合程度，首先计算任务相对于一个确定内核 内核P的任务队列长度下限。当|Tls|≤-min 的优先级T,然后取其在所有内核上的最大值作 时，内核P请求调度程序分配任务，而当T|≥ 为任务优先级T,表示为式(1)： l_max时，就不允许向内核P上分配任务，从而保 omax (1) 证内核P的任务队列长度满足：l-min≤|T.|≤ 式中：m为内核数量，T表示任务T,相对于内核P I_max。需要说明的是，在一些极端情况下，比如 的优先级。STDS算法在计算T.时，综合考虑等待 当有多个内核同时请求分配任务，或者暂时没有任 时间、任务间通信开销和内核负载状态因素。等待 务可分配时，调度程序无法及时响应内核任务调度 时间为当前时间与就绪时间的差值，任务间通信开 请求，而内核继续从其任务队列上取任务执行，此时 销是任务T,与其所有依赖任务T通信时间之和，而 会出现|Tl|<lmin的情况，但只要调度粒度设 置合理，这种情况不会频繁出现，所以不影响整体负 内核负载状态用于实现内核负载均衡。 多核处理器的负载均衡要求避免出现一个或多 载均衡。内核P的任务队列长度上限与下限之差 个内核负载较低甚至空闲，而其他内核处于高负载 l-max-l-min=(6,+8,),而式(5)设置约束条 状态的情况，从而充分发挥多核处理器优势。STDS 件8，+62=1，从而使得lk-max-l-min=l,内核 算法使用任务队列长度！TL:〡作为内核负载指标， P在其任务队列长度为lmin时请求分配任务，调 内核的任务队列越长，说明分配的任务越多，所以其 度程序响应请求并为P分配：（调度粒度）个任务， 负载越大。 此时内核P的任务队列长度为其上限值l,-max。 上述阐述了计算任务优先级时的内核队列上下 为实现负载均衡引入调度粒度，内核P的调度 限问题，式(6)~(10)则是对任务优先级计算时的 粒度定义为一次调度过程中为P分配的任务数量， 等待时间、通信开销和内核负载均衡因素的描述。 这里的一次调度过程是指一个内核请求调度，调度 STDS算法在计算任务优先级时，综合考虑等待时 算法为其分配任务的过程，在实际运行中，可能出现 间、通信开销和内核负载均衡因素，式(1)中Tt表 调度算法一次性处理多个内核调度请求，调度的任 示任务T分配到内核P适合程度，其计算公式为： 务数量等于为每个内核分配的任务数量之和。粒度 Tt=(PW:+PCa)·ld (6) 大小要根据系统模型而定，调度粒度过大，不能充分 PW;=B(t-T) (7) 发挥动态调度优势，而粒度过小，会引发频繁调度， 增大调度程序运行时间开销，降低处理器效率。对 PCk=- 0≤s≤m-1 (8) 于异构多核处理器，调度粒度与内核处理速度是正 m·Ct 比关系。STDS算法将调度粒度定义为式(2)： li ms -1 ThI (9) lk=l·sp4,0≤k≤m-1 (2) = lms-lki血
降低了调度器调度频率，而且中心调度器与各内核 可以并行地运行。 全局调度队列和局部调度队列结 合的方式在整体上是全局队列方式，与集中式调度 策略配合使用易于实现负载均衡；在底层实现上是 局部队列方式，降低了系统对队列共享性要求，克服 了集中式调度模式的性能瓶颈问题。 文中通过重载和轻载阀值确定调度时机，当内 核处于轻载状态时请求任务调度，处于重载时不允 许再向内核分配任务，这种策略在保证一定负载均 衡效果的同时提高了内核执行效率。 ２ 任务优先级 将任务分配到最合适的内核上是任务调度的核 心问题，而任务优先级计算是任务分配的关键，任务 优先级表明任务被优先调度程度。 在多核环境下， 各内核的状态不尽相同，ＳＴＤＳ 算法为评价任务与内 核的适合程度，首先计算任务相对于一个确定内核 的优先级 Ｔｉｐｋ，然后取其在所有内核上的最大值作 为任务优先级 Ｔｉｐ，表示为式（１）： Ｔｉｐ ＝ ｍａｘ ０≤ｋ≤ｍ－１ Ｔｉｐｋ （１） 式中： ｍ 为内核数量，Ｔｉｐｋ 表示任务 Ｔｉ 相对于内核 Ｐｋ 的优先级。 ＳＴＤＳ 算法在计算 Ｔｉｐｋ 时，综合考虑等待 时间、任务间通信开销和内核负载状态因素。 等待 时间为当前时间与就绪时间的差值，任务间通信开 销是任务Ｔｉ 与其所有依赖任务Ｔｉｄ 通信时间之和，而 内核负载状态用于实现内核负载均衡。 多核处理器的负载均衡要求避免出现一个或多 个内核负载较低甚至空闲，而其他内核处于高负载 状态的情况，从而充分发挥多核处理器优势。 ＳＴＤＳ 算法使用任务队列长度 ｜ ＴＬｋ ｜ 作为内核负载指标， 内核的任务队列越长，说明分配的任务越多，所以其 负载越大。 为实现负载均衡引入调度粒度，内核 Ｐｋ的调度 粒度定义为一次调度过程中为 Ｐｋ分配的任务数量， 这里的一次调度过程是指一个内核请求调度，调度 算法为其分配任务的过程，在实际运行中，可能出现 调度算法一次性处理多个内核调度请求，调度的任 务数量等于为每个内核分配的任务数量之和。 粒度 大小要根据系统模型而定，调度粒度过大，不能充分 发挥动态调度优势，而粒度过小，会引发频繁调度， 增大调度程序运行时间开销，降低处理器效率。 对 于异构多核处理器，调度粒度与内核处理速度是正 比关系。 ＳＴＤＳ 算法将调度粒度定义为式（２）： ｌ ｋ ＝ ｌ·ｓｐｋ，０ ≤ ｋ ≤ ｍ － １ （２） 式中：ｌ ｋ表示内核 Ｐｋ 的调度粒度，ｌ 表示粒度因子， ｓｐｋ表示内核 Ｐｋ的处理速度。 对于一个实际的处理 器系统，内核速度是确定的已知量，调度粒度 ｌ ｋ的大 小，可以通过粒度因子 ｌ 调节，粒度因子与具体的运 行状况有关，它起到将内核的计算速度转换为内核 调度任务数量功能。 ＳＴＤＳ 算法通过限制内核任务队列长度实现负 载均衡，为有效发挥调度队列作用，算法引入 ２ 个负 载因子，分别确定队列的上限和下限，具体定义如式 （３） ～ （５）： ｌ ｋ＿ｍａｘ ＝ ｌ ｋ（１ ＋ δ１ ） （３） ｌ ｋ＿ｍｉｎ ＝ ｌ ｋ（１ － δ２ ） （４） δ１ ＋ δ２ ＝ １ （５） ０ ≤ ｋ ≤ ｍ － １ 式中： δ１ 是负载上限因子， ｌ ｋ＿ｍａｘ 表示内核 Ｐｋ的任 务队列长度上限， δ２ 是负载下限因子， ｌ ｋ＿ｍｉｎ 表示 内核 Ｐｋ 的任务队列长度下限。 当 Ｔｌ ｋ ≤ ｌ ｋ＿ｍｉｎ 时，内核 Ｐｋ 请求调度程序分配任务，而当 Ｔｌ ｋ ≥ ｌ ｋ＿ｍａｘ 时，就不允许向内核 Ｐｋ上分配任务，从而保 证内核 Ｐｋ的任务队列长度满足： ｌ ｋ＿ｍｉｎ ≤ Ｔｌ ｋ ≤ ｌ ｋ＿ｍａｘ 。 需要说明的是，在一些极端情况下，比如 当有多个内核同时请求分配任务，或者暂时没有任 务可分配时，调度程序无法及时响应内核任务调度 请求，而内核继续从其任务队列上取任务执行，此时 会出现 Ｔｌ ｋ ＜ ｌ ｋ＿ｍｉｎ 的情况，但只要调度粒度设 置合理，这种情况不会频繁出现，所以不影响整体负 载均衡。 内核 Ｐｋ的任务队列长度上限与下限之差 ｌ ｋ＿ｍａｘ － ｌ ｋ＿ｍｉｎ ＝ ｌ ｋ（δ１ ＋ δ１ ） ，而式（５）设置约束条 件 δ１ ＋ δ２ ＝ １，从而使得 ｌ ｋ＿ｍａｘ － ｌ ｋ＿ｍｉｎ ＝ ｌ ｋ ，内核 Ｐｋ在其任务队列长度为 ｌ ｋ＿ｍｉｎ 时请求分配任务，调 度程序响应请求并为 Ｐｋ分配 ｌ ｋ （调度粒度）个任务， 此时内核 Ｐｋ的任务队列长度为其上限值 ｌ ｋ＿ｍａｘ 。 上述阐述了计算任务优先级时的内核队列上下 限问题，式（６） ～ （１０）则是对任务优先级计算时的 等待时间、通信开销和内核负载均衡因素的描述。 ＳＴＤＳ 算法在计算任务优先级时，综合考虑等待时 间、通信开销和内核负载均衡因素，式（１）中 Ｔｉｐｋ表 示任务 Ｔｉ分配到内核 Ｐｋ适合程度，其计算公式为： Ｔｉｐｋ ＝ （ＰＷｉ ＋ ＰＣｉｋ）·ｌ ｋ ｊ （６） ＰＷｉ ＝ β ｔ － Ｔｉｔ ( ) （７） ＰＣｉｋ ＝ ０≤∑ｓ≤ｍ－１ Ｃｉｓ ｍ·Ｃｉｋ （８） ｌ ｋ ＝ ｌ ｋ ＿ｍａｘ －｜ Ｔｌ ｋ ｜ ｌ ｋ＿ｍａｘ － ｌ ｋ＿ｍｉｎ （９） 第 ２ 期 刘正：基于动态任务调度的 ＳＴＤＳ 算法设计研究 ·３２７·
.328. 智能系统学报 第10卷 3)任务不可抢占。 Rate a Ct=】 Dataij (10)》 系统运行时首先将任务初始化，构造TDS,由于 0≤k≤m-1,0≤s≤m-1,0≤i<|Ta1 算法中大多计算只针对就绪任务，特别是任务分配 式中：PW代表任务T的等待时间所占优先级比重， 时，所以为了节约计算开销，算法初始化时会生成一 PC代表通信时间所占优先级比重，L为内核P:的 个就绪任务列表和一个等待任务列表。当内核P: 负载状态。t是当前时间，1-T表示任务T的等待时 任务队列长度ITLI≤l时，就向调度程序请求分 间，等待时间越长的任务优先级相对越高，同等条件 配任务，调度程序遍历就绪列表，计算相对于内核 下，调度程序优先调度等待时间长的任务，避免存在 P的优先级，选择优先级T值最大的任务分配到P 就绪任务长时间等待的“饥饿”现象，B是实时性因 上，重复执行此过程，直到内核P任务队列长度 子，用来调节等待时间在优先级中所占比重。C表 ITLI≥。若同时有多个内核请求任务分配，调度 示任务T,的通信时间，STDS算法假设同一内核内的 程序分配任务时需要响应这几个内核的请求，计算 任务通信开销忽略不计，C:值即任务T,与除内核P 优先级时需要计算相对于这几个内核的优先级，然 以外的其他内核P,上依赖任务通信的时间之和，用 后取最大值作为最终优先级，调度程序选择优先级 Daau表示，下标s即任务T,的T,属性值， 最大的任务分配到对应的内核。 jeTe+Rate. 值得注意的是在动态调度过程中，为了保证数 据实时有效，STDS算法在每个任务分配完成或执行 表示任务T分配给内核P。s-1 一表示平均通信 结束时对数据进行更新。当任务T分配给内核P m 后，需要将任务T对应数据项中的T置为k,此时内 时间，通信时间越小，PC值越大，优先级也相应越 核P负载也相应改变；当任务T执行完成时，如果 大，对于C4相同的任务，若任务的∑C。值较 任务T依赖任务T,需要将任务T的T值减1，若 0≤s≤m-1 大，则说明此任务如果分配到内核P上节省的通信 减1后T:=0,将任务T状态置为就绪态并从等待 开销更多，相应的其优先级也较高。在实际计算时， 列表移到就绪列表。为了降低复杂度节省时间， 因为任务T的依赖任务已经全部分配执行，所以若 STDS算法采用先记录再批量执行的方式，即在任务 分配在内核P:上，通信开销是个定值，因此PC.只 执行期间暂时将完成的任务编号记录，在任务调度 程序执行时批量更新数据：如果任务T执行完毕且 需计算一次。少尼 一反应了内核的负载状 所有依赖T的任务也执行完毕，就将任务T的信息 态，ITLI是内核P当前任务队列长度，当1TL:I= 从TDS中删除，从而释放内存节省空间。 lm时其值为0，从而T=0为最小值，则当前状态 如果就绪列表为空，调度程序不会响应内核的 下不能向内核P分派任务。在一次调度过程中，调 任务分配请求，当就绪列表和等待列表全为空时，说 度程序可能需要响应多个内核的调度请求，对于 明任务全部执行完毕，调度结束。 |TLI较小的内核，其L较大，从而实现优先将任务 STDS算法实现步骤： 分配到负载较轻的内核，并进而达到负载均衡效果。 Procedure STDS(SM,TDS,PL,TL)/*SM 综上所述，任务优先级值的计算，是对等待时 示处理器内核系统；TDS是所有任务信息；Pm是需 间、通信开销和内核负载3个因素综合考量的过程， 要分配任务的内核列表，T。是执行完毕但还未进 其结果可能不是单一因素中最优的，但一定是综合 行信息更新的任务列表*/ 考虑全部3种因素后最优的选择。 1)for each Te TL 2){Ta[]-T:; 3算法实现 3) for each T∈Ta 在上节中详细介绍了任务优先级的计算，本节 4) T←T-1;/*执行完毕的任务信息 将介绍STDS算法的具体实现过程。 更新，将其后继任务的依赖任务数量减一*/ 为了使任务调度算法得到较理想的实现，STDS /end for each Tie TLee * 算法的研究基于以下假设条件： 5)TLa助[]←-TDS;/*就绪任务放入就绪队列*/ 1)假设任务间的依赖关系固定不变： 6)for each TiTLready 2)同一内核上任务间通信开销忽略不计； 7){for each P&∈Pia
Ｃｉｋ ＝ ｊ∈Ｔ∑ｉｄｄ＆＆ｓ≠ｋ Ｄａｔａｉ，ｊ Ｒａｔｅｓ，ｋ （１０） ０ ≤ ｋ ≤ ｍ － １，０ ≤ ｓ ≤ ｍ － １，０ ≤ ｉ ＜ ｜ ＴＬｉｓｔ ｜ 式中：ＰＷｉ代表任务 Ｔｉ的等待时间所占优先级比重， ＰＣｉｋ代表通信时间所占优先级比重，Ｌｋ为内核 Ｐｋ的 负载状态。 ｔ 是当前时间，ｔ－Ｔｉｔ表示任务 Ｔｉ的等待时 间，等待时间越长的任务优先级相对越高，同等条件 下，调度程序优先调度等待时间长的任务，避免存在 就绪任务长时间等待的“饥饿”现象， β 是实时性因 子，用来调节等待时间在优先级中所占比重。 Ｃｉｋ表 示任务 Ｔｉ的通信时间，ＳＴＤＳ 算法假设同一内核内的 任务通信开销忽略不计，Ｃｉｋ值即任务 Ｔｉ与除内核 Ｐｋ 以外的其他内核 Ｐｓ上依赖任务通信的时间之和，用 ｊ∈Ｔ∑ｉｄｄ＆＆ｓ≠ｋ Ｄａｔａｉ，ｊ Ｒａｔｅｓ，ｋ 表示，下标 ｓ 即任务 Ｔｊ的 Ｔｊｃ属性值， 表示任务 Ｔｊ分配给内核 Ｐｓ。 ０≤∑ｓ≤ｍ－１ Ｃｉｓ ｍ 表示平均通信 时间，通信时间越小，ＰＣｉｋ值越大，优先级也相应越 大，对于 Ｃｉｋ 相同的任务，若任务的 ０≤∑ｓ≤ｍ－１ Ｃｉｓ 值较 大，则说明此任务如果分配到内核 Ｐｋ上节省的通信 开销更多，相应的其优先级也较高。 在实际计算时， 因为任务 Ｔｉ的依赖任务已经全部分配执行，所以若 分配在内核 Ｐｋ上，通信开销是个定值，因此 ＰＣｉｋ只 需计算一次。 ｌ ｋ ＿ｍａｘ －｜ Ｔｌ ｋ ｜ ｌ ｋ＿ｍａｘ － ｌ ｋ＿ｍｉｎ 反应了内核的负载状 态， ｜ ＴＬｋ ｜ 是内核 Ｐｋ当前任务队列长度，当 ｜ ＴＬｋ ｜ ＝ ｌ ｋ＿ｍａｘ时其值为 ０，从而 Ｔｉｐｋ ＝ ０ 为最小值，则当前状态 下不能向内核 Ｐｋ分派任务。 在一次调度过程中，调 度程序可能需要响应多个内核的调度请求，对于 ｜ ＴＬｋ ｜较小的内核，其 Ｌｋ较大，从而实现优先将任务 分配到负载较轻的内核，并进而达到负载均衡效果。 综上所述，任务优先级值的计算，是对等待时 间、通信开销和内核负载 ３ 个因素综合考量的过程， 其结果可能不是单一因素中最优的，但一定是综合 考虑全部 ３ 种因素后最优的选择。 ３ 算法实现 在上节中详细介绍了任务优先级的计算，本节 将介绍 ＳＴＤＳ 算法的具体实现过程。 为了使任务调度算法得到较理想的实现，ＳＴＤＳ 算法的研究基于以下假设条件： １）假设任务间的依赖关系固定不变； ２）同一内核上任务间通信开销忽略不计； ３）任务不可抢占。 系统运行时首先将任务初始化，构造 ＴＤＳ，由于 算法中大多计算只针对就绪任务，特别是任务分配 时，所以为了节约计算开销，算法初始化时会生成一 个就绪任务列表和一个等待任务列表。 当内核 Ｐｋ 任务队列长度｜ Ｔｌ ｋ ｜ ≤ｌ ｋ＿ｍｉｎ时，就向调度程序请求分 配任务，调度程序遍历就绪列表，计算相对于内核 Ｐｋ的优先级，选择优先级 Ｔｉｐ值最大的任务分配到 Ｐｋ 上，重复执行此过程，直到内核 Ｐｋ 任务队列长度 ｜ Ｔｌ ｋ ｜≥ｌ ｋ。 若同时有多个内核请求任务分配，调度 程序分配任务时需要响应这几个内核的请求，计算 优先级时需要计算相对于这几个内核的优先级，然 后取最大值作为最终优先级，调度程序选择优先级 最大的任务分配到对应的内核。 值得注意的是在动态调度过程中，为了保证数 据实时有效，ＳＴＤＳ 算法在每个任务分配完成或执行 结束时对数据进行更新。 当任务 Ｔｉ分配给内核 Ｐｋ 后，需要将任务 Ｔｉ对应数据项中的 Ｔｉｃ置为 ｋ，此时内 核 Ｐｋ负载也相应改变；当任务 Ｔｉ执行完成时，如果 任务 Ｔｊ依赖任务 Ｔｉ，需要将任务 Ｔｊ的 Ｔｉｄｎ值减 １，若 减 １ 后 Ｔｉｄｎ ＝ ０，将任务 Ｔｊ状态置为就绪态并从等待 列表移到就绪列表。 为了降低复杂度节省时间， ＳＴＤＳ 算法采用先记录再批量执行的方式，即在任务 执行期间暂时将完成的任务编号记录，在任务调度 程序执行时批量更新数据；如果任务 Ｔｉ执行完毕且 所有依赖 Ｔｉ的任务也执行完毕，就将任务 Ｔｉ的信息 从 ＴＤＳ 中删除，从而释放内存节省空间。 如果就绪列表为空，调度程序不会响应内核的 任务分配请求，当就绪列表和等待列表全为空时，说 明任务全部执行完毕，调度结束。 ＳＴＤＳ 算法实现步骤： Ｐｒｏｃｅｄｕｒｅ ＳＴＤＳ（ＳＭ，ＴＤＳ， ＰＬｉｓｔ，ＴＬｅｘｅ ） ／ ∗ＳＭ 表 示处理器内核系统；ＴＤＳ 是所有任务信息； ＰＬｉｓｔ 是需 要分配任务的内核列表， ＴＬｅｘｅ 是执行完毕但还未进 行信息更新的任务列表∗／ １）｛ｆｏｒ ｅａｃｈ Ｔｉ∈ ＴＬｅｘｅ ２） ｛ Ｔｉａ ［］←Ｔｉ； ３） ｆｏｒ ｅａｃｈ Ｔｊ∈Ｔｉａ ４） Ｔｊｄｎ←Ｔｊｄｎ －１； ／ ∗执行完毕的任务信息 更新，将其后继任务的依赖任务数量减一∗／ ｝ ／ ∗ ｅｎｄ ｆｏｒ ｅａｃｈ Ｔｉ∈ ＴＬｅｘｅ ∗／ ５）ＴＬｒｅａｄｙ［］←ＴＤＳ；／ ∗就绪任务放入就绪队列∗／ ６） ｆｏｒ ｅａｃｈ Ｔｉ∈ＴＬｒｅａｄｙ ７）｛ ｆｏｒ ｅａｃｈ Ｐｋ∈ ＰＬｉｓｔ ·３２８· 智 能 系 统 学 报 第 １０ 卷
第2期 刘正：基于动态任务调度的STDS算法设计研究 ·329. 8) C←-式(10)；/*任务T若在内核P 处于同一量级。 上与前驱任务的通信开销，只需计算一次*/ 4实验 /end for each T;e TLrady 9)while(TL cady≠and Pu≠) 任务调度目前还没有形成统一规范的性能测试 l0){for each T:∈TL ady 方案4]，大多数对调度算法的研究都是采用随机 11) {PW:-式(7)； DAG图生成器来生成各种不同形状的DAG图集合 12) for each P∈Puis 作为任务调度算法的测试用例。 13) {PC4-式(8)： 文中借助TGF℉工具生成随机任务图，并以 14) L4←-式(9)； 此完成TDS初始化，用内核上任务长度表示负载 15) Tt←-式(6)； 情况，通过任务总执行时间和负载均衡等衡量算 /end for each P PList * 法优劣，在Simics1s]模拟平台上对本文算法性能 16) Tip =max Tk: 进行模拟实验测试。为了测试本文提出的算法 /end for each T;E TLd,* 对并行任务调度问题的求解效果，采用下面2类 17) T←-max T{;/*选出最大优先级的 实验来验证。 任务，设T就是选出的任务，且其对应内核为P,即 4.1参数对调度算法的影响 To=Tim * STDS算法用到的参数有：粒度因子1、负载因子 18)TL,←TL+{T};/*任务T,分配给 δ，和δ2、实时性因子B。1的大小决定一次调度过 内核P,*/ 程分配的任务数量，进而决定调度频度；l、δ，和δ2 19）TLea←-TLa,-{T}: 共同影响着负载均衡；B主要调节算法实时性。下 20)T=s; 面分别通过实验数据说明参数l、8,、62、B对STDS 21)if ITL,I=l.ms then PLs +PLis -P.; 算法性能的影响。 /*内核P分配任务结束*/ 1)调度粒度对STDS算法调度频度和负载影响 22)if TL吨≠☑then return;/*没有就绪 通过TGFF工具分别生成具有3OO0个任务和 任务*/ 5000个任务的随机任务图，测试这2类任务在不同 /end for while * 调度粒度下的调度效果，为屏蔽其他因素影响，设置 参数B=0,l4min=l4(1-δ2)=2，结果如图3所 其中1)~5)是算法对执行完毕但未进行数 示。由图3可以看出，调度次数随着调度粒度增大 据更新的任务进行处理，将其后继任务的T属 而减小，进而降低STDS调度算法消耗时间：粒度较 性值减1，且减为0时放入就绪队列等待调度。 小时调度次数减少幅度较大，而在较大粒度情况下 算法中有两重循环，外层循环遍历T列表，内 效果较弱。 层循环遍历后继任务列表，所以时间复杂度为 0(n)×0(logn)=0(nlog n)。而任务更新发生 12*10 10 ◆-5000 在每次任务分配时，次数大约为任务数量与调度 。-3000 粒子比值即n八，而在具体应用环境中调度粒子 6 为定值，所以数据更新总时间复杂度为 豆 4 0(n1ogn)。6~20是进行任务分配，其中优先级 2 计算是关键。计算每个任务相对于每个请求分 0 68 1012 配任务内核的优先级，其时间复杂度为O(mn), 调度粒度 其中m是内核数量，n是就绪任务数量。而算法 图3调度粒度对调度次数影响 最终需要将任务全部分配完成，所以任务分配的 Fig.3 Change of scheduling times in the situation of 总时间复杂度为0(mn)×0(n)=0(mn2)。因此 different scheduling granularities STDS算法的时间复杂度为O(n2logn)+ 虽然较大粒度下节省调度时间，但并不是( O(mn2)=Max(0(n'logn),0(mn2)),而经典 取最大值时STDS算法性能最优，I取极大值时， Min-Min算法的时间复杂度为O(mn2)【13],两者 调度频度最小，但此时对于内核P:的请求，STDS
８） Ｃｉｋ←式（１０）； ／ ∗任务 Ｔｉ若在内核 Ｐｋ 上与前驱任务的通信开销，只需计算一次 ∗／ ｝ ／ ∗ ｅｎｄ ｆｏｒ ｅａｃｈ Ｔｉ∈ＴＬｒｅａｄｙ∗／ ９）ｗｈｉｌｅ（ＴＬｒｅａｄｙ≠⌀ ａｎｄ ＰＬｉｓｔ ≠⌀） １０）｛ ｆｏｒ ｅａｃｈ Ｔｉ ∈ＴＬｒｅａｄｙ １１） ｛ ＰＷｉ←式（７）； １２） ｆｏｒ ｅａｃｈ Ｐｋ ∈ ＰＬｉｓｔ １３） ｛ ＰＣｉｋ←式（８）； １４） Ｌｋ ←式（９）； １５） Ｔｉｐｋ ←式（６）； ｝ ／ ∗ ｅｎｄ ｆｏｒ ｅａｃｈ Ｐｋ∈ ＰＬｉｓｔ ∗／ １６） Ｔｉｐ ＝ｍａｘ｛ Ｔｉｐｋ｝； ｝ ／ ∗ ｅｎｄ ｆｏｒ ｅａｃｈ Ｔｉ∈ＴＬｒｅａｄｙ∗／ １７） Ｔｊ ←ｍａｘ｛ Ｔｉｐ｝； ／ ∗选出最大优先级的 任务，设 Ｔｊ就是选出的任务，且其对应内核为 Ｐｓ，即 Ｔｊｐ ＝ Ｔ ｊｐｓ ∗／ １８） ＴＬｓ ← ＴＬｓ ＋ ｛Ｔｊ｝； ／ ∗ 任务 Ｔｊ 分配给 内核 Ｐｓ∗／ １９） ＴＬｒｅａｄｙ←ＴＬｒｅａｄｙ －｛Ｔｊ｝； ２０） Ｔ ｊｃ ＝ ｓ ； ２１） ｉｆ ｜ ＴＬｓ ｜ ＝ ｌ ｓ＿ｍａｘ ｔｈｅｎ ＰＬｉｓｔ ← ＰＬｉｓｔ －｛Ｐｓ｝； ／ ∗内核 Ｐｓ分配任务结束∗／ ２２） ｉｆ ＴＬｒｅａｄｙ≠⌀ ｔｈｅｎ ｒｅｔｕｒｎ； ／ ∗没有就绪 任务∗／ ｝ ／ ∗ ｅｎｄ ｆｏｒ ｗｈｉｌｅ∗／ ｝ 其中 １） ～ ５）是算法对执行完毕但未进行数 据更新的任务进行处理，将其后继任务的 Ｔｉｄｎ属 性值减 １，且减为 ０ 时放入就绪队列等待调度。 算法中有两重循环，外层循环遍历 ＴＬｅｘｅ 列表，内 层循环遍历后继任务列表，所以时 间 复 杂 度 为 Ｏ（ ｎ） ×Ｏ（ ｌｏｇ ｎ） ＝ Ｏ（ ｎｌｏｇ ｎ） 。 而任务更新发生 在每次任务分配时，次数大约为任务数量与调度 粒子比值即 ｎ ／ ｌ，而在具体应用环境中调度粒子 为 定 值， 所 以 数 据 更 新 总 时 间 复 杂 度 为 Ｏ（ ｎ ２ ｌｏｇ ｎ） 。 ６ ～ ２０ 是进行任务分配，其中优先级 计算是关键。 计算每个任务相对于每个请求分 配任务内核的优先级，其时间复杂度为 Ｏ（ ｍｎ） ， 其中 ｍ 是内核数量，ｎ 是就绪任务数量。 而算法 最终需要将任务全部分配完成，所以任务分配的 总时间复杂度为 Ｏ（ ｍｎ） ×Ｏ（ ｎ） ＝ Ｏ（ ｍｎ ２ ） 。 因此 ＳＴＤＳ 算 法 的 时 间 复 杂 度 为 Ｏ （ ｎ ２ ｌｏｇ ｎ ） ＋ Ｏ（ ｍｎ ２ ） ＝ Ｍａｘ（ Ｏ（ ｎ ２ ｌｏｇ ｎ） ， Ｏ （ ｍｎ ２ ） ） ， 而 经 典 Ｍｉｎ⁃Ｍｉｎ 算法的时间复杂度为 Ｏ（ ｍｎ ２ ） ［ １３ ］ ，两者 处于同一量级。 ４ 实验 任务调度目前还没有形成统一规范的性能测试 方案［１ ４ ］ ，大多数对调度算法的研究都是采用随机 ＤＡＧ 图生成器来生成各种不同形状的 ＤＡＧ 图集合 作为任务调度算法的测试用例。 文中借助 ＴＧＦＦ 工具生成随机任务图，并以 此完成 ＴＤＳ 初始化，用内核上任务长度表示负载 情况，通过任务总执行时间和负载均衡等衡量算 法优劣，在 Ｓｉｍｉｃｓ ［ １ ５ ］ 模拟平台上对本文算法性能 进行模拟实验测试。 为了测试本文提出的算法 对并行任务调度问题的求解效果，采用下面 ２ 类 实验来验证。 ４．１ 参数对调度算法的影响 ＳＴＤＳ 算法用到的参数有：粒度因子 ｌ、负载因子 δ １ 和 δ ２ 、实时性因子 β 。 ｌ 的大小决定一次调度过 程分配的任务数量，进而决定调度频度；ｌ、 δ １ 和 δ ２ 共同影响着负载均衡； β 主要调节算法实时性。 下 面分别通过实验数据说明参数 ｌ、 δ １ 、 δ ２ 、 β 对 ＳＴＤＳ 算法性能的影响。 １）调度粒度对 ＳＴＤＳ 算法调度频度和负载影响 通过 ＴＧＦＦ 工具分别生成具有 ３ ０００ 个任务和 ５ ０００ 个任务的随机任务图，测试这 ２ 类任务在不同 调度粒度下的调度效果，为屏蔽其他因素影响，设置 参数 β ＝ ０， ｌ ｋ＿ｍｉｎ ＝ ｌ ｋ（１ － δ ２ ） ＝ ２，结果如图 ３ 所 示。 由图 ３ 可以看出，调度次数随着调度粒度增大 而减小，进而降低 ＳＴＤＳ 调度算法消耗时间；粒度较 小时调度次数减少幅度较大，而在较大粒度情况下 效果较弱。 图 ３ 调度粒度对调度次数影响 Ｆｉｇ．３ Ｃｈａｎｇｅ ｏｆ ｓｃｈｅｄｕｌｉｎｇ ｔｉｍｅｓ ｉｎ ｔｈｅ ｓｉｔｕａｔｉｏｎ ｏｆ ｄｉｆｆｅｒｅｎｔ ｓｃｈｅｄｕｌｉｎｇ ｇｒａｎｕｌａｒｉｔｉｅｓ 虽然较大粒度下节省调度时间，但并不是 ｌ 取最大值时 ＳＴＤＳ 算法性能最优，ｌ 取极大值时， 调度频度最小，但此时对于内核 Ｐｋ的请求，ＳＴＤＳ 第 ２ 期 刘正：基于动态任务调度的 ＳＴＤＳ 算法设计研究 ·３２９·
·330· 智能系统学报 第10卷 算法会将全部就绪任务分配给P:,从而造成各 核负载3种因素共同决定的，通过实时性因子可以 内核上负载差别较大。表1说明了粒度对负载 调节等待时间因素的重要程度，实时性因子反映了 均衡的影响，在调度过程中对内核负载进行采 系统对等待时间的容忍程度。表2是在B取不同值 样，每次采样时，用此时内核上任务队列长度占 时对STDS算法平均等待时间和总运行时间的影 所有内核任务队列长度之和的比例，评价负载均 响，其中AWT(average of wait time)表示平均等待时 衡效果。表1中P。、P,、P2的处理速度为1GHz, 间，此时设置l=6,8,=1/3,δ2=2/3以消除其他因 P,的处理速度为2GHz,据STDS算法设定，P,的 素影响。由表2可以看出，随着B值的增大，等待时 负载应为P。、P,、P,的2倍。从表1可以看出，负 间最大的100个任务的平均等待时间减小，而全部 载均衡效果随调度粒度的增大而降低。 任务的平均等待时间的趋势不能确定，因为此时通 表1调度粒度对负载均衡影响 信开销不是最小的，所以算法总执行时间增大，从而 Table 1 Change of load balancing in the situation of differ- 会造成某些任务的等待时间增大。在B取较大值 ent scheduling granularities (>2.0)时，STDS算法性能基本不再变化，此时STDS 调度粒度P。/%P,/% P,/% P3/% 算法近似于先来先服务(FIFO)算法。所以B应取 19.61 20.44 20.3739.58 满足系统对实时性要求前提下的最小值。 20.11 19.80 21.19 38.90 表2实时性因子对算法性能影响 14 22.51 19.13 20.9137.45 Table 2 Change of performance in the situation of differ- ent real-time factors 2)负载因子对算法性能影响 6,是负载上限因子，6，是负载下限因子，δ和6， AWT of Top100/ms AWT of All/ms运行时间/ms 0 7603.11 689.446 32562 满足公式(5)约束条件：81+62=1，当62确定时，8 的值也是确定的。δ，的大小决定了内核P调度队列 0.4 6752.75 1084.344 34250 长度下限l_min的大小，lmin较大时，内核P的负 0.8 6179.30 901.595 34922 载也相对较大，然而此时会引发另一个问题，虽然内 1.0 4838.11 882.158 35125 核P,负载达到下限lmin并请求分配任务，但此刻 2.0 4517.32 911.572 35756 P依然有较多任务待执行，当就绪任务不是很充足 5.0 4497.84 926.485 35998 时，容易发生STDS算法频繁响应分配请求。图4是 综上所述，参数会对算法的调度时间、调度次 在δ，取不同值时的调度统计结果，固定调度粒度1= 数、负载均衡效果以及实时性产生影响，对于不同应 6,可以看出，调度次数随着6，的增大而增大。 用环境，应适当调整参数大小，在满足系统要求前提 下充分发挥算法性能。对于实时性要求不严格系 ×10 统，可以减少实时因子大小，降低总调度时间：对于 6 规模较大系统，应增大调度粒度在减小调度次数，尽 量减少调度器的调度压力，适当增大负载下限因子， 保证在调度器调度不及时情况下，内核依然有充足 3 的任务可以执行：反之亦然。本文没有明确参数值 ◆-5000 -3000 的具体大小，此工作需要通过大量具体的实际实验 完成。 1 1 82 4.2算法对比实验 图4负载因子对调度次数影响 为有效评价STDS算法性能，将其与Mim-Min Fig.4 Change of scheduling times in the situation of 算法和文献[11]的Vinay算法进行比较。对于每个 different load factor 固定的内核数，通过TGF℉工具随机产生10组5000 3)实时性因子对算法性能影响 节点的DAG图，记录其调度执行时间，然后求出其 STDS算法设立实时性因子主要是解决就绪任 平均值。由于内核数目改变，系统模型发生变化，所 务长时间得不到内核资源的“饥饿”现象。由式(6) 以实验时适当调节STDS算法参数，以充分发挥算 可知，任务优先级是任务等待时间、任务间通信和内 法性能，表3是不同内核数目时STDS算法参数取 值，内核数目较多时，增大调度粒度L,虽然负载均衡
算法会将全部就绪任务分配给 Ｐｋ， 从而造成各 内核上负载差别较大。 表 １ 说明了粒度对负载 均衡的影响，在调度过程中对内核 负 载 进 行 采 样，每次采样时，用此时内核上任务队列长度占 所有内核任务队列长度之和的比例，评价负载均 衡效果。 表 １ 中 Ｐ０ 、Ｐ１ 、Ｐ２的处理速度为 １ ＧＨｚ， Ｐ３的处理速度为 ２ ＧＨｚ，据 ＳＴＤＳ 算法设定，Ｐ３的 负载应为 Ｐ０ 、Ｐ１ 、Ｐ２的 ２ 倍。 从表 １ 可以看出，负 载均衡效果随调度粒度的增大而降低。 表 １ 调度粒度对负载均衡影响 Ｔａｂｌｅ １ Ｃｈａｎｇｅ ｏｆ ｌｏａｄ ｂａｌａｎｃｉｎｇ ｉｎ ｔｈｅ ｓｉｔｕａｔｉｏｎ ｏｆ ｄｉｆｆｅｒ⁃ ｅｎｔ ｓｃｈｅｄｕｌｉｎｇ ｇｒａｎｕｌａｒｉｔｉｅｓ 调度粒度 Ｐ０ ／ ％ Ｐ１ ／ ％ Ｐ２ ／ ％ Ｐ３ ／ ％ ２ １９．６１ ２０．４４ ２０．３７ ３９．５８ ８ ２０．１１ １９．８０ ２１．１９ ３８．９０ １４ ２２．５１ １９．１３ ２０．９１ ３７．４５ ２）负载因子对算法性能影响 δ１ 是负载上限因子， δ２ 是负载下限因子， δ１ 和 δ２ 满足公式（５）约束条件： δ１ ＋ δ２ ＝ １，当 δ２ 确定时， δ１ 的值也是确定的。 δ２ 的大小决定了内核 Ｐｋ调度队列 长度下限 ｌ ｋ＿ｍｉｎ 的大小， ｌ ｋ＿ｍｉｎ 较大时，内核 Ｐｋ的负 载也相对较大，然而此时会引发另一个问题，虽然内 核 Ｐｋ负载达到下限 ｌ ｋ＿ｍｉｎ 并请求分配任务，但此刻 Ｐｋ依然有较多任务待执行，当就绪任务不是很充足 时，容易发生 ＳＴＤＳ 算法频繁响应分配请求。 图 ４ 是 在 δ２ 取不同值时的调度统计结果，固定调度粒度 ｌ ＝ ６，可以看出，调度次数随着 δ２ 的增大而增大。 图 ４ 负载因子对调度次数影响 Ｆｉｇ．４ Ｃｈａｎｇｅ ｏｆ ｓｃｈｅｄｕｌｉｎｇ ｔｉｍｅｓ ｉｎ ｔｈｅ ｓｉｔｕａｔｉｏｎ ｏｆ ｄｉｆｆｅｒｅｎｔ ｌｏａｄ ｆａｃｔｏｒ ３）实时性因子对算法性能影响 ＳＴＤＳ 算法设立实时性因子主要是解决就绪任 务长时间得不到内核资源的“饥饿”现象。 由式（６） 可知，任务优先级是任务等待时间、任务间通信和内 核负载 ３ 种因素共同决定的，通过实时性因子可以 调节等待时间因素的重要程度，实时性因子反映了 系统对等待时间的容忍程度。 表 ２ 是在 β 取不同值 时对 ＳＴＤＳ 算法平均等待时间和总运行时间的影 响，其中 ＡＷＴ（ａｖｅｒａｇｅ ｏｆ ｗａｉｔ ｔｉｍｅ）表示平均等待时 间，此时设置 ｌ ＝ ６， δ１ ＝ １ ／ ３， δ２ ＝ ２ ／ ３ 以消除其他因 素影响。 由表 ２ 可以看出，随着 β 值的增大，等待时 间最大的 １００ 个任务的平均等待时间减小，而全部 任务的平均等待时间的趋势不能确定，因为此时通 信开销不是最小的，所以算法总执行时间增大，从而 会造成某些任务的等待时间增大。 在 β 取较大值 （＞２．０）时，ＳＴＤＳ 算法性能基本不再变化，此时 ＳＴＤＳ 算法近似于先来先服务（ＦＩＦＯ）算法。 所以 β 应取 满足系统对实时性要求前提下的最小值。 表 ２ 实时性因子对算法性能影响 Ｔａｂｌｅ ２ Ｃｈａｎｇｅ ｏｆ ｐｅｒｆｏｒｍａｎｃｅ ｉｎ ｔｈｅ ｓｉｔｕａｔｉｏｎ ｏｆ ｄｉｆｆｅｒ⁃ ｅｎｔ ｒｅａｌ⁃ｔｉｍｅ ｆａｃｔｏｒｓ β ＡＷＴ ｏｆ Ｔｏｐ １００ ／ ｍｓ ＡＷＴ ｏｆ Ａｌｌ ／ ｍｓ 运行时间／ ｍｓ ０ ７ ６０３．１１ ６８９．４４６ ３２ ５６２ ０．４ ６ ７５２．７５ １ ０８４．３４４ ３４ ２５０ ０．８ ６ １７９．３０ ９０１．５９５ ３４ ９２２ １．０ ４ ８３８．１１ ８８２．１５８ ３５ １２５ ２．０ ４ ５１７．３２ ９１１．５７２ ３５ ７５６ ５．０ ４ ４９７．８４ ９２６．４８５ ３５ ９９８ 综上所述，参数会对算法的调度时间、调度次 数、负载均衡效果以及实时性产生影响，对于不同应 用环境，应适当调整参数大小，在满足系统要求前提 下充分发挥算法性能。 对于实时性要求不严格系 统，可以减少实时因子大小，降低总调度时间；对于 规模较大系统，应增大调度粒度在减小调度次数，尽 量减少调度器的调度压力，适当增大负载下限因子， 保证在调度器调度不及时情况下，内核依然有充足 的任务可以执行；反之亦然。 本文没有明确参数值 的具体大小，此工作需要通过大量具体的实际实验 完成。 ４．２ 算法对比实验 为有效评价 ＳＴＤＳ 算法性能，将其与 Ｍｉｎ⁃Ｍｉｎ 算法和文献［１１］的 Ｖｉｎａｙ 算法进行比较。 对于每个 固定的内核数，通过 ＴＧＦＦ 工具随机产生 １０ 组５ ０００ 节点的 ＤＡＧ 图，记录其调度执行时间，然后求出其 平均值。 由于内核数目改变，系统模型发生变化，所 以实验时适当调节 ＳＴＤＳ 算法参数，以充分发挥算 法性能，表 ３ 是不同内核数目时 ＳＴＤＳ 算法参数取 值，内核数目较多时，增大调度粒度 ｌ，虽然负载均衡 ·３３０· 智 能 系 统 学 报 第 １０ 卷
第2期 刘正：基于动态任务调度的STDS算法设计研究 ·331· 效果有所下降，但降低了调度次数。图5是STDS 12 算法、Min-Min和Vinay算法在不同内核数目下执行 10 ▣STDS Min-Min 时间的比较结果。 由图5可以看出在内核数目较少时，Vinay算法 6 4 比较高效，这是因为Vinay算法实现简单，算法复杂 度低，每个内核分配一个任务，不需要考虑负载均衡 0 8 16 32 等问题。随着内核数目增加，STDS算法优势逐步体 内核数目 现，这是因为Vinay算法一次调度分配一个任务，调 图6STDS算法与Min-Min算法等待时间对 度较频繁，内核数目较多时，会发生多个内核同时请 Fig.6 Comparison of waiting time between STDS and Min-Min 求调度，但同一时刻只有一个内核可以调度成功，其 他内核不得不等待。STDS算法为每个内核设置一 可以看出STDS算法中任务最大等待时间明显 个任务队列，每次调度会分配若干个任务，这样虽然 小于Min-Min算法。由此也可以得出STDS算法的 增大了算法复杂度，但减少了调度次数且最大限度 另一大优势，就是可以通过调整参数取值，从而适应 避免了内核等待现象，所以总时间较小。STDS算法 不同的系统要求。为了排除偶然因素影响，本文通 比较适合内核数目较多的系统，但值得注意的是在 过生成另外9组不同结构的3000个节点与5000 内核数目较多的系统中，对任务量的要求也较大，否 个节点的DAG图，进行相同的实验，实验结果与上 则难以充分发挥多核系统和STDS算法性能。 述描述吻合。 表3不同内核数目时的参数值 5结束语 Table 3 Value of parameters in the situation of different quantity of cores 文中研究了异构多核动态任务调度算法，结合 内核数目 设计的调度模型，提出了动态任务调度STDS算法。 3 1/3 2/3 0.1 该算法分析了调度粒度对任务调度的影响可以根据 4 4 1/2 1/2 0.1 当前内核负载和任务状态调整任务优先级，从而将 8 6 1/3 2/3 0.1 高优先级的任务合理高效地分配到内核，并通过限 定内核任务队列的上下限值达到负载均衡的目的。 16 6 1/2 1/2 0.1 通过引入实时性因子使任务总能及时得到执行处 32 10 3/10 7/10 0.1 理，减少了过长的等待时间。实验表明，STDS算法 ×10 在内核较大情况下效率较高，且能够保持负载均衡。 3 ◆-STDS Vinay 参考文献： Min-Min 9 [1]GENG X,XU G,ZHANG Y.Dynamic load balancing scheduling model based on multi-core processor[C]//2010 Fifth International Conference on Frontier of Computer Sci- ence and Technology (FCST).[S.1.]2010:398-403. 8 16 [2]GRAY M R,JOHNSON D S.Computers and intractability: 内核数目 a guide to the theory of NP-completeness[M].New York: 图5STDS、Min-Min、Vinay算法执行时间 W H Freeman and Company,1979:92-115. Fig.5 Comparison of running time among STDS, [3]JIN H,CHEN H,CHEN J,et al.Real-time strategy and Min-Min andVinay practice in service grid[C]//Proceedings of the 28th Annu- STDS算法复杂度与Min-Min算法相当，但调度 al International on Computer Software and Applications Con- 运行时间比Min-Min算法稍长，原因是Min-Min算 ference,2004.2004:161-166. 法将运行时间作为其唯一考虑因素，优先选取最早 [4]HE X S,SUN X H,VON LASZEWSKI G.A QoS guided 完成时间最小的任务进行调度。但Min-Min算法中 scheduling algorithm for grid computing[J].Journal of Com- 执行时间较长的任务得不到及时执行，图6是STDS puter Science and Technology,2003,18(4):442-451. [5]FREUND R F,GHERRITY M,AMBROSIUS S,et al. 算法与Min-Min算法等待时间的对比结果。 Scheduling resources in multi-user,heterogeneous,compu-
效果有所下降，但降低了调度次数。 图 ５ 是 ＳＴＤＳ 算法、Ｍｉｎ⁃Ｍｉｎ 和 Ｖｉｎａｙ 算法在不同内核数目下执行 时间的比较结果。 由图 ５ 可以看出在内核数目较少时，Ｖｉｎａｙ 算法 比较高效，这是因为 Ｖｉｎａｙ 算法实现简单，算法复杂 度低，每个内核分配一个任务，不需要考虑负载均衡 等问题。 随着内核数目增加，ＳＴＤＳ 算法优势逐步体 现，这是因为 Ｖｉｎａｙ 算法一次调度分配一个任务，调 度较频繁，内核数目较多时，会发生多个内核同时请 求调度，但同一时刻只有一个内核可以调度成功，其 他内核不得不等待。 ＳＴＤＳ 算法为每个内核设置一 个任务队列，每次调度会分配若干个任务，这样虽然 增大了算法复杂度，但减少了调度次数且最大限度 避免了内核等待现象，所以总时间较小。 ＳＴＤＳ 算法 比较适合内核数目较多的系统，但值得注意的是在 内核数目较多的系统中，对任务量的要求也较大，否 则难以充分发挥多核系统和 ＳＴＤＳ 算法性能。 表 ３ 不同内核数目时的参数值 Ｔａｂｌｅ ３ Ｖａｌｕｅ ｏｆ ｐａｒａｍｅｔｅｒｓ ｉｎ ｔｈｅ ｓｉｔｕａｔｉｏｎ ｏｆ ｄｉｆｆｅｒｅｎｔ ｑｕａｎｔｉｔｙ ｏｆ ｃｏｒｅｓ 内核数目 ｌ δ１ δ２ β ２ ３ １ ／ ３ ２ ／ ３ ０．１ ４ ４ １ ／ ２ １ ／ ２ ０．１ ８ ６ １ ／ ３ ２ ／ ３ ０．１ １６ ６ １ ／ ２ １ ／ ２ ０．１ ３２ １０ ３ ／ １０ ７ ／ １０ ０．１ 图 ５ ＳＴＤＳ、Ｍｉｎ⁃Ｍｉｎ、Ｖｉｎａｙ 算法执行时间 Ｆｉｇ．５ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｒｕｎｎｉｎｇ ｔｉｍｅ ａｍｏｎｇ ＳＴＤＳ， Ｍｉｎ⁃Ｍｉｎ ａｎｄＶｉｎａｙ ＳＴＤＳ 算法复杂度与 Ｍｉｎ⁃Ｍｉｎ 算法相当，但调度 运行时间比 Ｍｉｎ⁃Ｍｉｎ 算法稍长，原因是 Ｍｉｎ⁃Ｍｉｎ 算 法将运行时间作为其唯一考虑因素，优先选取最早 完成时间最小的任务进行调度。 但 Ｍｉｎ⁃Ｍｉｎ 算法中 执行时间较长的任务得不到及时执行，图 ６ 是 ＳＴＤＳ 算法与 Ｍｉｎ⁃Ｍｉｎ 算法等待时间的对比结果。 图 ６ ＳＴＤＳ 算法与 Ｍｉｎ⁃Ｍｉｎ 算法等待时间对 Ｆｉｇ．６ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｗａｉｔｉｎｇ ｔｉｍｅ ｂｅｔｗｅｅｎ ＳＴＤＳ ａｎｄ Ｍｉｎ⁃Ｍｉｎ 可以看出 ＳＴＤＳ 算法中任务最大等待时间明显 小于 Ｍｉｎ⁃Ｍｉｎ 算法。 由此也可以得出 ＳＴＤＳ 算法的 另一大优势，就是可以通过调整参数取值，从而适应 不同的系统要求。 为了排除偶然因素影响，本文通 过生成另外 ９ 组不同结构的 ３ ０００ 个节点与 ５ ０００ 个节点的 ＤＡＧ 图，进行相同的实验，实验结果与上 述描述吻合。 ５ 结束语 文中研究了异构多核动态任务调度算法，结合 设计的调度模型，提出了动态任务调度 ＳＴＤＳ 算法。 该算法分析了调度粒度对任务调度的影响可以根据 当前内核负载和任务状态调整任务优先级，从而将 高优先级的任务合理高效地分配到内核，并通过限 定内核任务队列的上下限值达到负载均衡的目的。 通过引入实时性因子使任务总能及时得到执行处 理，减少了过长的等待时间。 实验表明，ＳＴＤＳ 算法 在内核较大情况下效率较高，且能够保持负载均衡。 参考文献： ［１］ ＧＥＮＧ Ｘ， ＸＵ Ｇ， ＺＨＡＮＧ Ｙ． Ｄｙｎａｍｉｃ ｌｏａｄ ｂａｌａｎｃｉｎｇ ｓｃｈｅｄｕｌｉｎｇ ｍｏｄｅｌ ｂａｓｅｄ ｏｎ ｍｕｌｔｉ⁃ｃｏｒｅ ｐｒｏｃｅｓｓｏｒ［Ｃ］ ／ ／ ２０１０ Ｆｉｆｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｆｒｏｎｔｉｅｒ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉ⁃ ｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ （ＦＣＳＴ）． ［Ｓ．ｌ．］，２０１０： ３９８⁃４０３． ［２］ＧＲＡＹ Ｍ Ｒ， ＪＯＨＮＳＯＮ Ｄ Ｓ． Ｃｏｍｐｕｔｅｒｓ ａｎｄ ｉｎｔｒａｃｔａｂｉｌｉｔｙ： ａ ｇｕｉｄｅ ｔｏ ｔｈｅ ｔｈｅｏｒｙ ｏｆ ＮＰ⁃ｃｏｍｐｌｅｔｅｎｅｓｓ［Ｍ］． Ｎｅｗ Ｙｏｒｋ： Ｗ Ｈ Ｆｒｅｅｍａｎ ａｎｄ Ｃｏｍｐａｎｙ， １９７９： ９２⁃１１５． ［３］ＪＩＮ Ｈ， ＣＨＥＮ Ｈ， ＣＨＥＮ Ｊ， ｅｔ ａｌ． Ｒｅａｌ⁃ｔｉｍｅ ｓｔｒａｔｅｇｙ ａｎｄ ｐｒａｃｔｉｃｅ ｉｎ ｓｅｒｖｉｃｅ ｇｒｉｄ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２８ｔｈ Ａｎｎｕ⁃ ａｌ Ｉｎｔｅｒｎａｔｉｏｎａｌ ｏｎ Ｃｏｍｐｕｔｅｒ Ｓｏｆｔｗａｒｅ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ Ｃｏｎ⁃ ｆｅｒｅｎｃｅ， ２００４． ２００４： １６１⁃１６６． ［４］ＨＥ Ｘ Ｓ， ＳＵＮ Ｘ Ｈ，ＶＯＮ ＬＡＳＺＥＷＳＫＩ Ｇ ． Ａ ＱｏＳ ｇｕｉｄｅｄ ｓｃｈｅｄｕｌｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｇｒｉｄ ｃｏｍｐｕｔｉｎｇ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍ⁃ ｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， ２００３，１８（４）： ４４２⁃４５１． ［５］ ＦＲＥＵＮＤ Ｒ Ｆ， ＧＨＥＲＲＩＴＹ Ｍ， ＡＭＢＲＯＳＩＵＳ Ｓ， ｅｔ ａｌ． Ｓｃｈｅｄｕｌｉｎｇ ｒｅｓｏｕｒｃｅｓ ｉｎ ｍｕｌｔｉ⁃ｕｓｅｒ， ｈｅｔｅｒｏｇｅｎｅｏｕｓ， ｃｏｍｐｕ⁃ 第 ２ 期 刘正：基于动态任务调度的 ＳＴＤＳ 算法设计研究 ·３３１·
.332. 智能系统学报 第10卷 ting environments with SmartNet[C]//Proceedings on Het- [11]VAIDYA V G,RANADIVE P,SAH S.Dynamic scheduler erogeneous Computing Workshop.,1998:184-199. for multi-core systems [C]//International Conference on [6]ARMSTRONG R,HENSGEN D,KIDD T.The relative per- Software Technology and Engineering,2010 2nd.Puerto formance of various mapping algorithms is independent of Rico:EEE,2010,1:V1-13-V1-16. sizable variances in run-time predictions[C]//Proceedings [12]陈锐忠，齐德昱，林伟伟.一种面向非对称多核处理器的 on Heterogeneous Computing Workshop.,1998:79-87. 综合性调度算法.软件学报，2013,24(2)：34-3357. [7]石威，郑纬民.相关任务图的均衡动态关键路径调度算 CHEN Ruozhong,QI Deyu,LIN Weiwei.Comprehensive 法[J].计算机学报，2001,24(9)：991-997. scheduling algorithm for asymmetric multi-core processors SHI Wei,ZHENG Weimin.The balanced dynamic critical [J].Journal of Software,2013,24(2):34-3357. path scheduling algorithm of dependent task graph[J].Chi- [12]邓晓衡，卢锡城，王怀民.VCE中基于可信评价的资 nese Journal of Computers,2001,24(9):991-997. 源调度研究[J].计算机学报，2007,30：1750-1762 [8]李仁发，刘彦，徐成.多处理器片上系统任务调度研究 DENG Xiaoheng,LU Xicheng,WANG Huaimin.Study on 进展评述[J].计算机研究与发展，2008,45(9)：1620- trust evaluation based resource scheduling in iVCE [J]. 1629. Chinese Joural of Computers,2007,30:1750-1762. LI Renfa,LIU Yan,XU Cheng.A survey of task scheduling [12]KWOK Y K,AHMAD I.Benchmarking the task graph research progress on multiprocessor system-on-chip[J]. scheduling algorithms [C]//Parallel Processing Symposi- Journal of Computer Research and Development,2008,45 um,1998.IPPS/SPDP 1998.Proceedings of the First (9):1620-1629. Merged International...and Symposium on Parallel and [9]耿晓中.基于多核分布式环境下的任务调度关键技术研 Distributed Processing 1998.IEEE,1998:531-537. 究[D].吉林：吉林大学，2013： [12]FORSGREN D,ESKILSON J,CHRISTENSSON M,et al. GENG Xiaozhong.Research on key techniques of task Simics:a full system simulation platform[J].IEEE Com- scheduling based on multi-core distributed environment[D]. puter,2002,35(2):50-58. Jilin:Jilin University,2013. 作者简介： [10]徐雨明，李肯立.异构系统中DAG任务调度的双螺旋 结构遗传算法[J].计算机研究与发展，2014,51(6)： 刘正，男，1983年生，讲师，博士研 1240-1252 究生，主要研究方向为性能优化、信息 XU Yuming,LI Kenli.A structure genetic algorithm for 安全与智能信息处理。 task scheduling double-helix on heterogeneous computing systems [J].Journal of Computer Research and Develop- ment,2014,51(6):1240-1252
ｔｉｎｇ ｅｎｖｉｒｏｎｍｅｎｔｓ ｗｉｔｈ ＳｍａｒｔＮｅｔ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｎ Ｈｅｔ⁃ ｅｒｏｇｅｎｅｏｕｓ Ｃｏｍｐｕｔｉｎｇ Ｗｏｒｋｓｈｏｐ． ， １９９８： １８４⁃１９９． ［６］ＡＲＭＳＴＲＯＮＧ Ｒ， ＨＥＮＳＧＥＮ Ｄ， ＫＩＤＤ Ｔ． Ｔｈｅ ｒｅｌａｔｉｖｅ ｐｅｒ⁃ ｆｏｒｍａｎｃｅ ｏｆ ｖａｒｉｏｕｓ ｍａｐｐｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｉｓ ｉｎｄｅｐｅｎｄｅｎｔ ｏｆ ｓｉｚａｂｌｅ ｖａｒｉａｎｃｅｓ ｉｎ ｒｕｎ⁃ｔｉｍｅ ｐｒｅｄｉｃｔｉｏｎｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｎ Ｈｅｔｅｒｏｇｅｎｅｏｕｓ Ｃｏｍｐｕｔｉｎｇ Ｗｏｒｋｓｈｏｐ． ， １９９８： ７９⁃８７． ［７］石威， 郑纬民． 相关任务图的均衡动态关键路径调度算 法［Ｊ］． 计算机学报， ２００１， ２４（９）： ９９１⁃９９７． ＳＨＩ Ｗｅｉ， ＺＨＥＮＧ Ｗｅｉｍｉｎ． Ｔｈｅ ｂａｌａｎｃｅｄ ｄｙｎａｍｉｃ ｃｒｉｔｉｃａｌ ｐａｔｈ ｓｃｈｅｄｕｌｉｎｇ ａｌｇｏｒｉｔｈｍ ｏｆ ｄｅｐｅｎｄｅｎｔ ｔａｓｋ ｇｒａｐｈ［Ｊ］． Ｃｈｉ⁃ ｎｅｓｅ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒｓ， ２００１， ２４（９）： ９９１⁃９９７． ［８］李仁发， 刘彦， 徐成． 多处理器片上系统任务调度研究 进展评述［Ｊ］． 计算机研究与发展， ２００８， ４５（９）： １６２０⁃ １６２９． ＬＩ Ｒｅｎｆａ， ＬＩＵ Ｙａｎ， ＸＵ Ｃｈｅｎｇ． Ａ ｓｕｒｖｅｙ ｏｆ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ｒｅｓｅａｒｃｈ ｐｒｏｇｒｅｓｓ ｏｎ ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ ｓｙｓｔｅｍ⁃ｏｎ⁃ｃｈｉｐ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ， ２００８， ４５ （９）： １６２０⁃１６２９． ［９］耿晓中． 基于多核分布式环境下的任务调度关键技术研 究［Ｄ］． 吉林： 吉林大学， ２０１３： ． ＧＥＮＧ Ｘｉａｏｚｈｏｎｇ． Ｒｅｓｅａｒｃｈ ｏｎ ｋｅｙ ｔｅｃｈｎｉｑｕｅｓ ｏｆ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ｂａｓｅｄ ｏｎ ｍｕｌｔｉ⁃ｃｏｒｅ ｄｉｓｔｒｉｂｕｔｅｄ ｅｎｖｉｒｏｎｍｅｎｔ［Ｄ］． Ｊｉｌｉｎ： Ｊｉｌｉｎ Ｕｎｉｖｅｒｓｉｔｙ， ２０１３． ［１０］徐雨明，李肯立． 异构系统中 ＤＡＧ 任务调度的双螺旋 结构遗传算法［ Ｊ］． 计算机研究与发展，２０１４，５１（ ６）： １２４０⁃１２５２． ＸＵ Ｙｕｍｉｎｇ， ＬＩ Ｋｅｎｌｉ． Ａ ｓｔｒｕｃｔｕｒｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ｄｏｕｂｌｅ⁃ｈｅｌｉｘ ｏｎ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｃｏｍｐｕｔｉｎｇ ｓｙｓｔｅｍｓ ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐ⁃ ｍｅｎｔ， ２０１４， ５１（６）： １２４０⁃１２５２． ［１１］ＶＡＩＤＹＡ Ｖ Ｇ， ＲＡＮＡＤＩＶＥ Ｐ， ＳＡＨ Ｓ． Ｄｙｎａｍｉｃ ｓｃｈｅｄｕｌｅｒ ｆｏｒ ｍｕｌｔｉ⁃ｃｏｒｅ ｓｙｓｔｅｍｓ ［ Ｃ］ ／ ／ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｏｆｔｗａｒｅ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， ２０１０ ２ｎｄ． Ｐｕｅｒｔｏ Ｒｉｃｏ： ＩＥＥＥ， ２０１０， １： Ｖ１⁃１３⁃Ｖ１⁃１６． ［１２］陈锐忠，齐德昱，林伟伟．一种面向非对称多核处理器的 综合性调度算法． 软件学报， ２０１３， ２４（２）： ３４⁃３３５７． ＣＨＥＮ Ｒｕｏｚｈｏｎｇ， ＱＩ Ｄｅｙｕ， ＬＩＮ Ｗｅｉｗｅｉ． Ｃｏｍｐｒｅｈｅｎｓｉｖｅ ｓｃｈｅｄｕｌｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｓｙｍｍｅｔｒｉｃ ｍｕｌｔｉ⁃ｃｏｒｅ ｐｒｏｃｅｓｓｏｒｓ ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔｗａｒｅ， ２０１３， ２４（２）： ３４⁃３３５７． ［１２］邓晓衡， 卢锡城， 王怀民． ｉＶＣＥ 中基于可信评价的资 源调度研究［Ｊ］． 计算机学报， ２００７， ３０： １７５０⁃１７６２． ＤＥＮＧ Ｘｉａｏｈｅｎｇ， ＬＵ Ｘｉｃｈｅｎｇ， ＷＡＮＧ Ｈｕａｉｍｉｎ． Ｓｔｕｄｙ ｏｎ ｔｒｕｓｔ ｅｖａｌｕａｔｉｏｎ ｂａｓｅｄ ｒｅｓｏｕｒｃｅ ｓｃｈｅｄｕｌｉｎｇ ｉｎ ｉＶＣＥ ［ Ｊ］． Ｃｈｉｎｅｓｅ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒｓ， ２００７， ３０： １７５０⁃１７６２． ［１２］ ＫＷＯＫ Ｙ Ｋ， ＡＨＭＡＤ Ｉ． Ｂｅｎｃｈｍａｒｋｉｎｇ ｔｈｅ ｔａｓｋ ｇｒａｐｈ ｓｃｈｅｄｕｌｉｎｇ ａｌｇｏｒｉｔｈｍｓ ［ Ｃ］ ／ ／ Ｐａｒａｌｌｅｌ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｍｐｏｓｉ⁃ ｕｍ， １９９８． ＩＰＰＳ ／ ＳＰＤＰ １９９８． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｆｉｒｓｔ Ｍｅｒｇｅｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ．．． ａｎｄ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｐｒｏｃｅｓｓｉｎｇ １９９８． ＩＥＥＥ， １９９８： ５３１⁃５３７． ［１２］ＦＯＲＳＧＲＥＮ Ｄ， ＥＳＫＩＬＳＯＮ Ｊ， ＣＨＲＩＳＴＥＮＳＳＯＮ Ｍ， ｅｔ ａｌ． Ｓｉｍｉｃｓ：ａ ｆｕｌｌ ｓｙｓｔｅｍ ｓｉｍｕｌａｔｉｏｎ ｐｌａｔｆｏｒｍ［ Ｊ］． ＩＥＥＥ Ｃｏｍ⁃ ｐｕｔｅｒ， ２００２， ３５（２）： ５０⁃５８． 作者简介： 刘正， 男，１９８３ 年生，讲师，博士研 究生，主要研究方向为性能优化、信息 安全与智能信息处理。 ·３３２· 智 能 系 统 学 报 第 １０ 卷