Computer Systems: Arithmetical and Logical Unit PDF

Structure of Computer Systems Course 3 The Arithmetical and Logical Unit ALU- Arithmetical and Logical Unit Purpose: computes arithmetical and logical operations: ⚫ arithmetical: basic operations: add, subtract, multiply, division, modulo special...

Structure of Computer Systems Course 3 The Arithmetical and Logical Unit ALU- Arithmetical and Logical Unit Purpose: computes arithmetical and logical operations: ⚫ arithmetical: basic operations: add, subtract, multiply, division, modulo special functions: exponential, logarithm, sine, cosine, tangent, atangent, etc. ⚫ logical: AND, OR, NOT, inclusiveOR, exclusiceOR Types of arithmetic units: ⚫ integer arithmetic ⚫ floating point arithmetic (e.g. Intel’s co-processor) ⚫ signal processing arithmetic (e.g. with saturation MMX) ⚫ parallel arithmetic (MMX - integer, SSE2- floating point)  Addition most used operation all the other arithmetic operations are based on addition: ⚫ subtract – adding the complement ⚫ multiply – repetitive adding ⚫ division – repetitive subtraction and adding efficient implementation of adding operation: ⚫ influence directly all the other operations ⚫ efficiency: speed and cost (complexity)  Addition Basic (full) adder unit – one bit adder ⚫ inputs: xi, yi, Ci ⚫ outputs: Si = xi yi Ci Ci = xiyi + (xi  yi) Ci-1 ⚫ delay: 3* gate_delay xi yi Ci-1 xi yi   Ci One bit adder Ci-1 Si Ci Si  “n” bit adder with ripple carry n bit adder = n * (1 bit full adder) delay: n*3*gate_delay ⚫ example: n=32; gate_delay = 10 ns (TTL gate) => delay: 32*3*10ns ~= 1000 ns => fclk_max = 1/1000 ns = 106 =1MHz !!! xn-1 xn-2 x1 x0 X Y yn-1 yn-2 y1 y0 Cn-1 1 bit Cn-2 1 bit Cn-3 1 bit C0 1 bit C-1 n bit adder adder adder adder adder S1 S0 S Sn-1 Sn-2  Subtract subtract = adding with the second number’s 2th complement n bit add and subtract: ⚫ Add/Sub = 0 => adding ⚫ Add/Sub = 1 => subtraction xn-1 y xn-2 y x1 x0 n-1 n-2 y1 y0 Add/Sub     Cn-1 1 bit Cn-2 1 bit Cn-3 1 bit C0 1 bit adder adder adder adder Sn-1 Sn-2 S1 S0  Sequence of steps for adding Data Bus (D0-D15) 0 1 MUX Sel Clk Ld_A/ Control Ld_B/ unit Instr. Amp. Temp Reg. A Reg. B code Add/Sub Add&Sub Wr_m/ Step BUS SEL LD_A/ LD_B/ Add/Sub Wr_m/ Result 1 X 1 0 1 - 1 A 32 address lines => 2 32 = 4GB (TOO MUCH) ⚫ Solution: Multiply 8*8 bits in multiple steps to obtain multiply on 16, 32 or 64 bits Example: X= X15,8 X7,0 Y= Y15,8 Y7,0 P = X*Y = X7,0*Y7,0 + X15,8*Y7,0 *28 + X7,0*Y15,8 *28 + X15,8*Y15,8 *216 Observation: multiplies with 28 and 216 are achieved by placing the result in a proper binary position; also the first and the last partial products may be combined in a single 32 bit register with no adding required  Multiply with look-up table X15,8 X7,0*Y15,8 X15,8*Y7,0 X7,0*Y7,0 X15,0 M X7,0 U WrX X Memory A15,0 D15,0 Y15,8 Look-up X15,8*Y15,8 Y15,0 M table Y7,0 U X WrY Sel1 Sel0 MUX WrP1,2 WrP0 WrP3 Control unit Adder Sel2 WrAcc Accumulator  Multiply with look-up table Step WrX WrY WrP0 WrP1,2 WrP3 WrAcc Sel0 Sel1 Sel2 Description 1 1 1 0 0 0 0 0 0 0 Load operands 2 0 0 1 0 0 0 0 0 0 Write P0 3 0 0 0 0 1 0 1 1 0 Write P3 4 0 0 0 1 0 0 1 0 0 Write P1 5 0 0 0 0 0 1 0 1 0 Acc=P0+ P3 +P1 6 0 0 0 1 0 0 0 1 0 Write P2 7 0 0 0 0 0 1 0 0 1 Acc=Acc+P2 Multiply with look-up table requires only 7 steps instead of 16-20 it can be further optimized  Arithmetical operations in floating point (FP) representation Floating point representation of a number: ⚫ Used in case of very big or very small numbers ⚫ 3 fields for representation: Sign Exponent – magnitude of the number Mantissa – some significant figures (digits) of the number ⚫ IT IS NOT THE REPRESENTATION OF REAL NUMBERS from mathematics !!!!! ⚫ A lots of anomalies and precision problems: Operating with numbers having different magnitudes may generate errors caused by rounding: ⚫ M+m-M = 0 ; M-M+m = m Number with decimal parts, in most cases have no precise FP representation ⚫ Example: 0.3 has no precise representation in floating point Floating point adder/ subtracter X Shift right Inc/Dec S exponent mantissa Control < = > Compare Add & subtract unit S exponent mantissa Inc/Dec Shift right Add/Sub Y  Adding floating point numbers 1. Load the operands 2. Compare exponents (5 cases): ex = ey, add mantissas and copy the exponent ex > ey and (ex – ey) < number of bits in the mantissa, than the my mantissa is aligned by shifting it with ex-ey positions to the right; ex >> ey and (ex – ey) ≥ number of bits in the mantissa, than X is copied in the result (Y is too small); go to step 4 ex < ey and (ey – ex) < number of bits in the mantissa, than the mx mantissa is aligned by shifting it with ey-ex positions to the right; than mantissas are added ex Ue = 5V Ui=1.00 V; A=100 =>U e = 10V !!! – upper saturation  Add and Subtract with saturation X7,0 Y7,0 Add and subtract with saturation for unsigned 8 bit representation Add/Sub Add&Sub the result is selected with a multiplexer: Carry (C) = 0 => result correct Carry ⚫ FF 00 ⚫ C=1 and adding => overflow, result=FFh S1 ⚫ C=1 and subtract => underflow, result=00h 3 2 1 0 S0 MUX C Add/ Operation Result S1 S0 Sub 0 0 adding Correct X+Y 1 X S7,0 0 1 subtract Correct X-Y 1 X Add/Sub Add/Sub 1 0 adding Overflow FFh 0 1 S0 0 1 S1 0 1 1 1 subtract Underflow 00h 0 0 0 X X 0 1 1 C C 1 1 0 1 0 0 homework: do it for 2th complement