A general space-filling curve algorithm for partitioning 2D meshes

Aparna Sasidharan, John M. Dennis, Marc Snir

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages875-879
Number of pages5
ISBN (Electronic)9781479989362
DOIs
StatePublished - Nov 23 2015
Externally publishedYes
Event17th IEEE International Conference on High Performance Computing and Communications, IEEE 7th International Symposium on Cyberspace Safety and Security and IEEE 12th International Conference on Embedded Software and Systems, HPCC-ICESS-CSS 2015 - New York, United States
Duration: Aug 24 2015Aug 26 2015

Publication series

NameProceedings - 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security and 2015 IEEE 12th International Conference on Embedded Software and Systems, HPCC-CSS-ICESS 2015

Other

Other17th IEEE International Conference on High Performance Computing and Communications, IEEE 7th International Symposium on Cyberspace Safety and Security and IEEE 12th International Conference on Embedded Software and Systems, HPCC-ICESS-CSS 2015
CountryUnited States
CityNew York
Period8/24/158/26/15

Keywords

  • Geometric Partitioning
  • Mesh Partitioning
  • Metis
  • Scotch
  • Space-filling Curve

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'A general space-filling curve algorithm for partitioning 2D meshes'. Together they form a unique fingerprint.

Cite this