An improved bi-level algorithm for partitioning dynamic grid hierarchies.

Deiterding, Ralf ; Johansson, Henrik ; Steensland, Johan ; Ray, Jaideep

Sandia National Laboratories

关键词: Classification;    Implementation;    Computerized Simulation;    99 General And Miscellaneous//Mathematics, Computing, And Information Science;    Communications;   

DOI  :  10.2172/884741
RP-ID  :  SAND2006-2487
RP-ID  :  AC04-94AL85000
RP-ID  :  884741

美国|英语

来源: UNT Digital Library

【 摘 要 】

Structured adaptive mesh refinement methods are being widely used for computer simulations of various physical phenomena. Parallel implementations potentially offer realistic simulations of complex three-dimensional applications. But achieving good scalability for large-scale applications is non-trivial. Performance is limited by the partitioner's ability to efficiently use the underlying parallel computer's resources. Designed on sound SAMR principles, Nature+Fable is a hybrid, dedicated SAMR partitioning tool that brings together the advantages of both domain-based and patch-based techniques while avoiding their drawbacks. But the original bi-level partitioning approach in Nature+Fable is insufficient as it for realistic applications regards frequently occurring bi-levels as ''impossible'' and fails. This document describes an improved bi-level partitioning algorithm that successfully copes with all possible bi-levels. The improved algorithm uses the original approach side-by-side with a new, complementing approach. By using a new, customized classification method, the improved algorithm switches automatically between the two approaches. This document describes the algorithms, discusses implementation issues, and presents experimental results. The improved version of Nature+Fable was found to be able to handle realistic applications and also to generate less imbalances, similar box count, but more communication as compared to the native, domain-based partitioner in the SAMR framework AMROC.