High-performance streaming applications represent a new and distinct domain of programs that is becoming increasingly important. Within this domain, the StreamIt language is designed to satisfy two criteria: first, it provides high-level abstractions that improve programmer productivity, and second, it is amenable to straightforward compiler analyses for achieving high performance. In this talk, I will describe domain-specific optimizations that are enabled by the clean structure of the StreamIt language. We focus on filters that are linear; that is, each of their outputs can be represented as an affine combination of their inputs. Linearity is common in DSP components; examples include FIR filters, expanders, compressors, FFTs and DCTs.

We demonstrate that several algorithmic transformations, traditionally hand-tuned by DSP experts, can be completely automated by the compiler. First, we present a linear extraction analysis that automatically detects linear filters from the C-like code in their work function. Then, we give a procedure for combining adjacent linear filters into a single filter, as well as for translating a linear filter to operate in the frequency domain. We also present an optimization selection algorithm, which finds the sequence of combination and frequency transformations that will give the maximal benefit.

We have completed a fully-automatic implementation of the above techniques as part of the StreamIt compiler, and we demonstrate a 450% performance improvement over our benchmark suite.

This work was done primarily by Andrew Lamb as part of his M.Eng thesis. More information is available here.