Compiling High Performance Recursive Filters

Simple item page
dc.contributor.authorChaurasia, Gauraven_US
dc.contributor.authorRagan-Kelley, Jonathanen_US
dc.contributor.authorParis, Sylvainen_US
dc.contributor.authorDrettakis, Georgeen_US
dc.contributor.authorDurand, Frédoen_US
dc.contributor.editorPetrik Clarberg and Elmar Eisemannen_US
dc.date.accessioned2016-01-19T10:32:56Z
dc.date.available2016-01-19T10:32:56Z
dc.date.issued2015en_US
dc.description.abstractInfinite 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.en_US
dc.description.sectionheadersHigh-Performance Data Processingen_US
dc.description.seriesinformationHigh-Performance Graphicsen_US
dc.identifier.doi10.1145/2790060.2790063en_US
dc.identifier.isbn978-1-4503-3707-6en_US
dc.identifier.pages85-94en_US
dc.identifier.urihttps://doi.org/10.1145/2790060.2790063en_US
dc.publisherACM Siggraphen_US
dc.subjectImage processingen_US
dc.subjectIIR filteren_US
dc.subjectGPU computationen_US
dc.subjectparallelismen_US
dc.subjectmemory localityen_US
dc.subjectcompileren_US
dc.subjectdomainen_US
dc.subjectspecific languageen_US
dc.subjecthigh performanceen_US
dc.titleCompiling High Performance Recursive Filtersen_US
Files
Collections
High-Performance Graphics 2015