# Midterm Exam II

 Date 31.01.2017 Size 67.58 Kb.

14:332:331 Midterm Exam II

14:332:331
Midterm Examination #2
Fall 2002

Name: __________________________________________

S.S.#: _______________________________

 1 40 2 30 3 30 Total 100

Instructions:

This exam contains 3 questions. It is closed book and notes. Calculators are allowed. Do all of your work on the attached sheets.
Please make sure that you finish all the questions.

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

CarryIn MSB is not equal to CarryOut MSB

1. (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

sll \$s3, \$s2, 3

1. (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

1. (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.

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

-1

1. (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

Assuming that the multiplexors, control unit, PC accesses, sign extension unit, and wires have no delay, what would be the minimum cycle time? (Hint: You may want to refer to the datapath shown on page 8).
The minimum cycle time = longest instruction execution length

R-type instructions : 8 ns

lw instruction: 10 ns

sw instruction: 6 ns

beq instruction: 9 ns

j instruction: 2

as a result, the minimum cycle time = 10 ns.

(30 pts) 3. ALU Design

Consider a 4-bit version of MIPS ALU shown on the next page. Here add/subt determines whether an addition (add/subt = 0) or subtraction (add/subt = 1) takes place and op selects the multiplexor output (assume that the top input is selected by an op of 000, etc.). Assume that it takes

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

4 ticks for a 4-input nor to settle at its final output

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

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

of a 1-bit full adder to settle at their final output
When do the result outputs settle at their final values for the inputs shown below (ignoring the test for zero and for overflow)?
add/subt = 0 outputs settle at tick _____10________ (3 pt)

op = 000

A = 1111

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)

When do the result outputs settle at their final values for the inputs shown below (ignoring the test for zero and for overflow)?
add/subt = 0 outputs settle at tick ______40_______ (3 pt)

op = 100

A = 1111

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

Does this operation overflow? ___NO______ If so, why; if not, why not?(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)?

add/subt = 1 outputs settle at tick ________40_____ (3 pt)

op = 101

A = 1111

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.

Is there a way to do it faster (with the hardware shown)? ____yes__­­­­­_______ (1 pt)

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)

outputs settle at tick ___________14______

(30 pts) 4. Single Cycle Datapath Design

Give the setting for the control signals for the single cycle datapath shown on the next page when executing a sw instruction. (10 pt)

 Control Signal Setting Control Signal Setting RegDst X ALUOp1 0 Jump 0 ALUOp0 0 Branch 0 MemWrite 1 MemRead X ALUSrc 1 MemtoReg X RegWrite 0

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.

jalr rs, rd 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.

Augment the single cycle MIPS datapath shown on the next page to also handle the jalr instruction. You may only use additional 2-to-1 multiplexors, additional data interconnects, and additional 1-bit control signals. Mark a line that is no longer connected with an X somewhere along its length where the disconnect should occur. (7pt) on figure

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

when the instruction is a jalr (src1 from the RegFile to PC and PC+4 to

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)

 Control Signal Setting Control Signal Setting RegDst 1 MemWrite 0 Jump X ALUSrc X Branch X RegWrite 1 MemRead X 1 MemtoReg X ALUOp1 X ALUOp0 X

Page of