多核系统的实时任务调度算法研究

关 沫， 佟 彤

(沈阳工业大学 信息科学与工程学院，辽宁 沈阳 110870)

多核系统的实时任务调度算法研究

关 沫， 佟 彤

(沈阳工业大学 信息科学与工程学院，辽宁 沈阳 110870)

为更好地解决多核系统实时任务调度问题，针对基本蚁群算法求解最短路径过程中容易陷入局部最优的情况，对基本蚁群算法进行了改进。改进算法根据系统的实际情况对概率选择公式做出调整，同时根据相应策略对信息素进行调整，有效地缩小了信息素之间的差距，有利于跳出局部最优状态。实验结果表明，该算法与基本蚁群算法相比在收敛速度和计算最优解方面都有了提高。

蚁群优化算法；多核系统；实时；任务调度

0 引言

随着程序的时间复杂性的增加和硬件成本的减少，多核系统的利用已经越来越多。同时，实时系统领域的实时控制要求也在日益增加，因而提高系统的实时性能至关重要。在这些系统中，程序被划分成一些任务映射到一些处理器上，以减少程序的完成时间。在这些架构中最重要的挑战之一是如何视处理器的数量和处理能力来安排任务，在满足所有任务的时限要求的前提下，给予外部请求及时的响应，使程序的整体执行时间可以尽量最小化。

目前，已出现很多研究著作对异构多核系统下的实时任务调度提出了一些性能较好的算法及其改进算法。然而，即使在简化了一些问题的假设后，多核系统的任务调度也是NP(Non-deterministic Polynomial)难题[1]。传统穷举法计算复杂度大，耗时长[2]，所以至今为止还没有一种被确定为最优的调度算法。正因如此，很多学者仍在孜孜不倦地追求更优解，也为后来的研究者提供了极大的可改进和可拓展空间。

1 多核任务调度

在多核系统中，一个程序被划分成更小的段，命名为任务分布在处理器上。通过同时运行任务来减少程序的整体执行时间。一个程序的任务之间是有依赖关系的。一些任务需要其他任务所产生的数据。因此，任务之间有约束关系，并且内核之间需要数据通信。在本文中，假定是异构体系结构和完全连接的处理器。

早期的异构多核系统大部分是通过启发式算法解决任务调度问题的，一般是结合最早完成时间(makespan)[3]、最少完成时间和负载均衡等指标，通过使用贪婪算法的思想去求解任务分配的次优解。这种算法虽然收敛速度很快，可是由于所供参考的任务范围较小，因此比较容易陷入局部最优解[4]。在异构多核系统的任务调度问题中，启发式算法的局限性导致了人工智能算法的引入，这类算法的主要思想是凭借设定启发信息去合理引导搜索过程向最优解逐渐收敛，主要有遗传算法[5]、禁忌搜索算法、邻域搜索算法、蚁群算法等。它们擅长找到全局最优解，但也普遍存在算法收敛时间较长的缺点，在具体应用过程中很难按基础算法使用。为了改进人工智能算法，研究者们采用混合调度策略或者设置相关约束条件来不断加快算法的收敛速度。其中蚁群算法[6]是一种有效的随机模拟进化算法，它模拟蚁群觅食过程中发现最优路径的过程，可用于解决组合优化问题。

2 基本蚁群算法

蚁群算法是一种人工蚂蚁合作来找到一个给定的问题的优化解决方案的并行算法。蚁群算法[7]最早是由DORIGO M等人提出的，灵感来源于大自然中蚂蚁寻找食物的群体行为。作为一种解决旅行商问题[8](TSP)的机率型模拟进化算法，它已经成功地应用于许多复杂的离散性优化问题，如二次分配问题(QAP)、车间调度[9](JSP)、车辆路径、图着色、排序、网络路由等。实验证明该算法能较为出色地解决复杂优化问题,特别是离散性优化问题，是一种比较卓越的优化算法。

