A General Space-filling Curve Algorithm for Partitioning 2D Meshes
A General Space-filling Curve Algorithm for Partitioning 2D Meshes
复制标题
一种用于划分二维网格的通用空间填充曲线算法
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Snir
中科院分区：
文献类型：
--
作者：
Aparna Sasidharan;J. Dennis;M. Snir
本文描述了一种递归算法，用于为二维点的任意分布构建通用空间填充曲线（SFC）。我们使用 SFC 对结构化和非结构化的二维网格进行划分，并将划分质量与传统 SFC 以及 Metis 和 Scotch 的多层划分方案进行比较。该算法独立于网格的几何形状，并且可以轻松适应不规则的网格。我们讨论了科学模拟中 SFC 相对于网格多级分区器的优势。我们定义了三个性能指标来合理比较分区：每个分区的容量或负载、通信图中分区的不同边的程度或数量以及通信图中每个分区的通信量或传出边的权重总和。我们使用这些指标为现代架构提出了一个性能模型。我们发现我们的分区与最好的多级分区相当，并且在某些情况下比最好的多级分区更好，同时计算速度更快。与 Metis 不同，我们的分层方法产生良好的分层分区（例如，用于分区到节点和核心级别），并且适用于自适应网格细化内核。
This paper describes a recursive algorithm for constructing a general Space-Filling Curve (SFC) for an arbitrary distribution of points in 2D. We use the SFC to partition 2D meshes, both structured and unstructured, and compare the quality of partitions with traditional SFCs and the multilevel partitioning schemes of Metis and Scotch. The algorithm is independent of the geometry of the mesh and can be easily adapted to irregular meshes. We discuss the advantages of SFCs over multilevel partitioners for meshes in scientific simulations. We define three performance metrics for a reasonable comparison of partitions: volume or load per partition, degree or the number of distinct edges of a partition in the communication graph and communication volume or the sum of the weights of outgoing edges for each partition in the communication graph. We propose a performance model for modern architectures using these metrics. We find our partitions comparable to and in some cases better than the best multilevel partitions, while being computed much faster. Unlike Metis, our hierarchical approach yields good hierarchical partitions (e.g., for partitioning to node and core level), and is appropriate for adaptive mesh refinement kernels.