Multi-way Divide and Conquer Parallel Programming based on PLists

published in Proceedings of the 27^th International Conference on Software, Telecommunications and Computer Networks (SoftCOM), pp. 1-6, DOI: 10.23919/SOFTCOM.2019.8903794, September 19-21, 2019, Split, Croatia.

Cite as

Full paper

Multi-way Divide and Conquer Parallel Programming based on PLists

Authors

Virginia Niculescu*, Darius Bufnea*, Adrian Sterca*, Robert Silimon**
* Department of Computer Science, Faculty of Mathematics and Computer Science, Babeș-Bolyai University of Cluj-Napoca, Romania
** Frequentis Romania

Copyright

© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Abstract

Divide and Conquer with all its variants represents an important paradigm of parallel programming. In this paper we present an implementation of PLists data structures and functions, which is introduced as an extension of a Java parallel programming framework – JPLF. The JPLF framework was initially based on PowerLists and their associated theory. By using functions defined on PLists, we may easily define programs based on the multi-way Divide and Conquer paradigm. Also, their definition allows the description of any kind of embarrassingly parallel computation. By introducing PLists into the JPLF framework, its application domain is very much enlarged, and also the flexibility of choosing the best computation variants is increased. The sizes of the data lists are not constrained any more – as it is for PowerLists to a power of two – and the level of parallelism could be much easier controlled. The experiments done for several applications reveal important improvements of the obtained performance.

Key words

parallel computation; divide&conquer; recursive data structures; performance; framework.

BibTeX bib file

niculescu-2019b.bib

References

1. K. Achatz, W. Schulte, Architecture independent massive parallelization of divide-and-conquer algorithms, Fakultaet fuer Informatik Universitaet Ulm, 1995.
2. M. Aldinucci, M. Danelutto, P. Teti, An advanced environment supporting structured parallel programming in Java, Future Generation Computer Systems, vol. 19, pp. 611-626, 2003.
3. A. S. Anand, R. K. Shyamasundarn, Scaling computation on GPUs using powerlists, Proceedings of the 22^nd International Conference on High Performance Computing Workshops (HiPCW), pp. 34-43, 2015.
4. R. Bird, M. Broy, An introduction to the theory of lists, Logic of Programming and Calculi of Discrete Design, Springer, pp. 5-42, 1987.
5. I E. Oran Brigham, The fast Fourier transform and its applications, Prentice-Hall, 1998.
6. M. Cole, Algorithmic Skeletons: Structured Management of Parallel Computation, MIT Press, 1989.
7. J. W. Cooley, J. W. Tukey, An algorithm for the machine calculation of complex fourier series, Math. Comput., vol. 19, pp. 297-301, 1965.
8. D. Caromel, M. Leyton, A transparent non-invasive file data model for algorithmic skeletons, Parallel and Distributed Processing 2008. IPDPS 2008. IEEE International Symposium on, pp. 1-10, 2008.
9. P. Ciechanowicz, H. Kuchen, Enhancing Muesli’s Data Parallel Skeletons for Multi-core Computer Architectures, IEEE International Conference on High Performance Computing and Communications (HPCC), pp. 108-113, 2010.
10. Gh. Coman, Numerical Analysis, Editura Libris Cluj-Napoca, 1995.
11. M. Danelutto, T. De Matteis, G. Mencagli, M. Torquati, A Divide-and-Conquer Parallel Pattern Implementation for Multicores, The Third International Workshop on Software Engineering for Parallel Systems, pp. 10-19, 2016.
12. J. Dean, S. Ghemawat, MapReduce: Simplified Data Processing on Large Clusters in OSDI, USENIX Association, pp. 137-150, 2004.
13. E. Gamma, R. Helm, R. Johnson, J. Vlissides, Design patterns: elements of reusable object-oriented software, Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1995.
14. C. H. Gonzalez, B. B. Fraguela, A generic algorithm template for divide-and-conquer in multicore systems, 12^th International Conference on High Performance Computing and Communications HPCC ’10, pp. 79-88, 2010.
15. C. A. Herrmann, C. Lengauer, A higher-order language for divide-and-conquer, Parallel Processing Letters, vol. 10, no. 02n03, pp. 239-250, 2000.
16. J. Kornerup, Data structures for parallel recursion, 1997.
17. M. Leyton, J. M. Piquer, Skandium: Multi-core Programming with Algorithmic Skeletons in PDP: Parallel Distributed and Network-Based Processing, IEEE Computer Society, pp. 289-296, 2010.
18. Frédéric Loulergue, Virginia Niculescu, Julien Tesson, Implementing powerlists with Bulk Synchronous Parallel ML, 16^th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2014), pp. 325-332, 2014.
19. J. Misra, Powerlist: A structure for parallel recursion, ACM Trans. Program. Lang. Syst., vol. 16, no. 6, pp. 1737-1767, November 1994.
20. V. Niculescu, F. Loulergue, D. Bufnea, A. Sterca, A Java Framework for High Level Parallel Programming using Powerlists, 18^th International Conference on Parallel and Distributed Computing Applications and Technologies (PDCAT), pp. 255-262, Dec. 2017.
21. V. Niculescu, PARES – A Model for Parallel Recursive Programs, Romanian Journal of Information Science and Technology (ROMJIST), vol. 14, no. 2, pp. 159-182, 2011.
22. D. Skillicorn, D. Talia, Models and languages for parallel computation, Computing Surveys, vol. 30, no. 2, pp. 123-169, June 1998.
23. G. L. Taboada, S. Ramos, R. R. Expósito, J. Touriño, R. Doallo, Java in the High Performance Computing arena: Research practice and experience, Science of Comput. Program., vol. 78, no. 5, pp. 425-444, 2013.