Scalable Algorithms for Distributed-Memory Adaptive Mesh Refinement

• Akhil Langer University of Illinois
• Jonathan Lifflander University of Illinois
• Phil Miller University of Illinois
• Kuo-Chuan Pan University of Illinois
• Laxmikant V. Kalé University of Illinois
• Paul Ricker University of Illinois

Resumo

This paper presents scalable algorithms and data structures for adaptive mesh refinement computations. We describe a novel mesh restructuring algorithm for adaptive mesh refinement computations that uses a constant number of collectives regardless of the refinement depth. To further increase scalability, we describe a localized hierarchical coordinate-based block indexing scheme in contrast to traditional linear numbering schemes, which incur unnecessary synchronization. In contrast to the existing approaches which take O(P) time and storage per process, our approach takes only constant time and has very small memory footprint. With these optimizations as well as an efficient mapping scheme, our algorithm is scalable and suitable for large, highly-refined meshes. We present strong-scaling experiments up to 2k ranks on Cray XK6, and 32k ranks on IBM Blue Gene/Q.

Palavras-chave: Program processors, Algorithm design and analysis, Synchronization, Runtime, Mathematical model, Benchmark testing, Heuristic algorithms