标题： 强非均匀模拟中的负载均衡——Vlasiator案例研究 显示英文标题

标题： Load Balancing in Strongly Inhomogeneous Simulations -- a Vlasiator Case Study

摘要： 由于需要处理的数据量巨大，大规模模拟需要并行化。本文以Vlasiator（一种全球磁层模拟）作为案例研究，探讨了不同的负载均衡方法。负载均衡的理论基础是（超）图划分问题，即将模拟单元建模为顶点，数据依赖性建模为边。由于这是一个NP难问题，因此动态运行时平衡需要启发式算法。我们首先通过一种称为并行超图划分器(PHG)的算法进行超图划分；这是通过对简化网格进行划分，然后尝试在更精细的网格上优化解决方案来实现的。第二种和第三种方法分别是递归坐标二分法(RCB)和递归惯性二分法(RIB)的几何方法。最后，我们考虑希尔伯特空间填充曲线(HSFC)的方法。该算法沿希尔伯特曲线投影模拟单元，并沿着曲线进行分割。由于希尔伯特曲线具有极好的局部性，这种方法效果很好，并且可以通过选择曲线进一步优化。我们总共引入并研究了六种三维希尔伯特曲线。我们的测试结果表明，HSFC方法提供了最佳的负载均衡，其次是RIB和PHG方法，最后是RCB方法。在评估的希尔伯特曲线中，Beta曲线比最常用的曲线性能高出几个百分点。 显示英文摘要

摘要： Parallelization is a necessity for large-scale simulations due to the amount of data processed. In this article we investigate different load balancing methods using Vlasiator, a global magnetospheric simulation as our case study. The theoretical basis for load balancing is the (hyper)graph partitioning problem, modeling simulation units as vertices and their data dependencies as edges. As it is an NP-hard problem, heuristics are necessary for dynamic runtime balancing. We consider first hypergraph partitioning via an algorithm called parallel hypergraph partitioner (PHG); this is done by partitioning a simplified grid and then attempting to optimize the solution on the finer grid. The second and third are the geometric methods of recursive coordinate bisection (RCB) and recursive inertial bisection (RIB). Finally we consider the method of Hilbert space filling curves (HSFC). The algorithm projects simulation cells along a Hilbert curve and makes cuts along the curve. This works well due to the excellent locality of Hilbert curves, and can be optimized further by choice of curve. We introduce and investigate six three-dimensional Hilbert curves in total. Our findings on runs of two different scales indicate the HSFC method provides optimal load balance, followed by RIB and PHG methods and finally by RCB. Of the Hilbert curves evaluated, the Beta curve outperformed the most commonly used curve by a few percent.