A Task-parallel Clustering Algorithm for Structured AMR

Gunney, B N ; Wissink, A M

Lawrence Livermore National Laboratory

关键词: Lawrence Livermore National Laboratory;    99 General And Miscellaneous//Mathematics, Computing, And Information Science;    Computers;    Communications;    Algorithms;   

DOI  :  10.2172/15016415
RP-ID  :  UCRL-TR-207651
RP-ID  :  W-7405-ENG-48
RP-ID  :  15016415

美国|英语

来源: UNT Digital Library

【 摘 要 】

A new parallel algorithm, based on the Berger-Rigoutsos algorithm for clustering grid points into logically rectangular regions, is presented. The clustering operation is frequently performed in the dynamic gridding steps of structured adaptive mesh refinement (SAMR) calculations. A previous study revealed that although the cost of clustering is generally insignificant for smaller problems run on relatively few processors, the algorithm scaled inefficiently in parallel and its cost grows with problem size. Hence, it can become significant for large scale problems run on very large parallel machines, such as the new BlueGene system (which has {Omicron}(10{sup 4}) processors). We propose a new task-parallel algorithm designed to reduce communication wait times. Performance was assessed using dynamic SAMR re-gridding operations on up to 16K processors of currently available computers at Lawrence Livermore National Laboratory. The new algorithm was shown to be up to an order of magnitude faster than the baseline algorithm and had better scaling trends.