基于蚁群优化算法的异构多核线程调度方法  

Heterogeneous multi-core thread scheduling method based on ant colony optimization algorithm

作　　者：李静梅[1] 张大虎[1] 吴艳霞[1] 孙传恒 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,黑龙江哈尔滨150001 [2]哈尔滨转承制造有限公司,黑龙江哈尔滨150001

出　　处：《计算机工程与设计》2014年第6期1946-1950,共5页Computer Engineering and Design

基　　金：国家自然科学基金项目(61003036);黑龙江省自然科学基金项目(F201124);黑龙江省教育厅科学技术研究基金项目(12513048);中央高校基本科研业务费专项基金项目(HEUCF100606)

摘　　要：针对如何发挥异构多核处理器的优势、提高程序执行效率,提出一种异构多核线程调度的蚁群优化算法—ACOTS(ant colony optimization for thread scheduling)。建立线程调度模型和路径选择规则实现连续搜索空间在离散空间的映射,使蚁群算法能够适用于异构多核处理器线程调度问题;通过引入遗传算法中的变异因子对局部搜索过程进行优化,克服蚁群算法搜索时间过长和"早熟"收敛现象,降低总的程序执行时间。仿真结果表明,ACOTS算法性能优于现有的遗传算法,能有效降低程序执行时间,适用于异构多核等大规模并行环境的线程调度。Based on the ant colony optimization algorithm,a heterogeneous multi-core thread scheduling method named ACOTS （ant colony optimization for thread scheduling） were proposed to make use of the advantages of heterogeneous multi-core processors,which could improve the runtime efficiency.Firstly,the algorithm ACOTS realized the mapping from continuous searching space to discrete space by establishing thread scheduling model and path choice rules,making the ant colony algorithm applicable for problems about heterogeneous multi-core thread scheduling.Secondly,the algorithm introduced the variability factor of genetic algorithms to decrease the searching time of ant colony algorithms and to avoid premature convergence phenomenon.The simulation experiment results show that ACOTS could reduce the execution time more than genetic algorithms did,and ACOTS could be applied to thread scheduling in heterogeneous multi-core and other large-scale parallel environments.

关 键 词：异构多核处理器 线程调度 蚁群算法 遗传算法 调度方法 

分 类 号：TP303[自动化与计算机技术—计算机系统结构]