1Computer System DesignLecture 12: Computer ArithmeticProf. R. Iris BaharEN164February 23, 2007Reading: Appendix I, I.1, I.2, I.8 EN164Lecture 11-2Arithmetic• Where we've been:–Performance (seconds, cycles, instructions)– Instruction Set Architecture– Basic pipelining• What's up ahead:–Implementing the ArchitectureIM Re g DM RegALUEN164Lecture 11-3Arithmetic• We start with the Arithmetic and Logic Unit323232operationresultabALUEN164Lecture 11-4Numbers• Bits are just bits (no inherent meaning)–conventions define relationship between bits and numbers• Binary numbers (base 2)–0000 0001 0010 0011 0100 0101 0110 0111 1000 1001...– decimal: 0...2n-1• Of course it gets more complicated:–numbers are finite (overflow)– fractions and real numbers– negative numbers• How do we represent negative (or signed) numbers?• Which bit patterns will represent which numbers?–Octal and hexadecimal numbers– Floating-point numbersEN164Lecture 11-5Representing Signed Numbers• Sign Magnitude: 1's Complement 2's Complement000 = +0 000 = +0 000 = +0001 = +1 001 = +1 001 = +1010 = +2 010 = +2 010 = +2011 = +3 011 = +3 011 = +3100 = -0 100 = -3 100 = -4101 = -1 101 = -2 101 = -3110 = -2 110 = -1 110 = -2111 = -3 111 = -0 111 = -1• Issues: balance, number of zeros, ease of operations.• 2’s complement is best.EN164Lecture 11-72's Complement Operations• How do you negate a 2's complement number?–Invert all bits and add 1– Remember: “Negate” and “invert” are different operations.• Numbers are negated, bits are inverted.• How do you convert an n bit number to a 2n bit number?–MIPS 16 bit immediate gets converted to 32 bits for arithmetic– copy the most significant bit (the sign bit) into the other bits0010 Æ 0000 00101010 Æ 1111 1010– "sign extension"2EN164Lecture 11-8Addition and Subtraction• Unsigned numbers add/subtract just like in grade school 0111 0111 0110+ 0110 - 0110 - 01011101 0001 0001• 2's complement operations are also easysubtraction is done using addition of negated number0111+ 101010001(result is 0001, carry bit is set)• 2's complement overflow (result is out of number range)adding two 4-bit numbers does not yield an 4-bit number0111+ 00111010(result is -6, overflow bit is set) EN164Lecture 11-9Detecting Overflow• Adding a positive and a negative number can never cause an overflow• Similarly, no overflow is possible when signs are the same for subtraction• Overflow occurs when the value affects the sign:–overflow when adding two positives yields a negative – or, adding two negatives gives a positive– or, subtract a negative from a positive and get a negative– or, subtract a positive from a negative and get a positive• Consider the operations A + B, and A – B–Can overflow occur if B is 0 ? – Can overflow occur if A is 0 ?EN164Lecture 11-10Effects of Overflow• An exception (interrupt) occurs–Control jumps to predefined address for exception handler routine– Interrupted address is saved for possible resumption• Details based on software system / language–example: flight control vs. homework assignment• Some instructions may allow you to ignore overflow–e.g., MIPS instructions: addu, addiu, subu– Some multimedia/DSP operations do not care about overflowEN164Lecture 11-14Different Implementations• No clear best way to build something–Don't want too many inputs to a single gate– Don’t want to have to go through too many gates– For our purposes, ease of comprehension is important• Let's look at a 1-bit ALU for addition:How can we build a 32-bit ALU for AND, OR and ADD?cout= a b + a cin+ b cinsum = a ⊕ b ⊕ cinSumCarryInCarryOutaba b cincoutsum0 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1EN164Lecture 11-1532-bit ALU for AND, OR & ADDResult31a31b31Result0CarryIna0b0Result1a1b1Result2a2b2OperationALU0CarryInCarryOutALU1CarryInCarryOutALU2CarryInCarryOutALU31CarryIn1-bit ALU:b02ResultOperationa1CarryInCarryOutEN164Lecture 11-16What about subtraction (a – b)?• Two's complement approach: Just negate b and add.• Use carry-in for LSB for part of the negation02ResultOperationa1CarryInCarryOut01bsubtractWhat’s another way of implementing this function?3EN164Lecture 11-19Chained 1-bit adders are slow• A 32-bit ALU is much slower than a 1-bit ALU.–Carry must ripple through all 32 bits to determine result• c1= b0c0+ a0c0+ a0b0• c2= b1c1+ a1c1+ a1b1• c3= b2c2+ a2c2+ a2b2• c4= b3c3+ a3c3+ a3b3• How do you get rid of the ripple effect?–Generate the “carries” a different wayEN164Lecture 11-20Carry-lookahead adder• A carry-out signal is “1” when it is propagated to generated by a single bit cell: –When would we always generate a carry? gi= aibi– When would we propagate the carry? pi= ai+ bic1= g0+ p0c0c2= g1+ p1c1c2= g1+p1g0+p1p0c0c3= g2+ p2c2c3= g2+p2g1+p2p1g0+p2p1p0c0c4= g3+ p3c3c4= ...• Note that cionly depends on ai, bi, and c0• But there is a practical limit to the number of inputs used to generate