Coarse grain parallelization of evolutionary algorithms on GPGPU cards with EASEA

ABSTRACT

This paper presents a straightforward implementation of a standard evolutionary algorithm that evaluates its population in parallel on a GPGPU card.

Tests done on a benchmark and a real world problem using an old NVidia 8800GTX card and a newer but not top of the range GTX260 card show a roughly 30x (resp. 100x) speedup for the whole algorithm compared to the same algorithm running on a standard 3.6GHz PC. Knowing that much faster hardware is already available, this opens new horizons to evolutionary computation, as search spaces can now be explored 2 or 3 orders of magnitude faster, depending on the number of used GPGPU cards.

Since these cards remains very difficult to program, the knowhow has been integrated into the old EASEA language, that can now output code for GPGPU (-cuda option).

REFERENCES

• 1: Maribel García Arenas , Pierre Collet , A. E. Eiben , Márk Jelasity , Juan J. Merelo Guervós , Ben Paechter , Mike Preuß , Marc Schoenauer, A Framework for Distributed Evolutionary Algorithms, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.665-675, September 07-11, 2002
• 2: L.A. Baumes, M. Moliner, and A. Corma. Design of a full-profile matching solution for high-throughput analysis of multi-phases samples through powder x-ray diffraction. Chemistry -- A European Journal, In Press.
• 3: L.A. Baumes, M. Moliner, N. Nicoloyannis, and A. Corma. A reliable methodology for high throughput identification of a mixture of crystallographic phases from powder x-ray diffraction data. CrystEngComm, 10:1321--1324, 2008.
• 4: Pierre Collet , Evelyne Lutton , Marc Schoenauer , Jean Louchet, Take It EASEA, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.891-901, September 18-20, 2000
• 5: P. Collet and M. Schoenauer. GUIDE: Unifying evolutionary engines through a graphical user interface. In P. Liardet et al., eds, EA'03, volume 2936 of LNCS, pages 203--215, Marseilles, 2003. Springer.
• 6: A. Corma, M. Moliner, J.M. Serra, P. Serna, M.J. Diaz-Cabanas, and L.A. Baumes. A new mapping/exploration approach for ht synthesis of zeolites. Chemistry of Materials, pages 3287--3296, 2006.
• 7: A. Corma, F. Rey, J. Rius, M. Sabater, and S. Valencia. Supramolecular self-assembled molecules as organic directing agent for synthesis of zeolites. Nature, 431:287--290, 2004.
• 8: D.B. Fogel. Evolving artificial intelligence. Technical report, 1992.
• 9: Ka-Ling Fok , Tien-Tsin Wong , Man-Leung Wong, Evolutionary Computing on Consumer Graphics Hardware, IEEE Intelligent Systems, v.22 n.2, p.69-78, March 2007 [doi>10.1109/MIS.2007.28]
• 10: JIAN-MING LI , XIAO-JING WANG , RONG-SHENG HE , ZHONG-XIAN CHI, An Efficient Fine-grained Parallel Genetic Algorithm Based on GPU-Accelerated, Proceedings of the 2007 IFIP International Conference on Network and Parallel Computing Workshops, p.855-862, September 18-21, 2007
• 11: Evelyne Lutton , Pierre Collet , Jean Louchet, EASEA Comparisons on Test Functions: GALib versus EO, Selected Papers from the 5th European Conference on Artificial Evolution, p.219-230, October 29-31, 2001
• 12: G. Moore. Cramming more components onto integrated circuits. Electronics Magazine, 38(8), April 19 1965.
• 13: R.A. Young. The Rietveld Method. OUP and International Union of Crystallography, 1993.
• 14: Q. Yu, C. Chen, and Z. Pan. Parallel genetic algorithms on programmable graphics hardware. In Advances in Natural ComputationICNC 2005, Proceedings, Part III, volume 3612 of LNCS, pages 1051--1059, Changsha, August 27-29 2005. Springer.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming

General Terms:
Performance

Keywords:
easea, evolutionary computation, genetic algorithms, gpgpu, gpu, graphic processing unit, many-core, multi-core, parallelization