Paper Info
Title
Dynamic Load Balancing Based On Constrained K-D Tree Decomposition For Parallel Particle Tracing
Abstract
We propose a dynamically load-balanced algorithm for parallel particle tracing, which periodically attempts to evenly redistribute particles across processes based on k-d tree decomposition. Each process is assigned with (1) a statically partitioned, axis-aligned data block that partially overlaps with neighboring blocks in other processes and (2) a dynamically determined k-d tree leaf node that bounds the active particles for computation; the bounds of the k-d tree nodes are constrained by the geometries of data blocks. Given a certain degree of overlap between blocks, our method can balance the number of particles as much as possible. Compared with other load-balancing algorithms for parallel particle tracing, the proposed method does not require any preanalysis, does not use any heuristics based on flow features, does not make any assumptions about seed distribution, does not move any data blocks during the run, and does not need any master process for work redistribution. Based on a comprehensive performance study up to 8K processes on a Blue Gene/Q system, the proposed algorithm outperforms baseline approaches in both load balance and scalability on various flow visualization and analysis problems.
Year
DOI
Venue
2018
10.1109/TVCG.2017.2744059
IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS
Keywords
Field
DocType
Parallel particle tracing, dynamic load balancing, k-d trees, performance analysis
Load management,Algorithm design,Load balancing (computing),Computer science,Tree decomposition,Parallel computing,Tree (data structure),k-d tree,Block (data storage),Scalability
Journal
Volume
Issue
ISSN
24
1
1077-2626
Citations 
PageRank 
References 
2
0.38
29
Authors
5
Name
Order
Citations
PageRank
Jiang Zhang1303.36
Hanqi Guo233823.06
Fan Hong3404.32
Xiaoru Yuan4115770.28
Tom Peterka553149.78