Balancing processor loads and exploiting data locality in N-body simulations

ABSTRACT

Although N-body simulation algorithms are amenable to parallelization, performance gains from execution on parallel machines are difficult to obtain due to load imbalances caused by irregular distributions of bodies. In general, there is a tension between balancing processor loads and maintaining locality, as the dynamic re-assignment of work necessitates access to remote data. Fractiling is a dynamic scheduling scheme that simultaneously balances processor loads and maintains locality by exploiting the self-similarity properties of fractals. Fractiling is based on a probabilistic analysis, and thus, accommodates load imbalances caused by predictable phenomena, such as irregular data, and unpredictable phenomena, such as data-access latencies. In experiments on a KSR1, performance of N-body simulation codes were improved by as much as 53% by fractiling. Performance improvements were obtained on uniform and nonuniform distributions of bodies, underscoring the need for a scheduling scheme that accommodates system induced variance. As the fractiling scheme is orthogonal to the N-body algorithm, we could use simple codes that discretize space into equal-size subrectangles (2-d) or subcubes (3-d) as the base algorithms.

REFERENCES

• 1: A. W. Appel, An Efficient Program for Many-Body Simulations, SIAM Journal of Computing 6, 1985.
• 2: J. Barnes and P. Hutt, A Hierarchical O(N log N) Force Calculation Algorithm, Nature 324, 1986.
• 3: M. J. Berger , S. H. Bokhari, A partitioning strategy for nonuniform problems on multiprocessors, IEEE Transactions on Computers, v.36 n.5, p.570-580, May 1987 [doi>10.1109/TC.1987.1676942]
• 4: J. A. Board, KSR implementation of Greengard's PFMA, email, Oct. 1994.
• 5: J. A. Board, J. W. Causey, J. F. Leathrum, A. Windemuth and K. Schulten, Accelerated Molecular Dynamic Simulations with the Parallel Fast Multipole Algorithm, Chem. Phys. Let. 198, 1992.
• 6: J. A. Board, Z. H. Halura, W. D. Elliot and W. T. Rakin, Scalable Variants of Multipole-based Algorithms for Molecular Dynamics Applications, Proc. of SIAM Conf. on Parallel Processing for Scientific Computing pp 295-300, Feb. 1995.
• 7: M.D. Durand, T. Montaut, L. Kervella and W. Jalby, Impact of Memory Contention on Task Duration in Self-Scheduled Programs, Int. Conf. on Parallel Processing I258-I262, Aug. 1993.
• 8: L. E. Flynn and S. Flynn Hummel, The Mathematical Foundations of the Factoring Scheduling Method, IBM Research Report RC18462, Oct. 1992.
• 9: Susan Flynn Hummel , Edith Schonberg , Lawrence E. Flynn, Factoring: a method for scheduling parallel loops, Communications of the ACM, v.35 n.8, p.90-101, Aug. 1992 [doi>10.1145/135226.135232]
• 10: S. F. Hummel , E. Schonberg, Low-overhead scheduling of nested parallelism, IBM Journal of Research and Development, v.35 n.5-6, p.743-765, Sept./Nov. 1991
• 11: S. Flynn Hummel, D. Kimelman and E. Schonberg, Experience with Program Visualization in Tuning Parallel Loop Scheduling, Proc. of HICSS- 25 pp. II275-II286, Jan. 1992.
• 12: S. Flynn Hummel, Fractiling: A Method for Scheduling Parallel Loops on NUMA Machines, IBM Research Report RC18958, June 1993.
• 13: S. Flynn Hummel, C. Wang, and J. Wein, Simulations of Fractiling in the logP Model, unpublished manuscript, 1994.
• 14: S. Flynn Hummel, I. Banicescu, C. Wang, and J. Wein, On the Scalability of Dynamic Scheduling, to appear in Proc. Third Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, May 1995.
• 15: Ananth Y. Grama , Vipin Kumar , Ahmed Sameh, Scalable parallel formulations of the Barnes-Hut method for n-body simulations, Proceedings of the 1994 conference on Supercomputing, p.439-448, December 1994, Washington, D.C., United States
• 16: D. C. Gray, Load Balancing the Parallel Fast Multipole Algorithm, Duke University Tech Report 94-003, Apr. 1994.
• 17: L. Greengard, The Rapid Evaluation of Potential Fields in Particle Systems, ACM Press, 1987.
• 18: Leslie Greengard , William Gropp, A Parallel Version of the Fast Multipole Method-Invited Talk, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.213-222, December 01-04, 1987
• 19: S. Frank, H. Burkhardt and J. Rothnie, The KSR1: Bridging the Gap between Shared Memory and MMPs, Proc. Compcon '93.
• 20: H. Li, S. Tandri, M. Stumm and K. C. Sevcik, Locality and Loop Scheduling on NUMA Machines, Int. Conf. on Parallel Processing pp. II140--II147, 1993.
• 21: E. P. Markatos , T. J. LeBlanc, Using Processor Affinity in Loop Scheduling on Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.5 n.4, p.379-400, April 1994 [doi>10.1109/71.273046]
• 22: G. M. Morton, A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing, IBM, Ottowa, Canada, 1966.
• 23: C. Polychronopoulos, Loop Coalescing: A Compiler Transformation for Parallel Machines, Int. Conf. on Parallel Processing pp. 235--242, 1987.
• 24: C. D. Polychronopoulos , D. J. Kuck, Guided self-scheduling: A practical scheduling scheme for parallel supercomputers, IEEE Transactions on Computers, v.36 n.12, p.1425-1439, Dec. 1987 [doi>10.1109/TC.1987.5009495]
• 25: K. E. Schmidt and M. A. Lee, Implementing the Fast Multiple Method in Parallel, J. Stat. Phy. 63:1120, 1991.
• 26: J. P. Singh , C. Holt , J. L. Hennessy , A. Gupta, A parallel adaptive fast multipole method, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.54-65, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169651]
• 27: S. Talla, C implementation of Greengard's FMA, email, June 1994.
• 28: C. D. Thompson , H. T. Kung, Sorting on a mesh-connected parallel computer, Communications of the ACM, v.20 n.4, p.263-271, April 1977 [doi>10.1145/359461.359481]
• 29: M. S. Warren , J. K. Salmon, Astrophysical N-body simulations using hierarchical tree data structures, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.570-576, November 16-20, 1992, Minneapolis, Minnesota, United States
• 30: M. S. Warren , J. K. Salmon, A parallel hashed Oct-Tree N-body algorithm, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.12-21, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169640]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Physics

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

General Terms:
Algorithms, Performance

Keywords:
exploiting locality, factoring scheduling, multiprocessor load balancing, N-body simulations, tiling