Load-Balanced Parallel Streamline Generation on Large Scale Vector Fields
Load-Balanced Parallel Streamline Generation on Large Scale Vector Fields
复制标题
DOI：
10.1109/tvcg.2011.219
复制
发表时间：
2011-12
影响因子：
5.2
通讯作者：
B. Nouanesengsy;Teng-Yok Lee;Han-Wei Shen
中科院分区：
文献类型：
--
作者：
B. Nouanesengsy;Teng-Yok Lee;Han-Wei Shen
由于科学模拟输出数据的规模不断增大，人们越来越依赖超级计算机来生成可视化效果。超级计算机的一个用途是从大规模的流场中产生场线。当并行生成场线时，矢量场通常被分解成块，然后将这些块分配给处理器。由于矢量场的不同区域可能具有不同的流复杂性，处理器将需要不同数量的计算时间来跟踪其粒子，从而导致负载不平衡，从而限制性能加速比。为了实现负载均衡的流水线生成，我们提出了一种基于负载感知的划分算法，将向量场分解成工作负载接近相等的分区。由于实际的工作量是事先未知的，我们提出了一种在局部向量场中预测工作量的工作量估计算法。使用矢量场的基于图形的表示来生成这些估计。一旦估计了工作负载，我们的分区算法就会被分层应用，以将工作负载分配给所有分区。我们在几个计时研究中测试了我们的工作负载估计和工作负载感知分区算法的性能，结果表明，通过使用这些方法，可以在很小的开销下获得更好的可扩展性。
Because of the ever increasing size of output data from scientific simulations, supercomputers are increasingly relied upon to generate visualizations. One use of supercomputers is to generate field lines from large scale flow fields. When generating field lines in parallel, the vector field is generally decomposed into blocks, which are then assigned to processors. Since various regions of the vector field can have different flow complexity, processors will require varying amounts of computation time to trace their particles, causing load imbalance, and thus limiting the performance speedup. To achieve load-balanced streamline generation, we propose a workload-aware partitioning algorithm to decompose the vector field into partitions with near equal workloads. Since actual workloads are unknown beforehand, we propose a workload estimation algorithm to predict the workload in the local vector field. A graph-based representation of the vector field is employed to generate these estimates. Once the workloads have been estimated, our partitioning algorithm is hierarchically applied to distribute the workload to all partitions. We examine the performance of our workload estimation and workload-aware partitioning algorithm in several timings studies, which demonstrates that by employing these methods, better scalability can be achieved with little overhead.