Parallel clustering algorithms for structured AMR
| Autor: | David Hysom, Brian T. N. Gunney, Andrew M. Wissink |
|---|---|
| Rok vydání: | 2006 |
| Předmět: |
Computer Networks and Communications
Adaptive mesh refinement Computer science Parallel algorithm Parallel computing Supercomputer Theoretical Computer Science Data stream clustering Artificial Intelligence Hardware and Architecture Asynchronous communication Canopy clustering algorithm Cluster analysis SPMD Algorithm Software |
| Zdroj: | Journal of Parallel and Distributed Computing. 66:1419-1430 |
| ISSN: | 0743-7315 |
| Popis: | 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(102) processors. Our goal is a clustering algorithm for machines of up to O(105) 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect