Computer Organiza0on and Design Sample Test

Computer Organiza0on and Design Sample Test
Part I. Multiple choice questions
Please select one answer for each question by circling the index of the answer. 3 points for each
question.
1. The binary representation of -21
en in 8 bits in 2’s complement is
(a) 1011 1011
(b) 1110 1011
(c) 1101 1011
(d) None of the above.
b
2. The single precision floating point representation of 3.875
en is
(a) 0 10000000 11110000000000000000000
(b) 0 10000000 11111000000000000000000
(c) 0 10000001 01110000000000000000000
(d) None of the above.
a
3. Assume the current values in
$t0 and $t1 are 0 and 1, respectively. What will be the value in
$t0 after the following instructions?
xor $t0, $t0, $t1
ori $t0, $t0, 6
(a) 0.
(b) 6.
(c) 7.
(d) None of the above.
c
4. Assume the current values in
$t0 and $t1 are 0 and 1, respectively. What will be the value in
$t0 after the following instructions?
sll $t0, $t1, 3
sub $t0, $t0, $t1
(a) 0.
(b) 6.
(c) 7.
(d) None of the above.
c
5. Assume the content of word array
A is 0,1,2,3,4,5,6,7,8,9 and its starting address is
currently in
$t0. What will be the value in $t0 after the following instructions?
addi $t0, $t0, 20
lw $t0, 8($t0)
(a) 4
(b) 7
(c) 8
(d) None of the above.
b
6. When the processor runs to this code segment, which of the following statements is true?

addi $t0, $t0, 16
jal P6fun
lw $t1, -4($t0)

P6fun: ori $t0, $0, 0
jr $ra
(a) The function P6fun is not following MIPS calling conventions.
(b) The code will not run correctly.
(c) Both of the above.
(d) None of the above.
b
7. We used 2-1 selectors extensively in our MIPS processor design. Suppose you have to build a
4-1 selector with only 2-1 selectors. What is the minimum number of 2-1 selectors needed?
(a) 2.
(b) 3
(c) 4.
(d) None of the above.
b
8. Please read the following Verilog module, where
Dff1 is the D flipflop module we used in
homework and the class:
module statem (clk, O);
input clk;
output [1:0] O;
wire D1, D0, Q1, Q0, Q1bar, Q0bar;
assign D0 = Q1bar;
Dff1 C0 (D0, clk, Q0, Q0bar);
assign D1 = Q0;
Dff1 C1 (D1, clk, Q1, Q1bar);
assign O[1] = Q1;
assign O[0] = Q0;
endmodule
Which of the following statements is true?
(a) It generates a sequence of 01320132…
(b) It generates a sequence of 0303…

(c) It generates a sequence of 021021…
(d) None of the above
a
9. The following datapath supports the
R-type, lw, sw, and beq instructions. Which of the
following statements is true?
(a) The datapath also supports
addi.
(b) The datapath also supports
jr.
(c) Both of the above.
(d) None of the above.
a
10. The following datapath supports the
R-type, lw, sw, and beq instructions, where the 2-1
MUX have been given indices shown in the figure. When the instruction being executed is
lw $t0, 8($t1)
what are the values of the control signals of the 2-1 MUX in the order from MUX1 to MUX4?
(a) 0110
(b) 1011
(c) 0101
(d) None of the above
C
11. Consider the same datapath as Problem 11 that supports the
R-type, lw, sw, and beq
instructions. When the instruction being executed is
beq $t0, $t1, L1
which of the control signals of the 2-1 MUX can be set as “don’t care”?
(a) MUX 1, 4
(b) MUX 2, 3, 4
(c) MUX 1
(b) None of the above

a
12. Consider the same datapath as Problem 11
. Suppose $t0 is holding 0, $t1 is holding 1, when
the following instruction is encountered:
beq $t0, $t1, L1
Suppose the control signal for a 2-1 MUX is 0 if we do not care about its value. What will be the
stable values showing at ports
WriteData of the register file and WriteData of the data
memory during the execution of this instruction?
(a) -1 and 1.
(b) 0 and 1.
(c) -1 and 0.
(d) None of the above.
a
13. Consider the single-cycle CPU that supports
R-type, lw, sw, and beq. Suppose the current
instruction is
add $t0, $t1, $t2. Which of the following statements is true about the time
when the output of the ALU first equals
$t1+$t2?
(a) Immediately after the rising edge of the clock in the cycle of this instruction.
(b) Somewhere in the middle of the clock cycle of this instruction.
(c) Immediately after the rising edge of the clock in the cycle of the next instruction.
(d) None of the above.
b
14. Consider the processor that supports
R-type, lw, sw, and beq. Suppose we want to add a
new instruction called
swr rs, rt, rd which changes the memory content at address rs+rt
to the value of rd, which of the following statements is true?
(a) The new instruction can be supported by only modifying the logic of the control signals.
(b) The new instruction can be supported by 1) modifying the datapath, e.g., adding some wires
and 2-1 MUX, and 2) modifying the logic of the control signals.

