Tree type numerical algorithms successfully applied in science and engineering

Mannheim, Friday 11th June 1999 To earn the Second prize in the SuParCup, a team from the Rheinische Friedrich-Wilhelms-Universität in Bonn has developed a cost-effective but very efficient load-balancing scheme for hierarchical tree algorithms based on space-filling curves for partial differential equations (PDEs) or N-body problems. The parallel codes were performed on the Parnass2 cluster, consisting of Shared Memory Processor (SMP) PCs and a Myrinet network at Gigabit/s speed configured with full bisection bandwidth.

The team tested the algorithms in two different case studies. The first one constituted an adaptive parallel multi-grid method for the solution of partial differential equations and the second one was a parallel Barnes-Hut/multipole method for the fast evaluation of forces in a molecular dynamics Verlet integrator.

A space-filling curve partitioning heuristic was applied to cope with the issue of load-balancing in the presence of adaptive grid refinement and particle clustering. A comparison with the most recent commercial Cray T3E computer resulted in the demonstration of the competitiveness of the cluster design. Not only Parnass2 is running at a far better price/performance ratio, but the absolute performance figures are stronger.

In the scenario of a fictive budget of DM 1 million, (euro 500.000) the team believes it would be possible to simulate 128 million particles in molecular dynamics with long range potentials or over 30 million degrees of freedom in partial differential equations. Enough to say that the path for cluster computing is wide open.

Leslie Versweyveld