Argonne National Laboratory

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

TitleDynamic Load Balancing Based on Constrained K-D Tree Decomposition for Parallel Particle Tracing
Publication TypeJournal Article
Year of Publication2017
AuthorsZhang, J, Guo, H, Yuan, X, Hong, F, Peterka, T
JournalIEEE Transactions on Visualization and Computer Graphics
Date Published108/2017
Other NumbersANL/MCS-P7034-0417
AbstractParticle tracing is a fundamental technique in flow field data visualization. In this work, we present a novel dynamic load balancing method for parallel particle tracing. Specifically, we employ a constrained k-d tree decomposition approach to dynamically redistribute tasks among processes. Each process is initially assigned a regularly partitioned block along with duplicated ghost layer under the memory limit. During particle tracing, the k-d tree decomposition is dynamically performed by constraining the cutting planes in the overlap range of duplicated data. This ensures that each process is reassigned particles as even as possible, and on the other hand the new assigned particles for a process always locate in its block. Result shows good load balance and high efficiency of our method.  
URLhttp://ieeexplore.ieee.org/document/8017633/
DOI10.1109/TVCG.2017.2744059
PDFhttp://www.mcs.anl.gov/papers/P7034-0417.pdf