Dynamic Load Balancing Based on Constrained K-D Tree Decomposition for Parallel Particle Tracing.

Area of Science:

• Scientific Visualization
• High-Performance Computing
• Computational Science

Background:

• Parallel particle tracing is crucial for scientific visualization and analysis.
• Existing load-balancing methods often require pre-analysis or heuristics, limiting their applicability.
• Efficiently distributing computational tasks across numerous processors remains a challenge.

Purpose of the Study:

• To introduce a novel dynamically load-balanced algorithm for parallel particle tracing.
• To improve the efficiency and scalability of particle tracing on large-scale parallel systems.
• To overcome limitations of existing load-balancing techniques in particle tracing.

Main Methods:

• The algorithm employs k-d tree decomposition for dynamic particle redistribution.
• Each process manages a data block with overlapping neighbors and a k-d tree leaf node for active particles.
• Particle distribution is balanced based on k-d tree leaf node bounds constrained by data block geometries.

Main Results:

• The proposed method achieves significant improvements in load balance and scalability.
• Performance was validated on a Blue Gene/Q system up to 8,192 processes.
• The algorithm demonstrated superior results compared to baseline approaches across various applications.

Conclusions:

• The dynamically load-balanced algorithm offers an effective solution for parallel particle tracing.
• It provides a robust and scalable approach without relying on pre-analysis or flow-specific heuristics.
• This method enhances the feasibility of large-scale flow visualization and analysis.