Cooperative and out-of-core execution of the irregular wavefront propagation pattern on hybrid machines with Intel((R)) Xeon Phi

• Type of Material: Article
• Authors: Jeremias Gomes, University of Brasilia; Alba C. M. A. de Melo, University of Brasilia; Jun Kong, Emory University; Tahsin Kurc, Stony Brook University; Joel H. Saltz, Stony Brook University; George Teodoro, University of Brasilia
• Language: English
• Date: 2018-07-25
• Publisher: Wiley: 12 months
• Publication Version: Author Accepted Manuscript (After Peer Review)
• Copyright Statement: Copyright © 2018 John Wiley & Sons, Ltd.
• Final Published Version (URL): http://dx.doi.org/10.1002/cpe.4425
• Title of Journal or Parent Work: Concurrency and Computation: Practice and Experience
• ISSN: 1532-0626
• Volume: 30
• Issue: 14
• Start Page: e4425
• End Page: e4425
• Grant/Funding Information: National Cancer Institute (NCI), Grant/Award Number: 1U24CA180924-01A1; U.S. National Library of Medicine (NLM), Grant/Award Number: R01LM011119-01, and R01LM009239; Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq); Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES); National Institutes of Health (NIH), Grant/Award Number: K25CA181503; XSEDE Science Gateways, Grant/Award Number: TG-ASC130023
• Keywords: Computer Science, Software Engineering; RECONSTRUCTION; EFFICIENT; Morphological Reconstruction; Intel((R)) Xeon Phi; Irregular Algorithm Propagation Pattern; Science & Technology; Computer Science, Theory & Methods; Computer Science; Fill Holes; Technology
• Research Categories: Computer Science; Biology, Bioinformatics

Abstract

The Irregular Wavefront Propagation Pattern (IWPP) is a core computing structure in several image analysis operations. Efficient implementation of IWPP on the Intel Xeon Phi is difficult because of the irregular data access and computation characteristics. The traditional IWPP algorithm relies on atomic instructions, which are not available in the SIMD set of the Intel Phi. To overcome this limitation, we have proposed a new IWPP algorithm that can take advantage of non-atomic SIMD instructions supported on the Intel Xeon Phi. We have also developed and evaluated methods to use CPU and Intel Phi cooperatively for parallel execution of the IWPP algorithms. Our new cooperative IWPP version is also able to handle large out-of-core images that would not fit into the memory of the accelerator. The new IWPP algorithm is used to implement the Morphological Reconstruction and Fill Holes operations, which are operations commonly found in image analysis applications. The vectorization implemented with the new IWPP has attained improvements of up to about 5× on top of the original IWPP and significant gains as compared to state-of-the-art the CPU and GPU versions. The new version running on an Intel Phi is 6.21× and 3.14× faster than running on a 16-core CPU and on a GPU, respectively. Finally, the cooperative execution using two Intel Phi devices and a multi-core CPU has reached performance gains of 2.14× as compared to the execution using a single Intel Xeon Phi.