计算机应用 ›› 2010, Vol. 30 ›› Issue (10): 2781-2784.

• 软件过程技术与先进计算 • 上一篇    下一篇

基于TBB和Cilk++的并行蚁群算法在路径寻优中的应用

王磊,曹菡   

  1. 陕西师范大学
  • 收稿日期:2010-04-06 修回日期:2010-05-16 发布日期:2010-09-21 出版日期:2010-10-01
  • 通讯作者: 王磊
  • 基金资助:
    陕西师范大学研究生培养创新基金资助项目

Application of parallel ant colony algorithm based on TBB and Cilk++ in path optimization

  • Received:2010-04-06 Revised:2010-05-16 Online:2010-09-21 Published:2010-10-01

摘要: 针对实际道路路网的一类路径寻优问题,提出了带回退机制的蚁群搜索算法,求解在实际道路路网中完成遍历所有规定节点的一条较优路径。为解决大规模实际道路路网数据量大、蚁群算法收敛速度慢的问题,分别采用Intel Threading Building Blocks(TBB)和Cilk++并行编程模型实现了并行蚁群搜索。与基于WinAPI函数的多线程蚁群算法相比,这两种模型均避免了手动启动线程及识别临界区资源等复杂操作,开发难度降低;在运行效率方面,基于TBB的并行蚁群算法和基于WinAPI的并行蚁群算法效率接近,而基于Cilk++的并行蚁群算法在双核环境下,运行效率和加速比都超过了基于WinAPI的并行蚁群算法。

关键词: TBB, Cilk, 并行蚁群算法, 多核

Abstract: An Ant Colony Algorithm (ACA) with rollback mechanism was proposed for obtaining optimized path, which traverses all necessary nodes in real road network. In case of the large scale real road network, the convergence speed of traditional sequential ACA was quite slow. Therefore, two parallel ACAs based on Intel Threading Building Blocks (TBB) and Cilk++ parallel programming model were designed separately. Both of them were easier to operate with simple instructions than complicated thread triggering and critical resource boundary recognition. Therefore, these two models were easier to develop and more applicable compared with WinAPI multi-threaded based parallel ACA (pACA). The experimental results show that pACA based TBB is nearly identical with pACA based on WinAPI in terms of efficiency, while pACA based on Cilk++ exhibits higher efficiency and better speed-up than pACA based on WinAPI in dual-core system.

Key words: Intel Threading Building Blocks (TBB), Cilk, parallel Ant Colony Algorithm (ACA), multi-core

中图分类号: