title: Efficient Irregular Wavefront Propagation Algorithms on Hybrid CPU-GPU Machines.
abstract: We address the problem of efficient execution of a computation pattern, referred to here as the irregular wavefront propagation pattern (IWPP), on hybrid systems with multiple CPUs and GPUs. The IWPP is common in several image processing operations. In the IWPP, data elements in the wavefront propagate waves to their neighboring elements on a grid if a propagation condition is satisfied. Elements receiving the propagated waves become part of the wavefront. This pattern results in irregular data accesses and computations. We develop and evaluate strategies for efficient computation and propagation of wavefronts using a multi-level queue structure. This queue structure improves the utilization of fast memories in a GPU and reduces synchronization overheads. We also develop a tile-based parallelization strategy to support execution on multiple CPUs and GPUs. We evaluate our approaches on a state-of-the-art GPU accelerated machine (equipped with 3 GPUs and 2 multicore CPUs) using the IWPP implementations of two widely used image processing operations: morphological reconstruction and euclidean distance transform. Our results show significant performance improvements on GPUs. The use of multiple CPUs and GPUs cooperatively attains speedups of 50× and 85× with respect to single core CPU executions for morphological reconstruction and euclidean distance transform, respectively.
authors.affiliation: Center for Comprehensive Informatics and Biomedical Informatics Department, Emory University, Atlanta, GA 30322.
authors.forename: George
authors.initials: G
authors.lastname: Teodoro
authors.forename: Tony
authors.initials: T
authors.lastname: Pan
authors.forename: Tahsin
authors.initials: T
authors.lastname: Kurc
authors.forename: Jun
authors.initials: J
authors.lastname: Kong
authors.forename: Lee
authors.initials: L
authors.lastname: Cooper
authors.forename: Joel
authors.initials: J
authors.lastname: Saltz
keywords: Cooperative CPU-GPU Execution; Euclidean Distance Transform; GPGPU; Heterogeneous Environments; Irregular Wavefront Propagation Pattern; Morphological Reconstruction
references.citation: IEEE Trans Image Process. 2004 Aug;13(8):1078-91
references.pmid: 15326850
references.citation: IEEE Trans Image Process. 1993;2(2):176-201
references.pmid: 18296207
references.citation: Proc IPDPS (Conf). 2012 May;2012:1093-1104
references.pmid: 25419545