Synthesis.And.Optimization.Of.DSP.Algorithms.May.2004.pdf
Preface
Digital signal processing (DSP) has undergone an immense expansion since
the foundations of the subject were laid in the 1970s. New application areas
have arisen, and DSP technology is now essential to a bewildering array of
fields such as computer vision, instrumentation and control, data compression,
speech recognition and synthesis, digital audio and cameras, mobile telephony,
echo cancellation, and even active suspension in the automotive industry.
In parallel to, and intimately linked with, the growth in application areas
has been the growth in raw computational power available to implement DSP
algorithms. Moore’s law continues to hold in the semiconductor industry, resulting
every 18 months in a doubling of the number of computations we can
perform.
Despite the rapidly increasing performance of microprocessors, the computational
demands of many DSP algorithms continue to outstrip the available
computational power. As a result, many custom hardware implementations of
DSP algorithms are produced - a time consuming and complex process, which
the techniques described in this book aim, at least partially, to automate.
This book provides an overview of recent research on hardware synthesis an
optimization of custom hardware implementations of digital signal processors.
It focuses on techniques for automating the production of area-efficient designs
from a high-level description, while satisfying user-specified constraints. Such
techniques are shown to be applicable to both linear and nonlinear systems:
from finite impulse response (FIR) and infinite impulse response (IIR) filters
to designs for discrete cosine transform (DCT), polyphase filter banks, and
adaptive least mean square (LMS) filters.
This book is designed for those working near the interface of DSP algorithm
design and DSP implementation. It is our contention that this interface
is a very exciting place to be, and we hope this book may help to draw
the reader nearer to it.
London, George A. Constantinides
February 2004 Peter Y.K. Cheung
Wayne Luk
This page intentionally left blank
Contents
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1 Digital Design for DSP Engineers . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Microprocessors vs. Digital Design . . . . . . . . . . . . . . . . . . . 5
2.1.2 The Field-Programmable Gate Array . . . . . . . . . . . . . . . . 6
2.1.3 Arithmetic on FPGAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 DSP for Digital Designers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Computation Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4 The Multiple Word-Length Paradigm . . . . . . . . . . . . . . . . . . . . . . 12
2.5 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 Peak Value Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1 Analytic Peak Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1.1 Linear Time-Invariant Systems . . . . . . . . . . . . . . . . . . . . . . 16
3.1.2 Data-range Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Simulation-based Peak Estimation . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Hybrid Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4 Word-Length Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.1 Error Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.1.1 Word-Length Propagation and Conditioning . . . . . . . . . . 29
4.1.2 Linear Time-Invariant Systems . . . . . . . . . . . . . . . . . . . . . . 32
4.1.3 Extending to Nonlinear Systems. . . . . . . . . . . . . . . . . . . . . 38
4.2 Area Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3 Problem Definition and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3.1 Convexity and Monotonicity . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4 Optimization Strategy 1: Heuristic Search . . . . . . . . . . . . . . . . . . 51
4.5 Optimization Strategy 2: Optimum Solutions . . . . . . . . . . . . . . . 53
4.5.1 Word-Length Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.5.2 Adders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.5.3 Forks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.5.4 Gains and Delays. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.5.5 MILP Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.6 Some Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.6.1 Linear Time-Invariant Systems . . . . . . . . . . . . . . . . . . . . . . 62
4.6.2 Nonlinear Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.6.3 Limit-cycles in Multiple Word-Length Implementations 75
4.7 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5 Saturation Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.2 Saturation Arithmetic Overheads . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.3 Preliminaries. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.4 Noise Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.4.1 Conditioning an Annotated Computation Graph . . . . . . 85
5.4.2 The Saturated Gaussian Distribution . . . . . . . . . . . . . . . . 85
5.4.3 Addition of Saturated Gaussians . . . . . . . . . . . . . . . . . . . . 88
5.4.4 Error Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4.5 Reducing Bound Slackness. . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.4.6 Error estimation results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.5 Combined Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.6 Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.6.1 Area Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.6.2 Clock frequency results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.7 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6 Scheduling and Resource Binding . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.2 Motivation and Problem Formulation . . . . . . . . . . . . . . . . . . . . . . 114
6.3 Optimum Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.3.1 Resources, Instances and Control Steps . . . . . . . . . . . . . . 117
6.3.2 ILP Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.4 A Heuristic Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.4.1 Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.4.2 Word-Length Compatibility Graph . . . . . . . . . . . . . . . . . . 124
6.4.3 Resource Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
6.4.4 Latency Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.4.5 Scheduling with Incomplete Word-Length Information . 129
6.4.6 Combined Binding and Word-Length Selection . . . . . . . . 134
6.4.7 Refining Word-Length Information . . . . . . . . . . . . . . . . . . 138
6.5 Some Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6.6 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
X Contents
Contents XI
7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
7.1 Summary. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
A Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
A.1 Sets and functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
A.2 Vectors and Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
A.3 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
A.4 Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
A.5 Pseudo-Code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
Synthesis.And.Optimization.Of.DSP.Algorithms.May.2004: Synthesis.And.Optimization.Of.DSP.Algorithms.May.2004.pdf
