Unrolled Memory Inner-Products: An Abstract GPU Operator for Efficient Vision-Related Computations

Yu-Sheng Lin, Wei-Chao Chen, Shao-Yi ChienICCV 2017 · DOI

Abstract

The Unrolled-Memory-Inner-Product (UMI) operator is a high-level GPU primitive designed to simplify the development of high-performance vision kernels. By abstracting complex memory access patterns into a unified inner product form, UMI enables researchers to achieve significant speedups—up to 26x over standard libraries like OpenCV and Caffe—without requiring deep expertise in CUDA optimization. This paper introduces the mathematical abstraction, on-the-fly unrolling techniques, and hardware-level optimizations such as conflict-free memory access and register tiling that underpin the UMI operator.

Introduction: The Challenge of GPU Optimization

Optimizing vision algorithms for GPUs is a notoriously difficult task. Developers often face a choice between using "black box" vendor libraries like NVIDIA’s cuDNN, which are fast but inflexible, or writing custom CUDA kernels, which requires managing complex hardware details such as shared memory banks and register pressure.

A standard approach for operations like convolutions is "unrolling" (or im2col), where an image is rearranged into a large matrix to leverage standard BLAS libraries. However, physical unrolling incurs massive memory overhead due to data duplication.

The UMI operator abstracts the convolution of image M with kernel K as a matrix-vector product U x k.

As shown in the figure above, the goal is to treat the convolution $M * K$ as equivalent to a matrix-vector product $U \times k$. The challenge lies in performing this operation efficiently on GPU hardware without the memory bloat of a physical $U$ matrix.

The UMI Operator: Methods and Implementation

The authors introduce the UMI Operator, a programmatic abstraction that treats various vision tasks as generalized inner products. Instead of creating a physical unrolled matrix, UMI uses "functors" to calculate data indices at runtime—a technique called on-the-fly unrolling.

Key Technical Components

  • Strategy Classes: Using C++11, developers define a "Strategy" (e.g., a dot product for CNNs or an L1-norm for motion estimation). The UMI framework then handles the messy hardware-level scheduling.
  • Tiled Execution & Register Tiling: The operator automatically divides work into tiles that fit into the GPU’s fast shared memory and uses registers as an extra cache layer to minimize slow trips to main VRAM.
  • Conflict-Free Memory Access: A critical innovation is the use of XOR-hashing and specific tiling patterns to ensure that memory accesses are perfectly shuffled across SRAM banks, preventing performance-killing bank conflicts.
Comparison of memory access strategies. UMI optimizes the path from DRAM to GPU cores by utilizing shared memory and conflict-free permutations to maximize throughput.

The figure above illustrates how UMI moves beyond standard cache hierarchies by explicitly managing shared memory and implementing conflict-free permutations to feed GPU cores at peak rates.

Evaluation and Results

The UMI operator was evaluated against several industry-standard benchmarks and libraries, including Caffe, OpenCV, and the Parboil suite.

Key Results

  • Significant Speedups: UMI achieved speedups ranging from 1.3x to 26.4x compared to the GPU implementations in OpenCV and Caffe.
  • Efficiency vs. cuDNN: While cuDNN remains the gold standard for specific 3x3 convolutions, UMI outperformed Caffe (which uses cuBLAS) and remained competitive with cuDNN on non-standard strides and larger kernels.
  • Reduced Complexity: UMI significantly reduces the "token count" for developers. For motion estimation, UMI required roughly 25% of the identifiers needed by a traditional hand-tuned implementation, making high-performance code more accessible to non-specialists.

Conclusion and Future Work

The UMI operator demonstrates that high-level abstractions do not have to sacrifice performance. By providing a formal model of memory access to the compiler, UMI can outperform hand-tuned code that fails to account for hardware quirks like bank conflicts.

Future work includes extending the abstraction to data-dependent kernels (like recursive trees) and improving write-back optimizations. The authors also suggest that future GPU hardware could natively support UMI-style fetch units to further enhance performance.

Summary updated

BibTeX
@inproceedings{lin2017unrolled,
  author = {Yu-Sheng Lin and Wei-Chao Chen and Shao-Yi Chien},
  title = {{Unrolled Memory Inner-Products: An Abstract GPU Operator for Efficient Vision-Related Computations}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2017},
  doi = {10.1109/iccv.2017.490},
}
Figure