Synthesis And Optimization Of DSP Algorithms

by Constantinides, George A.; Cheung, Peter Y. K.; Luk, Wayne

• ISBN13: 9781402079306
• ISBN10: 1402079303
• Format: Hardcover
• Copyright: 2004-05-31
• Publisher: Kluwer Academic Pub

Summary

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

1 Introduction	1	(4)
1.1 Objectives	1	(1)
1.2 Overview	2	(3)
2 Background	5	(10)
2.1 Digital Design for DSP Engineers	5	(3)
2.1.1 Microprocessors vs. Digital Design	5	(1)
2.1.2 The Field-Programmable Gate Array	6	(1)
2.1.3 Arithmetic on FPGAs	7	(1)
2.2 DSP for Digital Designers	8	(1)
2.3 Computation Graphs	9	(3)
2.4 The Multiple Word-Length Paradigm	12	(1)
2.5 Summary	13	(2)
3 Peak Value Estimation	15	(12)
3.1 Analytic Peak Estimation	15	(9)
3.1.1 Linear Time-Invariant Systems	16	(6)
3.1.2 Data-range Propagation	22	(2)
3.2 Simulation-based Peak Estimation	24	(1)
3.3 Hybrid Techniques	25	(1)
3.4 Summary	25	(2)
4 Word-Length Optimization	27	(52)
4.1 Error Estimation	27	(15)
4.1.1 Word-Length Propagation and Conditioning	29	(3)
4.1.2 Linear Time-Invariant Systems	32	(6)
4.1.3 Extending to Nonlinear Systems	38	(4)
4.2 Area Models	42	(3)
4.3 Problem Definition and Analysis	45	(6)
4.3.1 Convexity and Monotonicity	45	(6)
4.4 Optimization Strategy 1: Heuristic Search	51	(2)
4.5 Optimization Strategy 2: Optimum Solutions	53	(8)
4.5.1 Word-Length Bounds	55	(1)
4.5.2 Adders	56	(2)
4.5.3 Forks	58	(2)
4.5.4 Gains and Delays	60	(1)
4.5.5 MILP Summary	60	(1)
4.6 Some Results	61	(17)
4.6.1 Linear Time-Invariant Systems	62	(7)
4.6.2 Nonlinear Systems	69	(6)
4.6.3 Limit-cycles in Multiple Word-Length Implementations	75	(3)
4.7 Summary	78	(1)
5 Saturation Arithmetic	79	(34)
5.1 Overview	79	(1)
5.2 Saturation Arithmetic Overheads	80	(3)
5.3 Preliminaries	83	(1)
5.4 Noise Model	84	(17)
5.4.1 Conditioning an Annotated Computation Graph	85	(1)
5.4.2 The Saturated Gaussian Distribution	85	(3)
5.4.3 Addition of Saturated Gaussians	88	(4)
5.4.4 Error Propagation	92	(2)
5.4.5 Reducing Bound Slackness	94	(4)
5.4.6 Error estimation results	98	(3)
5.5 Combined Optimization	101	(3)
5.6 Results and Discussion	104	(6)
5.6.1 Area Results	104	(4)
5.6.2 Clock frequency results	108	(2)
5.7 Summary	110	(3)
6 Scheduling and Resource Binding	113	(36)
6.1 Overview	113	(1)
6.2 Motivation and Problem Formulation	114	(3)
6.3 Optimum Solutions	117	(5)
6.3.1 Resources, Instances and Control Steps	117	(4)
6.3.2 ILP Formulation	121	(1)
6.4 A Heuristic Approach	122	(19)
6.4.1 Overview	123	(1)
6.4.2 Word-Length Compatibility Graph	124	(2)
6.4.3 Resource Bounds	126	(1)
6.4.4 Latency Bounds	127	(2)
6.4.5 Scheduling with Incomplete Word-Length Information	129	(5)
6.4.6 Combined Binding and Word-Length Selection	134	(4)
6.4.7 Refining Word-Length Information	138	(3)
6.5 Some Results	141	(6)
6.6 Summary	147	(2)
7 Conclusion	149	(2)
7.1 Summary	149	(1)
7.2 Future Work	150	(1)
A Notation	151	(6)
A.l Sets and functions	151	(1)
A.2 Vectors and Matrices	151	(1)
A.3 Graphs	152	(1)
A.4 Miscellaneous	152	(1)
A.5 Pseudo-Code	152	(5)
References	157	(6)
Index	163