Assessment Reminders:
Exam Format and Grading Scheme:
UNIVERSITY OF TORONTO Faculty of Arts & Science
DECEMBER 2020 FINAL ASSESSMENT CSC258H1F
Copyright By PowCoder代写 加微信 powcoder
• Fill out your name and student number on every PDF page that you submit for grading (not the text or .asm files).
• Once the assessment is released, there is a 48-hour window to complete it and submit each part on Markus. You may
submit as many times as you like, but you will be graded on the final submission once the assessment period is over.
• This assessment is open book, meaning that all course materials are permitted.
• Plagiarism is taken extremely seriously and by submitting an answer to a question here you declare that you understand
the academic integrity rules are not representing another person’s work as your own.
• Questions about the assessment are to be emailed to the instructor directly. Answers to common questions will be posted
on a FAQ on Quercus (where this assessment document was found). Please do not expect immediate responses to your
questions, especially outside of normal business hours.
• If you are feeling ill and unable to finish your exam, please bring it to the attention of the course instructor so it can be
recorded for future consideration.
Special Instructions:
• This assessment has 12 questions on 18 pages (not counting the bonus question).
• Read over the entire exam before starting.
• If you need space to show your work or your solution requires more space than what is provided in the question page,
make sure to include any extra pages in the single PDF submission for that question.
• Some questions provide a text or .asm file for you to fill in and submit while others require you to provide your answer
on the question sheet and submit a PDF image of your answer. Make sure you understand what you need to submit before you answer each question. Use text editors like Notepad instead of Word when opening and saving text files.
Part A: Part E: PartI: Bonus:
Part B: Part F: PartJ:
/ 14 / 15 /12
Part C: Part G: PartK:
/ 20 / 11 /16
Part D: Part H: PartL:
Total: / 232
Part A: Short Answer (47 marks)
For the following short answer questions, a text file called q1.txt has been provided for you to fill in your answers (in addition to this question sheet). Each question below is represented by a line in this text file, with an underscore character (“_”) that must be replaced with your answer.
For example, the examples below show what the contents of q1.txt might look like before and after you fill in your answers:
Before After
Here are a few things to keep in mind when filling out the answers to this question:
1. All letters should be lowercase, unless specified otherwise.
2. Once you have filled in all the answers, submit the text file through Markus (not Quercus).
3. Do not submit your answers as a Word file or PDF file. Make sure to view your text file with a
plain text editor before submitting your solution, to make sure the content is what you expect.
1. How many integers can be stored in a memory unit that uses 12 address bits with a 32-bit architecture? (3 marks)
2. How many address bits are needed to specify a location in byte-addressable memory, given a 2048 bit memory unit and a 64-bit architecture? (3 marks)
3. True or False? Multiplication with Booth’s Algorithm uses the same number of clock cycles as multiplication with an accumulator circuit. (1 mark)
4. What colour appears on the RGB Video display when the Data In 888 RGB is 0xFFFF00? (2 marks)
5. True or False? As the stack increases in size, the value in $sp decreases. (1 mark)
Student Number: __________________ 2 (continued)
3. counter
6. True or False? As interrupt priority increases, the value in the cause register value decreases. (1 mark)
7. True or False? As the clock speed increases, the clock frequency decreases. (1 mark)
8. Which of the following assembly instructions use a Shift Left 2 unit in the datapath? Provide
the instruction as your answer here, not the multiple choice letter. (2 marks) a) add b) beq c) lw d) jr
9. Which of the following assembly instructions use a Shift Left 2 unit in the datapath? Again, provide the instruction as your answer here, not the multiple choice letter. (2 marks)
a) xori b) sw c) jal d) sll
10. Fill in the blank. When performing a j instruction, the maximum distance between the
initial and final value of the program counter is 2 to the power of ___ bytes (2 marks)
11. Fill in the blank. When performing a beq instruction, the maximum distance between the
initial and final value of the program counter is 2 to the power of ___ bytes (2 marks) 12. True or False? All valid logic gates are implemented by transistors so that each
combination of high and low input values produces a high or low output voltage. (1 mark) 13. How many flip-flops are needed to implement an FSM with 100 states? (1 mark)
14. True or False? If the inputs to a JK flip-flop come from the same source, it behaves like a T flip-flop. (1 mark)
15. True or False? Diffusion current and drift current at a PN junction always flow in opposite directions. (1 mark)
16. TrueorFalse?Callersmustsavethe$sregisters,calleessavethe$tregisters. (1mark) 17. True or False? A ripple carry adder is a synchronous circuit. (1 mark)
Student Number: __________________ 3 (continued)
18. Fill in the blank. To make a PN junction conduct electricity, you need to apply a _______ bias to the junction. (1 mark)
19. True or False? The voltage across a stable depletion layer is equal to the reverse bias voltage that created it. (1 mark)
20. What is the maximum number of minterms in a circuit with 3 inputs and 2 flip-flops? (1 mark)
21. True or False? Applying a voltage to the gate of a MOSFET allows current to flow between the source and the drain. (1 mark)
22. What is the decimal value for the highest 8-bit unsigned binary number? (1 mark) 23. What is the 8-bit 2’s complement of 01101101? (1 mark)
24. True or False? When writing a register to memory, big endian writes the register’s bits into memory in the reverse order of little endian. (1 mark)
25. True or False? When calculating the gate cost of a combinational circuit, the increase in the cost that comes from including NOT gates is the same as the number of inputs. (1 mark)
26. Fill in the blank. When electrons flow from an n-type material to a p-type material in a pn junction, this results in a ______________ current. (1 mark)
27. The output of a finite state machine depends solely on the current state. What is that kind of FSM called? (1 mark)
28. True or False? Doping a semiconductor with phosphorus gives the resulting material an overall positive charge. (1 mark)
29. For this final question, perform Booth’s Algorithm on operands A = 10011 and B = 10110. In the spaces provided as parts a) to f), provide the contents of P after each right shift of A and P in the algorithm. The initial value has been provided for you in part a). (10 marks)
Student Number: __________________ 4 (continued)
Part B: Transistors (14 marks)
The following transistor diagrams are attempting to implement various logic gates from Week 2 of the course, but part of each transistor circuit is missing. In the diagrams below, complete the missing parts of each circuit and fill in the name of the completed gate in the space provided below the circuit.
Student Number: __________________
(continued)
Part C: Circuit Design (20 marks)
A vending machine that dispenses tea has four buttons: H (hot), L (lemon), M (milk) and S (sugar). Create the logic for the signal that will dispense a stirring stick, based on the following rules:
1. If the Hot button is left unpressed, then the machine will dispense cold tea.
2. The machine will not allow lemon and milk to be selected at the same time. If you don’t already know why, look this up and never, ever serve tea this way.
3. If the tea is cold, you need to provide the user with a stirring stick to mix in lemon or sugar.
MSMSMSMS HL
In the Karnaugh map provided here, fill in the values that indicate whether to dispense a stirring stick (1) or not to dispense a stick (0). (8 marks)
Once you’ve filled in these values, group the values that would create the most efficient/reduced implementation of this circuit. (4 marks)
In the space below, indicate what the Boolean expression is for this circuit in terms of inputs H, L, M and S. (3 marks)
Stick = _________________________
In the space below, draw the circuit diagram for the output Stick. For full marks, your diagram
should be drawn entirely with only NAND gates. (5 marks)
4. Also provide a stirring stick when hot tea is selected with lemon but no milk and no sugar.
Student Number: __________________ 6 (continued)
Part D: Logical Devices (10 marks)
1. Consider the half adder and the multiplexer on the right. In the space below, draw a diagram that implements the half adder behaviour using only multiplexers and NOT gates.
For full marks, use the fewest multiplexers and gates possible. (5 marks)
2. Consider the same half adder and the multiplexer devices above. Draw a diagram in the space below that implements the multiplexer behaviour using only half adders and NOT gates. For full marks, use the fewest half adders and gates possible. (5 marks)
Student Number: __________________ 7 (continued)
Part E: Sequential Circuits (12 marks)
1. The diagram below and to the right illustrates the timing diagram for writing a D flip-flop. What are the names of the timing delays indicated by A and B? (4 marks)
A: ______________ B: ______________
2. In the waveform diagram below, show what the waveform looks like for the signals in the flip-flop circuit below. Assume that Q0 and Q1 each start with initial values of 0. (8 marks)
Student Number: __________________ 8
(continued)
Part F: Sequential Devices (15 marks)
1. By adding to the flip-flop diagram shown below, design a ripple counter diagram that counts down instead of up. Make sure to label the inputs and outputs properly. Full marks will only be given to the implementation with the fewest additional gates. (4 marks)
2. 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. (8 marks)
00 1 01 10
F1 F0 X F1 F0
000 001 010 011 100 101 110 111
2. On the finite state diagram, circle the transitions that cause a race condition in the flip-flops. If this is a Moore machine and state 00 has an output of 1, what output values would the other states need, to avoid having these race conditions disrupt the FSM output? (3 marks)
01: ________ 10: ________ 11: ________
Student Number: __________________ 9 (continued)
Part G: Processors, part 1 (11 marks)
1. In the memory write diagram below, label the regions in the address and data input where those signals have valid values (4 marks). On the same diagram, label the Setup Address Time and the Hold Data Time, and describe the reasons for these delays in the spaces provided. (4 marks)
Mem Enable Read/Write
Data Input
Define these and label on the diagram
Setup Address Time Hold Data Time
2. In the diagram below, fill in the circuitry for an 8-bit shift-by-two circuit, similar to those found in the processor datapath. Assume that the A pins represent the inputs and the Y pins represent the outputs. For full marks, use the fewest gates possible. (3 marks)
A7 A6 A5 A4 A3 A2 A1 A0
Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0
Student Number: __________________ 10 (continued)
Part H: Processors, part 2 (39 marks)
For the following questions, a text file called q8.txt has been provided for you to fill in your answers (in addition to this question sheet). Each question below is represented by a line in this text file, with an underscore character (“_”) that must be replaced with your answer.
1. For each of the following assembly language instructions, write the equivalent machine code instruction in the file q8.txt. You might find the reference information in the appendix helpful for this question. Fill in the space with an X if that digit doesn’t matter. (12 marks)
a) jal main (where main is the label of an instruction at address 0x0000FFFF) b) sll $zero, $zero, 0
c) lb $a0, -16($sp)
2. For the following machine code instructions, provide the equivalent assembly language instruction in the file q8.txt. (12 marks)
a) 10001111101110001111111111111111 b) 00000000101001100010011101000110 c) 00100100000111110000000000000111
3. For each of the processor tasks below, indicate what the values of the control unit signals will be by filling in q8.txt. (15 marks)
• If a control signal doesn’t affect the operation, fill in its value with an X.
• For ALUOp, simply write the operation (e.g. “add”, “subtract”, “multiply”).
a) Store the program counter value into $ra.
b) Movethestackpointeraddressbackby12bytes.
c) Write the contents of $a0 into the stack.
Student Number: __________________ 11 (continued)
Part I: Processors, part 3 (12 marks)
Consider the datapaths below. For each of the following operations, highlight the path that the data needs to take from start to finish.
a) Fill$t0withtheintegervaluestoredinmemoryataddress$s0
b) Add 32 to the value stored in the program counter
c) Jump to address stored in $t0
Student Number: __________________ 12 (continued)
Part J: Assembly Language, part 1 (12 marks)
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.
a) Set the value stored in $s0 to one eighth of its original value. (3 marks)
b) Set $a1 to the 1’s complement of the value stored in $a0. (3 marks)
c) Set $a1 to the 2’s complement of the value stored in $a0. (3 marks)
d) Set the program counter to zero. (3 marks)
Student Number: __________________ 13
(continued)
Part K: Assembly Language, part 2 (16 marks)
We need to extend the MIPS assembler to create the following new pseudo instructions. For each new pseudo-instruction, write the real MIPS instructions that will perform that operation. Only implementations that use the fewest instructions will get full marks. (12 marks total)
a) divi $t, i
b) push $t
c) bev $t, label
d) blue $t
Divide $t by the constant i and store result in lo and hi. (4 marks)
Push the value in $t onto the stack. (4 marks)
Branch to label if the value in $t is even. (4 marks)
Isolate the blue component of the 24-bit colour value stored in $t (i.e. remove the red and green components). (4 marks)
Student Number: __________________ 14 (continued)
Part L: Assembly Language, part 3 (24 marks)
For this question, three text files called q12a.asm, q12b.asm and q12c.asm have been provided for you to fill in your answers. Each of these files contain the following starter code:
.globl q12
len: .word 6
list: .word -3, 2, 0, -1, 4, -5
.text q12:
la $s0, list
la $s1, len
For this question, you must provide code that completes each of the functions below. When doing so, make sure that you do the following:
• Only add to the end of this starter code, do not change it in any major way.
• Submit your solutions in plain text file format (do not save it in Word or as a PDF).
• Your code should still work even if we replace the elements of list with new values.
• Comment your code to help us understand each of your steps.
• Make sure your code assembles and runs before you submit it.
a) In q12a.asm, add code that sets all the negative elements of list to zero. (8 marks)
b) Inq12b.asm,addcodethatreturnsthelargestvaluefromlist. (8marks)
c) In q12c.asm, add code that sorts the elements of list into increasing order (the smallest element first, largest element last). (8 marks)
This is to help us test your code.
Do not remove it!
Student Number: __________________ 15 (continued)
Part M: Bonus Question (1 mark)
Since Steve has not seen most of your faces, draw a post-CSC258 self-portrait in the space below. Feel free to exercise as much creative interpretation as you would like.
Student Number: __________________ 16 (continued)
Reference Information
ALU Arithmetic Input Table:
Assembly Instruction Table:
Instruction Type Op/Func Syntax
Select Input
Operation Cin=0 Cin=1
G=A G=A+1 G=A+B G=A+B+1 G=A-B-1 G=A-B G=A-1 G=A
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 R R I I R R I
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 101010 101001 001010 001011 010000 010010 001100
$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) $d, $s, $t $d, $s, $t $t, $s, i $t, $s, i $d
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)
Student Number: __________________
(continued)
This page is left blank intentionally for answer overflows.
Student Number: __________________ 18
Total Marks = 232 Total Pages = 18
End of exam (continued)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com