IIR filter parallelization

Question

Is there any current ideas about IIR filter algorithm parallelization with thread count greater than filter order?

Ideally, parallelization method should load GPU efficiently.

Answer 1

You might be interested in the following paper:

Nehab, D; Maximo, A; Lima, R; Hoppe, H: GPU-Efficient Recursive Filtering and Summed-Area Tables. ACM Trans. Graph. 30(6):176 (December 2011). doi://10.1145/2024156.2024210 http://w3.impa.br/~diego/publications/NehEtAl11.pdf

The basic idea is to recognize that linear filters are associative (at least in theory) and thus you can

1. divide your input into chunks.
2. every thread initializes its iir filter state with 0s and processes its chunk.
3. every thread stores the final state of its iir filter for its chunk.
4. now (because of associativity) you can figure out what the beginning filter state is of every chunk.
5. so then you run the filter over the chunk again, this time correctly initialized and get the correct output.

As @jonsca pointed out, you were a bit vague about your use case. The above all assumes that you can do batch processing on your input. If you need some kind of real-time filtering none of what I said is relevant.