Midterm Exam II

Name: __________________________________________

Instructions:

(31 pts) 1. Short Answer

1. 
   (5 pt) Describe the condition for an overflow to occur when executing MIPS instruction add $s0, $s1, $s2 .
   

2. 
   (10 pt) Instead of using a special hardware multiplier, it is possible to multiply using shift instructions and add instructions. This is particularly attractive when multiplying by small constants. Suppose we want to put 9 times the value of $s2 into $s3 ignoring any overflow that may occur. Give the minimal sequence of MIPS instructions to perform $s3  $s2 * 9 using only add instructions and shift instructions. As a reminder the syntax for the MIPS shift left logical (sll) instruction is
   

sll $t2, $s0, 8 #$t2 = $s0 << 8 bits

3. 
   (10 pt) For the VHDL implementation of a full adder shown below, when do the outputs cout and S settle at their final values (consider the worst case timing path with the worst case inputs)?
   

cout – 4ns

S – 7ns

4. 
   (3 pt) Give the key disadvantage of the single cycle MIPS datapath design?
   

Not all the instructions have the same length. Single cycle datapath imposes a uniform clock cycle time, which should be the slowest instruction execution length.

5. 
   (3 pt) What decimal number does this two’s complement binary number represent: 1111 1111 1111 1111 1111 1111 1111 1111_two?
   

-1

6. 
   (9 pt) Assume that the operation times for the major functional units in the single-cycle implementation of the MIPS datapath are the following:
   

• 
  Memory Units: 2ns
  

• 
  ALU: 2ns
  
• 
  Adder for PC+4: 1ns
  
• 
  Adder for branch address computation: 8ns
  

R-type instructions : 8 ns

lw instruction: 10 ns

sw instruction: 6 ns

beq instruction: 9 ns

j instruction: 2

(30 pts) 3. ALU Design

2. 
   ticks for a 2-input and, or, xor, nor to settle at its final output
   

6 ticks for a 6-input multiplexor to settle at its final output

8. 
   ticks from the latest arriving input for the sum and carry outputs
   

op = 000

B = 0001
To what MIPS instruction does this control setting correspond to? (You do not need to write down the formal instruction, rather, something like A+B will do) ____________________________A AND B __________________________(3 pt)

op = 100

B = 0001
What is the zero output value for this set of inputs? ­­­­ ____1_____________ (3 pt)

• 
  carry into MSB = 1 and carry out of MSB = 1
  
• 
  adding a negative (-1) and positive (1) cannot overflow.
  

When do the result outputs settle at their final values for the inputs shown below (ignoring the test for zero and for overflow)?

op = 101

B = 0000
What is the zero output value for this set of inputs? ________0___________ (2 pt)

To what MIPS instruction does this control setting correspond to? ___________________slt_________________________________________ (3 pt)

With the ALU design described in class (and shown in its 4-bit version on the previous page) we assumed that a subtraction operation had to be performed as part of the beq instruction. This would mean that we would have to wait for the subtraction operation to complete before selecting the output of the adder (through the multiplexor) and then testing the result bits for all zero.

If so, what would be the control bit setting for your new approach? (3 pt)

op = 010
With the timing model given, how long would it take for the zero output to settle using your new approach to beq? (3pt)

(30 pts) 4. Single Cycle Datapath Design

Your task is now to augment this single cycle MIPS datapath so that it can also perform the instruction jalr (jump and link register) as defined below.

Its functioning is to cause the datapath to unconditionally jump to the instruction whose address is in register rs and to save the address of the next instruction (the instruction following the jalr instruction in the code) in the register rd.

What new control signal(s) did you need to add and explain their basic function.

(3 pt)

jalr control signal that selects the correct input to the two additional muxes

write data input of the RegFile)

Give the setting for all the control signals (both previously existing and the one(s) you added) to execute the jalr. (10 pt)