Synthesis and optimization of DSP algorithms

Constantinides, Cheung, Luk.1402079311

Synthesis and Optimization of DSP Algorithms describes approaches taken to synthesising structural hardware descriptions of digital circuits from high-level descriptions of Digital Signal Processing (DSP) algorithms. The book contains: -A tutorial on the subjects of digital design and architectural synthesis, intended for DSP engineers, -A tutorial on the subject of DSP, intended for digital designers, -A discussion of techniques for estimating the peak values likely to occur in a DSP system, thus enabling an appropriate signal scaling. Analytic techniques, simulation techniques, and hybrids are discussed. The applicability of different analytic approaches to different types of DSP design is covered, -The development of techniques to optimise the precision requirements of a DSP algorithm, aiming for efficient implementation in a custom parallel processor. The idea is to trade-off numerical accuracy for area or power-consumption advantages. Again, both analytic and simulation techniques for estimating numerical accuracy are described and contrasted. Optimum and heuristic approaches to precision optimisation are discussed, -A discussion of the importance of the scheduling, allocation, and binding problems, and development of techniques to automate these processes with reference to a precision-optimized algorithm, -Future perspectives for synthesis and optimization of DSP algorithms. A wide body of literature exists covering separately the areas of DSP, hardware design, and design automation. This book brings together the fields, concentrating on those transformations, optimizations, and design techniques that would usually be considered to cross the domain boundaries between “pure DSP” and “pure digital implementation”. As such, this book forms a valuable contribution to the existing literature. Synthesis and Optimization of DSP Algorithms is of use both to researchers and students in the field of design automation for DSP systems, and to those wishing to implement state-of-the-art techniques within an Electronic Design Automation framework.

---

Table of contents :
Team DDU……Page 1
Contents……Page 10
1.1 Objectives……Page 14
1.2 Overview……Page 15
2.1.1 Microprocessors vs Digital Design……Page 18
2.1.2 The Field-Programmable Gate Array……Page 19
2.1.3 Arithmetic on FPGAs……Page 20
2.2 DSP for Digital Designers……Page 21
2.3 Computation Graphs……Page 22
2.4 The Multiple Word-Length Paradigm……Page 25
2.5 Summary……Page 26
3.1 Analytic Peak Estimation……Page 28
3.1.1 Linear Time-Invariant Systems……Page 29
3.1.2 Data-range Propagation……Page 35
3.2 Simulation-based Peak Estimation……Page 37
3.4 Summary……Page 38
4.1 Error Estimation……Page 40
4.1.1 Word-Length Propagation and Conditioning……Page 42
4.1.2 Linear Time-Invariant Systems……Page 45
4.1.3 Extending to Nonlinear Systems……Page 51
4.2 Area Models……Page 55
4.3.1 Convexity and Monotonicity……Page 58
4.4 Optimization Strategy 1: Heuristic Search……Page 64
4.5 Optimization Strategy 2: Optimum Solutions……Page 66
4.5.1 Word-Length Bounds……Page 68
4.5.2 Adders……Page 69
4.5.3 Forks……Page 71
4.5.5 MILP Summary……Page 73
4.6 Some Results……Page 74
4.6.1 Linear Time-Invariant Systems……Page 75
4.6.2 Nonlinear Systems……Page 82
4.6.3 Limit-cycles in Multiple Word-Length Implementations……Page 88
4.7 Summary……Page 91
5.1 Overview……Page 92
5.2 Saturation Arithmetic Overheads……Page 93
5.3 Preliminaries……Page 96
5.4 Noise Model……Page 97
5.4.2 The Saturated Gaussian Distribution……Page 98
5.4.3 Addition of Saturated Gaussians……Page 101
5.4.4 Error Propagation……Page 105
5.4.5 Reducing Bound Slackness……Page 107
5.4.6 Error estimation results……Page 111
5.5 Combined Optimization……Page 114
5.6.1 Area Results……Page 117
5.6.2 Clock frequency results……Page 121
5.7 Summary……Page 123
6.1 Overview……Page 126
6.2 Motivation and Problem Formulation……Page 127
6.3.1 Resources, Instances and Control Steps……Page 130
6.3.2 ILP Formulation……Page 134
6.4 A Heuristic Approach……Page 135
6.4.1 Overview……Page 136
6.4.2 Word-Length Compatibility Graph……Page 137
6.4.3 Resource Bounds……Page 139
6.4.4 Latency Bounds……Page 140
6.4.5 Scheduling with Incomplete Word-Length Information……Page 142
6.4.6 Combined Binding and Word-Length Selection……Page 147
6.4.7 Refining Word-Length Information……Page 151
6.5 Some Results……Page 154
6.6 Summary……Page 160
7.1 Summary……Page 162
7.2 Future Work……Page 163
A.2 Vectors and Matrices……Page 164
A.5 Pseudo-Code……Page 165
References……Page 170
Index……Page 176