A General Space-filling Curve Algorithm for Partitioning 2D Meshes

This paper describes a recursive algorithm for constructing a generalSpace-Filling Curve (SFC) for an arbitrary distribution of points in2D. We use the SFC to partition 2D meshes, both structured andunstructured, and compare the quality of partitions with traditionalSFCs 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 ofpartitions: volume or load per partition, degree or the number ofdistinct edges of a partition in the communication graph andcommunication volume or the sum of the weights of outgoing edges foreach partition in the communication graph. We propose a performancemodel for modern architectures using these metrics. We find ourpartitions comparable to and in some cases better than the bestmultilevel partitions, while being computed much faster. Unlike Metis, our hierarchical approach yields good hierarchical partitions (e.g., forpartitioning to node and core level), and is appropriate for adaptivemesh refinement kernels.