PARA'04 State-of-the-Art
in Scientific Computing
June 20-23, 2004 (Home page)
Updated: 17 April 2004

A run-time load balancing algorithm for object based distributed particle simulation

M.F. Dixon
Heuchera Technologies, UK
email: matthew.dixon@imperial.ac.uk

Abstract: This research investigates optimal dynamic load rebalancing algorithms for distributed particle simulation using the POOMA framework developed at Los Alamos. Under this framework, particle allocation is separated into two levels, namely allocation of particles to virtual nodes, by particle position, and allocation of virtual nodes to processors. The current framework enables balancing of particles between virtual nodes but does not allocate virtual nodes to processors using the dynamic properties of processor and network such as available CPU capacity.

A new algorithm is proposed for optimal dynamic load balancing in the POOMA framework using run-time information. Particles are allocated to virtual nodes based on their proximity to each other. Virtual nodes are then allocated to each processor based on the runtime cpu capacity of each processor. The load balance is then re-performed after an appropriate number of time steps.

Parallel scalability results are provided from a $3D$ particle elastic collision particle simulation on a $32$ quad-processor $833$MHZ Compaq Alpha cluster connected by a gigabit ethernet with Quadrics interconnects.

Home page