Skip to Main content Skip to Navigation
Conference papers

Compiling High Performance Recursive Filters

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 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 {\em program transformations}, which we mechanize through a {\em 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-01167185
Contributor : Team Reves <>
Submitted on : Wednesday, June 24, 2015 - 12:52:34 AM
Last modification on : Thursday, March 5, 2020 - 4:52:04 PM
Long-term archiving on: : Tuesday, September 15, 2015 - 10:31:14 PM

File

recfilter.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01167185, version 1

Collections

Citation

Gaurav Chaurasia, Jonathan Ragan-Kelley, Sylvain Paris, George Drettakis, Fredo Durand. Compiling High Performance Recursive Filters. High Performance Graphics, Eurographics/ACM SIGGRAPH, Aug 2015, Los Angeles, United States. ⟨hal-01167185⟩

Share

Metrics

Record views

1230

Files downloads

1239