Advanced Computer Arithmetic Design

This volume presents the results of a decade's research in innovative and progressive design techniques. Covering all the most important research topics in the field, Advanced Computer Arithmetic Design is the most up-to-date and comprehensive treatment of new research currently available.

MICHAEL J. FLYNN is Director of the Sub-Nanosecond Arithmetic Processor (SNAP) project at Stanford University. For the past decade, he has been the leading source of published research in the area of computer arithmetic design. Stuart F. Oberman earned his Phd at Stanford University and is currently manager of VLSI Design at Nishan Systems, San Jose, California. He previously worked at AMD, where he was the architect of the Athlon floating-point unit. His research interests include new algorithms for high-speed computer arithmetic, high-speed switch-fabric design, and architectures for high-throughput network processors.

Preface

xi

Acknowledgments

xiii

Notation

xv

Integer Addition

1

(22)

Background

1

(5)

Ripple Adders; Manchester Carry Chain

2

(1)

Carry Skip Adders; Multilevel Carry Skip

2

(1)

Carry-Select and Conditional-Sum Adders

3

(1)

Carry Lookahead Adders; Canomic Adders

4

(2)

Ling Adders

6

(1)

Adder Implementations

7

(3)

An ECL Ling Adder

10

(4)

Group Generates

10

(1)

Lookahead Network

10

(3)

Final Sum

13

(1)

Critical Path

14

(1)

Implementation

14

(1)

A CMOS Ling Adder

14

(7)

Group Generates

16

(1)

Lookahead Network

17

(1)

Final Sum

18

(1)

Critical Path

19

(1)

Implementation

20

(1)

Conclusion

21

(2)

Floating-Point Addition

23

(20)

Improved Algorithms for High-Speed FP Addition

23

(10)

A Brief Review of FP Addition Algorithms (A1 and A2)

24

(3)

A New Algorithm: A3 (Two Path with Integrated Rounding)

27

(6)

Summary

33

(1)

Variable-Latency FP Addition

33

(5)

Variable-Latency Algorithm

34

(1)

Two-Cycle Algorithm

34

(2)

One-Cycle Algorithm

36

(2)

Performance Results

38

(4)

Conclusion

42

(1)

Multiplication with Partially Redundant Multiples

43

(22)

Introduction

43

(1)

Background

43

(7)

Add and Shift

43

(2)

Dot Diagrams

45

(1)

Booth's Algorithm

46

(1)

Booth 3

47

(3)

Booth 4 and Higher

50

(1)

Redundant Booth

50

(1)

Booth 3 with Fully Redundant Partial Products

50

(2)

Booth 3 with Partially Redundant Partial Products

52

(1)

Dealing with Negative Partial Products

52

(1)

Booth with Bias

53

(10)

Choosing the Right Constant

55

(2)

Producing the Multiples

57

(1)

Redundant Booth 3

57

(1)

Redundant Booth 4

58

(5)

Choosing the Adder Length

63

(1)

Conclusion

63

(2)

Multiplier Topologies

65

(36)

Review of Issues in Partial-Product Summation

66

(2)

Regular Topologies

68

(21)

Array Topologies

69

(6)

Tree Topologies

75

(10)

Effects of the Number of Tracks per Channel

85

(4)

Irregular Topologies

89

(10)

Wallace Tree

89

(1)

Algorithmic Generation

89

(10)

Conclusion

99

(2)

Technology Scalling Effects on Multipliers

101

(16)

Effects of Smaller Feature Sizes

101

(1)

Wire Effects

102

(4)

Binary Trees vs Procedural Layouts

106

(3)

Scaling Effects on Encoding Schemes

109

(5)

Topology

110

(2)

Area X Time Product

112

(1)

Pipelining

113

(1)

Power

114

(2)

Encoding Schemes

115

(1)

Topology

115

(1)

Conclusion

116

(1)

Design Issues in Division

117

(16)

Introduction

117

(1)

System Level Study

118

(2)

Instrumentation

118

(1)

Method of Analysis

119

(1)

Results

120

(10)

Instruction Mix

120

(1)

Compiler Effects

120

(2)

Performance and Area Tradeoffs

122

(3)

Shared-Multiplier Effects

125

(2)

Shared Square Root

127

(1)

On-the-Fly Rounding and Conversion

128

(1)

Consumers of Division Results

129

(1)

Conclusion

130

(3)

Minimizing the Complexity of SRT Tables

133

(20)

Theory of SRT Division

134

(4)

Recurrence

134

(1)

Choice of Radix

135

(1)

Choice of Quotient Digit-Set

135

(3)

Implementing SRT Tables

138

(5)

Divisor and Partial-Remainder Estimates

138

