Number Systems andComputer ArithmeticCounting to four billiontwo fingers at a timeCSE 141, S2'06Jeff Brown

What do all those bits mean now?bits (011011011100010 .01)datainstructionnumberR-formatI-format .signed.CSE 141, S2'06integerunsigned.text chars.floating pointsingle precision.double precision.Jeff Brown

Questions About Numbers How do you represent––––negative numbers?fractions?really large numbers?really small numbers? How do you– do arithmetic?– identify errors (e.g. overflow)? What is an ALU and what does it look like?– ALU arithmetic logic unitCSE 141, S2'06Jeff Brown

Review: Binary NumbersConsider a 4-bit binary 0120010601103001170111Examples of binary arithmetic:3 2 53 3 61 00110010CSE 141, S2'06 1100110011Jeff Brown

Negative Numbers? We would like a number system that provides––––––obvious representation of 0,1,2.uses adder for additionsingle value of 0equal coverage of positive and negative numberseasy detection of signeasy negationCSE 141, S2'06Jeff Brown

Some Alternatives Sign Magnitude -- MSB is sign bit, rest the same-1 1001-5 1101 One’s complement -- flip all bits to negate-1 1110-5 1010CSE 141, S2'06Jeff Brown

Two’s Complement Representation 2’s complement representation of negative numbers – Take the bitwise inverse and add 1Biggest 4-bit Binary Number: 7Smallest 4-bit Binary Number: -8Decimal-8-7-6-5-4-3-2-101234567CSE 141, S2'06Two’s Complement 00110100010101100111Jeff Brown

Two’s Complement ArithmeticDecimal2’s Complement BinaryDecimal2’s Complement 40100-5101150101-6101060110-7100170111-81000 Examples: 7 - 6 7 (- 6) 1 CSE 141, S2'06011110103 - 5 3 (- 5) -2 00111011Jeff Brown

Some Things We Want To Know About OurNumber System negation sign extension– 3 0011, 00000011, 0000000000000011– -3 1101, 11111101, 1111111111111101 overflow detection0101 0110CSE 141, S2'0656Jeff Brown

Overflow Detection0 0 010100102001130101511101117001131010-6 1 1001100-41110-21010-60101100-41011-501117So how do we detect overflow?CSE 141, S2'06Jeff Brown

InstructionFetchArithmetic -- The heartof instruction ExecuteALUresultResultStore32b32NextInstructionCSE 141, S2'06Jeff Brown

Designing an Arithmetic Logic UnitALUopA3NZeroALUNResultOverflowBNCarryOut ALU Control Lines (ALUop)–––––000001010110111CSE 141, S2'06FunctionAndOrAddSubtractSet-on-less-thanJeff Brown

A One Bit ALU This 1-bit ALU will perform AND, OR, and ADD1 1001100-41110-21010-6CSE 141, S2'06Jeff Brown

A 32-bit ALU1-bit ALUCSE 141, S2'0632-bit ALUJeff Brown

How About Subtraction? Keep in mind the following:– (A - B) is the same as: A (-B)– 2’s Complement negate: Take the inverse of every bit and add 1 Bit-wise inverse of B is !B:– A - B A (-B) A (!B 1) A !B 11 CSE 141, S2'06011011010011011Jeff Brown

