1. Proceedings
  2. I3M
  3. 2018
  4. EMSS
  5. 10.46354/i3m.2018.emss.003

Parallel simulation of the N-body problem using Quad-Tree HLPC

  • a Mario Rossainz-López  ,
  • b Manuel I. Capel   ,
  • c E. Álvarez Martínez   ,
  • d Ivo Pineda Torres  
  • aFaculty of Computer Science, Autonomous University of Puebla, San Claudio Avenue and South 14th Street,
    San Manuel, Puebla, Puebla, 72000, México
  • bSoftware 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., Capel M.I., Álvarez Martínez E., Pineda Torres I. (2018). Parallel simulation of the N-body problem using Quad-Tree HLPC. Proceedings of the 30th European Modeling & Simulation Symposium (EMSS 2018), pp. 12-20. DOI: https://doi.org/10.46354/i3m.2018.emss.003

Abstract

This work proposes the use of Parallel Objects using the model of High Level Parallel Compositions (HLPC) to implement a proposal for parallel simulation of the Nbody Problem using the communication pattern between processes N-Tree under the HLPC Model. Particularly the implementation of the partitioning strategy divide and conquer as part of HLPC using the object orientation paradigm is shown. A HLPC comes from the composition of a set three object types: An object manager that represents the HLPC itself and makes an encapsulated abstraction out of it that hides the internal structure. The object manager controls a set of objects references, which address the object Collector and several Stage objects and represent the HLPC components whose parallel execution is coordinated by the object manager. With the strategy divide and conquer as HLPC the parallel processing technique NTree is used to parallelize sequential code that solve problems that can be partitioned by divide and conquer a N-ary Tree such the N-body problem that concerns with determining the effects of forces between ""bodies"". A case study of the N-body problem in terms of particles charged according to Coloumb’s electrostatic law is shown, which is solved with the implementation of a new HLPC: the Quad-Tree HLPC. Finally the performance analysis of this implementation is shown comparing them with its corresponding sequential implementations to demonstrate their usefulness: programmability and performance.

References

  1. Alonso J. 2014. Fast methods for N-body problems. CME342- Parallel Methods in Numerical
    Analysis. Lecture Notes Springer. USA.
  2. Andrews G.R., 2000. Foundations of Multithreaded, Parallel, and Distributed Programming, Addison-Wesley
  3. Appel Andrew W. 1985. An Efficient Program for many-body simulation. Society for Industrial and Applied Mathematics. Volume 6, Number 1. SIAM.
  4. Bacci, Danelutto, Pelagatti, Vaneschi, 1999. SklE: A Heterogeneous Environment for HPC
    Applications. Parallel Computing 25.
  5. Bhatt S., Chen M, Lin C. Y. and Liu P., 1992. Abstractions for Parallel N-Body Simulations.
    Proceeding of Scalable High Performance Computing Conference. Pp:26-29.
  6. Birrell A., 1989. An Introduction to Programming with Threads, Digital Equipment Corporation, Systems Research Center, Palo Alto California, USA.
  7. Brassard G. and Bratley P., 2000. Fundamentals of Algorithmics, Prentice-Hall, USA.
  8. Brinch Hansen, 1993. Model Programs for Computational Science: A programming
    methodology for multicomputers, Concurrency: Practice and Experience, Volume 5, Number 5.
  9. Carugati N. 2016. The Parallelization and Optimization of the N-Body Problem using OpenMP and OpenMPI. Gettysburg College. Student Publications.422.http://cupola.gettysburg.edu/stud
    ent_scholarship/422
  10. Corradi A., Leonardi L., 1991. PO Constraints as tools to synchronize active objects. Journal Object Oriented Programming 10, pp. 42-53
  11. Corradi A, Leonardo L, Zambonelli F., 1995. Experiences toward an Object-Oriented Approach
    to Structured Parallel Programming. DEIS technical report no. DEIS-LIA-95-007.
  12. Danelutto M. and Torquati M, 2014. Loop parallelism: a new skeleton perspective on data parallel patterns, in Proc. of Intl. Euromicro PDP: Parallel Distributed and Network-based Processing, Torino, Italy
  13. D’Angelo A. 2016. A Brief Introduction to Quadtrees and Their Applications. Style file from the 28th Canadian Conference on Computational Geometry. Canada.
  14. Darlington et al., 1993, Parallel Programming Using Skeleton Functions. Proceedings PARLE’93,
    Munich (D).
  15. Devanshu M. and Munish M., 2014. N-Body Simulation. University at Buffalo. The State
    University of New York.
  16. Greengard L. and Rokhijn V. 1997. A Fast Algorithm for particle simulations. Journal of Computational Phiysics, Volume 135, Issue 2. pp:280-292
  17. Lavander G.R., Kafura D.G. 1995. A Polimorphic Future and First-class Function Type for
    Concurrent Object-Oriented Programming. Journal of Object-Oriented Systems.
  18. Liwu Li, 2002. Java Data Structures and Programming. Springer Verlag. Germany. ISBN: 3-540-63763X. Müller M. 2008. CUDA Particle-based fluid simulation. NVIDIA Corporation
  19. Roosta, Séller, 1999. Parallel Processing and Parallel Algorithms. Theory and Computation. Springer.
  20. Rossainz, M., Capel M., 2008. A Parallel Programming Methodology using Communication Patterns named CPANS or Composition of Parallel Object. 20TH European Modeling & Simulation Symposium.Campora S. Giovanni. Italy.
  21. Rossainz M., Capel M., 2014. Approach class library of high level parallel compositions to implements communication patterns using structured parallel programming. 26TH European Modeling & Simulation Symposium. Campora Bordeaux, France.
  22. Wilkinson B., Allen M., 1999. Parallel Programming Techniques and Applications Using Networked Workstations