1. Proceedings
  2. I3M
  3. 2021
  4. EMSS
  5. 10.46354/i3m.2021.emss.004

Parallel Design Patterns vs Parallel Object Compositions. Two Proposals for Parallelization of the Divide & Conquer Technique

  • a Mario Rossainz-López ,
  • b Ivo Pineda-Torres,
  • c Bárbara Sánchez-Rinza,
  • d Manuel Capel-Tuñón
  • a,b.c  Faculty of Computer Science, Autonomous University of Puebla, Av. San Claudio and 14 Sur Street, San Manuel, Puebla, Mexico, C.P. 72570
  • d Software Engineering Department, College of Informatics and Telecommunications ETSIIT, University of Granada, Daniel Saucedo Aranda s/n, Granada 18071, Spain
Cite as
Rossainz-López M., Pineda-Torres I., Sánchez-Rinza B., Capel-Tuñón M. (2021). Parallel Design Patterns vs Parallel Object Compositions. Two Proposals for Parallelization of the Divide & Conquer Technique. Proceedings of the 33rd European Modeling & Simulation Symposium (EMSS 2021), pp. 23-32. DOI: https://doi.org/10.46354/i3m.2021.emss.004

Abstract

The present work shows the parallelization of the algorithmic design technique Divide & Conquer in two different ways: As a Parallel Design Pattern (PDP) through Active Objects and as Composition High-Level Parallel (HLPC). The overall purpose is to provide the user and novice programmer with two approaches within the object-oriented programming environment, particularly within the programming of Parallel Objects (PO), so that they can develop their programs according to a sequential programming style, automatically obtaining, easy and without much effort, the parallel counterpart of your code with the help of a specific programming environment like the one proposed. It is common for parallel applications to follow predetermined patterns in communication between processes. That is why this proposal proposes two different methods that solve problems with the same parallel control structure. Both methods use Structured Parallel Programming and Parallel Objects. The proposal is specialized in the algorithmic technique of divide & conquer to solve ordering, search, and optimization problems. The default pattern used to communicate problem solving processes is the tree structure. The proposed methods are novel because they offer the programmer the communication pattern between tree-like processes that is already defined in its structure. The programmer is only concerned with implementing the sequential algorithms that solve the problem under the divide & conquer paradigm. Both approaches are effective because they show good speedup analysis, and their usefulness, programmability, and performance are demonstrated.

References

  1. Alba, E., Luque, G., Garcia, J. and Ordonez, G. (2007). MALLBA: a software library to design efficient optimization algorithms. International Journal of Innovative Computing and Applications, Vol. 1, No. 1, pp.74–85.
  2. Brassard G. and Bratley P. (1997). Fundamentals of Algorithmics, Prentice-Hall, USA.
  3. Brinch Hansen. (1993). Model Programs for Computational Science: A programming methodology for multicomputers. Concurrency: Practice and Experience. Volume 5, Number 5.
  4. Collins A.J. (2011). Automatically Optimizing Parallel Skeletons. MSc thesis in Computer Science, School of Informatics University of Edinburgh, UK.
  5. Corradi A. and Leonardi L. (1991). PO Constraints as tools to synchronize active objects. Journal Object Oriented Programming 10:42-53.
  6. Corradi A. and Zambonelli I. (1995). Experiences toward an Object-Oriented Approach to Structured Parallel Programming. DEIS technical report no. DEIS-LIA-95-007.
  7. Danelutto M. and Torquati M. (2014). Loop parallelism: a new skeleton perspective on data parallel patterns, in Proc. Of Intl. Euromicro PDP 2014. Parallel Distributed and Network-based Processing, Torino, Italy.
  8. Danish S.A. and Farooqui Z. (2013). Approximate multiple pattern string matching using bit parallelism: a review, International Journal of Computer Applications, 74:47–51.
  9. Darlington et al. (1993). Parallel Programming using Skeleton Functions. Proceedings PARLE’93, Munich(D).
  10. De Simone, et al. (1997). Design Patterns for Parallel Programming. PDPTA’96 International Conference.
  11. Ernsting S. and Kuchen H. (2012). Algorithmic skeletons for multi-core, multi-GPU systems and clusters. Int. J. of High-Performance Computing and Networking, Vol. 7:129–138.
  12. Lavander G.R. and Kafura D.G. (2010). A Polymorphic Future and First-class Function Type for Concurrent Object-Oriented Programming. Journal of Object-Oriented Systems.
  13. McCool M., Robison A.D. and Reinders J. (2012). Structured Parallel Programming. Patterns for Efficient Computation. Morgan Kaufmann Publishers Elsevier. USA.
  14. Roosta and Séller. (1999). Parallel Processing and Parallel Algorithms. Theory and Computation. Springer.
  15. Rossainz M. and Capel M. (2014). Approach class library of high-level parallel compositions to implements communication patterns using structured parallel programming. 26TH European Modeling & Simulation Symposium. Bordeaux, France.
  16. Rossainz M. and Capel M. (2017). Design and implementation of communication patterns using parallel objects. Especial edition, Int. J. Simulation and Process Modelling, 12:1.
  17. Steuwer, M., Kegel, P. and Gorlatch, S. (2011). SkelCL a portable skeleton library for high-level GPU programming. Proceedings of the 16th IEEE Workshop on High-Level Parallel Programming Models and Supportive Environments, May, Anchorage, AK, USA.
  18. Theelen B.D., Florescu O., et al. (2007). Software/Hardware Engineering with the Parallel Object-Oriented Specification Language. IEEE/ACM International Conference on Formal Methods and Models for Codesign. Doi: 10.1109/MEMCOD.2007.371231. Nice, France. 
  19. Torquati, M., Aldinucci, M. and Danelutto, M. (2014). FastFlow documentation, Parallel programming in FastFlow, Computer Science Department, University of Pisa, Italy, [online] http://calvados.di.unipi.it/storage/refman/doc/html/index.html
  20. Torquati, M., Aldinucci, M. and Danelutto, M. (2015) FastFlow Testimonials, Computer Science Department. University of Pisa, Italy. [online] https://alpha.di.unito.it/
  21. Wilkinson B. and Allen M. (1999). Parallel Programming Techniques and Applications Using Networked Workstations and Parallel Computers. Prentice-Hall. USA.