{"id":1708,"date":"2019-09-30T12:13:42","date_gmt":"2019-09-30T09:13:42","guid":{"rendered":"https:\/\/www.cs.ubbcluj.ro\/~bufny\/?p=1708"},"modified":"2022-01-10T00:24:22","modified_gmt":"2022-01-09T22:24:22","slug":"multi-way-divide-and-conquer-parallel-programming-based-on-plists","status":"publish","type":"post","link":"https:\/\/www.cs.ubbcluj.ro\/~bufny\/multi-way-divide-and-conquer-parallel-programming-based-on-plists\/","title":{"rendered":"Multi-way Divide and Conquer Parallel Programming based on PLists"},"content":{"rendered":"

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

Cite as<\/strong><\/p>\n

V. Niculescu, D. Bufnea, A. Sterca and R. Silimon, \"Multi-way Divide and Conquer Parallel Programming based on PLists\", 2019 International Conference on Software, Telecommunications and Computer Networks (SoftCOM), 2019, pp. 1-6, doi: 10.23919\/SOFTCOM.2019.8903794<\/pre>\n
Full paper<\/strong><\/p>\n
\"\" Multi-way Divide and Conquer Parallel Programming based on PLists<\/a><\/p>\n
Authors<\/strong><\/p>\n
Virginia Niculescu*, Darius Bufnea*, Adrian Sterca*, Robert Silimon**
\n* Department of Computer Science, Faculty of Mathematics and Computer Science, Babe\u0219-Bolyai University of Cluj-Napoca, Romania
\n** Frequentis Romania<\/p>\n
Copyright<\/strong><\/p>\n
\u00a9 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.<\/p>\n
Abstract<\/strong><\/p>\n
Divide and Conquer with all its variants represents an important paradigm of parallel programming. In this paper we present an implementation of PLists<\/em> 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<\/em> and their associated theory. By using functions defined on PLists<\/em>, 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<\/em> 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<\/em> 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.<\/p>\n
Key words<\/strong><\/p>\n
parallel computation; divide&conquer; recursive data structures; performance; framework.<\/p>\n
BibTeX bib file<\/strong><\/p>\n
\"\" niculescu-2019b.bib<\/a><\/p>\n
<\/pre>\n
References<\/strong><\/p>\n
    \n
  1. K. Achatz, W. Schulte, Architecture independent massive parallelization of divide-and-conquer algorithms<\/em>, Fakultaet fuer Informatik Universitaet Ulm, 1995.<\/li>\n
  2. M. Aldinucci, M. Danelutto, P. Teti, An advanced environment supporting structured parallel programming in Java<\/em>, Future Generation Computer Systems, vol. 19, pp. 611-626, 2003.<\/li>\n
  3. A. S. Anand, R. K. Shyamasundarn, Scaling computation on GPUs using powerlists<\/em>, Proceedings of the 22nd<\/sup> International Conference on High Performance Computing Workshops (HiPCW), pp. 34-43, 2015.<\/li>\n
  4. R. Bird, M. Broy, An introduction to the theory of lists<\/em>, Logic of Programming and Calculi of Discrete Design, Springer, pp. 5-42, 1987.<\/li>\n
  5. I E. Oran Brigham, The fast Fourier transform and its applications<\/em>, Prentice-Hall, 1998.<\/li>\n
  6. M. Cole, Algorithmic Skeletons: Structured Management of Parallel Computation<\/em>, MIT Press, 1989.<\/li>\n
  7. J. W. Cooley, J. W. Tukey, An algorithm for the machine calculation of complex fourier series<\/em>, Math. Comput., vol. 19, pp. 297-301, 1965.<\/li>\n
  8. D. Caromel, M. Leyton, A transparent non-invasive file data model for algorithmic skeletons<\/em>, Parallel and Distributed Processing 2008. IPDPS 2008. IEEE International Symposium on, pp. 1-10, 2008.<\/li>\n
  9. P. Ciechanowicz, H. Kuchen, Enhancing Muesli’s Data Parallel Skeletons for Multi-core Computer Architectures<\/em>, IEEE International Conference on High Performance Computing and Communications (HPCC), pp. 108-113, 2010.<\/li>\n
  10. Gh. Coman, Numerical Analysis<\/em>, Editura Libris Cluj-Napoca, 1995.<\/li>\n
  11. M. Danelutto, T. De Matteis, G. Mencagli, M. Torquati, A Divide-and-Conquer Parallel Pattern Implementation for Multicores<\/em>, The Third International Workshop on Software Engineering for Parallel Systems, pp. 10-19, 2016.<\/li>\n
  12. J. Dean, S. Ghemawat, MapReduce: Simplified Data Processing on Large Clusters<\/em> in OSDI, USENIX Association, pp. 137-150, 2004.<\/li>\n
  13. E. Gamma, R. Helm, R. Johnson, J. Vlissides, Design patterns: elements of reusable object-oriented software<\/em>, Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1995.<\/li>\n
  14. C. H. Gonzalez, B. B. Fraguela, A generic algorithm template for divide-and-conquer in multicore systems<\/em>, 12th<\/sup> International Conference on High Performance Computing and Communications HPCC ’10, pp. 79-88, 2010.<\/li>\n
  15. C. A. Herrmann, C. Lengauer, A higher-order language for divide-and-conquer<\/em>, Parallel Processing Letters, vol. 10, no. 02n03, pp. 239-250, 2000.<\/li>\n
  16. J. Kornerup, Data structures for parallel recursion<\/em>, 1997.<\/li>\n
  17. M. Leyton, J. M. Piquer, Skandium: Multi-core Programming with Algorithmic Skeletons<\/em> in PDP: Parallel Distributed and Network-Based Processing, IEEE Computer Society, pp. 289-296, 2010.<\/li>\n
  18. Fr\u00e9d\u00e9ric Loulergue, Virginia Niculescu, Julien Tesson, Implementing powerlists with Bulk Synchronous Parallel ML<\/em>, 16th<\/sup> International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2014), pp. 325-332, 2014.<\/li>\n
  19. J. Misra, Powerlist: A structure for parallel recursion<\/em>, ACM Trans. Program. Lang. Syst., vol. 16, no. 6, pp. 1737-1767, November 1994.<\/li>\n
  20. V. Niculescu, F. Loulergue, D. Bufnea, A. Sterca, A Java Framework for High Level Parallel Programming using Powerlists<\/em><\/a>, 18th<\/sup> International Conference on Parallel and Distributed Computing Applications and Technologies (PDCAT), pp. 255-262, Dec. 2017.<\/li>\n
  21. V. Niculescu, PARES – A Model for Parallel Recursive Programs<\/em>, Romanian Journal of Information Science and Technology (ROMJIST), vol. 14, no. 2, pp. 159-182, 2011.<\/li>\n
  22. D. Skillicorn, D. Talia, Models and languages for parallel computation<\/em>, Computing Surveys, vol. 30, no. 2, pp. 123-169, June 1998.<\/li>\n
  23. G. L. Taboada, S. Ramos, R. R. Exp\u00f3sito, J. Touri\u00f1o, R. Doallo, Java in the High Performance Computing arena: Research practice and experience<\/em>, Science of Comput. Program., vol. 78, no. 5, pp. 425-444, 2013.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"
    published in Proceedings of the 27th 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 V. Niculescu, D. Bufnea, A. Sterca and R. Silimon, “Multi-way Divide and Conquer Parallel… Continue Reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[110],"tags":[],"_links":{"self":[{"href":"https:\/\/www.cs.ubbcluj.ro\/~bufny\/wp-json\/wp\/v2\/posts\/1708"}],"collection":[{"href":"https:\/\/www.cs.ubbcluj.ro\/~bufny\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.cs.ubbcluj.ro\/~bufny\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.cs.ubbcluj.ro\/~bufny\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.cs.ubbcluj.ro\/~bufny\/wp-json\/wp\/v2\/comments?post=1708"}],"version-history":[{"count":10,"href":"https:\/\/www.cs.ubbcluj.ro\/~bufny\/wp-json\/wp\/v2\/posts\/1708\/revisions"}],"predecessor-version":[{"id":1716,"href":"https:\/\/www.cs.ubbcluj.ro\/~bufny\/wp-json\/wp\/v2\/posts\/1708\/revisions\/1716"}],"wp:attachment":[{"href":"https:\/\/www.cs.ubbcluj.ro\/~bufny\/wp-json\/wp\/v2\/media?parent=1708"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.cs.ubbcluj.ro\/~bufny\/wp-json\/wp\/v2\/categories?post=1708"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.cs.ubbcluj.ro\/~bufny\/wp-json\/wp\/v2\/tags?post=1708"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}