APRIL 18-21, 2017
Previous Events

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

  • Jiang Zhang
    Peking University, Beijing, China
  • Hanqi Guo
    Argonne National Laboratory, Argonne, Illinois, United States
  • Tom Peterka
    Argonne National Laboratory, Argonne, Illinois, United States
  • Xiaoru Yuan
    Peking University, Beijing, China


Particle 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.