Parhami B. Computer Arithmetic Algorithms and Hardware Designs

Oxford University Press, 2000. — 510 p.Advances in computer architecture over the past two decades have allowed the performance of digital computer hardware to continue its exponential growth, despite increasing technological difficulty in speed improvement at the circuit level. This phenomenal rate of growth, which is expected to continue in the near future, would not have been possible without theoretical insights, experimental research, and toolbuilding efforts that have helped transform computer architecture from an art into one of the most quantitative branches of computer science and engineering. Better understanding of the various forms of concurrency and the development of a reasonably efficient and user-friendly programming model have been key enablers of this success story.
The downside of exponentially rising processor performance is an unprecedented increase in hardware and software complexity. The trend toward greater complexity is not only at odds with testability and certifiability but also hampers adaptability, performance tuning, and evaluation of the various trade-offs, all of which contribute to soaring development costs. A key challenge facing current and future computer designers is to reverse this trend by removing layer after layer of complexity, opting instead for clean, robust, and easily certifiable designs, while continuing to try to devise novel methods for gaining performance and ease-of-use benefits from simpler circuits that can be readily adapted to application requirements.
In the computer designers' quest for user-friendliness, compactness, simplicity, high performance, low cost, and low power, computer arithmetic plays a key role. It is one of oldest subfields of computer architecture. The bulk of hardware in early digital computers resided in accumulator and other arithmetic/logic circuits. Thus, first-generation computer designers were motivated to simplify and share hardware to the extent possible and to carry out detailed cost-performance analyses before proposing a design. Many of the ingenious design methods that we use today have their roots in the bulky, power-hungry machines of 30-50 years ago.
In fact computer arithmetic has been so successful that it has, at times, become transparent. Arithmetic circuits are no longer dominant in terms of complexity; registers, memory and memory management, instruction issue logic, and pipeline control have become the dominant consumers of chip area in today's processors. Correctness and high performance of arithmetic circuits are routinely expected, and episodes such as the Intel Pentium division bug of the mid 1990s are indeed rare.
The preceding context is changing for several reasons. First, at very high clock rates, the interfaces between arithmetic circuits and the rest of the processor become critical. Arithmetic units can no longer be designed and verified in isolation. Rather, an integrated design optimization is required, which makes the development even more complex and costly. Second, optimizing arithmetic circuits to meet design goals by taking advantage of the strengths of new technologies, and making them tolerant to the weaknesses, requires a reexamination of existing design paradigms. Finally, incorporation of higher-level arithmetic primitives into hardware makes the design, optimization, and verification efforts highly complex and interrelated.
This is why computer arithmetic is alive and well today. Designers and researchers in this area produce novel structures with amazing regularity. Carry-lookahead adders comprise a case in point. We used to think, in the not so distant past, that we knew all there was to know about carry-lookahead fast adders. Yet, new designs, improvements, and optimizations are still appearing. The IEEE 754 standard floating-point format has removed many of the concerns with compatibility and error control in floating-point computations, thus resulting in new designs and products with mass-market appeal. Given the arithmetic-intensive nature of many novel application areas (such as encryption, error checking, and multimedia), computer arithmetic will continue to thrive for years to come.Number Representation
Numbers and Arithmetic ~ What is computer arithmetic? ~ Motivating Examples ~ Numbers and their encodings ~ Fixed-radix positional number systems ~ Number radix conversion ~ Classes of number representations
Representing Signed Numbers ~ Signed-magnitude representation ~ Biased representations ~ Complement representations ~ Two's- and 1's-complement numbers ~ Direct and indirect signed arithmetic ~ Using signed positions or signed digits
Redundant Number Systems ~ Coping with the carry problem ~ Redundancy in computer arithmetic ~ Digit sets and digit-set conversions ~ Generalized signed-digit numbers ~ Carry-free addition algorithms ~ Conversions and support functions
Residue Number Systems ~ RNS representation and arithmetic ~ Choosing the RNS moduli ~ Encoding and decoding of numbers ~ Difficult RNS arithmetic operations ~ Redundant RNS representations ~ Limits of fast arithmetic in RNS
Addition/Subtraction
Basic Addition and Counting ~ Bit-serial and ripple-carry adders ~ Conditions and exceptions ~ Analysis of carry propagation ~ Carry completion detection ~ Addition of a constant: counters ~ Manchester carry chains and adders
Carry-Lookahead Adders ~ Unrolling the carry recurrence ~ Carry-lookahead adder design ~ Ling adder and related designs ~ Carry determination as prefix computation ~ Alternative parallel prefix networks ~ VLSI implementation aspects
Variations in Fast Adders ~ Simple carry-skip adders ~ Multilevel carry-skip adders ~ Carry-select adders ~ Conditional-sum adder ~ Hybrid designs and optimizations ~ Modular two-operand adders
Multi-Operand Addition ~ Using two-operand adders ~ Carry-save adders ~ Wallace and Dadda trees ~ Parallel counters and compressors ~ Adding multiple signed numbers ~ Modular multioperand adders
Multiplication
Basic Multiplication Schemes ~ Shift/add multiplication algorithms ~ Programmed multiplication ~ Basic hardware multipliers ~ Multiplication of signed numbers ~ Multiplication by constants ~ Preview of fast multipliers
High-Radix Multipliers ~ Radix-4 multiplication ~ Modified Booth's recoding ~ Using carry-save adders ~ Radix-8 and radix-16 multipliers ~ Multibeat multipliers ~ VLSI complexity issues
Tree and Array Multipliers ~ Full-tree multipliers ~ Alternative reduction trees ~ Tree multipliers for signed numbers ~ Partial-tree and truncated multipliers ~ Array multipliers ~ Pipelined tree and array multipliers
Variations in Multipliers ~ Divide-and-conquer designs ~ Additive multiply modules ~ Bit-serial multipliers ~ Modular multipliers ~ The special case of squaring ~ Combined multiply-add units
Division
Basic Division Schemes ~ Shift/subtract division algorithms ~ Programmed division ~ Restoring hardware dividers ~ Nonrestoring and signed division ~ Division by constants ~ Radix-2 SRT division
High-Radix Dividers ~ Basics of high-radix division ~ Using carry-save adders ~ Radix-4 SRT division ~ General high-radix dividers ~ Quotient-digit selection ~ Using p-d plots in practice
Variations in Dividers ~ Division with prescaling ~ Overlapped quotient-digit selection ~ Combinational and array dividers ~ Modular dividers and reducers ~ The special case of reciprocation ~ Combined multiply/divide units
Division by Convergence ~ General convergence methods ~ Division by repeated multiplications ~ Division by reciprocation ~ Speedup of convergence division ~ Hardware implementation ~ Analysis of lookup table size
Real Arithmetic
Floating-Point Representations ~ Floating-point numbers ~ The ANSI/IEEE floating-point standard ~ Basic floating-point algorithms ~ Conversions and exceptions ~ Rounding schemes ~ Logarithmic number systems
Floating-Point Operations ~ Floating-point adders/subtractors ~ Pre- and postshifting ~ Rounding and exceptions ~ Floating-point multipliers and dividers ~ Fused-multiply-add units ~ Logarithmic arithmetic unit
Arithmetic Errors and Error Control ~ Sources of computational errors ~ Invalidated laws of algebra ~ Worst-case error accumulation ~ Error distribution and expected errors ~ Forward error analysis ~ Backward error analysis
Precise and Certifiable Arithmetic ~ High precision and certifiability ~ Exact arithmetic ~ Multiprecision arithmetic ~ Variable-precision arithmetic ~ Error bounding via interval arithmetic ~ Adaptive and lazy arithmetic
Function Evaluation
Square-Rooting Methods ~ The pencil-and-paper algorithm ~ Restoring shift/subtract algorithm ~ Binary non-restoring algorithm ~ High-radix square-rooting ~ Square-rooting by convergence ~ Fast hardware square-rooters
The CORDIC Algorithms ~ Rotations and pseudorotations ~ Basic CORDIC iterations ~ CORDIC hardware ~ Generalized CORDIC ~ Using the CORDIC method ~ An algebraic formulation
Variations in Function Evaluation ~ Additive/multiplicative normalization ~ Computing logarithms ~ Exponentiation ~ Division and square-rooting, again ~ Use of approximating functions ~ Merged arithmetic
Arithmetic by Table Lookup ~ Direct and indirect table lookup ~ Binary-to-unary reduction ~ Tables in bit-serial arithmetic ~ Interpolating memory ~ Piecewise lookup tables ~ Multipartite table methods
Implementation Topics
High-Throughput Arithmetic ~ Pipelining of arithmetic functions ~ Clock rate and throughput ~ The Earle latch ~ Parallel and digit-serial pipelines ~ On-line or digit-pipelined arithmetic ~ Systolic arithmetic units
Low-Power Arithmetic ~ The need for low-power design ~ Sources of power consumption ~ Reduction of power waste ~ Reduction of activity ~ Transformations and trade-offs ~ New and emerging methods
Fault-Tolerant Arithmetic ~ Faults, errors, and error codes ~ Arithmetic error-detecting codes ~ Arithmetic error-correcting codes ~ Self-checking function units ~ Algorithm-based fault tolerance ~ Fault-tolerant RNS arithmetic
Reconfigurable Arithmetic ~ Programmable logic devices ~ Adder designs for FPGAs ~ Multiplier and divider designs ~ Tabular and distributed arithmetic ~ Function evaluation on FPGAs ~ Beyond fine-grained devices
Appendix: Past, Present, and Future