MASON CS 365 - Arithmetic and Logic Unit

Unformatted text preview:

1CS365 1Arithmetic and Logic UnitCS 365 Lecture 5Prof. Yih HuangCS365 2Inside a ProcessorData Cache Instruction Cache(Internal) BusInteger Arithmetic CircuitsFloating Point Arithmetic CircuitsBranchControlLogicRegisters2CS365 3Arithmetic and Logic Unit (ALU) The part of a processor circuit that actually gets the computations done.323232operationresultabALUCS365 4 Bits are just bits (no inherent meaning) Binary numbers (base 2) ⇒ decimal: 0...2n-1 ASCII codes Of course it gets more complicated:numbers are finite (overflow)fractions and real numbersnegative numbers How do we represent negative numbers?Numbers3CS365 5 Sign Magnitude: One's Complement Two'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 Most of the modern architectures use two’s complement.Possible RepresentationsCS365 6Two’s Complement Numbers 0010 =  1010 =  -10 in 8-bit two’s complement = X3X2X1X0202122−−−−234CS365 70000 0000 0000 0000 0000 0000 0000 0000 = 00000 0000 0000 0000 0000 0000 0000 0001 = +10000 0000 0000 0000 0000 0000 0000 0010 = +2...0111 1111 1111 1111 1111 1111 1111 1110 = +2,147,483,6460111 1111 1111 1111 1111 1111 1111 1111 = +2,147,483,6471000 0000 0000 0000 0000 0000 0000 0000 = –2,147,483,6481000 0000 0000 0000 0000 0000 0000 0001 = –2,147,483,6471000 0000 0000 0000 0000 0000 0000 0010 = –2,147,483,646...1111 1111 1111 1111 1111 1111 1111 1101 = –31111 1111 1111 1111 1111 1111 1111 1110 = –21111 1111 1111 1111 1111 1111 1111 1111 = –132-bit Signed NumbersTwo’s ComplementDecimalCS365 8 Negating a two's complement number: invert all bits and add 1– remember: “negate” and “invert” are different! Exercises (in 6 bits)– Negate 12– Negate -5Two's Complement Operations5CS365 9Sign Extensions 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 10104 bit number 8 bit equivalentCS365 10Additions & Subtractions Just like regular binary numbers0010+ 01101111+ 00011111+ 11110010- 01101111- 00011111- 11116CS365 11Overflows Result too large to store in finite-size computer words– e.g., adding two n-bit numbers does not always yields an n-bit number Depends on the kind of numbers you have in mind: Signed or unsigned0010+ 01101000- 0001CS365 12 No overflow when adding a positive and a negative number No overflow when signs are the same for subtraction Overflows when the value affects the sign:Detecting Overflow>0>0<0A−B<0<0>0A−B>0<0<0A+B<0>0>0A+BresultBA7CS365 13 Architecture and case dependent Solution 1: just remember it and leave the handing to software.– The condition/flag register of IA32 Solution 2: exception/interrupt– Control jumps to predefined address for exception– Interrupted address is saved for possible resumption– Used by MIPSEffects of OverflowCS365 14Discussion IA32 provides an addc (add with carry) instruction. What is its use?8CS365 15 Problem: Consider a logic function with three inputs: A, B, and C.Output D is true if at least one input is trueOutput E is true if exactly two inputs are trueOutput F is true only if all three inputs are true Show the truth table for these three functions. Show the Boolean equations for the three functions. Show an implementation consisting of inverters, AND, and OR gatesReview: Boolean Algebra & GatesCS365 16Design An Overflow Detector Inputs: SA (sign of A), SB (Sign of B), OP (operation, 0 for add, 1 for sub). Output: OF=0 no overflow, 1 overflow Truth Table: Boolean equation for OF. A circuit design of OF according to the equation above.111011101001110010100000OFSBSAOP9CS365 17 Selects one of the inputs to be the output, based on a control input Note: we call this 2-input multiplexer even though it actually has three inputsReview: The MultiplexerMultiplexorOutputSelectA BCS365 18More Inputs The general case: N-input multiplexer needs log2N select lines.  You should be able to design its logic circuit.MultiplexorOutputSelectA B C D210CS365 19Second Exercise Let us build a one-bit ALU to support addition and logic or.– Operation: 0 for add 1 for oroperationresultabALUCS365 20Solution Truth Table Sum of product11CS365 21Supporting MIPS Logic Instructions MIPS provides bit-wise and, or, xor, and nor instructions. Input operation (3 bits) determine the output.operationresultabALU3CS365 2232-bit ALU Both inputs A and B are 32 bit wide.– Size of the truth table ? Rather we will just cascade 32 1-bit ALU.– How about carries ?– We need to refine the spec of the 1-bit ALU12CS365 23Two Solutions Truth table and sum of product Use multiplexerCS365 241-bit Adder How could we build a 1-bit ALU for add, and, or? How could we build a 32-bit ALU?+ABCinCout= AB + ACin+ BCinSum = A xor B xor Cin13CS365 25Building a 32-bit ALUb02ResultOperationa1CarryInCarryOutR esu lt31a3 1b3 1R esu lt0C arr yIna0b0R esu lt1a1b1R esu lt2a2b2O pe ratio nA LU 0C arryInC arryO u tA LU 1C arryInC arryO u tA LU 2C arryInC arryO u tA LU 31C arryInCS365 26 Two's complement approach: negate b and add. How do we negate? A clever solution:What about subtraction (a – b) ?02ResultOperationa1CarryInCarryOut01Binvertb14CS365 27 Need to support the set-on-less-than instruction (slt)– remember: slt is an arithmetic instruction– produces a 1 if rs < rt and 0 otherwise– use subtraction: (a-b) < 0 implies a < b Need to support test for equality (beq $t5, $t6, offset)– use subtraction: (a-b) = 0 implies a = bTailoring the ALU to the MIPSCS365 28Supporting slt03ResultOp erationa1CarryInCarryO ut01Binvertb2Less03ResultOperationa1CarryIn01Bin vertb2LessSe tOverflo w de tectionOverflowa.b.15CS365 29Seta310ALU0Result0CarryIna0Result1a10Result2a20Operationb31b0b1b2Result31OverflowBinvertCarryInLessCarryInCarryOutALU1LessCarryInCarryOutALU2LessCarryInCarryOutALU31LessCarryInCS365 30Test for equality Notice control lines:Seta310Result0a0Result1a10Result2a20Operationb31b0b1b2Result31OverflowBnegateZeroALU0LessCarryInCarryOutALU1LessCarryInCarryOutALU2LessCarryInCarryOutALU31LessCarryIn000 = and001 = or010 = add110 = subtract111 = slt Ouput zero=1 when


View Full Document

MASON CS 365 - Arithmetic and Logic Unit

Download Arithmetic and Logic Unit
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Arithmetic and Logic Unit and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Arithmetic and Logic Unit 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?