Arithmetic Optimization Techniques for Hardware and Software Design

by Ryan Kastner , Anup Hosangadi , Farzan Fallah

• ISBN13: 9780521880992
• ISBN10: 0521880998
• Edition: 1st
• Format: Hardcover
• Copyright: 2010-06-14
• Publisher: Cambridge University Press

Summary

Obtain better system performance, lower energy consumption, and avoid hand-coding arithmetic functions with this concise guide to automated optimization techniques for hardware and software design. High-level compiler optimizations and high-speed architectures for implementing FIR filters are covered, which can improve performance in communications, signal processing, computer graphics, and cryptography. Clearly explained algorithms and illustrative examples throughout make it easy to understand the techniques and write software for their implementation. Background information on the synthesis of arithmetic expressions and computer arithmetic is also included, making the book ideal for new-comers to the subject. This is an invaluable resource for researchers, professionals, and graduate students working in system level design and automation, compilers, and VLSI CAD.

Author Biography

Ryan Kastner is an Associate Professor in the Department of Computer Science and Engineering at the University of California, San Diego. He received his Ph.D. in Computer Science from UCLA in 2002 and has since published over 100 technical papers and three books. His current research interests are in embedded system design, particularly the use of reconfigurable computing devices for digital signal processing.
Anup Hosangadi is an R&D Engineer in the Emulation Group at Cadence Design Systems, Inc. He received his Ph.D. in Computer Engineering from the University of California, Santa Barbara, in 2006 and his research interests include high-level synthesis, combinatorial optimization, and computer arithmetic.
Farzan Fallah is currently a Visiting Scholar at Stanford University, Stanford. He received his Ph.D. in Electrical Engineering and Computer Science from MIT in 1999, after which he worked as a Project Leader at Fujitsu Labs of America in Sunnyvale until 2008. Farzan has published over 60 papers and has 20 patents granted or pending.

Table of Contents

List of abbreviations	p. vii
Preface	p. ix
Introduction	p. 1
Overview	p. 1
Salient features of this book	p. 5
Organization	p. 6
Target audience	p. 7
Use of polynomial expressions and linear systems	p. 9
Chapter overview	p. 9
Approximation algorithms	p. 9
Computer graphics	p. 10
Digital signal processing (DSP)	p. 12
Cryptography	p. 16
Address calculation in data intensive applications	p. 17
Summary	p. 19
Software compilation	p. 21
Chapter overview	p. 21
Basic software compiler structure	p. 21
Algebraic transformations in optimizing software compilers	p. 25
Summary	p. 33
Hardware synthesis	p. 35
Chapter overview	p. 35
Hardware synthesis design flow	p. 35
System specification	p. 38
Program representation	p. 39
Algorithmic optimization	p. 44
Resource allocation	p. 45
Operation scheduling	p. 49
Resource binding	p. 56
Case study: FIR filter	p. 58
Summary	p. 63
Fundamentals of digital arithmetic	p. 68
Chapter overview	p. 68
Basic number representation	p. 68
Two-operand addition	p. 75
Multiple-operand addition	p. 82
Summary	p. 93
Polynomial expressions	p. 95
Chapter overview	p. 95
Polynomial expressions	p. 95
Problem formulation	p. 96
Related optimization techniques	p. 96
Algebraic optimization of arithmetic expressions	p. 99
Experimental results	p. 113
Optimal solutions for reducing the number of operations in arithmetic expressions	p. 117
Summary	p. 123
Linear systems	p. 126
Chapter overview	p. 126
Linear system basics	p. 126
Problem formulation	p. 129
Single-constant multiplication (SCM)	p. 130
Multiple-constant multiplication (MCM)	p. 133
Overview of linear system optimizations	p. 140
Transformation of a linear system into a polynomial expression	p. 142
Optimization for synthesis using two-operand adders	p. 143
FIR filter optimization	p. 147
Synthesis for multiple-operand addition	p. 158
Delay-aware optimization	p. 164
Software optimization	p. 174
Summary	p. 178
Index	p. 182
Table of Contents provided by Ingram. All Rights Reserved.