A parallel implementation of the Hoshen-Koppelman Algorithm using a finite state machine

In this thesis, improved sequential and parallel implementations of the Hoshen-Koppelman cluster identification algorithm are presented. The implementations pre-sented use a finite state machine to reduce redundant integer comparisons during the cluster identification process. Sequential efforts concentrated on large-scale maps and an efficient algorithm for performing cluster identification by partitioning the map along row boundaries and merging the results of the partitions. Parallel efforts on the (MIMD) 32-node Thinking Machine CM-5 concentrated on an efficient mecha-nism for performing cluster identification in parallel. The sequential implementation achieved promising speed improvements ranging from 1.39 to 2.00 over an exist-ing Hoshen-Koppelman implementation and the parallel implementation achieved a minimum speedup of 5.41 over the sequential implementation executing on a Sun SPARCstation 10.