(c) The new instruction can be supported by 1) adding an additional ALU, 2) modifying the
datapath, e.g., adding some wires and 2-1 MUX, and 3) modifying the logic of the control
signals.
(d) None of the above.
d
Part II. Short answer questions
Problem 1 (16 points). Please complete the code segments by writing exactly one real instruction
above each line (keep in mind that some pseudo instructions may result in more than one real
instruction). In some cases, part of the instruction has been given, and you would just need to complete it.
a) (4 points) Please write two instructions to set $t1 as $t0 times 7, assuming $t0 is a positive
integer and no overflow will occur :
sll $t1, $t0, 3
sub $t1, $t1, $t0
b) (4 points) Please write two instructions to overwrite element 3 in an array (the first element is
element 0) with 99, where the starting address of the array is in
$s0 (you many modify $t0):
ori $t0, $0, 99
sw $t0, 12($s0)
c) (4 points) The following code is supposed test if the least significant bit of $t0 is 0, and if so, add
4 to
$t0, otherwise do no change to $t0 (you many modify $t1):
andi $t1, $t0, 1
bne $t1, $0, L1
addi $t0, $t0, 4
L1: (the next instruction)

d) (4 points) The following code is supposed to implement a loop that scans the numbers in an
array, two consecutive numbers in each iteration, while the starting address of the array is in
$s0. The exiting is that in an iteration, the two numbers are the same.
ori $t0, $0, 0
ps1dL0:sll $t1, $t0, 2
add $t1, $t1, $s0
lw $t2, 0($t1)
lw $t3,
4($t1)
addi $t0, $t0, 1
bne $t2, $t3, ps1dL0
Problem 2 (8 points) Design a circuit that takes three bits X2, X1, X0 as input, and produces one bit
Y as output, where Y is 1 if and only if (X2, X1, X0) as an unsigned binary number is between 1 and
5, inclusive, but not 4. Please complete the truth table and use the Karnaugh map to simplify the circuit.

X2 X1 X0 Y
0 0 0
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0
1 0 1 1
1 1 0
1 1 1

X2X1
X0
00 01 11 10

0
1
1
1 1 1

~X2X1 + ~X1X0
Problem 3 (4 points) Please read the following transition diagram and complete the next state table.
Assume states S0, S1, S2, and S3 are encoded as 00, 01, 10, and 11, respectively.

Q1 Q0 X D1 D0
0 0 0 0 1
0 0 1 1 1
0 1 0 0 1

S0 S1
S3 S2
X=1
X=0
X=1
X=0
X=1
X=0
X=1 X=0

Each row must exactly match to get 0.5 points
Problem 4 (6 points) Suppose we need to design a circuit that has two inputs, clk and X, and produces
one output bit
Y. X may change every clock cycle, where the change happens at the falling edge of the
clock. The circuit samples
X at every rising edge of the clock. Y should be 1 if the last 5 bits of X are
“11010” from the least recent to the most recent.
Please write down the names of the states as
S0, S1,… , and so on, and clearly describe the
meanings of each state
. Please draw the state transition diagram of this circuit. Close to an arc, show
X=0 or X=1.

0 1 1 1 1
1 0 0 0 0
1 0 1 0 1
1 1 0 1 0
1 1 1 1 1

X=1
S2
S3
S0
S1
S4
X=0 X=1
X=1
X=0
X=0
X=1
X=1
X=0
X=1
X=0
S5
X=1
X=0

Problem 5 (16 points) Design a MIPS processor supporting only the sw and the AAA rs, rt, rd
instruction. The AAA rs, rt, rd instruction does the following:
rd will be rs + data memory value at address rt
if rd is 0 after this instruction, the next PC will be rt
For this problem, assume
The opcode of sw is 000000 and the opcode of AAA is 100000.
(a) (10 points) Please design the datapath of this processor, add 2-1 MUX when necessary. Please
show clearly the indices of the bits near the wires
. Please give clear indices to the 2-1 MUXes
starting from 1.
(b) (3 points) Please determine the values of he control signals of the 2-1 MUXes by filling in the
table. In case of “don’t care”, write down “X.” Assume other control signals have been generated
correctly.
(c) (3 points) Please write down the logic functions of the control signals of the 2-1 MUXes.Certain
bits in the instruction can be denoted, for example, as
ins[31]. When deriving the logic
functions, if the value of a signal is “don’t care” under a certain condition, assume it
should be 0.

sw AAA (rd will not
be 0)
AAA (rd will be 0)
MUXCtrl1
MUXCtrl2
MUXCtrl3