Assignment 8, Solutions

Part of the homework for 22C:60 (CS:2630), Fall 2011
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Background: Consider the logic circuit shown to the right. If the function inputs on the left, f₁ to f₇ are all set to one, the circuit behaves exactly like the adder circuit shown in the notes.
Assume, in the following, that 32 of these modified adders are ganged up with the carry connections as usual for adders and used to combine two 32-bit binary numbers a and b to produce a 32-bit result s. All f inputs are set to one unless specified otherwise in the following questions:
a) Suppose f₃, f₅ and f₆ are set to zero, and c₀ is also set to zero. What effect does this have the carry outputs from the modified adder? (0.5 points)

Wires and gates forced to zero are darkened in the figure. Setting c₀ to zero forces and gates 1, 3, 5 and 7 to output zero. Setting f₆ to zero forces and gate 6 to output zero. The net result is that c₁ will be zero, and as this propagates across all the stages of the adder, all of the c_i will be zero.

b) Suppose f₃, f₅ and f₆ are set to zero, and c₀ is also set to zero, as in part a). What is s as a function of a and b. (0.5 points)

Wires and gates forced to zero are darkened in the figure. Only and gates 2 and 4 remain capable of outputting a one. Gate 2 will output one if a_i is zero and b_i is one. Gate 4 will output one if a_i is one and b_i is zero. These ones are combined at s_i, where the result is equivalent to an exclusive or.
As it turns out, setting f₃ and f₅ to zero was unnecessary. These could have been left set to one for the same result.

Exercises from Chapter 9 of the Notes:

d) (0.5 points).

What happens if you multiply numbers together that generate a result of 2³² or greater? All the versions of multiply given in the notes prior to this question correctly compute the least significant 32 bits of the result. Any bits above the least significant 32 bits are lost.

g) (0.5 points)

Multiply R3 by 60 -- 60 = 111100
        MOVE    R1,R3
        ADDSL   R3,R1,1         ; R3 * 11
        ADDSL   R3,R1,1         ; R3 * 111
        ADDSL   R3,R1,1         ; R3 * 1111
        SL      R3,2            ; R3 * 111100
Multiply R3 by 60 -- 60 = (2 × 3) × (2 × 5) = 3 × 4 × 5 so:
        ADDSL   R3,R3,1         ; R3 * 3
        SL      R3,2            ; R3 * 4
        ADDSL   R3,R3,2         ; R3 * 5
The second solution is faster in this case. Generally speaking, you can't predict which approach will be faster until you both factor the number and count the number of one bits in the binary representation.

n) (1.0 points).

MULTIPLYS:              ; link through R1
                        ; R3 = multiplicand on entry, product on return
                        ; R4 = multiplier on entry, high 32-bits of product
                        ; R5 = temporary copy of multiplicand, destroyed
                        ; R6 = loop counter, destroyed
        MOVE    R5,R3           ; set aside multiplicand
        CLR     R3              ; product = 0
        SL      R4,1            ; multiplier = multiplier<<1, C=sign bit
        BCR     MULSEI          ; if (sign bit was 1) {
        SUB     R3,R0,R5        ;   product = product - multiplicand
MULSEI:                         ; }
        LIS     R6,31           ; loopcount = 31
MULSLP:                         ; do {
        SL      R3,1            ;   multipler[]product <<= 1
        ADDC    R4,R4           ;   -- a 64-bit shift, C holds the high bit
        BCR     MULSEIL         ;   if (top bit was 1) {
        ADD     R3,R3,R5        ;     product = product + multiplicand;
MULSEIL:                        ;   }
        ADDSI   R6,-1           ;   loopcount = loopcount - 1
        BGT     MULLP           ; } while (loopcount > 0)
        JUMPS   R1              ; return