Username   Password       Forgot your password?  Forgot your username? 

HACO-F: An Accelerating HLS-Based Floating-Point Ant Colony Optimization Algorithm on FPGA

Volume 13, Number 6, October 2017 - Paper 7  - pp. 854-863
DOI: 10.23940/ijpe.17.06.p7.854863

Shuo Zhanga,b, Zhangqin Huanga,b,*, Weidong Wanga,b,*, Rui Tiana,b, Jian Hea,b

aBeijing Advanced Innovation Center for Future Internet Technology, Beijing University of Technology, Beijing 100124,China
bBeijing Engineering Research Center for IOT Software and Systems, Beijing University of Technology, Beijing 100124,China

(Submitted on July 25, 2017; Revised on August 30, 2017; Accepted on September 15, 2017)

(This paper was presented at the Third International Symposium on System and Software Reliability.)


In this paper, a novel accelerating Ant Colony Optimization (ACO) algorithm based on High-Level Synthesis (HLS) on FPGA (Field Programmable Gate Array) is proposed. The proposed algorithm (HACO-F) is implemented by C/C++ programming language and calculated by floating-point. For the sake of accelerating, the algorithm mainly employs the data optimization strategy to redefine the variables precision in HACO-F to reduce resource utilization and energy consumption. Then, we explore a loop optimization strategy including pipeline and unroll to parallelize loops in HACO-F to decrease computation time. The experimental results show that the HACO-F algorithm can achieve more than 6 times accelerating performance than that of the AS (Ant System) at the same search ability. The resource utilization in HACO-F is 1% FF, 4% LUT, and 9% BRAM decrease. The total on-chip energy consumption of HACO-F is reduced by 23.9%.


References: 16

    1. S. Ahmad, V. Boppana, I. Ganusov, V. Kathail, V. Rajagopalan, and R. Wittig, "A 16-nm Multiprocessing System-on-Chip Field-Programmable Gate Array Platform," IEEE Micro, vol. 36, no. 2, pp. 48-62, April 2016
    2. J. Cong, B. Liu, S. Neuendorffer, J. Noguera, K. Vissers, and Z. Zhang, "High-Level Synthesis for Fpgas: From Prototyping to Deployment," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 4, pp. 473-491, March 2011
    3. M. Dorigo and L. M. Gambardella, "Ant colony system: a cooperative learning approach to the traveling salesman problem," IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53-66, April 1997
    4. M. Dorigo, V. Maniezzo, and A. Colorni, "Ant System: Optimization by a Colony of Cooperating Agents," IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26, no. 1, pp. 29-41, February 1996
    5. M. Guntsch, M. Middendorf, B. Scheuermann, O. Diessel, H. ElGindy, H. Schmeck, and K. So, "Population based ant colony optimization on FPGA," IEEE International Conference on Field-Programmable Technology, pp.125-132, Hong Kong, China, December 2002
    6. R. M. Hamou, H. A. Bouarara, and A. Amine, "Bio-inspired techniques in the clustering of texts: Synthesis and comparative study," International Journal of Applied Metaheuristic Computing, vol. 6, no. 4, pp. 39-68, October 2015
    7. C. C. Hsu, W. Y. Wang, Y. H. Chien, R. Y. Hou, and C. W. Tao, "FPGA implementation of improved ant colony optimization algorithm for path planning," IEEE Congress on Evolutionary Computation (CEC), pp.4516-4521, Vancouver, Canada, July 2016
    8. H. C. Huang, "A Taguchi-Based Heterogeneous Parallel Metaheuristic ACO-PSO and Its FPGA Realization to Optimal Polar-Space Locomotion Control of Four-Wheeled Redundant Mobile Robots," IEEE Transactions on Industrial Informatics, vol. 11, no. 4, pp. 915-922, June 2015
    9. C. F. Juang, C. M. Lu, C. Lo, and C. Y. Wang, "Ant Colony Optimization Algorithm for Fuzzy Controller Design and Its FPGA Implementation," IEEE Transactions on Industrial Electronics, vol. 55, no. 3, pp. 1453-1462, March 2008
    10. M. Mavrovouniotis, F. M. Muller, and S. Yang, "Ant Colony Optimization with Local Search for Dynamic Traveling Salesman Problems," IEEE Transactions on Cybernetics, vol. 47, no. 7, pp. 1743-1756, April 2016
    11. M. Ramirez, M. Daneshtalab, J. Plosila, and P. Liljeberg, "NoC-AXI interface for FPGA-based MPSoC platforms," International Conference on Field Programmable Logic and Applications (FPL), pp. 479-480, Oslo, Norway, August 2012
    12. A. Sakthivel, P. Vijayakumar, A. Senthilkumar, L. Lakshminarasimman, and S. Paramasivam, "Experimental investigations on Ant Colony Optimized PI control algorithm for Shunt Active Power Filter to improve Power Quality," Control Engineering Practice, vol. 42, pp. 153-169, June 2015
    13. B. Scheuermann and M. Middendorf, "Counter-Based ant colony optimization as a hardware-oriented meta-heuristic," European Conference on Applications of Evolutionary Computing, pp. 235-244, Berlin, Germany, March 2005
    14. B. Scheuermann, K. So, M. Guntsch, M. Middendorf, O. Diessel, H. Elgindy, and H. Schmeck, "FPGA implementation of population-based ant colony optimization," Applied Soft Computing, vol. 4, no. 3, pp. 303-322, March 2004
    15. N. Venugopal, V. Shobana, and R. Manimegalai, "Analysis of optimization techniques in FPGA placement," International Conference on Computer Communication and Informatics(ICCCI), pp. 1-5, Coimbatore, India, January 201
    16. Z. H. Xiong, J. H. Chen, and S. K. Li, "Hardware/software partitioning for platform-based design method," Asia and South Pacific Design Automation Conference(ASP-DAC), vol. 2, pp. 691-696, Shanghai, China, January 2005


      Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

      This site uses encryption for transmitting your passwords.