Parallel cluster identification for multidimensional lattices

Author

Fink, Stephen J. ; Huston, Craig ; Baden, Scott B. ; Jansen, Karl

Author_Institution

Dept. of Comput. Sci. & Eng., California Univ., San Diego, La Jolla, CA, USA

Volume

8

Issue

11

fYear

1997

fDate

11/1/1997 12:00:00 AM

Firstpage

1089

Lastpage

1097

Abstract

The cluster identification problem is a variant of connected component labeling that arises in cluster algorithms for spin models in statistical physics. We present a multidimensional version of K.P. Belkhale and P. Banerjee´s quad algorithm (1992) for connected component labeling on distributed memory parallel computers. Our extension abstracts away extraneous spatial connectivity information in more than two dimensions, simplifying implementation for higher dimensionality. We identify two types of locality present in cluster configurations, and present optimizations to exploit locality for better performance. Performance results from 2D, 3D, and 4D Ising model simulations with Swendson-Wang dynamics show that the optimizations improve performance by 20-80 percent

Keywords

Ising model; distributed memory systems; parallel algorithms; physics computing; Ising model simulations; Swendson-Wang dynamics; cluster algorithms; connected component labeling; distributed memory parallel computers; multidimensional lattices; parallel cluster identification; performance; spatial connectivity information; spin models; statistical physics; Abstracts; Clustering algorithms; Computational modeling; Concurrent computing; Distributed computing; Labeling; Lattices; Multidimensional systems; Parallel algorithms; Physics;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.642944

Filename

642944