Performance Optimization of Multi-Core Grammatical Evolution Generated Parallel Recursive Programs

ABSTRACT

Although Evolutionary Computation (EC) has been used with considerable success to evolve computer programs, the majority of this work has targeted the production of serial code. Recent work with Grammatical Evolution (GE) produced Multi-core Grammatical Evolution (MCGE-II), a system that natively produces parallel code, including the ability to execute recursive calls in parallel.

This paper extends this work by including practical constraints into the grammars and fitness functions, such as increased control over the level of parallelism for each individual. These changes execute the best-of-generation programs faster than the original MCGE-II with an average factor of 8.13 across a selection of hard problems from the literature.

We analyze the time complexity of these programs and identify avoiding excessive parallelism as a key for further performance scaling. We amend the grammars to evolve a mix of serial and parallel code, which spawns only as many threads as is efficient given the underlying OS and hardware; this speeds up execution by a factor of 9.97.

References

1. A. Agapitos and S. M. Lucas. Evolving efficient recursive sorting algorithms. In IEEE Congress on Evolutionary Computation, pages 2677--2684, 2006.
2. A. Agapitos and S. M. Lucas. Evolving modular recursive sorting algorithms. In M. Ebner et.al., editor, EuroGP 2007, volume 4445 of LNCS, pages 301--310. Springer, Heidelberg, 2007.
3. R. M. A. Azad and C. Ryan. The best things don't always come in small packages: Constant creation in grammatical evolution. In M. Nicolau et. al., editor, EuroGP 2014, volume 8599 of LNCS, pages 186--197. Springer, Heidelberg, 2014.
4. S. Brave. Evolving recursive programs for tree search. In Advances in Genetic Programming 2, pages 203--220. MIT Press, 1996.
5. G. Chennupati, R. M. A. Azad, and C. Ryan. Multi-core GE: automatic evolution of CPU based multi-core parallel programs. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pages 1041--1044. ACM, 2014.
6. G. Chennupati, R. M. A. Azad, and C. Ryan. Automatic evolution of parallel recursive programs. In EuroGP 2015, volume 9025 of LNCS, pages 167--178. Springer, Heidelberg, 2015.
7. G. Chennupati, J. Fitzgerald, and C. Ryan. On the efficiency of multi-core grammatical evolution (MCGE) evolving multi-core parallel programs. In Proceedings of the 6th World Congress on Nature and Biologically Inspired Computing, pages 238--243, 2014.
8. S. García and F. Herrera. An extension on "statistical comparisons of classifiers over multiple data sets" for all pairwise comparisons. Journal of Machine Learning Research, 9:2677--2694, 2008.
9. J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992.
10. A. Moraglio, F. E. B. Otero, C. G. Johnson, S. Thompson, and A. A. Freitas. Evolving recursive programs using non-recursive scaffolding. In IEEE CongressonEvolutionaryComputation, pages 1--8, 2012.
11. A. Nisbet. GAPS: A compiler framework for genetic algorithm (GA) optimised parallelisation. In P. Sloot et. al., editor, High-Performance Computing and Networking, volume 1401 of LNCS, pages 987--989. Springer, 1998.
12. M. O'Neill and C. Ryan. Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language. Kluwer Academic Publishers, 2003.
13. OpenMP Architecture Review Board. OpenMP application program interface version 3.0. http://www.openmp.org/mp-documents/spec30.pdf, May 2008.
14. C. Ryan. Automatic Re-engineering of Software Using Genetic Programming, volume 2 of Genetic Programming. Springer, 1999.
15. L. Spector, J. Klein, and M. Keijzer. The push3 execution stack and the evolution of control. In Proceedings of Genetic and Evolutionary Computation Conference, pages 1689--1696. ACM, 2005.
16. A. Trenaman. Concurrent genetic programming, tartarus and dancing agents. In R. Poli et. al., editor, EuroGP 1999, volume 1598 of LNCS, pages 270--282. Springer, Heidelberg, 1999.
17. P. A. Whigham and R. I. McKay. Genetic approaches to learning recursive relations. In X. Yao, editor, Progess in Evolutionary Computation, LNCS, pages 17--27. Springer, Heidelberg, 1995.
18. K. P. Williams. Evolutionary algorithms for automatic parallelization. PhD thesis, University of Reading, 1998.
19. M. L. Wong and T. Mun. Evolving recursive programs by using adaptive grammar based genetic programming. GPEM, 6:421--455, 2005.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Control methods

    • Search methodologies

• Theory of computation

  • Design and analysis of algorithms

    • Algorithm design techniques

      • Dynamic programming