next up previous
Next: Input File Format: Up: Introduction Previous: Introduction


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 (
Sat Mar 30 23:40:13 EST 1996