The objectives of this study are to supply a more efficient sequential
implementation of the Hoshen-Kopelman
(Hoshen and Kopelman, 1976) (HK) cluster
identification algorithm
for 2-dimensional binary maps and to provide an efficient parallel
implementation
for cluster identification on the Thinking Machines CM-5
(Thinking Machines Corp., 1993a).
Optimizing the Hoshen-Kopelman sequential implementation involves the
efficient use
of pointers and local variables which can significantly reduce the time spent
in * base-plus-offset* array indexing and redundant integer comparisons.

The particular file format (ERDAS/Lan) used for test maps
is briefly discussed below. Section 1
discusses the Hoshen-Kopelman
one-pass cluster identification algorithm, the input data set, the programming
data structures, the cluster * neighborhood rule* and the finite state
machine used. The performance methodology used to evaluate
the sequential and parallel implementations and the computing
environment are described in Section 2.
Section 3 demonstrates the sequential and parallel performance
of the FSM implementation, and
Section 4 contains a brief summary and a discussion of
future work.

Michael W. Berry (berry@cs.utk.edu)

Sat Mar 30 23:40:13 EST 1996