[SOLVED] CS CSC258H1S: Computer Organization Duration: 3 hours

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:

Copyright By Assignmentchef assignmentchef

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

Part A: / 21 Part B:

PartA:ShortAnswer (21marks)
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.
a) 256 b) 64 c) 32 d) 8
2. How many address bits are needed to specify each byte in a 512 byte memory unit? (1 mark)
1. How many instructions could fit into a 256 byte memory unit, given a 32-bit architecture? (2 marks)
a) 512 c) 32
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)
True False
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 differentstatementsinVerilogthatsetchighwhenaandbarelow. (2marks)
Student Number: __________________ 2
(continued)

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)
8. In p-type semiconductors, what are holes? (1 mark)
Operation: _____________________ _______________________________
a) absent electrons b) c) protons d)
positive charge carriers
where you plant silicon flowers
Numberofflip-flops: _______________
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: __________________
Student Number: __________________
(continued)

Part B: Design and Analysis (18 marks)
1. In the space below, draw a circuit whose behaviour matches the following waveform. (4 marks)
2. Which of the circuits below have equivalent behaviour? Draw lines that connect any circuits that match. (6 marks)
Student Number: __________________
(continued)

3. Draw gates into the following diagram to implement a subtractor circuit. (2 marks)
4. Given the following circuit, show what the output value of Q0, Q1, Q2 and Y will be in the waveform diagram. Assume that Q0, Q1 and Q2 start with initial values of zero. (6 marks)
T Q0 T Q1 T Q2 QQQ
Student Number: __________________ 5
(continued)

Part C: Processors (52 marks)
1. In the datapath diagram below, connect the following signals to the units that they affect. (8 marks)
IorD IRWrite MemRead MemToReg MemWrite PCSource PCWrite RegDst
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. (8 marks)
tSA: _____________________________________________________________ tAW: _____________________________________________________________ tSD: _____________________________________________________________ tHD: _____________________________________________________________
Student Number: __________________ 6 (continued)

3. In the space below, perform Booths Algorithm on the binary values A=10110 and B=01101. Show your steps in the space provided. (6 marks)
P= Step 1:
4. Verify your answer above by writing the decimal values for A, B and the final product in the spaces below. (2 marks)
Student Number: __________________ 7 (continued)

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
Student Number: __________________ 8 (continued)

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 doesnt affect the operation, fill in its value with an X.
For ALUOp, if you dont know the values, just write what kind of operation is taking place.
Reduce the program counter by the value stored in $t0.
PCWriteCond
IorD MemRead MemWrite PCSource ALUOp
Fetch the next instruction from the address in the program counter.
PCWriteCond
IorD MemRead MemWrite PCSource ALUOp
Add 64 to $s0 and store the result back in $s0.
PCWriteCond
IorD MemRead MemWrite PCSource ALUOp
Student Number: __________________ 9 (continued)

PartD:Verilog (14marks)
Consider the piece of Verilog code on the right. 1. In one sentence, describe what function this
code performs. (4 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])
3b000: r = a;
3b001: r = a + b;
3b010: r = a b;
3b011: r = a 1;
3b100: r = a & b;
3b101: r = a | b;
3b110: r = a ^ b;
3b111: r = ~a;
endcase end
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)
Student Number: __________________ 10 (continued)

PartE:FiniteStateMachines (20marks)
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.
Flip-Flop Assignments
StateA
F1 =0 F0 =0 StateB
F1 =0 F0 =1 StateC
F1 =1 F0 =1 StateD
F1 =1 F0 =0
Fill in the truth table below with the values that correspond to the FSM above. (8 marks)
000 001 010 011 100 101 110 111
Student Number: __________________ 11 (continued)

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)
F1F0 F1F0 F1F0 F1F0 X
F1F0 F1F0 F1F0 F1F0 X
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)
Student Number: __________________ 12 (continued)

PartF:AssemblyLanguage (30marks)
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)
Student Number: __________________ 13 (continued)

Consider the assembly language program in the box below.
list: .word 3,0,1,2,6,-2,4,7,3,7
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 #
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)
Student Number: __________________ 14 (continued)

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 youre doing. (8 marks)
Student Number: __________________ 15 (continued)
int make_even (int i) {
if (i % 2 == 1)
return i-1;

Reference Information
ALU arithmetic input table:
Select Input Operation
Instruction table:
Instruction Op/Func Syntax
Y Cin=0 Cin=1
All 0s G=A G=A+1
B G=A+B G=A+B+1 B G=A-B-1 G=A-B All 1s G=A-1 G=A
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 011010 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
$t, i ($s) $t, i ($s) $t, i ($s) $t, i ($s) $t, i ($s) $t, i ($s) $t, i ($s) $t, i ($s) i
Register table:
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)
Student Number: __________________
(continued)

This page is left blank intentionally for answer overflows.
Student Number: __________________ 17 (continued)

This page is left blank intentionally for answer overflows.
Total Marks = 155 Total Pages = 18
End of exam (continued)
Student Number: __________________ 18

CS: assignmentchef QQ: 1823890830 Email: [email protected]