Efficient Irregular Wavefront Propagation Algorithms on Hybrid CPU-GPU Machines.

Area of Science:

• Computer Science
• Image Processing
• High-Performance Computing

Background:

• Irregular wavefront propagation patterns (IWPP) are common in image processing but challenging for efficient execution on modern hybrid systems.
• Existing methods struggle with irregular data access and computations inherent in IWPP, leading to underutilization of parallel hardware.
• Hybrid architectures combining CPUs and GPUs offer potential for acceleration but require specialized strategies for IWPP.

Purpose of the Study:

• To develop and evaluate efficient strategies for executing the irregular wavefront propagation pattern (IWPP) on hybrid CPU-GPU systems.
• To optimize wavefront computation and propagation using novel data structures and parallelization techniques.
• To demonstrate performance improvements on real-world image processing applications.

Main Methods:

• Developed a multi-level queue structure to enhance GPU memory utilization and reduce synchronization overheads during wavefront propagation.
• Implemented a tile-based parallelization strategy for cooperative execution across multiple CPUs and GPUs.
• Evaluated the approach on a hybrid system using morphological reconstruction and Euclidean distance transform as IWPP benchmarks.

Main Results:

• Achieved significant performance improvements on GPUs for IWPP.
• Demonstrated cooperative execution on multiple CPUs and GPUs, yielding speedups of 50x for morphological reconstruction and 85x for Euclidean distance transform compared to single-core CPU execution.
• The multi-level queue and tile-based strategies effectively managed irregular data accesses and computations.

Conclusions:

• The proposed methods provide an efficient solution for executing irregular wavefront propagation patterns on hybrid CPU-GPU systems.
• The developed strategies significantly accelerate critical image processing operations, showcasing the benefits of optimized parallel execution.
• This work contributes to advancing high-performance computing for complex image analysis tasks.