摘要
研究一组多帧任务在异构多核处理平台上的分配,使得所有任务得以完成并耗费更少的时间。建立了带约束条件的异构多核周期多帧任务模型,运用蚁群算法来解决任务分配优化问题。其中结合了遗传算法中的复制、交叉、变异等遗传因子,以提高算法的收敛速度和全局搜索能力;改进了信息素的更新方式,以使算法在执行过程中可以根据收敛及进展情况动态地调整信息素残留程度,加快寻找最优解的能力;此外还引入了一种确定性搜索方法,以加快启发式搜索的收敛速度。实验证明,使用改进后的蚁群算法在解决异构多核平台上的多帧任务分配问题时,可以有效且快速地求得问题的最优解或近似最优解,并且拥有更低的时间复杂度。
Given a set of multi-frame tasks and a heterogeneous multi-processor processing platform,the problem was to determining whether the tasks could be partitioned among the processors in such a manner that all timing constraints were met.This paper constructed a heterogeneous multi-processors periodic multi-frame task model with constraints and proposed an improved ant colony algorithm to solve the partition optimization problem of periodic multi-frames tasks among heterogeneous multi-processors.It introduced several genetic operators,such as reproduction,crossover and mutation,into the ant colony algorithm to enhance the converging rate and global search capability.To improve the self-adaptability of the algorithm,it modified pheromone updating strategy by dynamically adjusting the pheromone residual according to the progress of the algorithm convergence.Additionally,it introduced a deterministic search approach into the algorithm to accelerate the converging rate of the heuristic method.The experimental result proves that it can obtain an optimal or nearly optimal solutions to the multi-frame task allocation in heterogeneous multi-processor quickly with the improved ant colonyalgorithm,which has lower time-complexity as well
出处
《计算机应用研究》
CSCD
北大核心
2012年第9期3251-3254,共4页
Application Research of Computers
基金
国家自然科学基金资助项目(60973030)
关键词
异构多核
多帧任务
蚁群算法
heterogeneous multi-processors
multi-frames tasks
ant colony algorithm
