Title :
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
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;
Conference_Titel :
Scalable High-Performance Computing Conference, 1994., Proceedings of the
Conference_Location :
Knoxville, TN
Print_ISBN :
0-8186-5680-8
DOI :
10.1109/SHPCC.1994.296649
