computer arithmetic

COMPUTER ARITHMETIC Algorithms and Hardware Designs Behrooz Parhami Department of Electrical and Computer Engineering University of California, Santa Barbara New York Oxford OXFORD UNIVERSITY PRESS 2000 CONTENTS Preface xv PART I NUMBER REPRESENTATION NUMBERS AND ARITHMETIC 3 i .1 What Is Computer Arithmetic? 3 1.2 A Motivating Example 5 1.3 Numbers and Their Encodings 6 1.4 Fixed-Radix Positional Number Systems 8 1.5 Number Radix Conversion 11 1.6 Classes of Number Representations 14 Problems 15 References 18 REPRESENTING SIGNED NUMBERS 19 2.1 Signed-Magnitude Representation 19 2.2 Biased Representations 21 2.3 Complement Representations 22 2.4 Two's- and 1's-Complement Numbers 24 2.5 Direct and Indirect Signed Arithmetic 27 2.6 Using Signed Positions or Signed Digits 28 Problems 31 References 33 REDUNDANT NUMBER SYSTEMS 35 3.1 Coping with the Carry Problem 35 3.2 Redundancy in Computer Arithmetic 37 3.3 Digit Sets and Digit-Set Conversions 39 3.4 Generalized Signed-Digit Numbers 41 vii viii Contents 3.5 Carry-Free Addition Algorithms 43 3.6 Conversions and Support Functions 48 Problems 50 References 52 4 RESIDUE NUMBER SYSTEMS 54 4.1 RNS Representation and Arithmetic 54 4.2 Choosing the RNS Moduli 57 4.3 Encoding and Decoding of Numbers 60 4.4 Difficult RNS Arithmetic Operations 64 4.5 Redundant RNS Representations 66 4.6 Limits of Fast Arithmetic in RNS 67 Problems 70 References 72 PART II ADDITION/SUBTRACTION 5 BASIC ADDITION AND COUNTING 75 5.1 Bit-Serial and Ripple-Carry Adders 75 5.2 Conditions and Exceptions 78 5.3 Analysis of Carry Propagation 80 5.4 Carry Completion Detection 82 5.5 Addition of a Constant: Counters 83 5.6 Manchester Carry Chains and Adders 85 Problems 87 References 90 6 CARRY-LOOKAHEAD ADDERS 91 6.1 Unrolling the Carry Recurrence 91 6.2 Carry-Lookahead Adder Design 93 6.3 Ling Adder and Related Designs 97 6.4 Carry Determination as Prefix Computation 98 6.5 Alternative Parallel Prefix Networks 100 6.6 VLSI Implementation Aspects 104 Problems 104 References 107 7 VARIATIONS IN FAST ADDERS 108 7.1 Simple Carry-Skip Adders 108 Contents ix 7.2 Multilevel Carry-Skip Adders 111 7.3 Carry-Select Adders 114 7.4 Conditional-Sum Adder 116 7.5 Hybrid Adder Designs 117 7.6 Optimizations in Fast Adders 120 Problems 120 References 123 8 MULTIOPERAND ADDITION 125 8.1 Using Two-Operand Adders 125 8.2 Carry-Save Adders 128 8.3 Wallace and Dadda Trees 131 8.4 Parallel Counters 133 8.5 Generalized Parallel Counters 134 8.6 Adding Multiple Signed Numbers 136 Problems 137 References 140 PART III MULTIPLICATION 9 BASIC MULTIPLICATION SCHEMES 143 9.1 Shift/Add Multiplication Algorithms 143 9.2 Programmed Multiplication 145 9.3 Basic Hardware Multipliers 146 9.4 Multiplication of Signed Numbers 148 9.5 Multiplication by Constants 151 9.6 Preview of Fast Multipliers 153 Problems 153 References 156 10 HIGH-RADIX MULTIPLIERS 157 10.1 Radix-4 Multiplication 157 10.2 Modified Booth's Recoding 159 10.3 Using Carry-Save Adders 162 10.4 Radix-8 and Radix-16 Multipliers 164 10.5 Multibeat Multipliers 166 10.6 VLSI Complexity Issues 167 Problems 169 References 171 Contents 11 TREE AND ARRAY MULTIPLIERS 172 11.1 Full-Tree Multipliers 172 11.2 Alternative Reduction Trees 175 . 11.3 Tree Multipliers for Signed Numbers 178 11.4 Partial-Tree Multipliers 180 11.5 Array Multipliers 181 11.6 Pipelined Tree and Array Multipliers 185 Problems 186 References 189 12 VARIATIONS IN MULTIPLIERS 191 12.1 Divide-and-Conquer Designs 191 12.2 Additive Multiply Modules 193 12.3 Bit-Serial Multipliers 195 12.4 Modular Multipliers 200 12.5 The Special Case of Squaring 201 12.6 Combined Multiply-Add Units 203 Problems 204 References 207 PART IV DIVISION 13 BASIC DIVISION SCHEMES 211 13.1 Shift/Subtract Division Algorithms 211 13.2 Programmed Division 213 13.3 Restoring Hardware Dividers 216 13.4 Nonrestoring and Signed Division 218 13.5 Division by Constants 221 13.6 Preview of Fast Dividers 223 Problems 224 References 226 14 HIGH-RADIX DIVIDERS 228 14.1 Basics of High-Radix Division 228 14.2 Radix-2SRT Division 230 14.3 Using Carry-Save Adders 234 14.4 Choosing the Quotient Digits 236 14.5 Radix-4 SRT Division 238 Contents xi 14.6 General High-Radix Dividers 240 Problems 241 References 244 15 VARIATIONS IN DIVIDERS 246 15.1 Quotient Digit Selection Revisited 246 15.2 Using p-d Plots in Practice 248 15.3 Division with Prescaling 250 15.4 Modular Dividers and Reducers 252 15.5 Array Dividers 253 15.6 Combined Multiply/Divide Units 255 Problems 256 References 259 16 DIVISION BY CONVERGENCE 261 16.1 General Convergence Methods 261 16.2 Division by Repeated Multiplications 263 16.3 Division by Reciprocation 265 16.4 Speedup of Convergence Division 267 16.5 Hardware Implementation 269 16.6 Analysis of Lookup Table Size 270 Problems 272 References 275 PARTV REAL ARITHMETIC 17 FLOATING-POINT REPRESENTATIONS 279 17.1 Floating-Point Numbers 279 1 7.2 The ANSI/IEEE Floating-Point Standard 282 17.3 Basic Floating-Point Algorithms 284 1 7.4 Conversions and Exceptions 286 17.5 Rounding Schemes 287 1 7.6 Logarithmic Number Systems 291 Problems 293 References 296 18 FLOATING-POINT OPERATIONS 297 18.1 Floating-Point Adders/Subtractors 297 18.2 Pre- and Postshifting 300 xii Contents 18.3 Rounding and Exceptions 303 18.4 Floating-Point Multipliers 304 18.5 Floating-Point Dividers 306 18.6 Logarithmic Arithmetic Unit 307 Problems 308 References 311 19 ERRORS AND ERROR CONTROL 313 19.1 Sources of Computational Errors 313 19.2 Invalidated Laws of Algebra 316 19.3 Worst-Case Error Accumulation 318 19.4 Error Distribution and Expected Errors 320 19.5 Forward Error Analysis 322 19.6 Backward Error Analysis 323 Problems 324 References 327 20 PRECISE AND CERTIFIABLE ARITHMETIC 328 20.1 High Precision and Certiflability 328 20.2 Exact Arithmetic 329 20.3 Multiprecision Arithmetic 332 20.4 Variable-Precision Arithmetic 334 20.5 Error Bounding via Interval Arithmetic 336 20.6 Adaptive and Lazy Arithmetic 338 Problems 339 References 342 PART VI FUNCTION EVALUATION 21 SQUARE-ROOTING METHODS 345 21.1 The Pencil-and-Paper Algorithm 345 21.2 Restoring Shift/Subtract Algorithm 347 21.3 Binary Nonrestoring Algorithm 350 21.4 High-Radix Square-Rooting 352 21.5 Square-Rooting by Convergence 353 21.6 Parallel Hardware Square-Rooters 356 Problems 357 References 360 Contents xiii 22 THE CORDIC ALGORITHMS 361 22.1 Rotations and Pseudorotations 361 22.2 Basic CORDIC Iterations 363 22.3 CORDIC Hardware 366 22.4 Generalized CORDIC 367 22.5 Using the CORDIC Method 369 22.6 An Algebraic Formulation 372 Problems 373 References 376 23 VARIATIONS IN FUNCTION EVALUATION 378 23.1 Additive/Multiplicative Normalization 378 23.2 Computing Logarithms 379 23.3 Exponentiation 382 23.4 Division and Square-Rooting, Again 384 23.5 Use of Approximating Functions 386 23.6 Merged Arithmetic 388 Problems 389 References 393 24 ARITHMETIC BY TABLE LOOKUP 394 24.1 Direct and Indirect Table Lookup 394 24.2 Binary-to-Unary Reduction 395 24.3 Tables in Bit-Serial Arithmetic 397 24.4 Interpolating Memory 400 24.5 Trade-Offs in Cost, Speed, and Accuracy 402 24.6 Piecewise Lookup Tables 403 Problems 406 References 409 PART VII IMPLEMENTATION TOPICS 25 HIGH-THROUGHPUT ARITHMETIC 413 25.1 Pipelining of Arithmetic Functions 413 25.2 Clock Rate and Throughput 415 25.3 The Earle Latch 418 25.4 Parallel and Digit-Serial Pipelines 419 25.5 On-Line or Digit-Pipelined Arithmetic 421 25.6 Systolic Arithmetic Units 425 xiv Contents Problems 426 References 429 26 LOW-POWER ARITHMETIC 430 26.1 The Need for Low-Power Design 430 26.2 Sources of Power Consumption 432 26.3 Reduction of Power Waste 434 26.4 Reduction of Activity 436 26.5 Transformations and Trade-Offs 438 26.6 Some Emerging Methods 441 Problems 443 References 446 27 FAULT-TOLERANT ARITHMETIC 447 27.1 Faults, Errors, and Error Codes 447 27.2 Arithmetic Error-Detecting Codes 451 27.3 Arithmetic Error-Correcting Codes 455 27.4 Self-Checking Function Units 456 27.5 Algorithm-Based Fault Tolerance 458 27.6 Fault-Tolerant RNS Arithmetic 459 Problems 460 References 463 28 PAST, PRESENT, AND FUTURE 464 28.1 Historical Perspective 464 28.2 An Early High-Performance Machine 466 28.3 A Modern Vector Supercomputer 468 28.4 Digital Signal Processors 469 28.5 A Widely Used Microprocessor 472 28.6 Trends and Future Outlook 473 Problems 475 References 477 Index 479