CAJ | 학술논문

为提高异构CMP任务调度执行效率，充分发挥异构CMP的异构性和并行能力，提出一种基于异构CMP的改进蚁群优化任务调度算法——IACOTS。IACOTS算法首先建立任务调度模型、路径选择规则和信息素更新规则，使蚁群算法能够适用于异构CMP任务调度问题。同时通过采用动态信息素更新、相遇并行搜索策略和引入遗传算法中的变异因子对基本的蚁群算法进行优化，克服蚁群算法搜索时间过长和“早熟”现象。通过仿真实验获得的结果表明，IACOTS算法执行效率优于现有的遗传算法，完成相同的任务需要的迭代次数最少，能有效降低程序执行时间，适用于异构CMP等大规模并行环境的任务调度。
위제고이구CMP임무조도집행효솔，충분발휘이구CMP적이구성화병행능력，제출일충기우이구CMP적개진의군우화임무조도산법——IACOTS。IACOTS산법수선건립임무조도모형、로경선택규칙화신식소경신규칙，사의군산법능구괄용우이구CMP임무조도문제。동시통과채용동태신식소경신、상우병행수색책략화인입유전산법중적변이인자대기본적의군산법진행우화，극복의군산법수색시간과장화“조숙”현상。통과방진실험획득적결과표명，IACOTS산법집행효솔우우현유적유전산법，완성상동적임무수요적질대차수최소，능유효강저정서집행시간，괄용우이구CMP등대규모병행배경적임무조도。
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 prob-lem. 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 bet-ter than existing heterogeneous multiprocessor task scheduling algorithm.