ALU

ALU Construction

Executing the AND operation on registers X and Y.

Addition in Logic Gates

x

y

Carry

Sum

0

0

0

0

0

1

0

1

1

0

0

1

1

1

1

0

Half Adder

• Carry = x AND y
• Sum = x XOR y

Full Adder

Must add in the carry bit of previous sum

x

y

cI

Carry

Sum

0

0

0

0

0

0

0

1

0

1

0

1

0

0

1

0

1

1

1

0

1

0

0

0

1

1

0

1

1

0

1

1

0

1

0

1

1

1

1

1

• Carry = yc_i+ xy + xc_i
• Sum = ~x~yc_i + ~xy~c_i + x~y~c_i + xyc_i

Ripple Carry Adder

8 bit addition using full adders

What simple modification of the above would allow for an ADD with Carry (ADWC) instruction?

Subtraction

We want to compute X-Y

1. X-Y = X + (-Y) , that is , convert subtraction to an addition problem by adding the negative of Y
2. X-Y = X + (~Y)+1 , but the negative is a 2's complement value which is found by taking the 1's complement of Y and adding one
3. The +1 can be accomplished by using an initial carry in on the least significant bit that normally is zero.
4. One's complement is the logical negation .Flipflops that are used to build registers conveniently have the complement (~Q) value of each bit!

Following is the modification to an adder circuit to implement subtraction. Shown is the circuit on the outputs of only one of the bits on the Y register. The line from the right is the control line from the control unit of the CPU to the ALU that the add operation is either an add or subtract. The 2-AND-OR-NOT gate combination is a classic circuit to select one of two inputs as the output.

Multiplication

Multiplication circuits are typically built of adders, shifters. Also need control circuits

There are many techniques to perform multiplication

• repeat addition
• shift and add
• variations on shift and add

Some simple analyses on multiplication

• costliest operation in the final analysis is the add operation
• shifting of bits and testing of bits are relatively quick compared to add
• try to minimize invoking the add operation. Subtraction costs the same as addition.

A. Repeat Addition

Example

  25 (MULTIPLICAND or "Q")
x 13 (MULTIPLIER or "M")
= 25 + 25 + 25 + ... + 25 (13 times)
= 325 (PRODUCT or "P")

Analysis

• number of iterations (and additions)= M, i.e., performance depends on size of M
• So for efficiency, noting multiplication is commutative, then if Q<M then swap Q and M before invoking the additions
• But, the multiplier must be positive; if not then negate Q and M and the above test really must be |Q|<|M|

Check out the subroutine MULT1 which performs repeat addition multiplication.

B. Shift and Add

Example

  25
x 13
  75 = 25+25+25
25   = 250 (25 shifted one digit place) 
 325

Analysis and observations

• number of iterations (and maximum number of additions) = sum of digits of M
• it is not worth checking for minimum sum of digits
• be sure the multiplier is positive; multiplicand can be left as negative if you are certain the sign is extended.
• We can add the summands as we go.
• As we perform multiplication by hand, we "shift" the multiplicand to the left to create our diagonal array of summands. If we add on the fly we can shift the partial product (partial sum) to the right.

  25
x 13
 +75
   7:5  shift partial product to right
 +25
  32:5

In a binary number system context

   11001
  x 1101 
   11001 add
  00000 shift Q, no add
 11001 shift Q, add
11001 shift Q, add
101000101

   11001
  x 1101 
  +11001     add
  >>11001    shift P
  +00000     no add
    11001
  >> 11001   shift P
  +11001     add
   1111101
  >>1111101  shift
  +11001    add
  101000101

Check out the subroutine MULT2 which performs shift and add multiplication.

C. Booth's Multiplication Algorithm

Want to treat positive and negative multipliers uniformly, i.e., no sign analysis

Want to performs fewer additions (and subtractions) than in add/shift algorithm if possible

Idea:

• A binary number is normally viewed as a sum of powers of 2
• 28 = 16+8+4 = 2⁴+2³+2² = 00011100₂
• Decode the multiplier into a series of alternating subtractions and additions of powers of two ("signed digit" number system)
• Use the decoding to calculate the product by a series of additions and subtractions

Signed digit system

Example

28 = 32-8+4 = 2⁵- 2³+2² = 0 0 1 0 -1 1 0 0

Also 28 = 32-4 = 2⁵ -2²= 0 0 1 0 0 -1 0 0

Signed number systems are redundant.

Negative numbers

• -28 = -32+8-4 = -2⁵+2³-2²= 0 0 -1 0 1 -1 0 0
• -28 = -32+4 = -2⁵+2²= 0 0 -1 0 0 1 0 0

negate the one's in the positive representation

Translating 2's complement to sign system

Scan right to left analyzing each pair of bits

00 -> 0
01 -> 1
10 -> -1
11 -> 0

Example

