Model-Based Warp-Level Tiling for Image Processing Programs on GPUs

Abhinav Jangda, Arjun GuhaarXiv 2019 · arXiv

Abstract

Image processing pipelines are essential for applications ranging from mobile photography to autonomous driving. While Domain-Specific Languages (DSLs) like Halide and PolyMage have simplified GPU code generation, they often face performance bottlenecks due to inefficient resource management. This paper presents PolyMage-GPU, a system that optimizes image pipelines by shifting the unit of execution from thread blocks to warps. By integrating warp-level overlapped tiling with a hybrid memory strategy and an analytical cost model, PolyMage-GPU achieves significant performance gains, outperforming manually tuned Halide schedules by up to 1.65×.

Introduction

Modern image processing involves complex multi-stage pipelines. To execute these efficiently on GPUs, compilers typically employ overlapped tiling, which allows independent processing of image regions by performing redundant computations at tile boundaries. However, standard implementations map these tiles to GPU thread blocks, leading to high synchronization overhead and suboptimal memory usage. PolyMage-GPU addresses these challenges by rethinking the granularity of parallel execution and memory allocation.

The Bottleneck of Block-Level Tiling

Traditional block-level tiling suffers from three primary issues:

  1. Synchronization Overhead: Moving between pipeline stages within a thread block requires __syncthreads(), which stalls all warps in the block and leads to hardware underutilization.
  2. Memory vs. Occupancy Trade-off: Large tiles minimize redundant computation but consume excessive shared memory, reducing the number of active warps (occupancy). Conversely, small tiles increase occupancy but incur high computational redundancy.
  3. Simplistic Scheduling: Existing autoschedulers often fail to account for the complexities of global memory transactions and latency hiding on modern GPU architectures.

PolyMage-GPU Innovations

PolyMage-GPU introduces a novel compilation workflow designed to maximize GPU throughput through warp-centric optimizations.

The PolyMage-GPU compilation workflow from DSL specification to CUDA code.

1. Overlap Tile Per Warp (OTPW)

Instead of assigning tiles to thread blocks, PolyMage-GPU assigns one overlapped tile to a single warp (32 threads). This shift allows the use of __syncwarp(), a significantly lighter synchronization primitive. Since warps are the fundamental unit of GPU scheduling, this approach minimizes stalls and keeps the execution units busy.

2. Hybrid Tiling

A key innovation is the hybrid tiling strategy, which optimizes the memory footprint of intermediate data. While traditional methods rely solely on shared memory, PolyMage-GPU stores portions of the tile in thread-local registers.

Hybrid Tiling: Distributing data between shared memory and registers to optimize occupancy.

By utilizing warp shuffle instructions, threads within a warp can share data stored in registers without accessing shared memory. This reduces the shared memory pressure, enabling higher occupancy while maintaining the benefits of larger tile sizes.

3. Model-Based Automatic Fusion

To automate the selection of optimal schedules, the researchers developed a cost model for Dynamic Programming Fusion (DP-Fusion). This model analytically evaluates potential schedules based on global memory transactions, theoretical occupancy, redundant computation fractions, and load balancing across multiprocessors. This approach allows the system to find near-optimal schedules in seconds, whereas traditional autotuners might require hours.

Evaluation and Results

The system was evaluated across six canonical benchmarks, including Unsharp Mask, Harris Corner, and Camera Pipeline, on NVIDIA GTX 1080Ti and Tesla V100 GPUs.

Key findings include:

  • Performance Gains: PolyMage-GPU achieved an average speedup of 1.65× on the 1080Ti and 1.33× on the V100 compared to manually tuned Halide schedules. Against Halide’s autoscheduler, it provided a 2.42× speedup.
  • Occupancy Improvements: The hybrid tiling strategy successfully increased occupancy, notably by 16.6% in the Camera Pipeline benchmark on the V100 architecture.
  • Efficiency: The model-based search for optimal schedules was highly efficient, completing in under 30 seconds even for complex 49-stage pipelines.

Conclusion

PolyMage-GPU demonstrates that shifting the focus of GPU optimizations from the thread block to the warp level can unlock significant performance potential in image processing. By combining warp-level synchronization with a hybrid memory model and an accurate analytical cost model, the system provides a robust framework for generating high-performance GPU code from high-level DSL specifications. Future work will focus on improving handling for complex reductions and expanding the model's flexibility for dynamic dependencies.

Summary updated

Abstract

Domain-specific languages that execute image processing pipelineson GPUs, such as Halide and Forma, operate by 1) dividing the image into overlapped tiles, and 2) fusing loops to improve memory locality. However, current approaches have limitations: 1) they require intra thread block synchronization, which has a non-trivial cost, 2) they must choose between small tiles that require more overlapped computations or large tiles that increase shared memory access (and lowers occupancy), and 3) their autoscheduling algorithms use simplified GPU models that can result in inefficient global memory accesses. We present a new approach for executing image processing pipelines on GPUs that addresses these limitations as follows. 1) We fuse loops to form overlapped tiles that fit in a single warp, which allows us to use lightweight warp synchronization. 2) We introduce hybrid tiling, which stores overlapped regions in a combination of thread-local registers and shared memory. Thus hybrid tiling either increases occupancy by decreasing shared memory usage or decreases overlapping computations using larger tiles. 3) We present an automatic loop fusion algorithm that considers several factors that affect the performance of GPU kernels. We implement these techniques in PolyMage-GPU, which is a new GPU backend for PolyMage. Our approach produces code that is faster than Halide's manual schedules: 1.65x faster on an NVIDIA GTX 1080Ti and 1.33 faster on an NVIDIA Tesla V100.
BibTeX
@misc{jangda2019model,
  author = {Abhinav Jangda and Arjun Guha},
  title = {{Model-Based Warp-Level Tiling for Image Processing Programs on GPUs}},
  year = {2019},
  eprint = {1909.07190},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.07190},
}

Loading related content...

Figure