next up previous
Next: Parallel Performance Results Up: Performance Results Previous: Comparison Maps

3.2 Sequential Performance Results

As stated in the Introduction, the primary objective of the FSM sequential implementation (SI) was to optimize a sequential cluster identification algorithm for a subsequent parallel implementation (PI) on the CM-5. This objective was accomplished by implementing the HK cluster identification algorithm with efficient use of pointers and utilizing a finite state machine to eliminate redundant integer comparison operations. The FSM implementation was compared to the HK implementation in (Berry et al., 1994) and Figure 11 illustrates the execution times for the FSM implementation and that of the original HK implementation in Berry et al. (1994). The reduction in time for the FSM implementation can be attributed to the efficient use of pointers during array indexing, compression of the search path during cluster merge operations, and the use of a finite state machine to reduce redundant integer comparison operations by encapsulating the previous comparison result in a machine state. The FSM implementation achieved a minimum time improvement of 1.39 and a maximum time improvement of 2.00 on the FIRE map. The FORD map was not used for sequential comparisons because the previous implementation in Berry et al. (1994) was designed to handle maps smaller than pixels.



Michael W. Berry (berry@cs.utk.edu)
Sat Mar 30 23:40:13 EST 1996