Objective: To determine the most efficient algorithms for performing the indirect addressing data movement within a Particle-in-Cell (PIC) code on the MasPar MP-2. PIC codes are commonly used to model plasmas and gravitational N-body systems.
Approach: Three different algorithms were tested. The first emphasized uniform computational (not necessarily communication) load balance and ease of programming. The second exploited the speed of the X-Net interprocessor communication network using a particle data migration strategy. The third used sorting and vector scan-add operations on the particle data set to minimize the communication traffic required between the particle and mesh data structures. Algorithm efficiencies were measured as a function of the degree of spatial clustering of the particles (shown at right) and as a function of the total number of particles.
Significance: Previous Single Instruction Multiple Data (SIMD) implementations of PIC have reported serious performance degradation as the particles became more clustered in space, and it has even been suggested that this performance degradation might make the Vlasov-Maxwell method more appropriate than PIC for plasma models on the Thinking Machines Corp. CM-2 (an earlier SIMD architecture). Our results indicate how a hybrid algorithm combining the migration and sort/scan-add strategies can set an upper limit on the performance degradation associated with the spatial clustering of particles.
Status/Plans: A paper has been submitted for publication. A similar study is in progress on the Convex Exemplar.
Points of Contact:
Peter MacNeice
Hughes STX Corp.
macneice@alfven.gsfc.nasa.gov
301-286-2061
Clark Mobarry
Goddard Space Flight Center
mobarry@maxwell.gsfc.nasa.gov
301-286-2081
Kevin Olson
George Mason University
olson@jeans.gsfc.nasa.gov
301-286-8707