next up previous
Next: Introduction Up: Parallel Hoshen-Kopelman Algorithm Title Page Previous: Parallel Hoshen-Kopelman Algorithm Title


In applications such as landscape ecology, computer modeling is used to assess habitat fragmentation and its ecological implications. Maps (2-D grids) of habitat clusters or patches are analyzed to determine the number, location, and sizes of clusters. Recently, improved sequential and parallel implementations of the Hoshen-Kopelman cluster identification algorithm have been designed. These implementations use a finite state machine to reduce redundant integer comparisons during the cluster identification process. The sequential implementation for large maps performs cluster identification by partitioning the map along row boundaries and merging the results of the partitions. The parallel implementation on a 32-processor Thinking Machines CM--5 provides an efficient mechanism for performing cluster identification in parallel. While the sequential implementation achieved promising speed improvements ranging from 1.39 to 2.00 over an existing Hoshen-Kopelman implementation, the parallel implementation achieved a minimum speedup of 5.41 over the improved sequential implementation executing on a Sun SPARCstation 10.

Keywords: cluster identification, finite state machine, Hoshen-Kopelman algorithm, landscape ecology, parallel processing

Michael W. Berry (
Sat Mar 30 23:40:13 EST 1996