Parallel clustering algorithms for structured AMR

We compare several different parallel implementation approaches for the clustering operations performed during adaptive meshing operations in patch-based structured adaptive mesh refinement (SAMR) applications. Specifically, we target the clustering algorithm of Berger and Rigoutsos. which is commonly used in many SAMR applications. The baseline for comparison is a single program, multiple data extension of the original algorithm that works well for up to O(10(2)) processors. Our goal is a clustering algorithm for machines of up to O(10(5)) processors, such as the 64K-processor IBM BlueGene/L (BG/L) system. We first present an algorithm that avoids unneeded communications of the baseline approach, improving the clustering speed by up to an order of magnitude. We then present a new task-parallel implementation to further reduce communication wait time, adding another order of magnitude of improvement. The new algorithms exhibit more favorable scaling behavior for our test problems. Performance is evaluated on a number of large-scale parallel computer systems, including a 16K-processor BG/L system. (C) 2006 Elsevier Inc. All rights reserved.