Infinite impulse response (IIR) or recursive filters, are essential for image processing because they turn expensive large-footprint convolutions into operations that have a constant cost per pixel regardless of kernel size. However, their recursive nature constrains the order in which pixels can be computed, severely limiting both parallelism within a filter and memory locality across multiple filters. Prior research has developed algorithms that can compute IIR filters with image tiles. Using a divide-and-recombine strategy inspired by parallel prefix sum, they expose greater parallelism and exploit producer-consumer locality in pipelines of IIR filters over multi-dimensional images. While the principles are simple, it is hard, given a recursive filter, to derive a corresponding tile-parallel algorithm, and even harder to implement and debug it.
We show that parallel and locality-aware implementations of IIR filter pipelines can be obtained through program transformations, which we mechanize through a domain-specific compiler. We show that the composition of a small set of transformations suffices to cover the space of possible strategies. We also demonstrate that the tiled implementations can be automatically scheduled in hardware-specific manners using a small set of generic heuristics. The programmer specifies the basic recursive filters, and the choice of transformation requires only a few lines of code. Our compiler then generates high-performance implementations that are an order of magnitude faster than standard GPU implementations, and outperform hand tuned tiled implementations of specialized algorithms which require orders of magnitude more programming effort - a few lines of code instead of a few thousand lines per pipeline.
Publication
Compiling High Performance Recursive Filters
Gaurav Chaurasia, Jonathan Ragan-Kelley, Sylvain Paris, George Drettakis, Fredo Durand
High Performance Graphics 2015
Bibtex
@inproceedings{Chaurasia:2015,
author = {Chaurasia, Gaurav and Ragan-Kelley, Jonathan and Paris, Sylvain and Drettakis, George and Durand, Fredo},
title = {Compiling High Performance Recursive Filters},
booktitle= {Proceedings of the 7th Conference on High-Performance Graphics},
year = {2015},
isbn = {978-1-4503-3707-6},
location = {Los Angeles, California},
pages = {85--94},
numpages = {10},
url = {http://doi.acm.org/10.1145/2790060.2790063},
doi = {10.1145/2790060.2790063},
acmid = {2790063},
keywords = {GPU computation, IIR filter, compiler, domain-specific language, high performance, image processing, memory locality, parallelism},
}
License
RecFilter is open source, under a commercially permissive MIT license. We encourage you to use it in other projects, open source or commercial.
Acknowledgement
We thank Qatar Computing Research Institute (QCRI) for research funding.