Overflow Detection Logic Carry into MSB ! Carry out of MSB– For a N-bit ALU: Overflow CarryIn[N - 1] XOR CarryOut[N - UCarryIn3 CarryOut2A3B31-bitALUXYX XOR Y000011101110OverflowResult3CarryOut3CSE 141, S2'06Jeff Brown

Zero Detection Logic Zero Detection Logic is just one BIG NOR gate– Any non-zero input to the NOR gate will cause its output to be zeroCarryIn0A0B0A1B11-bitALUResult0CarryIn1 -bitALUZeroResult2CarryIn3 CarryOut2Result31-bitALUCarryOut3CSE 141, S2'06Jeff Brown

Set-on-less-than Do a subtract use sign bit– route to bit 0 of result– all other bits zeroCSE 141, S2'06Jeff Brown

Full ALUgive signals for:neg operadd?sub?and?or?beq?slt?sign bit (adder output from bit 31)CSE 141, S2'06Jeff Brown

The Disadvantage of Ripple Carry The adder we just built is called a “Ripple Carry Adder”– The carry bit may have to propagate from LSB to MSB– Worst case delay for an N-bit RC adder: 2N-gate t0CarryOut01-bitALUCarryInResult1ACarryIn2 CarryOut11-bitResult2ALUCarryIn3 CarryOut21-bitResult3ALUBCarryOut3Ripple carry adders are slow. Faster addition schemes are possible that accelerate themovement of the carry from one end to the other.CarryOut

MULTIPLY Paper and pencil example:MultiplicandMultiplierProduct ?m bits x n bits m n bit productBinary makes it easy:–– x100010110 place 0 ( 0 x multiplicand)1 place multiplicand ( 1 x multiplicand)we’ll look at a couple of versions of multiplication hardwareCSE 141, S2'06Jeff Brown

MULTIPLY HARDWAREVersion 1 64-bit Multiplicand reg, 64-bit ALU, 64-bit Product reg,32-bit multiplier regCSE 141, S2'06Jeff Brown

Multiply AlgorithmVersion 1Multiplier0101Multiplicand0000 0110CSE 141, S2'06Product0000 0000Jeff Brown

Observations on MultiplyVersion 1 1 clock per cycle 100 clocks per multiply– Ratio of multiply to add 100:1 1/2 bits in multiplicand always 0 64-bit adder is wasted 0’s inserted in left of multiplicand as shifted least significant bits of product never changed once formed Instead of shifting multiplicand to left, shift product to right? Wasted space (zeros) in product register exactly matchesmeaningful bits of multiplier at all times. Combine?CSE 141, S2'06Jeff Brown

MULTIPLY HARDWAREVersion 2 32-bit Multiplicand reg, 32 -bit ALU, 64-bit Product reg,(0-bit Multiplier reg)Multiplicand Product01100000 01010011 00100001 10010011 11000001 1110CSE 141, S2'06Jeff Brown

Observations on MultiplyVersion 2 2 steps per bit because Multiplier & Product combined32-bit adderMIPS registers Hi and Lo are left and right half of ProductGives us MIPS instruction MultUWhat about signed multiplication?– easiest solution is to make both positive & remember whether tocomplement product when done.CSE 141, S2'06Jeff Brown

Divide: Paper & PencilDivisor 10001101010QuotientDividendRemainderSee how big a number can be subtracted, creating quotient bit on each step– Binary 1 * divisor or 0 * divisor Dividend Quotient * Divisor RemainderCSE 141, S2'06Jeff Brown

DIVIDE HARDWAREVersion 1 64-bit Divisor reg, 64-bit ALU, 64-bit Remainder reg,32-bit Quotient regCSE 141, S2'06Jeff Brown

Divide AlgorithmVersion 1 Takes n 1 steps for n-bit Quotient & Rem.Quotient0000Divisor0011 0000Remainder0000 0111Start1. Subtract the Divisor register from theRemainder register, and place the result in theRemainder register.Remainder 0Remainder 0Test Remainder2a. Shift the Quotient register to the leftsetting the new rightmost bit to 1.2b. Restore the original value by adding theDivisor register to the Remainder register, andplace the sum in the Remainder register. Alsoshift the Quotient register to the left, setting thenew least significant bit to 0.3. Shift the Divisor register right 1 bit.33rd repetition?No: 33 repetitionsYes: 33 repetitionsCSE 141, S2'06DoneJeff Brown

Divide Hardware Version 1 Again, 64-bit adder is unnecessary. Quotient grows as remainder shrinksCSE 141, S2'06Jeff Brown

DIVIDE HARDWAREVersion 2 32-bit Divisor reg, 32 -bit ALU, 64-bitRemainder reg,(0-bit Quotient reg)CSE 141, S2'06Jeff Brown

Observations on DivideVersion 2 Same Hardware as Multiply: just need ALU to add or subtract, and 63-bit register to shift left or shift rightHi and Lo registers in MIPS combine to act as 64-bit register for multiplyand divideSigned Divides: Simplest is to remember signs, make positive, andcomplement quotient and remainder if necessary– Note: Dividend and Remainder must have same sign– Note: Quotient negated if Divisor sign & Dividend sign disagreeCSE 141, S2'06Jeff Brown

Key Points Instruction Set drives the ALU design ALU performance, CPU clock speed driven by adder delay Multiplication and division take much longer than addition,requiring multiple addition steps.CSE 141, S2'06Jeff Brown

So Far Can do logical, add, subtract, multiply, divide, . But.– what about fractions?– what about really large numbers?CSE 141, S2'06Jeff Brown

Binary Fractions10112 1x23 0x22 1x21 1x20so.101.0112 1x22 0x21 1x20 0x2-1 1x2-2 1x2-3e.g.,.75 3/4 3/22 1/2 1/4 .11CSE 141, S2'06Jeff Brown

Recall Scientific Notationexponentdecimal point23 6.02 x 10signMantissa-241.673 x 10radix (base)Issues: Arithmetic ( , -, *, / ) Representation, Normal form Range and Precision Rounding Exceptions (e.g., divide by zero, overflow, underflow) Errors Properties ( negation, inversion, if A B then A - B 0 )CSE 141, S2'06Jeff Brown

Floating-Point NumbersRepresentation of floating point numbers in IEEE 754 standard:1823single precisionsignSEexponent:excess 127binary integer(actual exponent is e E - 127)Mmantissa:sign magnitude, normalizedbinary significand w/ hiddeninteger bit: 1.M0 E 255N (-1)S 2E-127 (1.M)0 0 00000000 0 . . . 0-1.5 1 01111111 10 . . . 00325 101000101 X 2 1.01000101 X 28 0 10000111 01000101000000000000000.02 .0011001101100. X 20 1.1001101100. X 2-3 0 01111100 1001101100. range of about 2 X 10-38 to 2 X 1038 always normalized (so always leading 1, thus never shown) special representation of 0 (E 00000000) (why?) can do integer compare for greater-than, signCSE 141, S2'06Jeff Brown

What do you notice? 01.5 * 2-1001.75 * 2-1001.5 * 21001.75*21000 00000000 0000000000 0 00011011 1000000000 0 00011011 1100000000 0 11100011 1000000000 0 11100011 1100000000 Does this work with negative numbers, as well?CSE 141, S2'06Jeff Brown

Double Precision Floating PointRepresentation of floating point numbers in IEEE 754 standard:11120double precisionsignSEexponent:excess 1023binary integeractual exponent is e E - 1023M32Mmantissa:sign magnitude, normalizedbinary significand w/ hiddeninteger bit: 1.M0 E 2048N (-1)S 2E-1023 (1.M) 52 ( 1) bit mantissa range of about 2 X 10-308 to 2 X 10308CSE 141, S2'06Jeff Brown

Floating Point Addition How do you add in scientific notation?9.962 x 104 5.231 x 102 Basic Algorithm1. Align2. Add3. Normalize4. RoundCSE 141, S2'06Jeff Brown

FP Addition HardwareCSE 141, S2'06Jeff Brown

Floating Point Multiplication How do you multiply in scientific notation?(9.9 x 104)(5.2 x 102) 5.148 x 107 Basic Algorithm1. Add exponents2. Multiply3. Normalize4. Round5. Set SignCSE 141, S2'06Jeff Brown

FP Accuracy Extremely important in scientific calculations Very tiny errors can accumulate over time IEEE 754 FP standard has four rounding modes– always round up (toward )– always round down (toward - ) – truncate– round to nearest in case of tie, round to nearest even Requires extra bits in intermediate representationsCSE 141, S2'06Jeff Brown

Extra Bits for FP Accuracy Guard bits -- bits to the right of the least significant bit ofthe significand computed for use in normalization (couldbecome significant at that point) and rounding. IEEE 754 has two extra bits and calls them guard andround.CSE 141, S2'06Jeff Brown

When Keepin' it Real Goes Wrong Machine FP only approximates the real numbers Just calculating extra bits of precision is often enough– but not always!– knowing when, how to tell, and what to do about it can be subtle– analysis involves algorithm, program implementation, and hardware wkahan/– "How JAVA's Floating-Point Hurts Everyone Everywhere"– "Roundoff Degrades an Idealized Cantilever"– (and lots more)CSE 141, S2'06Jeff Brown

Key Points Floating Point extends the range of numbers that can berepresented, at the expense of precision (accuracy). FP operations are very similar to integer, but with pre- andpost-processing. Rounding implementation is critical to accuracy over time.CSE 141, S2'06Jeff Brown