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 underlying machine supports the fundamental operations used by the algorithm. This study analyzes various mappings of image correlation algorithms in SIMD, MIMD, and mixed-mode environments. Experiments were conducted on the Intel Paragon, MasPar MP-1, nCUBE 2, and PASM prototype. The machine Features considered in this study include: modes of parallelism, communication/computation ratio, network Topology and implementation, SIMD CU/PE overlap, and communication/computation overlap.