UNIVERSITY OF TORONTO CSC258: Computer Organization Final Assessment – Winter 2021
Assessment Period: 11:00am April 13th to 11:00am April 20th
Last Name (Family Name): _______________________________________
First Name (Given Name): _______________________________________
Student Number: __________________________________
Section (circle): LEC0101 / LEC9101 | LEC0201 / LEC9201 | LEC05101 / LEC6101
Submission via Quercus:
i) Please submit 1 single PDF file, without changing the format and spacing of the original paper.
One way to do this is to print out the assignment, hand-write your answers, and scan them into 1 PDF. Make sure your PDF is readable, so that it can be marked.
ii) For E.3, E.4 and E.5, please submit 3 ASCII text files, using the filenames specified in the question. Use only ANSI/ASCII encoding. Do not use UTF-8 or Unicode.
Instructions
1) We value academic integrity. This is your individual work. No collaboration please.
2) If you need extra space for any question, please include these extra pages in the same PDF. Indicate
clearly, on the original space provided, where our teaching staff will find this extra information.
3) If there are any corrections or clarifications needed on any of these questions, the information and
errata will be posted on the same Quercus page where you downloaded this PDF.
4) This assessment is open book. All course materials are permitted.
Part A: Short Answer (10 marks)
Answer the following questions in the space provided.
A.1) Doping a piece of silicon with phosphorus creates a semiconductor with a net negative charge.
True or False? (1 mark)
True False
A.2) Is this sentence true or false? “In the depletion region of a PN junction, when electrons move toward the N side of the PN junction, it creates a current called diffusion current.” (1 mark)
True False
A.3) Whatis60(decimal)inhexadecimal?(1mark)
A.4) How many bits does the “select” need for a 9-to-1 mux? (1 mark)
A.5) A complete truth table for a 3-to-1 mux has _________ rows. (1 mark)
A.6) There are 4 inputs A, B, C and D. Circle the valid minterms. (1 mark) a)A+B+C+D b) A·B+C·D
c)A·B·C·D d) A’·B’·C’·D’
Last, First Name: ______________________________ Page 2 of 20 Student # ____________________
A.7) Write the binary representation of -7 (decimal) as a 5-bit 2’s complement number. Please show your work to get full marks. (1 mark)
A.8) When the CTRL signal is high (diagram below), what arithmetic operation does this circuit perform? “FA” below stands for full-adder. (1 mark)
A.9) Complete the values for J and K for the truth table of a JK flip-flop below. (1 mark)
J
K
Qt+1
0 (regardless of Qt)
1 (regardless of Qt)
Qt’
Qt
A.10) To assist in reading memory dumps, a programmer wrote “DEADBEEF” to a block of memory. Each character (e.g. “D”) is not an English alphabet but a hexadecimal number. How many bits does “DEADBEEF” occupy? (1 mark)
Last, First Name: ______________________________ Page 3 of 20 Student # ____________________
Part B: Combinational Circuits and Logical Devices (14 marks)
B.1) Using the symbol for a 1-bit full adder below, create a 3-bit ripple subtractor that performs the operation d = b – a. You do not need to worry about overflow of this 3-bit
subtractor. (4 marks)
b2 a2 b1a1
b a ci
Co s
b0 a0
d2 d1 d0
B.2) Complete the following diagram to create a 1-bit full adder, using only 2 XOR gates.
(4 marks)
b a ci
10
co s
Last, First Name: ______________________________ Page 4 of 20 Student # ____________________
FA
B.3) K-map (6 marks)
Y
A
B
C
D
Y
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
AB
CD
0
CD
CD
1
CD
0
1
AB
0
X
0
0
AB
0
0
X
1
AB
1
0
0
1
Consider the Karnaugh map shown above.
1. Fill in the truth table on the right, given the Karnaugh map
values above. (2 marks)
2. On the Karnaugh map above, draw the groupings that would
result in the most optimized circuit possible. (2 marks)
3. In the space below, write the Boolean equation for the
groupings that you made in part 2. (2 marks)
Y = _________
Last, First Name: ______________________________ Page 5 of 20 Student # ____________________
Part C: Sequential Circuits (28 marks)
C.1)
Given the finite state diagram below, fill in the truth table diagram on the right with the correct state values. Assume that the numbers in each state below represent F1 and F0, respectively. (4 marks)
F1
0
0
0
1
1
F0
1
1
0
0
X
1
F1
F0
0
0
0
0
1
0
0
1
1
1
0
1
1
1
11
1 0,1
01
1
1
00
0
0
10 0
Last, First Name: ______________________________
Page 6 of 20
Student # ____________________
C.2) Complete the state diagram such that it would become a sequence recognizer that recognizes the following sequences of input: 110, 1101 and 1011.
Assume that the recognizer has a single-bit input called x. The states have been labeled with the detected sequence at various stages. The FSM should produce output ‘1’ when one of the sequences is found. Add output to each state. Create and label edges to move through the states. Add failure edges by finding the longest “suffix” of the sequence seen so far and transition to the corresponding “prefix” state (i.e. sequence 111 returns the FSM to state “11”) (6 marks)
1
“” /0
0
“1”
“11”
“10”
“110”
“1101”
Last, First Name: ______________________________
Page 7 of 20
Student # ____________________
“101”
“1011”
Clock Qo Q1
S Q2
Q3
C.3) For the sequential circuit below, fill in the waveform behaviour for the outputs Q0, Q1 and S. Assume the flip-flop output values are all low before the first positive clock edge, and that delays should be factored in your answer. (8 marks)
Last, First Name: ______________________________
Page 8 of 20
Student # ____________________
C.4) Consider the JK flip-flops shown below, where QA is the most significant bit and QB is the least significant bit. Assume QA and QB equal 0 at the beginning. (10 marks)
QA
X
Clock
QB
a) WritethefollowingBooleanequations:(2marks)
i. JA = _____________________________
ii. KA = _____________________________
iii. JB = _____________________________ iv. KB = _____________________________
b) Completethegivenstatetableandstatediagrambasedonthiscircuit.(8marks)
00 10
01 11
QA
0
0
0
QB
0
1
X
0
JA
KA
JB
KB
QA*
QB*
0
1
0
1
1
0
0
1
0
1
1
0
1
1
0
1
1
1
Last, First Name: ______________________________ Page 9 of 20 Student # ____________________
Part D: Processor (24 marks)
D.1) Considerthedatapathdiagramsbelow.Foreachofthefollowingstepsinanoperation,highlight the path (wires) that the data needs to take, from start to finish. Please use a color or marking that will scan properly onto your submission PDF. (4 marks)
a) Branch forward to 10 instructions ahead. (2 marks)
b) Give address ($s1 + 0x100) to memory for a load or store operation. (2 marks)
Last, First Name: ______________________________ Page 10 of 20 Student # ____________________
D.2) WhenBooth’sAlgorithmisperformedonthe4-bitbinaryinputsA=-5andB=-3,thevaluesforA 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. (6 marks)
Initial Values: A= Step #1:
1011 B= -B=
A =
Step #2:
A=
Step #3:
A=
Step #4:
A=
10110
Initial P value = value before shift =
Initial P value = value before shift =
Initial P value = value before shift =
Initial P value = value before shift =
0000 0000
0011 0000
P
P
P
P Final P value (binary) =
Final P value (decimal) =
Last, First Name: ______________________________
Page 11 of 20 Student # ____________________
D.3) Foreachassemblylanguageinstructionbelow,fillintheblankswiththecorresponding32-bit machine code instruction. (6 marks)
a)
b)
c)
j trgt (wherecurrentPCis3328andthe“trgt”labelisataddress3300)
beq $s0, $s2, top (“top”is4instructionsaftercurrentPC)
sh $s0, 15($fp)
X
X
1
0
0
0
0
1
X
X
1
0
0
0
0
1
X
X
1
0
0
0
0
1
D.4) Giventhemachinecodeinstructionsbelow,writethecorrespondingassemblylanguage instruction in the space below each machine code instruction. (6 marks)
a) 00111011111000100000000000000100
b) 00000011101000000000000000001000
c) 00000000000001110101000111000011
Last, First Name: ______________________________ Page 12 of 20 Student # ____________________
D.5) Thestackdiagramontheleftillustratesthetopfourbytesofastack,andtheemptyspaces above them for a 32-bit processor. What would this stack look like after the decimal integer 1025 has been pushed onto it? Draw the result on the diagram on the right (using binary values for the contents).
For this example, assume little endian byte storage, and draw an arrow to illustrate where $sp points to after this operation is complete. (2 marks)
00001000
00000100
01111000
00001111
Last, First Name: ______________________________ Page 13 of 20 Student # ____________________
Part E: Assembly (74 marks)
E.1) We need to extend the MIPS assembler to support the following new pseudo instructions. For each new pseudo-instruction, write the real MIPS instructions that will perform that operation. Only implementations that use at most 2 operations will get full marks. (8 marks total)
a) pushw $s Push the word stored in $s to the stack. (2 marks)
b) bod $t, dest Branch to label dest if the value in $t is odd. (3 marks)
c) multi $t,i Multiply $t by the constant i and store result in lo and hi. (3 marks)
Last, First Name: ______________________________ Page 14 of 20 Student # ____________________
E.2) 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. (6 marks total).
a) Multiply the value stored in $t4 by 32 and stored it back in $t4. (2 marks)
b) Store the remainder of dividing $t3 by 16 in $t9. (2 marks)
c) Store the current content of PC in $31, and set PC to the value stored in $t0. (2 marks)
Last, First Name: ______________________________ Page 15 of 20 Student # ____________________
E.3) Write a function get_n that takes n as an argument, and returns the n-th word of global arraylistwhichhaslenwords.Alsowritecodeatlabelmaintocallget_n function. If n is less than 1 or bigger than len, your function should return -1. (15 marks)
.data
len: .word
list: .word
.text main:
get_n:
6
5, -6, 8, -4, 7, 3
Please submit a separate text file named “get_n.s”. Use only ANSI/ASCII encoding. Do not use UTF-8 or Unicode.
Last, First Name: ______________________________ Page 16 of 20 Student # ____________________
E.4) Complete the program below to find the maximum value in the array list which has len elements, and return it in one of the return-value registers. Your solution should not use a recursive function. (15 marks)
.data
len: .word
list: .word
.text
main:
get_max:
6
5, -6, 8, -4, 7, 3
Please submit a separate text file named “get_max.s”. Use only ANSI/ASCII encoding. Do not use UTF-8 or Unicode.
Last, First Name: ______________________________ Page 17 of 20 Student # ____________________
E.5) Write a recursive function get_min to return the smallest element in an array of words. Call the function in your main program and pass it an array of 10 elements. (30 marks)
.data
len: .word
list: .word
.text main:
get_min:
10
5, -6, 8, -4, 7, 3, -2, 0, 18, 24
Please submit a separate text file named “get_min_recursion.s”. Use only ANSI/ASCII encoding. Do not use UTF-8 or Unicode.
Last, First Name: ______________________________ Page 18 of 20 Student # ____________________
This page is left blank intentionally for overflows.
Last, First Name: ______________________________ Page 19 of 20 Student # ____________________
Reference Information
Instruction Type Op/Func Syntax
ALU arithmetic input table:
add R addu R addi I addiu I div R divu R mult R multu R sub R subu R and R andi I nor R or R ori I xor R xori I sll R sllv R sra R srav R srl R srlv R beq I bgtz I blez I bne I j J jal J jalr R jr R lb I lbu I lh I lhu I lw I sb I sh I sw I trap I mflo R
100000 $d, $s, $t 100001 $d, $s, $t 001000 $t, $s, i 001001 $t, $s, i 011010 $s, $t 011011 $s, $t 011000 $s, $t 011001 $s, $t 100010 $d, $s, $t 100011 $d, $s, $t 100100 $d, $s, $t 001100 $t, $s, i 100111 $d, $s, $t 100101 $d, $s, $t 001101 $t, $s, i 100110 $d, $s, $t 001110 $t, $s, i 000000 $d, $t, a 000100 $d, $t, $s 000011 $d, $t, a 000111 $d, $t, $s 000010 $d, $t, a 000110 $d, $t, $s 000100 $s, $t, label 000111 $s, label 000110 $s, label 000101 $s, $t, label 000010 label 000011 label 001001 $s
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 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)
001000 $s 100000 $t, 100100 $t, 100001 $t, 100101 $t, 100011 $t, 101000 $t, 101001 $t, 101011 $t, 001100 i 010010 $d
i ($s) i ($s) i ($s) i ($s) i ($s) i ($s) i ($s) i ($s)
Last, First Name: ______________________________
Page 20 of 20
Student # ____________________