Algorithms and Parallel Computing

10.1 INTRODUCTION

The dependence graph technique is a very simple yet powerful approach for the design space exploration of regular iterative algorithms (RIAs). One restriction on this approach is that the algorithm must be two-dimensional (2-D) or three-dimensional (3-D) at the most so that the designer could visualize the resulting structures. Chapter 11 will extend this approach to algorithms having higher dimensions by replacing the dependence graph with a convex hull in the integer space. Many parallel algorithms have 2-D or 3-D dimensions such as one-dimensional (1-D) digital filters, 1-D decimators and interpolators, matrix–vector multiplication, and pattern matching algorithms. Furthermore, many types of higher-dimensional algorithms can be recursively broken down into lower-dimensional problems. For example, we can hierarchically decompose 2-D or 3-D digital filters into modules of 1-D filters. In this chapter, we illustrate how to obtain different multithreading and systolic structures for a given algorithm. We are going to use the 1-D finite impulse response (FIR) digital filter as a running example.