SYNTHESIS AND OPTIMIZATION OF DSP ALGORITHMS

This page intentionally left blank

©2004 Kluwer Academic Publishers

New York, Boston, Dordrecht, London, Moscow

Print ©2004 Kluwer Academic Publishers

Dordrecht

All rights reserved

No part of this eBook may be reproduced or transmitted in any form or by any means, electronic, mechanical, recording, or otherwise, without written consent from the Publisher

Created in the United States of America

To all progressive people

This page intentionally left blank

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-e cient 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.

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

XContents

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

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

This page intentionally left blank