PARALLEL IMAGE CORRELATION - CASE-STUDY TO EXAMINE TRADE-OFFS IN ALGORITHM-TO-MACHINE MAPPINGS

Performance of a parallel algorithm on a parallel machine depends not only on the time complexity of the algorithm, but also on how the unde rlying machine supports the fundamental operations used by the algorit hm. This study analyzes various mappings of image correlation algorith ms in SIMD, MIMD, and mixed-mode environments. Experiments were conduc ted on the Intel Paragon, MasPar MP-I, nCUBE 2, and PASM prototype. Th e machine features considered in this study include: modes of parallel ism, communication/computation ratio, network topology and implementat ion, SIMD CU/PE overlap, and communication/computation overlap. Perfor mance of an implementation can be enhanced by using algorithmic techni ques that match the machine features. Some algorithmic techniques disc ussed here are additional communication versus redundant computation, data block transfers, and communication/computation overlap. The resul ts presented are applicable to a large class of image processing tasks . Case studies, such as the one presented here, are a necessary step i n developing software tools for mapping an application task onto a sin gle parallel machine and for mapping the subtasks of an application ta sk, or a set of independent application tasks, onto a heterogeneous su ite of parallel machines.