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

Author

Jeffrey Michael Constantin

Date of Award

8-1995

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Michael W. Berry

Committee Members

David W. Straight, Brad Vander Zanden

Abstract

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.

Recommended Citation

Constantin, Jeffrey Michael, "A parallel implementation of the Hoshen-Koppelman Algorithm using a finite state machine. " Master's Thesis, University of Tennessee, 1995.
https://trace.tennessee.edu/utk_gradthes/11082