下面具体阐述蚁群搜索路径的原理[10]。如果有一个障碍物，蚂蚁要绕过它有两侧两条路径，其中一边的路径比另一边长。首先，蚂蚁通过随机运动来绕过障碍。然后，较长一侧的信息素蒸发更快，蚂蚁逐渐收敛到短的路径上。因此，它们总是能找到从食物到蚁穴的最短路径。由上述蚂蚁搜索路径的原理可知，路径上信息量越大，这条路径被选中的概率就越大，直到最后，蚂蚁完全选中这条路径，这种现象所体现出的是信息的正反馈机制。

蚁群算法模拟这种觅食行为。在开始时，所有任务的状态都是可以访问的，蚂蚁被设置为一个初始状态。它根据相邻状态信息素的值使用概率公式选择下一个任务，并在此路径上留下信息素，为下一只蚂蚁提供可参考信息。使用同样的方法为任务选择处理核。蚂蚁重复此操作，直到它遍历过所有的任务。此时，更新任务选择和处理器选择路径上的信息素变量。通过这种机制蚂蚁收敛得到最优解。

3 蚁群优化算法

为了提高多核系统的调度效率，针对蚁群算法的缺点，从两方面进行改进：一是在选择任务和为任务选择处理核的概率选择公式的设计上；二是信息素变量的更新。首先，n是给定的任务图的任务数，处理器的个数为m。τ(i,j)是指有向边i、j上的信息素变量，η(i,j)是指任务i后会选择任务j的期望程度。最初所有元素有相同的较小值。然后执行迭代的蚁群算法：

(1)生成蚁群；

(2)设置初始化信息；

(3)每只蚂蚁循环(直到完成调度任务)——根据信息素变量选择下一个就绪任务，为该任务选择处理器；

(4)记录信息素变量；

(5)信息素变量的更新。

改进蚁群算法的流程图如图1所示。

图1 蚁群优化算法流程图

在第一阶段，只是创建一个长度为n的列表。在第二阶段，每只蚂蚁从准备列表中选择一个任务，并为该任务选择一个处理核，直到完成任务调度。在每次迭代中，N只蚂蚁就会得到N组可行解。选择一组任务调度长度最短的解作为一次迭代的最优解。对于蚂蚁k，通过使用概率选择式(1)和式(2)为任务i选择下一个任务j。

(1)

(2)

公式的设计考虑如下几个因素：(1)Dj，任务j的截止期；(2)Mj，任务j的估计运算量；(3)ei,j，任务i和j之间的估计通信量。

在为任务选择处理器时，根据概率选择式(1)和式(3)进行选择。

(3)

考虑以下几个因素：(1)sp，处理核p的处理速率;(2)rj,p，任务j在处理核p上准备就绪的时间;(3)tp,处理核p的最早可用时间。

然后生成一个随机数，选择与所生成的数相对应的作为下一个任务。显然，有较大信息素值的任务有更大的机会被选择。选定的任务被添加到禁忌表中，

从允许被选择的列表中删除，被选择任务的子任务现在可以执行，增加到准备列表中。这些操作是重复的，直到完成所有任务的调度，换句话说，完成了蚂蚁的列表。

在第三阶段中，根据k组可行解的情况，对路径上的信息素变量进行更新，调整策略如式(4)、式(5)和式(6)所示。

τ(i,j)=(1-ρ)τ(i,j)+Δτ(i,j)

(4)

(5)

(6)

Lk表示第k只蚂蚁求得的任务调度长度，Q在基本蚁群算法中是常数，但通过实验发现，有时会导致搜索停滞，对Q作出两点改变来解决：一是限定信息素变量的最大值和最小值，二是根据迭代次数对Q值进行调整。

最后阶段，选择所有迭代结束后得到的调度时间最短的解作为最优的解决方案。

4 实验结果及分析

在MicrosoftVisualC++ 6.0 上使用C语言实现了本文提出的优化的蚁群算法。用有向无环图(DAG)对任务进行建模。图2表示了一个程序的任务图。

图2 程序的任务图

在图2中，节点是任务，边是指定任务之间的优先约束。边(i，j)表明，任务i必须在任务j开始前完成。每个节点的权重是任务的必要的执行时间，边(i，j)的权重是任务i向任务j传输数据所需的时间作为通信成本。如果两个任务在同一个处理器上执行，它们之间的通信成本将是零。在程序编译阶段产生任务执行时间、通信成本和任务之间的优先级约束。

