Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 8

Proceedings of the 2016 Federated Conference on Computer Science and Information Systems

Efficient parallel execution of genetic algorithms on Epiphany manycore processor

,

DOI: http://dx.doi.org/10.15439/2016F255

Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 865–872 ()

Full text

Abstract. Recent years have seen a growing trend towards the introduction of more advanced manycore processors. On the other hand, there is also a growing popularity for cheap, credit-card-sized, devices offering more and more advanced features and computational power. In this paper we evaluate Parallella -- a small board with the Epiphany manycore coprocessor consisting of sixteen MIMD cores connected by a mesh network-on-a-chip. Our tests are based on classical genetic algorithms. We discuss some possible optimizations and issues that arise from the architecture of the board. Although we achieve significant speed improvements, there are issues, such us the limited local memory size and slow memory access, that make the implementation of efficient code for Parallella difficult.

References

  1. J. Shalf, J. Bashor, D. Patterson, K. Asanovic, K. Yelick, K. Keutzer, and T. Mattson, “The MANYCORE revolution: will HPC lead or follow,” SciDAC Review, vol. 14, pp. 40–49, 2009.
  2. A. Olofsson, T. Nordström, and Z. Ul-Abdin, “Kickstarting High-performance Energy-efficient Manycore Architectures with Epiphany,” Nov. 2-5, 2014. http://dx.doi.org/10.1109/ACSSC.2014.7094761
  3. G. Chrysos, “Intel® Xeon PhiTM Coprocessor-the Architecture,” Intel Whitepaper, 2014.
  4. M. Kisiel-Dorohinicki, G. Dobrowolski, and E. Nawarecki, “Agent populations as computational intelligence,” in Neural Networks and Soft Computing: Proceedings of the Sixth International Conference on Neural Networks and Soft Computing, Zakopane, Poland, June 11–15, 2002, L. Rutkowski and J. Kacprzyk, Eds. Heidelberg: Physica-Verlag HD, 2003, pp. 608–613. ISBN 978-3-7908-1902-1
  5. M. Kisiel-Dorohinicki, “Agent-based models and platforms for parallel evolutionary algorithms,” in Computational Science - ICCS 2004, M. Bubak, G. D. van Albada, P. M. A. Sloot, and J. Dongarra, Eds. Springer Berlin Heidelberg, 2004, pp. 646–653.
  6. Ł. Faber, K. Pi ̨etak, A. Byrski, and M. Kisiel-Dorohinicki, Agent-Based Simulation in AgE Framework. Springer Berlin Heidelberg, 2012, pp. 55–83. ISBN 978-3-642-28888-3
  7. D. Krzywicki, W. Turek, A. Byrski, and M. Kisiel-Dorohinicki, “Massively concurrent agent-based evolutionary computing,” Journal of Computational Science, vol. 11, pp. 153–162, nov 2015. http://dx.doi.org/10.1016/j.jocs.2015.07.003
  8. M. Pietroń, A. Byrski, and M. Kisiel-Dorohinicki, “GPGPU for difficult black-box problems,” Procedia Computer Science, vol. 51, pp. 1023–1032, 2015. http://dx.doi.org/10.1016/j.procs.2015.05.249
  9. Epihany SDK Reference, rev. 5.13.09.10. [Online]. Available: http://adapteva.com/docs/epiphany_sdk_ref.pdf
  10. J. A. Ross, D. A. Richie, S. J. Park, and D. R. Shires, “Parallel Program- ming Model for the Epiphany Many-Core Coprocessor Using Threaded MPI,” in Proceedings of the 3rd International Workshop on Many-core Embedded Systems. ACM, 2015. http://dx.doi.org/10.1145/2768177.2768183 pp. 41–47.
  11. A. Papadogiannakis, S. N. Agathos, and V. V. Dimakopoulos, OpenMP 4.0 Device Support in the OMPi Compiler. Cham: Springer International Publishing, 2015, ch. OpenMP 4.0 Device Support in the OMPi Compiler, pp. 202–216. ISBN 978-3-319-24595-9
  12. T. Back, D. B. Fogel, and Z. Michalewicz, Eds., Handbook of Evolutionary Computation, 1st ed. Bristol, UK, UK: IOP Publishing Ltd., 1997. ISBN 0750303921
  13. M. Matsumoto and T. Nishimura, “Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator,” ACM Trans. Model. Comput. Simul., vol. 8, no. 1, pp. 3–30, Jan. 1998. http://dx.doi.org/10.1145/272991.272995
  14. (2011) Tiny Mersenne Twister (TinyMT): A small-sized variant of Mersenne Twister. [Online]. Available: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/TINYMT/
  15. Andreas Olofsson - Public forum communication. [Online]. Available: https://parallella.org/forums/viewtopic.php?f=9&t=2391&p=13653
  16. Epihany Architecture Reference, rev. 14.03.11. [Online]. Available: http://adapteva.com/docs/epiphany_sdk_ref.pdf
  17. A. Varghese, B. Edwards, G. Mitra, and A. P. Rendell, “Programming the Adapteva Epiphany 64-core network-on-chip coprocessor,” International Journal of High Performance Computing Applications, 2015. http://dx.doi.org/10.1109/IPDPSW.2014.112
  18. A. Byrski and M. Kisiel-Dorohinicki, Man-Machine Interactions 3. Cham: Springer International Publishing, 2014, ch. Agent-Based Approach to Continuous Optimisation, pp. 487–494. ISBN 978-3-319-02309-0
  19. A. Byrski, R. Dreżewski, L. Siwik, and M. Kisiel-Dorohinicki, “Evolutionary Multi-Agent Systems,” The Knowledge Engineering Review, vol. 30, no. 02, pp. 171–186, mar 2015. http://dx.doi.org/10.1017/s0269888914000289
  20. D. Krzywicki, Ł. Faber, A. Byrski, and M. Kisiel-Dorohinicki, “Computing agents for decision support systems,” Future Generation Computer Systems, vol. 37, pp. 390–400, jul 2014. http://dx.doi.org/10.1016/j.future.2014.02.002