csc258final12f
UNIVERSITY OF TORONTO
Faculty of Arts and Science
December 2012 Examinations
CSC258H1S: Computer Organization
Duration: 3 hours
No Aids Allowed
Last Name: _______________________________________
First Name: _______________________________________
Student Number: __________________________________
Instructor: Steve Engels
Total: / 155
/ 52
/ 18
/ 21 Part A:
Part B:
Part C:
Mark Breakdown Instructions:
• Write your name on every page of this exam.
• Do not open this exam until you hear the signal
to start.
• Have your student ID on your desk.
• No aids permitted other than writing tools. Keep
all bags and notes far from your desk before the
exam begins.
• There are 6 questions on 18 pages. When you hear
the signal to start, make sure that your exam is
complete before you begin.
• Read over the entire exam before starting.
• If you use any space for rough work or have to
user the overflow page, clearly indicate the
section(s) that you want marked.
/ 14 Part D:
/ 20 Part E:
/ 30 Part F:
2 (continued)
Student Number: __________________
Answer the following questions in the space provided. When providing a written answer, write as
clearly and legibly as possible. Marks will not be awarded to unreadable answers.
Part A: Short Answer (21 marks)
1. How many instructions could fit into a 256 byte memory unit, given a 32-bit architecture?
(2 marks)
2. How many address bits are needed to specify each byte in a 512 byte memory unit? (1 mark)
a) 256 b) 64
c) 32 d) 8
3. How many minterms could you have in a circuit with three inputs and two flip-flops? (1 mark)
4. True or False? MOSFETs act as a switch by creating a conductive channel between the two
n-type sections in a p-type substrate, or vice versa. (1 mark)
5. What are the HI and LO registers used for in the context of integer division? (2 marks)
6. Assume that wires have already been declared for a, b and c. In the space below, show TWO
different statements in Verilog that set c high when a and b are low. (2 marks)
True False
a) 512 b) 8
c) 32 d) 9
3 (continued)
Student Number: __________________
8. In p-type semiconductors, what are “holes”? (1 mark)
9. How many bits do you shift a binary number in order to divide it by 4? (1 mark)
10. Why are the addresses of all MIPS instructions divisible by 4? (1 mark)
11. What do the following output signals from the ALU signify? (4 marks)
C: _______________ V: __________________
N: _______________ Z: __________________
7. Consider the finite state machine shown below. The output of this circuit goes high
whenever it is in State C or State E. In the spaces below, indicate the operation that this finite
state machine performs, and how many flip-flops this will need. (5 marks)
Operation: _____________________
_______________________________
Number of flip-flops: _______________
A
B
C
D
E
0
0
1
1
1 1
0
1 0
0
a) absent electrons b) positive charge carriers
c) protons d) where you plant silicon flowers
4 (continued)
Student Number: __________________
Part B: Design and Analysis (18 marks)
1. In the space below, draw a circuit whose behaviour matches the following waveform. (4 marks)
input1
Clock
output
input2
2. Which of the circuits below have equivalent behaviour? Draw lines that connect any
circuits that match. (6 marks)
Y
B
C
Y
B
B
Y
C
B
A
B
C
Y
A
B
C
Y
B
C
C
A
A
C
Y B
C
A
Student Number: __________________
4. Given the following circuit, show what the output
waveform diagram. Assume that Q
Clock
Q0
Q2
Y
T Q0
Q Clock
1
Q1
3. Draw gates into the following diagram
5 Student Number: __________________
circuit, show what the output value of Q0, Q1, Q2
waveform diagram. Assume that Q0, Q1 and Q2 start with initial values of zero
T Q1
Q
T Q2
Q
Draw gates into the following diagram to implement a subtractor circuit
(continued)
2 and Y will be in the
start with initial values of zero. (6 marks)
Y
to implement a subtractor circuit. (2 marks)
Student Number: __________________
1. In the datapath diagram below, connect the following
affect. (8 marks)
2. For the following write signal diagram, describe what each labeled time segment is called,
and the purpose of each segment during a memory write operation
tSA: _____________________________________________________________
tAW: _____________________________________________________________
tSD: _____________________________________________________________
tHD: _____________________________________________________________
IorD MemRead IRWrite
Part C: Processors (52 marks)
6 Student Number: __________________
below, connect the following signals to the units that they
For the following write signal diagram, describe what each labeled time segment is called,
and the purpose of each segment during a memory write operation. (8
: _____________________________________________________________
: _____________________________________________________________
_____________________________________________________________
: _____________________________________________________________
MemWrite MemToReg PCSource
: Processors (52 marks)
(continued)
the units that they
For the following write signal diagram, describe what each labeled time segment is called,
8 marks)
: _____________________________________________________________
: _____________________________________________________________
_____________________________________________________________
: _____________________________________________________________
PCWrite PCSource RegDst
7 (continued)
Student Number: __________________
3. In the space below, perform Booth’s Algorithm on the binary values A=10110 and B=01101.
Show your steps in the space provided. (6 marks)
4. Verify your answer above by writing the decimal values for A, B and the final product in the
spaces below. (2 marks)
A =
B =
Product =
P =
Step 1:
Step 2:
Step 3:
Step 4:
Step 5:
8 (continued)
Student Number: __________________
5. For the following assembly language instructions, write the equivalent machine code
instruction in the space provided. You might find the reference information in the appendix
helpful for this question. (10 marks)
a) addu $t2, $t0, $t1
b) lw $t0, 20($s0)
c) jal top (where top is at hexadecimal address 0xFF00)
6. For the following machine code instructions, provide the equivalent assembly language
instruction in the space provided. (6 marks)
a) 00111001000000100000000011111111
b) 00000010000001000100000000100011
c) 00100111111000000000000000000000
9 (continued)
Student Number: __________________
7. For each of the processor tasks below, indicate what the values of the following control unit
signals will be by filling in the boxes next to each signal with the signal values. (12 marks)
• If a control signal doesn’t affect the operation, fill in its value with an X.
• For ALUOp, if you don’t know the values, just write what kind of operation is taking place.
Reduce the program counter by the value stored in $t0.
Fetch the next instruction from the address in the program counter.
Add 64 to $s0 and store the result back in $s0.
PCWrite PCWriteCond IorD MemRead MemWrite
MemToReg IRWrite PCSource ALUOp
ALUSrcA ALUSrcB RegWrite
PCWrite PCWriteCond IorD MemRead MemWrite
MemToReg IRWrite PCSource ALUOp
ALUSrcA ALUSrcB RegWrite
PCWrite PCWriteCond IorD MemRead MemWrite
MemToReg IRWrite PCSource ALUOp
ALUSrcA ALUSrcB RegWrite
10 (continued)
Student Number: __________________
Consider the piece of Verilog code on the right.
1. In one sentence, describe what function this
code performs. (4 marks)
2. Given your answer to part 1, what input signal is
missing from this device? (2 marks)
3. In the space below, write a Verilog module called counter that takes in input signals called
clock, reset and enable, and has a 4-bit output signal called value. (3 marks)
• Make the value output increment if enable is on when the clock goes high (3 marks)
• Implement an asynchronous reset that is also positive-edge triggered. (2 marks)
Part D: Verilog (14 marks)
module foo(a, b, s, r);
input [31:0] a, b;
input [2:0] s;
output reg [31:0] r;
always @(*) begin
case(s[2:0])
3’b000: r = a;
3’b001: r = a + b;
3’b010: r = a – b;
3’b011: r = a – 1;
3’b100: r = a & b;
3’b101: r = a | b;
3’b110: r = a ^ b;
3’b111: r = ~a;
endcase
end
endmodule
11 (continued)
Student Number: __________________
1. Consider the following state machine and flip-flop assignments below. Assume that the
input to this state machine is a single input called X.
Fill in the truth table below with the values that correspond to the FSM above. (8 marks)
F1 F0 X F1 F0
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Part E: Finite State Machines (20 marks)
A
B C
D
0
0
1
1 1
1
0
0
Flip-Flop Assignments
State A � F1 = 0 F0 = 0
State B � F1 = 0 F0 = 1
State C � F1 = 1 F0 = 1
State D � F1 = 1 F0 = 0
12 (continued)
Student Number: __________________
2. Given the truth table values on the previous page, fill in the Karnaugh map shown below,
and circle the largest minterm groupings possible. (6 marks)
3. Given the Karnaugh map groupings from the previous part, write the boolean equations
that express these groupings, and draw the resulting circuit diagram that implements this
behaviour in the space below. (6 marks)
F1·F0 F1·F0 F1·F0 F1·F0
X
X
F1·F0 F1·F0 F1·F0 F1·F0
X
X
F1:
F0:
13 (continued)
Student Number: __________________
1. In the spaces provided below, write the assembly language instruction(s) that corresponds
to each of the tasks provided. (12 marks total)
a) Perform a right arithmetic shift on the value in $t0. The number of bits to shift $t0 by is
stored in $s0. The result will be stored back into $t0. (3 marks)
b) Load half a word from a memory address stored at $a0, and store that value in register
$t0. The upper bits of $t0 should be filled with zeroes. (3 marks)
c) Jump back to the instruction at location top if the value in $t4 is anything other than zero.
(3 marks)
d) Take the value that is already stored in $t0, and set all of its bits to zero except for the last
3 digits, which are kept as their original values. (3 marks)
Part F: Assembly Language (30 marks)
14 (continued)
Student Number: __________________
Consider the assembly language program in the box below.
2. For each line in the code, provide a short descriptive comment on the right (6 marks)
3. In the space below, provide a one-sentence description of the overall task this code is trying
to perform. (2 marks)
4. One of the lines has a bug in it. What would need to be changed in order for this operation
to be correct? (2 marks)
.data
list: .word 3, 0, 1, 2, 6, -2, 4, 7, 3, 7
.text
main: addi $s0, $zero, list #
addi $t9, $zero, 10 #
top: lw $t1, 0($s0) #
lw $t2, 4($s0) #
sub $t3, $t2, $t1 #
bgtz $t3, inc #
sw $t2, 0($s0) #
sw $t1, 4($s0) #
inc: addi, $s0, $s0, 4 #
subi $t9, $t9, 1 #
bgtz $t9, top #
end: jr $ra #
15 (continued)
Student Number: __________________
5. In the space below, write a short assembly language
program that is a translation of the program on the
right. You can assume that i has been placed on the top
of the stack, and should be replaced by the return value
before returning to the calling program. Make sure that
you comment your code so that we understand what
you’re doing. (8 marks)
int make_even (int i) {
if (i % 2 == 1)
return i-1;
else
return i;
16 (continued)
Student Number: __________________
Register values : Processor role
• Register 0 ($zero): value 0.
• Register 1 ($at): reserved for the assembler.
• Registers 2-3 ($v0, $v1): return values
• Registers 4-7 ($a0-$a3): function arguments
• Registers 8-15, 24-25 ($t0-$t9): temporaries
• Registers 16-23 ($s0-$s7): saved temporaries
• Registers 28-31 ($gp, $sp, $fp, $ra)
Reference Information
ALU arithmetic input table:
Select Input Operation
S1 S0 Y Cin=0 Cin=1
0 0 All 0s G=A G=A+1
0 1 B G=A+B G=A+B+1
1 0 B G=A-B-1 G=A-B
1 1 All 1s G=A-1 G=A
Register table:
Instruction Op/Func Syntax
add 100000 $d, $s, $t
addu 100001 $d, $s, $t
addi 001000 $t, $s, i
addiu 001001 $t, $s, i
div 011010 $s, $t
divu 011011 $s, $t
mult 011000 $s, $t
multu 011001 $s, $t
sub 100010 $d, $s, $t
subu 100011 $d, $s, $t
and 100100 $d, $s, $t
andi 001100 $t, $s, i
nor 100111 $d, $s, $t
or 100101 $d, $s, $t
ori 001101 $t, $s, i
xor 100110 $d, $s, $t
xori 001110 $t, $s, i
sll 000000 $d, $t, a
sllv 000100 $d, $t, $s
sra 000011 $d, $t, a
srav 000111 $d, $t, $s
srl 000010 $d, $t, a
srlv 000110 $d, $t, $s
beq 000100 $s, $t, label
bgtz 000111 $s, label
blez 000110 $s, label
bne 000101 $s, $t, label
j 000010 label
jal 000011 label
jalr 001001 $s
jr 001000 $s
lb 100000 $t, i ($s)
lbu 100100 $t, i ($s)
lh 100001 $t, i ($s)
lhu 100101 $t, i ($s)
lw 100011 $t, i ($s)
sb 101000 $t, i ($s)
sh 101001 $t, i ($s)
sw 101011 $t, i ($s)
trap 011010 i
mflo 010010 $d
Instruction table:
17 (continued)
Student Number: __________________
This page is left blank intentionally for answer overflows.
18 (continued)
Student Number: __________________
This page is left blank intentionally for answer overflows.
Total Marks = 155
Total Pages = 18
End of exam