Characterization of a Split-C Barnes-Hut Implementation on the CM-5

Eric Anderson <eanders@cs>
Todd Hodes <hodes@cs>

This work was supported, in part, by National Science Foundation Infrastructure Grant number CDA-8722788 and the California MICRO fellowship program.

An example spherical distribution and its evolution

Abstract:

Herein we present some of the results obtained from our implementation of Barnes-Hut in Split-C, as measured on the CM-5. First, we describe our implementation. Then, we compare some characteristics of the two different tree-building algorithms utilized, such as speed-up, maximum problem size, and running-time dependence on problem size. Additionally, we mention some of the inherent performance characteristics of Split-C that we discovered along the way. We then mention some of the communication characteristics of the program. Finally, we lead the reader on a visual journey through the lifetimes of ``galaxy'' models with varying initial distributions, as generated by our program.

This work was done in conjunction with Prof. Culler's class on Parallel Computer Architecture in the Computer Science division of the University of California, Berkeley.

Index:

  • Introduction
  • Motivation
  • Space-Separated Tree Building
  • Calculation of Cell and Body Interactions
  • Caching
  • Load-Balancing
  • Results
  • Conclusions

  • Part II Proposal

    • Galaxy Evolution:

    We have made graphical tours of the lifetimes of some standard body distributions available. They include:

    We also have MPEG movies of the plummer evolution available:

    References:

    [1] D. Culler, A. Dusseau, S. Goldstein, A. Krishnamurthy, S. Lumetta, T. v. Eicken, K. Yelick, ``Parallel Programming in Split-C''

    [2] D. Culler, A. Dusseau, S. Goldstein, A. Krishnamurthy, S. Lumetta, S. Luna, T. v. Eicken, K. Yelick, ``Introduction to Split-C''

    [3] M. Franklin, V. Govindan, The N-body Problem: Distributed Load Balancing and Performance Evaluation, Washington University Technical Report

    [4] Y. Hu, S. Johnson, A Data Parallel Implementation of Hierarchical N-Body Methods, Harvard Technical Report #TR-26-94

    [5] Methodological Considerations and Characterization of the SPLASH-2 Parallel Applications Suite, Stanford University Computer Systems Lab Draft

    [6] J.P. Singh, Parallel Hierarchical N-body Methods and their Implications for Multiprocessors, Ph.D. Thesis, Stanford University.

    [7] J.P. Singh, J. Hennessey, A. Gupta, ``Implications of Hierarchical N-body Methods for Multiprocessor Architecture,'' ACM Transactions on Computer Systems.

    [8] J.P. Singh, C. Holt, T. Totsuka, A. Gupta, J. Hennessy, ``Load Balancing and Data Locality in Adaptive Hierarchical N-body Methods,'' Journal of Parallel and Distributed Computing.

    [9] J.P. Singh W.-D. Weber, A. Gupta, ``SPLASH: Stanford Parallel Applications for Shared Memory,'' Computer Architecture News, 20(1):5-44, 1992.

    [10] M.S. Warren, J.K. Salmon, ``A Parallel Hashed Oct-Tree N-body Algorithm,'' Proceedings of Supercomputing '93, pp. 12-21, Nov. 1993.

    [11] M.S. Warren, J.K. Salmon, ``Astrophysical N-body Simulations Using Hierarchical Tree Data Structures,'' Proceedings of Supercomputing '92, Sept. 1992.

    [12] J.K. Salmon, M.S. Warren, G. S. Winckelmans, ``Fast Parallel Tree Codes for Gravitational and Fluid Dynamical N-Body Problems,'' International Journal of Supercomputer Applications, Vol 8.2.

    [13] J.K. Salmon, M.S. Warren, ``Skeletons from the Treecode Closet,'' Journal of Computational Physics, July 1992.

    -----

    maintained by <hodes@cs.berkeley.edu>