Parallelization of the Hoshen-Kopelman algorithm using a finite state machine

In applications such as landscape ecology, computer modeling is used to assess habitat fragmentation and its ecological implications. Maps (two-dimensional 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 targe 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. Although 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, executed on a Sun SPARCstation 10.