Enhancing GPU parallelism in nature-inspired algorithms

详细信息    查看全文

• 作者：José M. Cecilia (1)
  Andy Nisbet (2)
  Martyn Amos (2)
  José M. García (3)
  Manuel Ujaldón (4)
  
• 关键词：GPUs ; HPC ; ACO ; P systems ; Bioinspired methods
• 刊名：The Journal of Supercomputing
• 出版年：2013
• 出版时间：March 2013
• 年：2013
• 卷：63
• 期：3
• 页码：773-789
• 全文大小：720KB
• 参考文献：1. Blum C (2005) Ant colony optimization: introduction and recent trends. Phys Life Rev 2(4):353-73 CrossRef
  2. Cecilia JM, García JM, Guerrero GD, Martínez-del-Amor MA, Pérez-Hurtado I, Pérez-Jiménez MJ (2010) Simulation of P systems with active membranes on CUDA. Brief Bioinform 11(3):313-22 CrossRef
  3. Cecilia JM, García JM, Guerrero GD, Martínez-del-Amor MA, Pérez-Jiménez MJ, Ujaldón M (2010) P systems simulations on massively parallel architectures. In: Third international workshop on parallel architectures and bioinspired algorithms (WPABA-10), in conjunction with the nineteenth international conference on parallel architectures and compilations techniques (PACT-10), Vienna, Austria
  4. Díaz-Pernil D, Pérez-Hurtado I, Pérez-Jiménez MJ, Riscos-Nú?ez A (2008) P-lingua: a programming language for membrane computing. In: Proceedings of the 6th brainstorming week on membrane computing, Sevilla, Spain
  5. Dorigo M (1992) Optimization, learning and natural algorithms. Dissertation, Politecnico di Milano
  6. Dorigo M, Birattari M, Stützle T (2006) Ant colony optimization. IEEE Comput Intell Mag 1(4):28-9
  7. Dorigo M, Bonabeau E, Theraulaz G (2000) Ant algorithms and stigmergy. Future Gener Comput Syst 16:851-71 CrossRef
  8. Dorigo M, Colorni A, Maniezzo V (1991) Positive feedback as a search strategy. Dipartimento di Elettronica, Politecnico di Milano, Milan, Italy, Tech Rep 91-016
  9. Dorigo M, Maniezzo V, Colorni A (1996) The ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern, Part B 26:29-1 CrossRef
  10. Dorigo M, Stützle T (2004) Ant colony optimization. Bradford Company, Scituate CrossRef
  11. Fu J, Lei L, Zhou G (2010) A parallel ant colony optimization algorithm with GPU-acceleration based on all-in-roulette selection. In: Proceedings of the third international workshop on advanced computational intelligence (IWACI), Suzhou, China
  12. Garland M, Le Grand S, Nickolls J, et al (2008) Parallel computing experiences with CUDA. IEEE Micro 28:13-7 CrossRef
  13. Garland M, Kirk DB (2010) Understanding throughput-oriented architectures. Commun ACM 53:58-6 CrossRef
  14. Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Longman, Reading, Harlow
  15. Johnson DS, Mcgeoch LA (1997) The traveling salesman problem: a case study in local optimization. In: Aarts EHL, Lenstra JK (eds) Local search in combinatorial optimization. Wiley, London, pp 215-10
  16. Lam MD, Rothberg EE, Wolf ME (1991) The cache performance and optimizations of blocked algorithms. ACM SIGPLAN Not 26(4):63-4 CrossRef
  17. Lawler E, Lenstra J, Kan A, Shmoys D (1987) The traveling salesman problem. Wiley, New York
  18. Li J, Hu X, Pang Z, Qian K (2009) A parallel ant colony optimization algorithm based on fine-grained model with GPU acceleration. Int J Innov Comput, Inf Control 5(11):3707-715
  19. NVIDIA CUDA C Programming Guide 4.0 (2011)
  20. NVIDIA CUDA C Best Practices Guide 4.0 (2011)
  21. NVIDIA, Whitepaper NVIDIA’s Next Generation CUDA Compute Architecture: Fermi (2009)
  22. P?un G (2002) Membrane computing: An introduction. Springer, Berlin CrossRef
  23. P?un G (2000) Computing with membranes. J Comput Syst Sci 61:108-43. TUCS Report No 208 CrossRef
  24. Pérez-Jiménez MJ, Romero-Jiménez á, Sancho-Caparrini F (2003) Complexity classes in models of cellular computing with membranes. Nat Comput 2(3):265-85 CrossRef
  25. Qasem M (2009) WinSAT website. http://users.ecs.soton.ac.uk/mqq06r/winsat
  26. Reinelt G (1991) TSPLIB: A traveling salesman problem library. ORSA J Comput 3(4):376-84 CrossRef
  27. Scavo T (2010) Scatter-to-gather transformation for scalability
  28. TSPLIB Webpage (2011) http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/
  29. You YS (2009) Parallel ant system for traveling salesman problem on GPUs. In: GECCO 2009—GPUs for genetic and evolutionary computation, pp 1-
  
• 作者单位：José M. Cecilia (1)
  Andy Nisbet (2)
  Martyn Amos (2)
  José M. García (3)
  Manuel Ujaldón (4)
  
  1. Departamento de Informática, Escuela politécnica, Universidad Católica San Antonio Murcia, Campus de los Jerónimos S/N, Guadalupe, 30107, Murcia, Spain
  2. School of Computing, Mathematics and Digital Technology, Manchester Metropolitan University, Chester Street, Manchester, M1 5GD, UK
  3. Facultad de Informática, Universidad de Murcia, Campus de Espinardo, 30080, Murcia, Spain
  4. Computer Architecture Department, ETSI Informática, University of Málaga, Campus Teatinos, Bulevar Louis Pasteur, s/n, 29071, Málaga, Spain
  
• ISSN：1573-0484

文摘

We present GPU implementations of two different nature-inspired optimization methods for well-known optimization problems. Ant Colony Optimization (ACO) is a two-stage population-based method modelled on the foraging behaviour of ants, while P systems provide a high-level computational modelling framework that combines the structure and dynamic aspects of biological systems (in particular, their parallel and non-deterministic nature). Our methods focus on exploiting data parallelism and memory hierarchy to obtain GPU factor gains surpassing 20x for any of the two stages of the ACO algorithm, and 16x for P systems when compared to sequential versions running on a single-threaded high-end CPU. Additionally, we compare performance between GPU generations to validate hardware enhancements introduced by Nvidia’s Fermi architecture.