OhHelp: a scalable domain-decomposing dynamic load balancing for particle-in-cell simulations

ABSTRACT

This paper proposes a new method for Particle-in-Cell (PIC) simulations which aims at achieving both good load balancing and scalability so as to be efficiently executed on distributed memory systems. This method, named OhHelp, simply and equally partitions the space domain where charged particles reside and assigns each partitioned subdomain to each computation node for scalable simulation with respect to the size of the domain. Load balancing and thus the scalability in terms of the number of particles are accomplished by making each node help another heavily loaded node which deputes a part of particles in its subdomain and replicated subdomain field data to its helpers. The OhHelp load balancer monitors particle movements through subdomain boundaries to check if the helpand-helpers configuration keeps good load balancing and, when unacceptable imbalance is found, dynamically reconfigures it to regain perfect balancing. The efficiency and scalability of OhHelp are confirmed through our experiment with a production-level full-3D plasma simulator and with uniform and non-uniform particle distributions. As a result, we found 256-core parallel simulations, including an extremely imbalanced setting to pack all the particles in a small region, exert 159-190 speedup compared to sequential execution.

REFERENCES

• 1: Erol Akarsu , Kivanc Dincer , Tomasz Haupt , Geoffrey C. Fox, Particle-in-cell simulation codes in High Performance Fortran, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.38-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369108]
• 2: J. Barnes and P. Hutt. A hierarchical O (N log N ) force calculation algorithm. Nature, 324:446--449, Dec. 1986.
• 3: S. Briguglio, B. D. Martino, G. Fogaccia, and G. Vlad. Hierarchical MPI+OpenMP implementation of parallel PIC applications on clusters of symmetric multiprocessors. In Euro PVM/MPI 2003, volume 2840 of Lecture Notes in Computer Science, pages 180--187. Springer-Verlag, 2003.
• 4: S. Briguglio, B. D. Martino, and G. Vlad. Workload decomposition strategies for hierarchical distributed-shared memory parallel systems and their implementation with integration of high-level parallel languages. Concurrency and Computation:Practice and Experience, 14:933--956, 2002.
• 5: P. M. Campbell and E. A. Carmona. Hierarchical domain decomposition with unitary load balancing for electromagnetic particle-in-cell codes. In Proc. 5th Distributed Memory Computing Conf., pages 943--950, 1990.
• 6: E. A. CarmonaandL. J. Chandler. OnparallelPIC versatility and the structure of parallel PIC approaches. Concurrency: Practice and Experience, 9(12):1377--1405, 1997.
• 7: J. M. Dawson. Particle simulation of plasmas. Review of Modern Physics, 55(2):403--447, 1983.
• 8: S. Ethier, W. M. Tang, and Z. Lin. Gyrokinetic particle-in-cell simulations of plasma microturbulence on advanced computing platforms. J. Physics: Conference Series, 16:1--15, 2005.
• 9: Ricardo A. Fonseca , L. O. Silva , F. S. Tsung , Viktor K. Decyk , W. Lu , C. Ren , W. B. Mori , S. Deng , S. Lee , T. Katsouleas , J. C. Adam, OSIRIS: A Three-Dimensional, Fully Relativistic Particle in Cell Code for Modeling Plasma Based Accelerators, Proceedings of the International Conference on Computational Science-Part III, p.342-351, April 21-24, 2002
• 10: G. C. Fox. A review of automatic load balancing and decomposition methods for the Hypercube. In Numerical Algorithms for Modern Parallel Computer Architectures, pages 63--76. Springer-Verlag, 1988.
• 11: D. F. Gordon, W. B. Mori, and T. M. Antonsen. A ponderomotive guiding center particle-in-cell code for efficient modeling of laser-plasma interactions. IEEE Trans. Plasma Science, 28(4):1135--1143, 2000.
• 12: J. Joseph D. Blahovec, L. A. Bowers, J. W. Luginsland, G. E. Sasser, and J. J. Watrous. 3-D ICEPIC simulations of the relativistic klystron oscillator. IEEE Trans. Plasma Science, 28(3):821--829, 2000.
• 13: E. Kawamura, C. K. Birdsall, and V. Vahedi. Physical and numerical methods of speeding up particle codes and paralleling as applied to RF discharges. Plasma Sources Science & Technology, 9:413--428, 2000.
• 14: Paulett C. Liewer , Viktor K. Decyk, A general concurrent algorithm for plasma particle-in-cell simulation codes, Journal of Computational Physics, v.85 n.2, p.302-322, Dec. 1989 [doi>10.1016/0021-9991(89)90153-8]
• 15: P. C. Liewer , V. K. Decyk , J. M. Dawson , G. C. Fox, A universal concurrent algorithm for plasma particle-in-cell simulation codes, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1101-1107, January 1989, Pasadena, California, United States [doi>10.1145/63047.63063]
• 16: C. S. Lin, A. L. Thring, and J. Koga. A parallel particle-in-cell model for the massively parallel processor. In Proc. Symp. Frontiers of Massively Parallel Computation, pages 339--342, 1988.
• 17: O. M. Lubeck and V. Faber. Modeling the performance of Hypercubes: A case study using the particle-in-cell application. Parallel Computing, 9:37--52, 1988.
• 18: B. Di Martino , S. Briguglio , G. Vlad , P. Sguazzero, Parallel PIC plasma simulation through particle decomposition techniques, Parallel Computing, v.27 n.3, p.295-314, February 1, 2001 [doi>10.1016/S0167-8191(00)00098-3]
• 19: B. Moon and J. Saltz. Adaptive runtime support for direct simulation Monte Carlo methods on distributed memory architectures. In Proc. Scalable High-Performance Computing Conference, pages 176--183, 1994.
• 20: Hiroshi Nakashima, T2K Open Supercomputer: Inter-university and Inter-disciplinary Collaboration on the New Generation Supercomputer, Proceedings of the International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008), p.137-142, January 17-17, 2008 [doi>10.1109/ICKS.2008.6]
• 21: S. J. Plimpton, D. B. Seidel, M. F. Pasik, R. S. Coats, and G. R. Montry. A load-balancing algorithm for a parallel electromagnetic particle-in-cell code. Computer Physics Communications, 152:227--241, 2003.
• 22: Ji Qiang , Miguel A. Furman , Robert D. Ryne, Parallel Particle-In-Cell Simulation of Colliding Beams in High Energy Accelerators, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.29, November 15-21, 2003
• 23: Robert D. Ferraro , Paulett C. Liewer , Viktor K. Decyk, Dynamic load balancing for a 2D concurrent plasma PIC code, Journal of Computational Physics, v.109 n.2, p.329-341, Dec. 1993 [doi>10.1006/jcph.1993.1221]
• 24: I. F. Sbalzarini , J. H. Walther , M. Bergdorf , S. E. Hieber , E. M. Kotsalis , P. Koumoutsakos, PPM: a highly efficient parallel particle-mesh library for the simulation of continuum systems, Journal of Computational Physics, v.215 n.2, p.566-588, 1 July 2006 [doi>10.1016/j.jcp.2005.11.017]
• 25: D. B. Seidel, S. J. Plimpton, M. F. Pasik, R. S. Coats, and G. R. Montry. Dynamic load balancing for a parallel electromagnetic particle-in-cell code. In Proc. IEEE Intl. Pulsed Power Conf., 2001.
• 26: The Analysis and Optimization of Collective Communications on a Beowulf Cluster, Proceedings of the 9th International Conference on Parallel and Distributed Systems, p.659, December 17-20, 2002
• 27: R. Thackera, G. Pringleb, H. M. P. Couchmana, and S. Boothb. HYDRA-MPI: An adaptive particle-particle, particle-mesh code for conducting cosmological simulations on MPP architectures. In Proc. Intl. Symp. High Performance Computing Systems and Applications, 2003.
• 28: T. Umeda, Y. Omura, T. Tominaga, and H. Matsumoto. A new charge conservation method in electro-magnetic particle-in-cell simulations. Computer Physics Communications, 156:73--85, 2003.
• 29: H. Usui et al. Development and application of geo-space environment simulator for the analysis of spacecraft-plasma interactions. IEEE Trans. Plasma Science, 34(5):2094--2102, 2006.
• 30: D. W. Walker. The implementation of a three dimensional PIC code on a Hypercube concurrent processor. In Proc. 4th Conf. Hypercube Concurrent Computers and Applications, 1989.
• 31: D. W. Walker. Particle-in-cell plasma simulation codes on the Connection Machine. Computer Systems in Engineering, 2(2--3):307--319, 1991.
• 32: F. Wolfheimer, E. Gjonaj, and T. Weiland. A parallel 3D particle-in-cell code with dynamic load balancing. Nuclear Instruments and Methods in Physics Research, A-558:202--204, 2006.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING

General Terms:
Algorithms

Keywords:
load balancing, particle-in-cell simulation, scalable parallelization