Algorithms and Parallel Computing

12.1 INTRODUCTION

In this chapter, we illustrate how to obtain different multithreaded or systolic array structures for the one-dimensional (1-D) infinite impulse response (IIR) digital filters. The IIR algorithm is an essentially a serial algorithm since each FOR loop iteration depends on N − 1 previous iterations where N is the filter length. Therefore, the programmer and the concurrency platforms would not be able to parallelize the algorithm. The techniques discussed in this book would help the programmer extract and explore the inherent parallelism in this seemingly serial algorithm.

We use the dependence graph technique introduced in Chapter 10 and the computational geometry technique discussed in Chapter 11. At the end of the chapter, we will also use the z-domain approach discussed in Chapter 9.