Synthesis of Parallel Iterative Sorts with Multi-Core Grammatical Evolution

ABSTRACT

Writing parallel programs is a challenging but unavoidable proposition to take true advantage of multi-core processors.

In this paper, we extend Multi-core Grammatical Evolution for Parallel Sorting (MCGE-PS) to evolve parallel iterative sorting algorithms while also optimizing their degree of parallelism. We use evolution to optimize the performance of these parallel programs in terms of their execution time, and our results demonstrate a significant optimization of 11.03 in performance when compared with various MCGE-PS variations as well as the GNU GCC compiler optimizations that reduce the execution time through code minimization.

We then analyse the evolutionary (code growth) and non-evolutionary (thread scheduling) factors that cause performance implications. We address them to further optimize the performance and report it as 12.52.

References

1. R. Abbott and J. G. B. Parviz. Guided genetic programming. In H. R. Arabnia and E. B. Kozerenko, editors, Proceedings of the International Conference on Machine Learning; Models, Technologies and Applications, pages 28--34. CSREA Press, 2003.
2. A. Agapitos and S. M. Lucas. Evolving efficient recursive sorting algorithms. In IEEE Congress on Evolutionary Computation, pages 2677--2684, 2006.
3. 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.
4. R. M. A. Azad and C. Ryan. The best things don't always come in small packages: Constant creation in grammatical evolution. In EuroGP 2014, volume 8599 of LNCS, pages 186--197. Springer, Heidelberg, 2014.
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 sorting programs on multi-cores. In A. M. Mora and G. Squillero, editors, EvoApplications 2015, volume 9028 of LNCS, pages 706--717. Springer, Heidelberg, 2015.
7. 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.
8. W. D. Hillis. Co-evolving parasites improve simulated evolution as an optimization procedure. Physica D: Nonlinear Phenomena, 42(1):228--234, 1990.
9. K. E. Kinnear Jr. Evolving a sort: Lessons in genetic programming. In IEEE International Conference on Neural Networks, pages 881--888. IEEE, 1993.
10. K. E. Kinnear Jr. Generality and difficulty in genetic programming: Evolving a sort. In S. Forrest, editor, Proceedings of International Conference on Genetic Algorithms, pages 287--294. Morgan Kaufmann, 1993.
11. D. E. Knuth. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998.
12. 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.
13. M. O'Neill, M. Nicolau, and A. Agapitos. Experiments in program synthesis with grammatical evolution: A focus on integer sorting. In IEEE Congress on Evolutionary Computation, pages 1504--1511, 2014.
14. M. O'Neill and C. Ryan. Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language. Kluwer Academic Publishers, Norwell, MA, USA, 2003.
15. OpenMP Architecture Review Board. OpenMP application program interface version 3.0. http://www.openmp.org/mp-documents/spec30.pdf, May 2008.
16. U.-M. O'Reilly and F. Oppacher. An experimental perspective on genetic programming. In R. Manner and B. Manderick, editors, Parallel Problem Solving from Nature 2, pages 331--340. Elsevier Science, 1992.
17. U.-M. O'Reilly and F. Oppacher. A comparative analysis of genetic programming. In P. J. Angeline et. al, editor, Advances in Genetic Programming 2, chapter 2, pages 23--44. MIT Press, 1996.
18. C. Ryan. Automatic Re-engineering of Software Using Genetic Programming, volume 2 of Genetic Programming. Springer, 1999.
19. C. Ryan, J. J. Collins, and M. O'Neill. Grammatical evolution: Evolving programs for an arbitrary language. In W. Banzhaf et. al., editor, EuroGP 1998, volume 1391 of LNCS, pages 83--95. Springer, Heidelberg, 1998.
20. C. Ryan and L. Ivan. Automatic parallelization of arbitrary programs. In R. Poli et. al., editor, EuroGP 1999, volume 1598 of LNCS, pages 244--254. Springer, Heidelberg, 1999.
21. L. Spector, J. Klein, and M. Keijzer. The push3 execution stack and the evolution of control. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1689--1696, 2005.
22. 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.
23. A. Vargha and H. D. Delaney. A critique and improvement of the "cl" common language effect size statistics of mcgraw and wong. Journal of Educational and Behavioral Statistics, 25(2):101--132, 2000.
24. P. A. Whigham. Grammatical Bias for Evolutionary Learning. PhD thesis, University of New South Wales, 1996.
25. K. P. Williams. Evolutionary algorithms for automatic parallelization. PhD thesis, University of Reading, 1998.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Control methods

    • Search methodologies

• Theory of computation

  • Design and analysis of algorithms

    • Algorithm design techniques

      • Dynamic programming