在实验中设置参数如下：蚂蚁个数为10，最大迭代次数为100，α为2，β为2，ρ为0.7，该算法成功完成了异构多核系统中的实时任务调度，求出的最优解不仅是可行解，而且任务调度长度较短，充分证明了本文混合算法的可行性。

同时改进蚁群算法与基本蚁群算法进行比较，分析结果如图3、图4所示。从图3可知，改进蚁群算法的平均任务调度长度明显优于基本蚁群算法；图4将不同算法得到的最优解进行对比，可知改进蚁群算法得到的最优解的任务调度长度更短并且较稳定，明显优于基本蚁群算法得到的最优解。

图3 不同算法的平均任务调度长度比较

5 结论

针对多核系统的实时性，本文算法考虑了任务的到达时间、就绪时间和截止期，再结合多核系统的复杂环境，考虑了各内核不同的运行速率和内核间不同的通信带宽。将所提出的方法与其他调度方法进行了实验对比，本文提出的蚁群优化算法在平均任务调度长度和最优解的任务调度长度上的表现均优于相比较的算法。

图4 不同算法的最优解调度长度比较

[1] CHRETIENNE P, COFFMAN E G, LENSTRA J K, et al. Scheduling theory and its application[J]. Journal of the Operational Research soeiety, 1995,48(7):764-765.

[2] Liu Yi, Zhang Xin, Li He,et al. Allocating tasks in multi-core processor based par-allel system[C]. Proceedings of the IFIP International Conference on Network and Parallel Computing Workshops, Washington DC, 2007: 748-753.

[3] Zhu Jie, Li Xiaoping. An effective meta-heuristic for no-wait job shops to minimize makespan[C]. IEEE Transactions on Automation Science and Engineering, 2012,1(9): 189-198.

[4] 刘进，刘春，陈家佳．基于改进蚁群算法的多处理器任务调度仿真[J]．计算机仿真，2014, 31( 6)：334-337．

[5] 王嘉平．多核系统中实时任务调度算法的研究[D]．南京：南京邮电大学，2012.

[6] 周会娇．异构多核系统多媒体流计算实时任务调度策略研究[D]．武汉：华中科技大学，2013.

[7] DORIGO M， BIRATTARI M， STUTZLE T. Ant colony optimization [J]. IEEE Computational Intelligence Magazine， 2006, 1(4)：28-39.

[8] 朱君,蔡延光,汤雅连，等.改进混合蚁群算法求解关联旅行商问题[J].微型机与应用, 2014, 33(9):80-84, 88.

[9] 张丽萍.改进的蚁群算法求解置换流水车间调度问题[J].微型机与应用,2014,33(12):66-68,72.

[10] 段海滨. 蚁群算法原理及其应用[M]. 北京： 科学出版社, 2005.

Research on real-time task scheduling algorithm of multi-core system

Guan Mo, Tong Tong

(School of Information Science and Engineering, Shenyang University of Techenology, Shenyang 110870, China)

Ant colony system algorithm can solve the real-time task scheduling problem, but it is easily trapped in local optimization problem. In order to solve the problem, the basic ant colony algorithm is improved. According to the actual situation of the system, improved algorithm makes the adjustment to the probability selection formula, and adjusts the pheromone with corresponding strategy. Effectively reducing the gap between the pheromone, it is advantageous to jump out of the local optimal state. Experimental results show that the proposed algorithm is improved compared with the basic ant colony algorithm in terms of convergence rate and computational optimization.

ant colony optimization; multi-core systems; real-time; task scheduling

TP332

A

1674-7720(2016)02-0017-03

关沫，佟彤. 多核系统的实时任务调度算法研究[J] .微型机与应用，2016,35(2)：17-19.

2015-09-22)

关沫(1976-)，女，博士，副教授，主要研究方向：嵌入式软件与实时系统，计算机视觉。

佟彤(1990-)，女，硕士研究生，主要研究方向：嵌入式软件与实时系统。