PList-based Divide and Conquer Parallel Programming

published in in Journal of Communications Software and Systems, Vol. 16, No. 2 (2020), pp. 197-206, DOI: 10.24138/jcomss.v16i2.1029.

Cite as

Full paper

PList-based Divide and Conquer Parallel Programming

Authors

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

Abstract

This paper details an extension of a Java parallel programming framework – JPLF. The JPLF framework is a programming framework that helps programmers build parallel programs using existing building blocks. The framework is based on PowerLists and PList Theories and it naturally supports multi-way Divide and Conquer. By using this framework, the programmer is exempted from dealing with all the complexities of writing parallel programs from scratch. This extension to the JPLF framework adds PLists support to the framework and so, it enlarges the applicability of the framework to a larger set of parallel solvable problems. Using this extension, we may apply more flexible data division strategies. In addition, the length of the input lists no longer has to be a power of two – as required by the PowerLists theory. In this paper we unveil new applications that emphasize the new class of computations that can be executed within the JPLF framework. We also give a detailed description of the data structures and functions involved in the PLists extension of the JPLF, and extended performance experiments are described and analyzed.

Key words

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

BibTeX bib file

niculescu-2020plists.bib

References

1. V. Niculescu, F. Loulergue, D. Bufnea, A. Sterca, A Java Framework for High Level Parallel Programming using Powerlists, in Proceedings of the 18^th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT’17), pp. 255-262, DOI: 10.1109/PDCAT.2017.00049, December 18-20, 2017, Taipei, Taiwan.
2. J. Misra, Powerlist: A Structure for Parallel Recursion, in ACM Trans. Program. Lang. Syst., Vol. 16, No. 6, pp. 1737-1767, DOI: 10.1145/197320.197356, November 1994.
3. 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, ISBN:978-0-201-63361-0.
4. V. Niculescu, D. Bufnea, A. Sterca, Multi-way Divide and Conquer Parallel Programming based on PLists, 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.
5. J. Kornerup, Data Structures for Parallel Recursion, Ph.D. dissertation, University of Texas, 1997.
6. V. Niculescu, PARES – A Model for Parallel Recursive Programs, in Romanian Journal of Information Science and Technology (ROMJIST), Vol. 14, No. 2, pp. 159-182, 2011.
7. D. Skillicorn, D. Talia, Models and Languages for Parallel Computation, Computing Surveys, Vol. 30, No. 2, pp. 123-169, DOI: 10.1145/280277.280278, June 1998.
8. M. Cole, Algorithmic Skeletons: Structured Management of Parallel Computation, MIT Press, 1989.
9. M. Aldinucci, M. Danelutto, P. Kilpatrick, M. Torquati, FastFlow: High-level and Efficient Streaming on Multi-core, in Programming Multi-core and Many-core Computing Systems, S. Pllana and F. Xhafa, Ed., Wiley, 2014.
10. M. Zandifar, M. Abduljabbar, A. Majidi, D. Keyes, N. Amato, L. Rauchwerger, Composing Algorithmic Skeletons to Express High-Performance Scientific Applications, in Proceedings of the 29^th ACM on International Conference on Supercomputing, pp. 415-424, DOI: 10.1145/2751205.2751241, 2015.
11. 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, in Science of Comput. Program., Vol. 78, No. 5, pp. 425-444, DOI: 10.1016/j.scico.2011.06.002, 2013.
12. M. Aldinucci, M. Danelutto, P. Teti, An Advanced Environment Supporting Structured Parallel Programming in Java, Future Generation Computer Systems, Vol. 19, pp. 611-626, DOI: 10.1016/S0167-739X(02)00172-3, 2003.
13. D. Caromel, M. Leyton, A Transparent non-invasive File Data Model for Algorithmic Skeletons, in Proceedings of 22^nd IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2008, pp. 1-10, DOI: 10.1109/IPDPS.2008.4536276, Miami, Florida USA, April 14-18, 2008.
14. M. Leyton, J. M. Piquer, Skandium: Multi-core Programming with Algorithmic Skeletons, in PDP: Parallel, Distributed, and Network-Based Processing, pp. 289-296, DOI: 10.1109/PDP.2010.26, IEEE Computer Society, 2010.
15. M. Danelutto, T. De Matteis, G. Mencagli, M. Torquati, A Divide-and-Conquer Parallel Pattern Implementation for Multicores, in the 3^rd International Workshop on Software Engineering for Parallel Systems, (SEPS 2016), co-located with SPLASH 2016, ACM, pp. 10-19, DOI: 10.1145/3002125.3002128, Amsterdam, 2016.
16. C. H. Gonzalez, B. B. Fraguela, A Generic Algorithm Template for Divide-and-conquer in Multicore Systems, in Proceedings of 12^th International Conference on High Performance Computing and Communications, HPCC ’10, pp. 79-88, DOI: 10.1109/HPCC.2010.24, Washington, DC, USA, 2010, IEEE Computer Society.
17. C. A. Herrmann, C. Lengauer, ℋ𝒟𝒞: A Higher-order Language for Divide-and-conquer, in Parallel Processing Letters, Vol. 10, No. 02n03, pp. 239-250, DOI: 10.1142/S0129626400000238, 2000.
18. K. Achatz, W. Schulte, Architecture Independent Massive Parallelization of Divide-and-conquer Algorithms, in Proceedings of International Conference on Mathematics of Program Construction, MPC 1995, Lecture Notes in Computer Science, Vol. 947, pp. 97-127, DOI: 10.1007/3-540-60117-1_7, Springer, Berlin, Heidelberg.
19. F. Loulergue, V. Niculescu, J. Tesson, Implementing Powerlists with Bulk Synchronous Parallel ML, in Proceedings of 16^th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, (SYNASC2014), Timisoara, Romania, 22-25 sept. 2014, pp. 325-332, DOI: 10.1109/SYNASC.2014.51, IEEE Computer Society.
20. A. S. Anand, R. K. Shyamasundarn, Scaling Computation on GPUs Using Powerlists, in Proceedings of the 22^nd International Conference on High Performance Computing Workshops (HiPCW), pp. 34-43, DOI: 10.1109/HiPCW.2015.14, Bangalore, 2015.
21. Y. Zhang, Y. Mei, Divide-and-Conquer Large Scale Capacitated Arc Routing Problems with Route Cutting Off Decomposition, arXiv:1912.12667, 2019.
22. S. Itzhaky, R. Singh, A. Solar-Lezama, K. Yessenov, Y. Lu, C. Leiserson, R. Chowdhury, Deriving Divide-and-conquer Dynamic Programming Algorithms Using Solver-aided Transformations, in Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, pp. 145-164, DOI: 10.1145/3022671.2983993, Amsterdam, Netherlands.
23. Gh. Coman, Numerical Analysis, Editura Libris, Cluj-Napoca, 1995 (in Romanian).