EECS Publication
Parallelization of the Hoshen-Koppelman Algorithm Using a Finite State Machine
Michael W. Berry, Jeff M. Constantin, and Brad Vander Zanden
In applications such as landscape ecology, computermodeling 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 theHoshen-Kopelman cluster identification algorithmhave been designed. These implementations use a finite state machine to reduce redundant integer comparisons during the cluster identification process. The sequential implementation for large-scalemaps performs cluster identification by partitioning themap along row boundaries andmerging the results of the partitions. The parallel implementation on a 32-processor ThinkingMachines CM-5 provides an efficient mechanismfor 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.
Published 1995-08-01 05:00:00 as ut-cs-95-300 (ID:416)