Using Program Shaping and Algorithmic Skeletons to Parallelise an Evolutionary Multi-Agent System in Erlang

Authors

  • Adam D. Barwell School of Computer Science, The University of St Andrews
  • Christopher Brown School of Computer Science, The University of St Andrews
  • Kevin Hammond School of Computer Science, The University of St Andrews
  • Wojciech Turek AGH University of Science and Technology, Kraków
  • Aleksander Byrski AGH University of Science and Technology, Kraków

Keywords:

Parallel programming, parallel patterns, refactoring, Erlang, agent-based computing

Abstract

This paper considers how to use program shaping and algorithmic skeletons to parallelise a multi-agent system that is written in Erlang. Program shaping is the process of transforming a program to better enable the introduction of parallelism. Whilst algorithmic skeletons abstract away the low-level aspects of parallel programming that often plague traditional techniques, it is not always easy to introduce them into an arbitrary program, especially one that has not been written with parallelism in mind. Amongst other issues, data may not always be in a compatible format, function calls may need to be replicated to support alternative uses, side-effects may need to be isolated, or there may be dependencies between functions and data that obstruct the introduction of parallelism. Program shaping can be used to transform such code to a form that allows skeletons to be more easily introduced. In this paper, we present a series of generic program shaping rewrite rules, provide their implementation as refactorings, and show how they can be used to parallelise an Evolutionary Multi-Agent System (MAS) written in Erlang. We show that we can significantly speed up this application, obtaining super-linear speedups of over 70 times the original sequential performance on a 64-core shared-memory machine.

Downloads

Download data is not yet available.

Downloads

Published

2017-02-07

How to Cite

Barwell, A. D., Brown, C., Hammond, K., Turek, W., & Byrski, A. (2017). Using Program Shaping and Algorithmic Skeletons to Parallelise an Evolutionary Multi-Agent System in Erlang. COMPUTING AND INFORMATICS, 35(4), 792–818. Retrieved from http://www.cai.sk/ojs/index.php/cai/article/view/3378

Issue

Section

Special Section Articles

Most read articles by the same author(s)