UNIVERSITY OF TORONTO Faculty of Arts and Science
April 2015 Examinations CSC258H1S: Computer Organization Duration: 3 hours
Permitted Aids: one ruler, one highlighter
Last Name: _______________________________________ First Name: _______________________________________ Student Number: __________________________________
Copyright By PowCoder代写 加微信 powcoder
Instructors:
Part A: Part B:
Instructions:
Write your name on every page of this exam.
Do not open this exam until you hear the signal
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 16 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 use
the overflow page, clearly indicate the section(s) that you want marked.
Total: / 140
Part A: Short Answer (34 marks)
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.
1. Which ones of the following hexadecimal addresses are valid PC values when translated into 32-bit binary addresses? Circle all that apply. (2 marks)
a) E45B23C1 c) 9B31FF1C
a) $zero c) $sp
a) sign extension c) ones extension
c) 1111 + 0001
b) 4C32A330 d) 1234ABCD
b) $t0 d) $ra
b) zero extension d) inversion
d) 0100 + 0100
2. Which is of the following registers always stores a value that is divisible by 4? Circle all that apply. (2 marks)
3. In an R-type instruction, how many bits are reserved for the shift amount? (1 mark) a) 5 b) 6
4. In an I-type instruction, what operations might need to be performed on the immediate value? Circle all that apply. (2 marks)
5. Which of the following 4-bit signed binary arithmetic operations will cause an overflow? Circle all that apply. (2 marks)
a) 1001 + 0100 b) 1010 + 1110
6. If a one-hot decoder has a binary output of 1000000000000000, what would the input be? (2 marks)
Student Number: __________________ 2
(continued)
7. What is the maximum distance that a branch instruction can jump (in bytes)? (1 mark)
a) 216 c) 226
9. What is the output of a tri-state buffer when both inputs are zero? (1 mark)
b) 218 d) 228
8. What is the maximum distance that a jump instruction can jump (in bytes)? (1 mark) a) 216 b) 218
10. How many bytes can a register unit store, with 6 address bits and 32-bit words? (2 marks)
11. How many bits does a register unit need to address each register, if it stores 1024 bytes in 32-bit integers? (2 marks)
12. To load the value 1101101100110110 into a 16-bit shift register, it takes X clock cycles. To load the same value into a 16-bit load register, it takes Y clock cycles. What are the values ofXandY? (2marks)
X = _____________ Y = _____________
13. Which of the following assembly code segments would implement the pseudo-instruction bge $s, $t, Label? Circle all that apply. (2 marks)
slt $d, $s, $t
beq $d, $zero, Label
slt $d, $t, $s
beq $d, $zero, Label
beq $s, $t, Label
slt $d, $s, $t
bne $d, $zero, Label
Student Number: __________________ 3
(continued)
beq $s, $t, Label
slt $d, $t, $s
bne $d, $zero, Label
14. Which of the following Verilog statements cannot appear inside an always block? Circle all that apply. (2 marks)
a) a=b; c) a<=b;
b) assigna=b; d) not(a,b);
15. In Lab 1, you had to implement a 5-to-1 multiplexer with 2-to-1 multiplexers. What is the minimum number of 2-to-1 multiplexers that you would need to implement a 15-to-1 multiplexer? (1 mark)
16. Which of the following are equivalent to XY? Circle all that apply. (2 marks) a) (X+Y) b) X(YZ+YZX)
d) XYZ+XYZ
Semiconductor
17. The MOSFET is made up of three types of material, listed below. Sort these materials according to the conductivity, from most conductive (1) to least conductive (3). (2 marks)
18. Other than the proposal, there were 5 parts of Lab 6 that you needed to do. What were those parts? Fill in your answer in the spaces below. (5 marks)
a) _______________ b) _______________ c) _______________ d) _______________ e) _______________
Student Number: __________________ 4
(continued)
Part B: Design and Analysis (26 marks)
1. Consider the flip-flop diagram below. What values will be on Q3, Q2, Q1, and Q0, after each consecutive clock cycle? Write your answer in the spaces provided, one space per clock cycle. (6 marks)
1111 Clock
Initial value (before first clock pulse):
Student Number: __________________
5 (continued)
2. Consider the Verilog code on the left, which implements a Finite State Machine. Refer to this code when answering the questions on the right. (14 marks)
module fsm(clock, reset, X, Z);
input clock, reset, X;
output reg Z;
reg [2:0] state, next_state;
always @ (posedge clock)
if (reset)
state <= 1;
state <= next_state;
always @ (state)
case (state)
default: Z = 0;
always @ (state, X)
case (state)
1: if (!X)
next_state = 4;
next_state = 1;
next_state =1;
next_state = 2;
4: if (!X)
next_state = 2;
next_state = 1;
default: next_state = 1;
i) Complete the state diagram of this FSM by filling in each state with the correct state number, and labeling each transition with the matchingvaluesforX(0or1). Ignoreany transitions due to reset. (9 marks)
ii) Given the above state transition diagram, fill in the output for each state. (3 marks)
iii) Given the sequence of inputs 0, 1, 0, which will be the resulting FSM state? (1 mark)
iv) What type of FSM is this? (1 mark) a) Mealy b) Moore
Student Number: __________________ 6
(continued)
3. For every output waveform below, specify in the spaces on the right which sequential circuits at the bottom would generate this output behaviour. If you think there is no match, write “None”. Assume functional simulation and that the initial Q state, when unknown, was zero. (6 marks)
(a) (b) (c)
(d) (e) (f)
Student Number: __________________ 7
(continued)
Part C: Processor Operations (17 marks)
1. When Booth’s Algorithm is performed on the binary inputs A=1011 and B=1001, the values for A and P change at each step of the algorithm. The framework is provided below, with a few values filled in for you. Fill in the rest, according to the steps shown in class. (5 marks)
InitialValues: A= 10110 B= 1001 -B= 0111 Step #1:
Initial P value = value =
Initial P value = value =
Initial P value = value =
Initial P value = value =
Final P value (binary) =
Final P value (decimal) =
Student Number: __________________ 8
(continued)
2. Consider the datapaths below. For each of the following operations, highlight the path that the data needs to take, from start to finish. (12 marks)
a) Store$raintotheprogramcounter.
b) Store the program counter in $ra.
c) Push the value stored in $a0 onto the stack.
Student Number: __________________ 9 (continued)
PartD:ProcessorInstructions (27marks)
1. Each assembly language instructions below matches a machine code instruction at the bottom. However, the opcodes have been removed from each machine code instruction. Match the assembly language instructions to their corresponding machine code instructions, and label each machine code instruction with its missing opcode. (12 marks)
A) or $t8, $t0, $t1 B) jalr $v0
C) lbu $t1, -30($t0)
D) lw $v0, -1($sp)
E) srlv $a0, $a1, $a2
F) addiu $ra, $zero, 6143
i. 11101000101111111111111111 Assembly code instruction: _________________
ii. 00110001010010011101000110 Assembly code instruction: _________________
ii. 00000111110001011111111111 Assembly code instruction: _________________
iv. 11000010000100100000100101 Assembly code instruction: _________________
v. 00010111110000000000001001 Assembly code instruction: _________________
vi. 01000010011111111111100001 Assembly code instruction: _________________
Student Number: __________________
(continued)
2. 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. (15 marks)
If a control signal doesn’t affect the operation, fill in its value with an X.
For ALUOp, full marks will only be given for binary values. If you don’t know what the
values are, just write what kind of operation is taking place instead.
Add 4 to the stack pointer value.
PCWriteCond
MemRead MemWrite ALUOp
Add 100 to the program counter, and store the result in $ra.
PCWriteCond
MemRead MemWrite ALUOp
Fetch and load the next instruction from memory.
PCWriteCond
MemRead MemWrite ALUOp
Student Number: __________________ 11 (continued)
Part E: Verilog (12 marks)
module one (o, s, t, d, i, m, w);
input [31:0] m;
output reg [5:0] o;
output reg [4:0] s, t, d;
output reg [15:0] i;
reg [31:0] c;
always @ (*)
if(w) c<=m; o <= c[31:26]; s <= c[25:21]; t <= c[20:16]; d <= c[15:11]; i <= c[15:0];
Consider the piece of Verilog code on the right. 1. In a sentence or less, describe what operation
this code performs. (4 marks)
2. Based on your answer above, what do the i andoregvaluesrepresent? (2marks)
i: ____________________
o: ____________________
Consider the piece of Verilog code on the right. 3. In one sentence, describe what function this
code performs. (4 marks)
4. Given your answer to part 1, what functions doinputsignalseandwperform? (2marks)
module two (c, e, w, a, di, do);
input c, w, e;
input [7:0] a;
input [3:0] di;
output [3:0] do;
reg [3:0] M [255:0];
reg [3:0] do;
always @(posedge c)
if (e) begin
M[a] <= di;
do <= M[a];
Student Number: __________________ 12 (continued)
Part F: Assembly Language (24 marks)
1. In the spaces provided below, write the assembly language instruction(s) that perform the following tasks. Full marks will only be given for one-instruction answers. (12 marks total)
a) Set the value stored in $s0 to one eighth of its original value. (3 marks)
b) Invert all the bits of the value stored in $a0. (3 marks)
c) Pop a character off the stack and store it in $t0. (3 marks)
d) Set the program counter to zero. (3 marks)
Student Number: __________________ 13 (continued)
2. In the space provided, write the resulting list values for each assembly program. (12 marks)
len: .word 5
list: .word -4, -1, 0, 1, 4
main: addi $s0, $zero, list
addi $s1, $zero, len
lw $t1, 0($s1)
top: lw $t0, 0($s0)
add $t0, $t0, $t0
sw $t0, 0($s0)
addi $t1, $t1, -1
addi $s0, $s0, 4
bne $t1, $zero, top
end: jr $ra
len: .word 5
list: .word -4, -1, 0, 1, 4
main: addi $s0, $zero, list
addi $s1, $zero, len
lw $t1, 0($s1)
top: lw $t0, 0($s0)
sub $t0, $t0, $t0
sw $t0, 0($s0)
addi $t1, $t1, -1
addi $s0, $s0, 4
bne $t0, $zero, top
end: jr $ra
len: .word 5
list: .word -4, -1, 0, 1, 4
main: addi $s0, $zero, list
addi $s1, $zero, len
lw $t1, 0($s1)
top: lw $t0, 0($s0)
addi $t1, $t1, -1
addi $s0, $s0, 4
add $t0, $t0, $t0
sw $t0, 0($s0)
bne $t1, $zero, top
end: jr $ra
len: .word 5
list: .word -4, -1, 0, 1, 4
main: addi $s0, $zero, list
addi $s1, $zero, len
lw $t1, 0($s1)
lw $t0, 0($s0)
top: addi $t1, $t1, -1
add $t0, $t0, $t1
bne $t1, $zero, top
addi $s0, $s0, 4
sw $t0, 0($s0)
end: jr $zero
Student Number: __________________ 14 (continued)
Reference Information
Instruction table:
Instruction Type Op/Func Syntax
ALU arithmetic input table:
R R I I R R R R R R R I R R I R I R R R R R R I I I I J J R R I I I I I I I I I R
100000 100001 001000 001001 011010 011011 011000 011001 100010 100011 100100 001100 100111 100101 001101 100110 001110 000000 000100 000011 000111 000010 000110 000100 000111 000110 000101 000010 000011 001001 001000 100000 100100 100001 100101 100011 101000 101001 101011 001100 010010
$d, $s, $t $d, $s, $t $t, $s, i $t, $s, i $s, $t
$d, $s, $t $d, $s, $t $d, $s, $t $t, $s, i
$d, $s, $t $d, $s, $t $t, $s, i
$d, $s, $t $t, $s, i
$d, $t, a $d, $t, $s $d, $t, a $d, $t, $s $d, $t, a $d, $t, $s $s, $t, label $s, label $s, label $s, $t, label label
Select Input
Operation Cin=1
G=A G=A+B G=A-B-1 G=A-1
G=A+1 G=A+B+1 G=A-B G=A
Register assignments:
Register values : Processor role
Register 0 ($zero): reserved value.
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)
Bonus Question:
label $s $s $t, $t, $t, $t, $t, $t, $t, $t,
(1 mark) Draw something in the space below.
i ($s) i ($s) i ($s) i ($s) i ($s) i ($s) i ($s) i ($s)
Student Number: __________________ 15
(continued)
This page is left blank intentionally for answer overflows.
Student Number: __________________ 16
Total Marks = 140 Total Pages = 16
(continued) End of exam
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com