(1)

Uncertainty Regions

139

(1)

Reducing Table Complexity

140

(3)

Experimental Methodology

143

(2)

TableGen

143

(2)

Table Synthesis

145

(1)

Results

145

(5)

Same-Radix Tradeoffs

145

(2)

Higher Radices

147

(3)

Conclusion

150

(3)

Very High-Radix Division

153

(30)

Taylor Series Expansion

153

(1)

Algorithm A

154

(8)

Number of Accurate Bits Per Iteration

157

(4)

Representing X Using Redundancy

161

(1)

Algorithm B

162

(9)

Number of Accurate Bits per Iteration

164

(6)

Representing X Using Redundancy

170

(1)

Algorithm C

171

(8)

Theory

171

(2)

Lookup-Table Construction

173

(1)

Booth Recoding

173

(2)

Error Analysis

175

(1)

Optimization Techniques

175

(3)

Discussion

178

(1)

Related Algorithms

179

(3)

Cyrix Short-Reciprocal Algorithm

179

(1)

Comparison with the Newton---Raphson Method

179

(2)

Comparison with the IBM RISC System/6000

181

(1)

Comparison with MacLaurin Series

181

(1)

Conclusion

182

(1)

Using a Multiplier for Function Approximation

183

(52)

Proposed Method: Implementation

183

(9)

Partial-Product Array

183

(3)

Related Work

186

(1)

Implementation

187

(5)

Summary of Implementation

192

(1)

Proposed Method: Derivation

192

(15)

Describing an Operation as a Signed PPA

192

(8)

Adapting the Signed PPA to the Multiplier's PPA

200

(3)

Performance and Comparisons

203

(4)

Summary of Derivation

207

(1)

Reciprocal, Division, and Square Root

207

(23)

Reciprocal Operation

208

(5)

Division Operation

213

(7)

Square-Root Operation

220

(10)

Conclusion

230

(5)

FUPA

235

(16)

Introduction

235

(2)

Background

237

(1)

Components of FUPA

237

(7)

Technology Scaling

238

(1)

Latency Component of FUPA

239

(1)

Derivation of Delay Scale Factor

239

(1)

Area Component of FUPA

240

(1)

Derivation of Area Scale Factor

240

(1)

Relationship between Area, Operating Frequency, and Power

241

(1)

Application Profiling

242

(1)

Computation of FUPA

243

(1)

Microprocessor FPU Comparisons

244

(5)

Effective and Normalized Effective Latency of Microprocessor FPUs

244

(2)

Die-Area and Normalized-Die-Area Usage of Microprocessor FPUs

246

(1)

FUPA of Microprocessor FPUs

247

(2)

Limitations of FUPA

249

(1)

Conclusion

249

(2)

High-Speed Clocking Using Wave Pipelining

251

(34)

Background

251

(3)

Pipelining and Wave Pipelining

252

(1)

Wave Pipeline Research

253

(1)

Theory

254

(5)

Minimum Clock Period for Traditional Pipelines

254

(2)

Minimum Clock Period for Wave Pipelines

256

(3)

Device Technologies: Applicability and Performance

259

(1)

Performance Limits of Wave Pipelining

260

(5)

Path-Length Imbalance

261

(1)

Data Dependences

261

(1)

Fabrication Process

262

(1)

Environmental Variation

263

(1)

CMOS Process and Environmental Performance Limits

264

(1)

Design Optimizations

265

(8)

Rough Tuning

266

(1)

Fine Tuning

266

(4)

CMOS Delay Compensation

270

(3)

SNAP Wave-Pipeline Demonstration VLSI

273

(10)

Bipolar Population Counter

273

(1)

CMOS Multipler Circuit

273

(1)

CMOS VLSI Vector Unit

274

(9)

Conclusion

283

(2)

Rational Arithmetic

285

(24)

Introduction

285

(2)

Continued Fractions

287

(3)

The M-log-Fraction Transformation

290

(2)

The Signed-Digit M-log Fraction

292

(1)

A Rational-Arithmetic Unit

293

(5)

Linear Fractional Transformation

297

(1)

Quadratic Transformations

298

(1)

A Shift-and-Add-Based Rational-Arithmetic Unit

298

(3)

Implementing the Bilinear Function (ax + b)/(cx + d)

299

(2)

VLSI Implementation of Rational Arithmetic Units

301

(1)

Higher-Radix Rational Arithmetic

302

(2)

Related Work

304

(2)

Conclusions

306

(1)

Historical Notes on Continued Fractions in Arithmetic

306

(3)

Bibliography

309

(12)

Index

321

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Advanced Computer Arithmetic Design

Summary

Author Biography

Table of Contents

Supplemental Materials