28 = 00011100.0 = 0 0 1 0 0 -1 0 0

-28 = 11100100.0 = 0 0 -1 0 1 -1 0 0

So 10 x 28 looks like:

         0  1  0  1  0
0  0  1  0  0 -1  0  0
       + 0  0  0  0  0  
  shift> 0  0  0  0  0 : 0  
       + 0  0  0  0  0
         0  0  0  0  0 : 0
  shift> 0  0  0  0  0 : 0  0 
       - 0  1  0  1  0
         1  0  1  1  0 : 0  0
  shift> 1  1  0  1  1 : 0  0  0
       + 0  0  0  0  0
         1  1  0  1  1 : 0  0  0
  shift> 1  1  1  0  1 : 1  0  0  0
       + 0  0  0  0  0
         1  1  1  0  1 : 1  0  0  0
  shift> 1  1  1  1  0 : 1  1  0  0  0
       + 0  1  0  1  0
         0  1  0  0  0 : 1  1  0  0  0
only shifts are left.  The above is binary for 280

C. Booth's Algorithm

Modification of shift and add

Scan M right to left and analyze bit pairs instead of the single bit:

• if 01 then add Q to P
• if 10 then subtract Q from P
• else (if 00 or 11) do nothing;
• in all cases shift the result (or Q)

Check out the subroutine MULT3 which performs Booth's algorithm.

D. Booth's Modified Algorithm

Take into account that immediately adjacent addition and subtraction pair can be replaced by one operation

Example

• 2³-2²= 2²
• 2ⁿ-2^n-1= 2^n-1
• -2ⁿ+2^n-1= -2^n-1

Now look at triples of bits instead of pairs (two pairs transform to one triple). Accounting for the shift that occurs, in the original algorithm:

00 -> Shift
01 -> Add then Shift
10 -> Sub then Shift
11 -> Shift

Replace with

000 -> Shift, Shift
001 -> Add, Shift, Shift
010 -> Add, Shift, Shift
011 -> Shift, Add, Shift
100 -> Shift, Sub, Shift
101 ->
110 ->
111 ->

Check out the subroutine MULT4 which performs Booth's modified algorithm.

Division

Division is repeat subtraction. Unfortunately, since division is not commutative there are few algorithms to efficiently perform subtraction.

Decimal example

   021 R1
13)274
    26
    14
    13
     1

Binary example

     000010101 R1
1101)100010010
      1101
       10000
        1101
          1110
          1101
             1

Restoring Technique

Shift next digit from dividend for subtraction

Subtract divisor from dividend'

If difference > 0 then set quotient bit

else clear quotient bit and add divisor back (restore) into dividend'

Repeat until all digits are shifted

Notes on implementation

Division is the inverse of multiplication.

Begin with double word dividend and a single word divisor.

Result in single word quotient and single word remainder. Note that overflow is possible.

As dividend shrinks (shifted) the quotient grows so that the dividend and quotient can share the register pair.

Examples

• 20/3 = 6 R2 or in binary: 10100/11 = 0110 R 0010

    R0     R1
0 0 0 1|0 1 0 0 initial
0 0 1 0|1 0 0:  shift (1)
0 0 1 0|1 0 0:0 sub/restore (1)
0 1 0 1|0 0:0   shift(2)
0 0 1 0|0 0:0 1 sub/set (2)
0 1 0 0|0:0 1   shift(3)
0 0 0 1|0:0 1 1 sub/set (3)
0 0 1 0:0 1 1   shift(4)
0 0 1 0:0 1 1 0 sub/restore (4)
remainder:quotient

Check out the subroutine RESDIV which performs restoring division.

Non-restoring division

Improvement: really don't need to restore quotient; instead, keep shifting and add rather than subtract.

Only when sub/add operation results in a positive dividend do we set quotient bit and switch back to subtract.

Sequence of operations in original algorithm in the loop after subtraction:

• IF dividend (A) is positive THEN shift and subtract divisor (M) = (2A-M)
• IF dividend (A) is negative THEN restore (A+M) then shift and subtract = 2(A+M)-M
• But 2(A+M)-M = 2A+M

Working through the example

• 10100/11 = 0110 R 0010

    R0      R1
0 0 0 1|0 1 0 0 initial
0 0 1 0|1 0 0:  shift (1)
1 1 1 1|1 0 0:0 sub/clear (1)
1 1 1 1|0 0:0   shift(2)
0 0 1 0|0 0:0 1 add/set (2)
0 1 0 0|0:0 1   shift(3)
0 0 0 1|0:0 1 1 sub/set (3)
0 0 1 0:0 1 1   shift(4)
1 1 1 1:0 1 1 0 sub/clear (4)
0 0 1 0:0 1 1 0 restore negative remainder
remainder:quotient

Check out the subroutine NONDIV which performs nonrestoring division.