Preparing for Petascale Computing: A look under the hood of Barnes-Hut

A multitude of opportunities for advancement of science and engineering await the advent of petascale computational facilities. However, it is not clear that future computational physicists will be ready to take full advantage of these capabilities. There is a long-standing gap between our training of physics students in computation in general and high-performance computing in particular. I am offering a sample package to support efforts to change this situation. This is a family of C codes that implement a Barnes-Hut method for calculating inter-particle forces in N-body systems, with particular application to simulating a system of gravitating objects. This family has both 1-D and 3-D codes. The former are several ``toy'' programs documented to clearly expose tactics to build tree structures and actions needed to execute both Barnes-Hut and multipole methods. The latter, based on the former, are for realistic N-body calculations on parallel processors for which I have some results from testing on clusters. I will briefly describe educational use of these materials. I hope these materials will give to practitioners a transparent look at fundamentals of the Barnes-Hut method and to instructors tools for improving students' understanding of scaling issues in large computations.