G22.2233 L01 Introduction.1 Banikazemi, NYU, 2007CS G22.2233 Computer Systems Design Spring 2007Lecture 02: MIPS Arithmetic ReviewMohammad Banikazemi[Slides from Prof. Mary Jane Irwin, PSU Adapted fromComputer Organization and Design, Patterson & Hennessy, © 2005, UCB]G22.2233 L01 Introduction.2 Banikazemi, NYU, 2007Review: MIPS OrganizationProcessorMemory32 bits230wordsread/writeaddrread datawrite dataword address(binary)0…00000…01000…10000…11001…1100Register Filesrc1 addrsrc2 addrdst addrwrite data32 bitssrc1datasrc2data32registers($zero - $ra)323232323232555PCALU32 3232323201237654byte address(big Endian)FetchPC = PC+4DecodeExecAdd32324Add3232branch offsetG22.2233 L01 Introduction.3 Banikazemi, NYU, 2007Review: MIPS Addressing Modes1. Operand: Register addressingop rs rt rd functRegisterword operandop rs rt offset2. Operand: Base addressingbase registerMemoryword or byte operand3. Operand: Immediate addressingop rs rt operand4. Instruction: PC-relative addressingop rs rt offsetProgram Counter (PC)Memorybranch destination instruction5. Instruction: Pseudo-direct addressingop jump addressProgram Counter (PC)Memoryjump destination instruction||G22.2233 L01 Introduction.4 Banikazemi, NYU, 2007Because ease of use is the purpose, this ratio of function to conceptual complexity is the ultimate test of system design. Neither function alone nor simplicity alone defines a good design.The Mythical Man-Month, Brooks, pg. 43G22.2233 L01 Introduction.5 Banikazemi, NYU, 2007 32-bit signed numbers (2’s complement):0000 0000 0000 0000 0000 0000 0000 0000two= 0ten0000 0000 0000 0000 0000 0000 0000 0001two= + 1ten...0111 1111 1111 1111 1111 1111 1111 1110two= + 2,147,483,646ten0111 1111 1111 1111 1111 1111 1111 1111two= + 2,147,483,647ten1000 0000 0000 0000 0000 0000 0000 0000two= – 2,147,483,648ten1000 0000 0000 0000 0000 0000 0000 0001two= – 2,147,483,647ten...1111 1111 1111 1111 1111 1111 1111 1110two= – 2ten1111 1111 1111 1111 1111 1111 1111 1111two= – 1tenMIPS Number Representationsmaxintminint Converting <32-bit values into 32-bit valuesO copy the most significant bit (the sign bit) into the “empty” bits0010 -> 0000 00101010 -> 1111 1010O sign extend versus zero extend (lb vs. lbu) MSBLSBG22.2233 L01 Introduction.6 Banikazemi, NYU, 2007MIPS Arithmetic Logic Unit (ALU) Must support the Arithmetic/Logic operations of the ISAadd, addi, addiu, addusub, subu, negmult, multu, div, divusqrtand, andi, nor, or, ori, xor, xoribeq, bne, slt, slti, sltiu, sltu323232m (operation)resultABALU4zero ovf11 With special handling forO sign extend – addi, addiu andi, ori, xori, slti, sltiuO zero extend – lbu, addiu, sltiuO no overflow detected – addu, addiu, subu, multu, divu, sltiu, sltuG22.2233 L01 Introduction.7 Banikazemi, NYU, 2007Review: 2’s Complement Binary Representation2’sc binary decimal1000 -81001 -71010 -61011 -51100 -41101 -31110 -21111 -10000 00001 10010 20011 30100 40101 50110 60111 723-1 =-(23-1) =-23=1010complement all the bits1011and add a 1 Note: negate and invert are different! NegateG22.2233 L01 Introduction.8 Banikazemi, NYU, 2007Review: A Full Adder1-bit Full AdderABScarry_incarry_outS = A ⊕ B ⊕ carry_in (odd parity function)carry_out = A&B | A&carry_in | B&carry_in(majority function)How can we use it to build a 32-bit adder? How can we modify it easily to build an adder/subtractor?A B carry_in carry_out S00 0 0 000 1 0 101 0 0 101 1 1 010 0 0 110 1 1 011 0 1 011 1 1 1G22.2233 L01 Introduction.9 Banikazemi, NYU, 2007A 32-bit Ripple Carry Adder/Subtractor Remember 2’s complement is justz complement all the bitsz add a 1 in the least significant bitA 0111 → 0111 B - 0110→ +1-bit FAS0c0=carry_inc11-bit FAS1c21-bit FAS2c3c32=carry_out1-bit FAS31c31. . .A0A1A2A31B0B1B2B31add/subB0control(0=add,1=sub)B0 if control = 0, !B0 if control = 10001100111 0001G22.2233 L01 Introduction.10 Banikazemi, NYU, 2007Overflow Detection Overflow: the result is too large to represent in 32 bits Overflow occurs whenO adding two positives yields a negative O or, adding two negatives gives a positiveO or, subtract a negative from a positive gives a negativeO or, subtract a positive from a negative gives a positive On your own: Prove you can detect overflow by:O Carry into MSB xor Carry out of MSB, ex for 4 bit signed numbers111101011001110011+7301–611001011+–4–5710G22.2233 L01 Introduction.11 Banikazemi, NYU, 2007 Need to support the logic operation (and,nor,or,xor)O Bit wise operations (no carry operation involved)O Need a logic gate for each function, mux to choose the output Need to support the set-on-less-than instruction (slt)O Use subtraction to determine if (a – b) < 0 (implies a < b)O Copy the sign bit into the low order bit of the result, set remaining result bits to 0 Need to support test for equality (bne, beq)O Again use subtraction: (a - b) = 0 implies a = bO Additional logic to “nor” all result bits together Immediates are sign extended outside the ALU with wiring (i.e., no logic needed)Tailoring the ALU to the MIPS ISAG22.2233 L01 Introduction.12 Banikazemi, NYU, 2007Shift Operations Also need operations to pack and unpack 8-bit characters into 32-bit words Shifts move all the bits in a word left or rightsll $t2, $s0, 8 #$t2 = $s0 << 8 bitssrl $t2, $s0, 8 #$t2 = $s0 >> 8 bitsop rs rt rd shamt functNotice that a 5-bit shamt field is enough to shift a 32-bit value 25–1 or 31 bit positions Such shifts are logical because they fill with zerosG22.2233 L01 Introduction.13 Banikazemi, NYU, 2007Shift Operations, con’t An arithmetic shift (sra) maintain the arithmetic correctness of the shifted value (i.e., a number shifted right one bit should be ½ of its original value; a number shifted left should be 2 times its original value)O so sra uses the most significant bit (sign bit) as the bit shifted inO note that there is no need for a sla when using two’s complement number representationsra $t2, $s0, 8 #$t2 = $s0 >> 8 bits The shift operation is implemented by hardware separate from the ALUO using a barrel shifter (which would takes lots of gates in discrete logic, but is pretty easy to implement in VLSI)G22.2233 L01 Introduction.14 Banikazemi, NYU, 2007Multiply Binary multiplication is just a bunch of right shifts and