Cluster identification on a distributed memory multiprocessor

Author

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

Author_Institution

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

fYear

1994

fDate

23-25 May 1994

Firstpage

239

Lastpage

246

Abstract

The cluster identification step is often the bottleneck in multiprocessor simulations of spin models for statistical mechanics. We have applied a connected component labeling algorithm originally developed for VLSI circuit extraction to the cluster identification problem. The algorithm is extended to more than two dimensions, abstracting away unnecessary spatial information to simplify implementation in higher dimensions. We identify two types of spatial locality in cluster configurations, and present optimizations to exploit each type of locality. Performance results are presented from two and three-dimensional Ising model simulations

Keywords

Ising model; distributed memory systems; pattern recognition; physics; physics computing; statistical mechanics; VLSI circuit extraction; cluster configurations; cluster identification; connected component labeling algorithm; distributed memory multiprocessor; multiprocessor simulations; spatial information; spatial locality; spin models; statistical mechanics; three-dimensional Ising model simulations; Circuit simulation; Clustering algorithms; Computational modeling; Computer science; Computer simulation; Concurrent computing; Labeling; Lattices; Physics; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Scalable High-Performance Computing Conference, 1994., Proceedings of the

Conference_Location

Knoxville, TN

Print_ISBN

0-8186-5680-8

Type

conf

DOI

10.1109/SHPCC.1994.296649

Filename

296649