基于蚁群优化算法的同构多核任务分配与调度  

Task allocation and scheduling for homogeneous multi-core processors based on ant colony optimization

作　　者：覃志东[1] 侯颖[1] 肖芳雄[2] 

机构地区：[1]东华大学计算机科学与技术学院,上海201620 [2]广西财经学院信息与统计学院,广西南宁530003

出　　处：《江苏大学学报（自然科学版）》2014年第6期679-684,共6页Journal of Jiangsu University：Natural Science Edition

基　　金：国家自然科学基金资助项目(6126200);中央高校基本科研业务费专项基金资助项目(11D11209)

摘　　要：针对现有流程序自动综合技术中任务分配与调度方法效率低下的问题,提出一种基于改进蚁群算法的多核任务分配与调度算法.基于建立的问题模型,改进了基本蚁群算法中的信息素更新规则和启发式信息的计算方法,并应用多样化机制避免算法早熟收敛.为了提高效率,算法创新地在确定任务分配方案的同时确定调度序列.以标准任务图集为试验对象,验证算法的有效性.试验结果表明:与模拟退火算法相比,使用改进的蚁群算法在优化程序的执行跨度时收敛速度较快,并且在相同的循环次数下,得到的解更接近最优解.To solve the inefficient task allocation and scheduling methods of automated synthesis for stream application,a task allocation and scheduling algorithm for homogeneous multi-core platform was proposed based on the improved ant colony optimization.Based on the established problem model,the updating rule of pheromone and the calculation method of local heuristic value in basic ant colony optimization were improved.In order to avoid premature convergence,the diversification mechanism was applied in the algorithm.To improve the efficiency,the allocation scheme and scheduling order were simultaneously determined,which was an innovation of the algorithm.With the experimental subjects in standard task graph set,the algorithm effectiveness was validated.The experiment results show that compared with simulated annealing algorithm,when the software makespan is optimized,the improved ant colony optimiation can get faster convergence rate,and the obtained solution is closer to the optimal solution under the same number of loops.

关 键 词：任务分配与调度 流程序 自动综合 蚁群优化算法 执行跨度 

分 类 号：TP311.52[自动化与计算机技术—计算机软件与理论]