Parallelize Over Data Particle Advection: Participation, Ping Pong Particles, and Overhead

Area of Science:

• Scientific visualization
• Computational science
• High-performance computing

Background:

• Particle advection is crucial for analyzing vector fields in scientific simulations.
• The Parallelize over Data (POD) algorithm is a standard for its simplicity and reduced data movement.
• Existing literature acknowledges scaling issues with the POD algorithm.

Purpose of the Study:

• To conduct in-depth analyses of the POD algorithm to uncover the root causes of its poor performance.
• To introduce novel metrics for measuring algorithmic efficiency.
• To perform particle-centric analysis to understand performance bottlenecks.

Main Methods:

• Designed representative workloads executed on a supercomputer.
• Collected timing and statistical data for analysis.
• Developed two novel metrics for algorithmic efficiency and employed particle-centric analysis.

Main Results:

• Identified that overheads from particle movement between processes, not communication, heavily impact execution time.
• Discovered that "ping pong particles"—repeated circulation between blocks—are a major performance cost.
• Quantified the impact of flow features spanning multiple blocks on POD algorithm efficiency.

Conclusions:

• The primary performance bottleneck in the POD algorithm stems from particle movement overheads and "ping pong" effects.
• Findings provide critical insights into the limitations of the POD algorithm for large-scale scientific data.
• Results guide future research toward developing more efficient particle advection algorithms.