Efficient irregular wavefront propagation algorithms on hybrid CPU-GPU machines

George Teodoro*, Tony Pan, Tahsin M. Kurc, Jun Kong, Lee Alex Donald Cooper, Joel H. Saltz

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

29 Scopus citations


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. Wedevelop and evaluate strategies for efficient computation and propagation of wavefronts using a multilevel 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 three GPUs and two 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.

Original languageEnglish (US)
Pages (from-to)189-211
Number of pages23
JournalParallel Computing
Issue number4-5
StatePublished - 2013


  • Cooperative CPU-GPU execution
  • Euclidean distance transform
  • Heterogeneous environments
  • Irregular wavefront propagation pattern
  • Morphological reconstruction

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Efficient irregular wavefront propagation algorithms on hybrid CPU-GPU machines'. Together they form a unique fingerprint.

Cite this