Abstract: In order to improve the efficiency of task scheduling for heterogeneous Chip Multi-core Processor, this paper proposes an improved ant colony optimization algorithm for task scheduling on heterogeneous CMP, called IACOTS, to exploit the power of heterogeneity and parallel capability of heterogeneous CMP. IACOTS algorithm creates a new task scheduling model and path selection rules. The ACO can be applied to discrete heterogeneous CMP task scheduling problem. Meanwhile, it uses dynamic pheromone updating, two ant parallel search strategy, and the variations factor of genetic algorithm, to overcome the ACO to search too long and “premature” convergence phenomenon, improving local search speed and reducing the total program execution time. The results obtained through simulation experiments show that the algorithm has good performance of global optimization, and distributed parallel computer system. The performance is better than existing heterogeneous multiprocessor task scheduling algorithm.

Key words: heterogeneous Chip Multi-core Processor, task scheduling, ant colony algorithm, genetic algorithm

摘要： 为提高异构CMP任务调度执行效率，充分发挥异构CMP的异构性和并行能力，提出一种基于异构CMP的改进蚁群优化任务调度算法——IACOTS。IACOTS算法首先建立任务调度模型、路径选择规则和信息素更新规则，使蚁群算法能够适用于异构CMP任务调度问题。同时通过采用动态信息素更新、相遇并行搜索策略和引入遗传算法中的变异因子对基本的蚁群算法进行优化，克服蚁群算法搜索时间过长和“早熟”现象。通过仿真实验获得的结果表明，IACOTS算法执行效率优于现有的遗传算法，完成相同的任务需要的迭代次数最少，能有效降低程序执行时间，适用于异构CMP等大规模并行环境的任务调度。

关键词: 异构多核处理器（CMP）, 任务调度, 蚁群算法, 遗传算法