Synthesis and optimization of DSP algorithms

Description

Team DDU......Page 1 Contents......Page 6 1.1 Objectives......Page 9 1.2 Overview......Page 10 2.1.1 Microprocessors vs Digital Design......Page 12 2.1.2 The Field-Programmable Gate Array......Page 13 2.1.3 Arithmetic on FPGAs......Page 14 2.2 DSP for Digital Designers......Page 15 2.3 Computation Graphs......Page 16 2.4 The Multiple Word-Length Paradigm......Page 19 2.5 Summary......Page 20 3.1 Analytic Peak Estimation......Page 22 3.1.1 Linear Time-Invariant Systems......Page 23 3.1.2 Data-range Propagation......Page 29 3.2 Simulation-based Peak Estimation......Page 31 3.4 Summary......Page 32 4.1 Error Estimation......Page 34 4.1.1 Word-Length Propagation and Conditioning......Page 36 4.1.2 Linear Time-Invariant Systems......Page 39 4.1.3 Extending to Nonlinear Systems......Page 45 4.2 Area Models......Page 49 4.3.1 Convexity and Monotonicity......Page 52 4.4 Optimization Strategy 1: Heuristic Search......Page 58 4.5 Optimization Strategy 2: Optimum Solutions......Page 60 4.5.1 Word-Length Bounds......Page 62 4.5.2 Adders......Page 63 4.5.3 Forks......Page 65 4.5.5 MILP Summary......Page 67 4.6 Some Results......Page 68 4.6.1 Linear Time-Invariant Systems......Page 69 4.6.2 Nonlinear Systems......Page 76 4.6.3 Limit-cycles in Multiple Word-Length Implementations......Page 82 4.7 Summary......Page 85 5.1 Overview......Page 86 5.2 Saturation Arithmetic Overheads......Page 87 5.3 Preliminaries......Page 90 5.4 Noise Model......Page 91 5.4.2 The Saturated Gaussian Distribution......Page 92 5.4.3 Addition of Saturated Gaussians......Page 95 5.4.4 Error Propagation......Page 99 5.4.5 Reducing Bound Slackness......Page 101 5.4.6 Error estimation results......Page 105 5.5 Combined Optimization......Page 108 5.6.1 Area Results......Page 111 5.6.2 Clock frequency results......Page 115 5.7 Summary......Page 117 6.1 Overview......Page 120 6.2 Motivation and Problem Formulation......Page 121 6.3.1 Resources, Instances and Control Steps......Page 124 6.3.2 ILP Formulation......Page 128 6.4 A Heuristic Approach......Page 129 6.4.1 Overview......Page 130 6.4.2 Word-Length Compatibility Graph......Page 131 6.4.3 Resource Bounds......Page 133 6.4.4 Latency Bounds......Page 134 6.4.5 Scheduling with Incomplete Word-Length Information......Page 136 6.4.6 Combined Binding and Word-Length Selection......Page 141 6.4.7 Refining Word-Length Information......Page 145 6.5 Some Results......Page 148 6.6 Summary......Page 154 7.1 Summary......Page 156 7.2 Future Work......Page 157 A.2 Vectors and Matrices......Page 158 A.5 Pseudo-Code......Page 159 References......Page 164 Index......Page 170