Parallelization of the Hoshen-Kopelman Algorithm Using a Finite State Machine

Jeffrey M. Constantin,
Michael W. Berry,
Bradley T. VanderZanden
Department of Computer Science,
107 Ayres Hall,
University of Tennessee,
Knoxville, TN 37996-1301,
constant@cs.utk.edu
berry@cs.utk.edu
bvz@cs.utk.edu

• Abstract
• Introduction
  • Objectives/Overview
  • Input File Format: ERDAS/Lan
• 1. Hoshen-Kopelman Algorithm
  • 1.1 Pre-Processing the ERDAS/Lan Maps
  • 1.2 Data Structures
  • 1.3 Neighborhood Rule
  • 1.4 Implementing the Hoshen-Kopelman Algorithm
  • 1.5 Finite State Machine Implementation
    • 1.5.1 Temporary Label Determination
    • 1.5.2 Search Path Compression
  • 1.6 The Finite State Machine
• 2. Performance Methodology
  • 2.1 Computing Environment
  • 2.2 Performance Methodology
    • 2.2.1 Algorithm Selection
    • 2.2.2 Algorithm Verification
    • 2.2.3 Sequential Implementation
    • 2.2.4 Parallel Implementation
• 3. Performance Results
  • 3.1 Comparison Maps
  • 3.2 Sequential Performance Results
  • 3.3 Parallel Performance Results
• 4. Summary and Future Work
• Acknowledgement
• Biographies
• References
• About this document ...