Compiling High Performance Recursive Filters
Loading...
Date
2015
Journal Title
Journal ISSN
Volume Title
Publisher
ACM Siggraph
Abstract
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 multidimensional 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 hardwarespecific 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.
Description
@inproceedings{10.1145:2790060.2790063,
booktitle = {High-Performance Graphics},
editor = {Petrik Clarberg and Elmar Eisemann},
title = {{Compiling High Performance Recursive Filters}},
author = {Chaurasia, Gaurav and Ragan-Kelley, Jonathan and Paris, Sylvain and Drettakis, George and Durand, Frédo},
year = {2015},
publisher = {ACM Siggraph},
ISBN = {978-1-4503-3707-6},
DOI = {10.1145/2790060.2790063}
}