沈阳工业大学 信息科学与工程学院，辽宁 沈阳 110870
择要：为更好地办理多核系统实时任务调度问题，针对基本蚁群算法求解最短路径过程中随意马虎陷入局部最优的情形，对基本蚁群算法进行了改进。改进算法根据系统的实际情形对概率选择公式做出调度，同时根据相应策略对信息素进行调度，有效地缩小了信息素之间的差距，有利于跳出局部最优状态。实验结果表明，该算法与基本蚁群算法比较在收敛速率和打算最优解方面都有了提高。
0弁言
随着程序的韶光繁芜性的增加和硬件本钱的减少，多核系统的利用已经越来越多。同时，实时系统领域的实时掌握哀求也在日益增加，因而提高系统的实时性能至关主要。在这些系统中，程序被划分成一些任务映射到一些处理器上，以减少程序的完成韶光。在这些架构中最主要的寻衅之一是如何视处理器的数量和处理能力来安排任务，在知足所有任务的时限哀求的条件下，给予外部要求及时的相应，使程序的整体实行韶光可以只管即便最小化。
目前，已涌现很多研究著为难刁难异构多核系统下的实时任务调度提出了一些性能较好的算法及其改进算法。然而，纵然在简化了一些问题的假设后，多核系统的任务调度也是NP（Nondeterministic 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蚁群优化算法流程图在第一阶段，只是创建一个长度为n的列表。在第二阶段，每只蚂蚁从准备列表中选择一个任务，并为该任务选择一个处理核，直到完成任务调度。在每次迭代中，N只蚂蚁就会得到N组可行解。选择一组任务调度长度最短的解作为一次迭代的最优解。对付蚂蚁k，通过利用概率选择式（1）和式（2）为任务i选择下一个任务j。
公式的设计考虑如下几个成分：(1)Dj，任务j的截止期；(2)Mj，任务j的估计运算量；(3)ei,j，任务i和j之间的估计通信量。
在为任务选择处理器时，根据概率选择式（1）和式（3）进行选择。
考虑以下几个成分：(1)sp，处理核p的处理速率;(2)rj,p，任务j在处理核p上准备就绪的韶光;(3)tp,处理核p的最早可用韶光。
然后天生一个随机数，选择与所天生的数相对应的作为下一个任务。显然，有较大信息素值的任务有更大的机会当选择。选定的任务被添加到禁忌表中，
从许可当选择的列表中删除，当选择任务的子任务现在可以实行，增加到准备列表中。这些操作是重复的，直到完成所有任务的调度，换句话说，完成了蚂蚁的列表。
在第三阶段中，根据k组可行解的情形，对路径上的信息素变量进行更新，调度策略如式（4）、式（5）和式（6）所示。
Lk表示第k只蚂蚁求得的任务调度长度，Q在基本蚁群算法中是常数，但通过实验创造，有时会导致搜索结束，对Q作出两点改变来办理：一是限定信息素变量的最大值和最小值，二是根据迭代次数对Q值进行调度。
末了阶段，选择所有迭代结束后得到的调度韶光最短的解作为最优的办理方案。
4实验结果及剖析
在 Microsoft Visual C++ 60 上利用 C措辞实现了本文提出的优化的蚁群算法。用有向无环图（DAG）对任务进行建模。图2表示了一个程序的任务图。
在图2中，节点是任务，边是指界说务之间的优先约束。边（i，j）表明，任务i必须在任务j开始前完成。每个节点的权重是任务的必要的实行韶光，边（i，j）的权重是任务i向任务j传输数据所需的韶光作为通信本钱。如果两个任务在同一个处理器上实行，它们之间的通信本钱将是零。在程序编译阶段产生任务实行韶光、通信本钱和任务之间的优先级约束。
在实验中设置参数如下：蚂蚁个数为10，最大迭代次数为100，α为2，β为2，ρ为07，该算法成功完成了异构多核系统中的实时任务调度，求出的最优解不仅是可行解，而且任务调度长度较短，充分证明了本文稠浊算法的可行性。
同时改进蚁群算法与基本蚁群算法进行比较，剖析结果如图3、图4所示。从图3可知，改进蚁群算法的均匀任务调度长度明显优于基本蚁群算法；图4将不同算法得到的最优解进行比拟，可知改进蚁群算法得到的最优解的任务调度长度更短并且较稳定，明显优于基本蚁群算法得到的最优解。
5结论
针对多核系统的实时性，本文算法考虑了任务的到达韶光、就绪韶光和截止期，再结合多核系统的繁芜环境，考虑了各内核不同的运行速率和内核间不同的通信带宽。将所提出的方法与其他调度方法进行了实验比拟，本文提出的蚁群
优化算法在均匀任务调度长度和最优解的任务调度长度上的表现均优于比较较的算法。
参考文献
［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):764765.
［2］ Liu Yi, Zhang Xin, Li He,et al. Allocating tasks in multicore processor based parallel system［C］. Proceedings of the IFIP International Conference on Network and Parallel Computing Workshops, Washington DC, 2007: 748753.
［3］ Zhu Jie, Li Xiaoping. An effective metaheuristic for nowait job shops to minimize makespan［C］. IEEE Transactions on Automation Science and Engineering, 2012,1(9): 189198.
［4］ 刘进，刘春，陈家佳．基于改进蚁群算法的多处理器任务调度仿真［J］．打算机仿真，2014, 31( 6)：334337．
［5］ 王嘉平．多核系统中实时任务调度算法的研究［D］．南京：南京邮电大学，2012.
［6］ 周会娇．异构多核系统多媒体流打算实时任务调度策略研究［D］．武汉：华中科技大学，2013.
［7］ DORIGO M， BIRATTARI M， STUTZLE T. Ant colony optimization ［J］. IEEE Computational Intelligence Magazine， 2006, 1(4)：2839.
［8］ 朱君,蔡延光,汤雅连，等.改进稠浊蚁群算法求解关联旅行商问题［J］.微型机与运用, 2014, 33(9):8084, 88.
［9］ 张丽萍.改进的蚁群算法求解置换流水车间调度问题［J］.微型机与运用,2014,33(12):6668,72.
［10］ 段海滨. 蚁群算法事理及其运用［M］. 北京： 科学出版社, 2005.
