PARALLELIZATION OF THE HOSHEN-KOPELMAN-ALGORITHM USING A FINITE-STATEMACHINE

In applications such as landscape ecology, computer modeling is used t o 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, impro ved sequential and parallel implementations of the Hoshen-Kopelman clu ster identification algorithm have been designed. These implementation s use a finite state machine to reduce redundant integer comparisons d uring the cluster identification process. The sequential implementatio n for targe maps performs cluster identification by partitioning the m ap along row boundaries and merging the results of the partitions. The parallel implementation on a 32-processor Thinking Machines CM-5 prov ides an efficient mechanism for performing cluster identification in p arallel. Although the sequential implementation achieved promising spe ed improvements ranging from 1.39 to 2.00 over an existing Hoshen-Kope lman implementation, the parallel implementation achieved a minimum sp eedup of 5.41 over the improved sequential implementation, executed on a Sun SPARCstation 10.