| 基于异构平台的并行最大最小蚁群算法 |
| |
| 引用本文： | 黄震华,赵振岐,林培裕,梅建华. 基于异构平台的并行最大最小蚁群算法[J]. 同济大学学报(自然科学版), 2016, 44(12): 1949-1955 |
| |
| 作者姓名： | 黄震华 赵振岐 林培裕 梅建华 |
| |
| 作者单位： | 同济大学 电子与信息工程学院，上海 200092,同济大学 电子与信息工程学院，上海 200092,同济大学 电子与信息工程学院，上海 200092,上海昕煜实业发展有限公司，上海 200062 |
| |
| 基金项目： | 国家自然科学基金(61272268)；上海市青年科技启明星计划 (15QA1403900)；霍英东教育基金会高等院校青年教师基金(142002)；教育部新世纪优秀人才支持计划(NCET-12-0413)；同济大学中央高校基本科研业务费专项资金。 |
| |
| 摘 要： | 最大最小蚂蚁系统(Max-min Ant System,MMAS)是一种性能优良的启发式算法,常用于解决组合优化问题.当解决的目标问题规模较大、迭代轮次较多时,最大最小蚁群算法存在运行时间长的缺点.试验以开源串行包ACOTSP为基准,利用GPU多线程并发的优势,采用并行蚂蚁策略将MMAS在CPU-GPU协同异构计算平台上并发实现.算法在GPU上运行时的影响因素,如数据传输、内存层次、库函数调用等,也得到有效分析,并作出针对性优化.试验最终取得了高达13倍的加速,表明并行MMAS策略具有高效性和实用性.
|
| 关 键 词： | 并行计算 异构平台 最大最小蚁群系统 加速比 |
| 收稿时间： | 2015-12-23 |
| 修稿时间： | 2016-10-25 |
Parallel Max min Ant System Based on Heterogeneous Platform |
| |
| HUANG Zhenhu,ZHAO Zhenqi,LIN Peiyu and MEI Jianhua. Parallel Max min Ant System Based on Heterogeneous Platform[J]. Journal of Tongji University(Natural Science), 2016, 44(12): 1949-1955 |
| |
| Authors: | HUANG Zhenhu ZHAO Zhenqi LIN Peiyu MEI Jianhua |
| |
| Affiliation: | College of Electronics and Information Engineering, Tongji University, Shanghai 200092, China,College of Electronics and Information Engineering, Tongji University, Shanghai 200092, China,College of Electronics and Information Engineering, Tongji University, Shanghai 200092, China and Shanghai Xinyu Industrial Development Co.,Ltd., Shanghai 200062, China |
| |
| Abstract: | Max min Ant System is a kind of heuristic algorithm with excellent performance, which is commonly used to solve combinatorial optimization problems. But it costs a long time when scale of the target problem is large as well as iterations are a lot. The experiment took the open source packet ACOTSP as a reference, used the advantage of multi threaded GPU, and implemented ACO algorithm on CPU GPU platform by parallel ants strategy. While the parallel algorithm is running on GPU, we also analyzed the impact factors carefully, such as data transmission, memory hierarchy, library calls et al, and made useful optimization. Eventually, the experiment made 13 times speedup, proving the parallel strategy is highly efficient and applicable. |
| |
| Keywords: | parallel computing heterogeneous platform Max min Ant System speedup ratio |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《同济大学学报(自然科学版)》浏览原始摘要信息 |
|
点击此处可从《同济大学学报(自然科学版)》下载全文 |
|
