Efficient Irregular Wavefront Propagation Algorithms on Intel(R) Xeon Phi(TM)

• Jeremias M. Gomes UnB
• George Teodoro UnB
• Alba De Melo UnB
• Jun Kong Emory University
• Tahsin Kurc Stony Brook University
• Joel H. Saltz Stony Brook University

Resumo

We investigate the execution of the Irregular Wave front Propagation Pattern (IWPP), a fundamental computing structure used in several image analysis operations, on the Intel® Xeon PhiTM co-processor. An efficient implementation of IWPP on the Xeon Phi is a challenging problem because of IWPP's irregularity and the use of atomic instructions in the original IWPP algorithm to resolve race conditions. On the Xeon Phi, the use of SIMD and vectorization instructions is critical to attain high performance. However, SIMD atomic instructions are not supported. Therefore, we propose a new IWPP algorithm that can take advantage of the supported SIMD instruction set. We also evaluate an alternate storage container (priority queue) to track active elements in the wave front in an effort to improve the parallel algorithm efficiency. The new IWPP algorithm is evaluated with Morphological Reconstruction and Imfill operations as use cases. Our results show performance improvements of up to 5.63× on top of the original IWPP due to vectorization. Moreover, the new IWPP achieves speedups of 45.7× and 1.62×, respectively, as compared to efficient CPU and GPU implementations.

Palavras-chave: Image reconstruction, Containers, Algorithm design and analysis, Image analysis, Propagation, Pipelines, Image resolution