University of Toronto Faculty of Applied Science and Engineering Unsupervised Final Assessment ECE243 – Computer Organization Examiners – Stephen Brown and Jonathan Rose Print and submit this page: First Name Last Name Student Number 1. This assessment is available at 4:30 pm on April 27, 2020 Eastern time. You must submit all of your answers to Quercus under this course before 4:30 pm on April 28, 2020 Eastern time. 2. There are four questions in this final assessment. Your answer to each question is to be submitted to Quercus using files that you create. The file names are specified in each question in this document. Question 4 also requires the submission of rough work. 3. This is an unsupervised final assessment. You are allowed to use only the following aids: a calculator, spreadsheet, textbooks, your notes and the instructors’ notes, your lab work in the course, CPUlator, and the Monitor Program. Writing an unsupervised final assessment necessitates a high level of integrity and honesty. Before beginning to write the assessment please read and sign the following statement: I pledge upon my honour that I will not violate our Faculty’s Code of Behaviour on Academic Matters during this assessment by acting in any way that would constitute cheating, misrepresentation, or unfairness, including but not limited to, using unauthorized aids and assistance, impersonating another person, and committing plagiarism. I acknowledge that providing unauthorized assistance to someone else is also considered a serious academic offence. (sign your name) If you have access to a printer: print this page, fill in your name and student number, sign the pledge, and then scan/photograph the page and submit it with the file name firstpledge.jpg or firstpledge.pdf to the Quercus assignment labelled ‘First Honour Statement and Signature.’ If you do not have access to a printer: in a text file named firstpledge.txt, type your name and student number, the full pledge into this file, and type your name in place of the signature. Upload this file to the same assignment as above. There is a second pledge at the end of this document that you must also sign and submit once you’re finished the assessment. Page 1 of 14 1. For this question you will submit to Quercus your ARM assembly code for all parts of the question[25 marks] in a single file namedQ1.s to the Quercus Assignment labelledQuestion 1. To create this file you can use any text editor—for example, the editor that you normally use to make your lab exercise assembly code. When grading your code, the submitted file Q1.s will be loaded into the CPUlator, assembled and executed. You are required to submit correctly-working code. Important: Your code for each part of this question will be tested independently of the other parts of the question. This means that you can obtain part-marks even if you have not correctly answered, or completed, all parts of the question. Very Important: No marks will be given if your answer uses the assembly code that is produced by a C compiler, or if you do not exactly follow the specification for how the ARM registers are to be used in each part of the question. In Part II of Lab Exercise 7 you were asked to write C code to make an animation in which a horizontal line “moves” up/down on the VGA screen. The goal of this question is to replicate this C code using assembly language. (a) The speed of the animation in Exercise 7 was controlled by using the wait for vsync( )[3 marks] subroutine. The C code below implements this subroutine: void wait_for_vsync() { *pixel_ctrl_ptr = 1; // start sync while ((*(pixel_ctrl_ptr + 3) & 0x1) != 0) ; } This subroutine assumes that the global variable pixel ctrl ptr has been declared and ini- tialized with the base address of the VGA controller. This declaration would be included in the C program as follows: volatile int * pixel_ctrl_ptr = 0xFF203020; // VGA controller Your task for this part of the question is to write equivalent code in the ARM assembly language for the wait for vsync subroutine. Start your subroutine with the label (all capitals): WAIT_FOR_VSYNC: In the WAIT FOR VSYNC subroutine your code must receive the global pointer to the VGA controller (mentioned above) in ARM register R12. You must follow the ARM procedure call standard (PCS) when writing your subroutine code. Specifically, in PCS a subroutine is allowed to modify only ARM registers R0-R3, but it is not permitted to have changed the contents of any other ARM registers after execution of the subroutine. Write the code in your fileQ1.s. Directly above this code there should be a comment that appears exactly as follows: // Question 1(a) Page 2 of 14 (b) The C code below shows the plot pixel(. . .) subroutine that is used to write a color to a[3 marks] specific pixel in the back buffer: void plot_pixel(int x, int y, int color) { int back_buffer = *(pixel_ctrl_ptr +1); *(short int *)(back_buffer + (y << 10) + (x << 1)) = color; } Note: although this code writes to the back buffer, in Part II of Lab Exercise 7 there is only one pixel buffer. That is, the address of the front and back pixel buffers are the same, and double- buffering is not used in this animation. For this part of the question you are to write equivalent code in the ARM assembly language for the plot pixel subroutine. As specified in part (a), assume that the global pointer to the VGA controller is contained in ARM register R12. You have to follow the ARM procedure call standard when writing your subroutine code. As mentioned in part (a) of this question, only the ARM registers R0-R3 can be modified by a subroutine according to the PCS. It also specifies that any parameters for the subroutine are provided in registers R0-R3. Start your subroutine with the label (all capitals): PLOT_PIXEL: Important: You must code your subroutine so that its parameters are provided exactly as fol- lows: register R0 has the x coordinate of the pixel, register R1 has the y coordinate, and register R2 has the color. Recall from Lab Exercise 7 that the color is a 16-bit value. Write the code in your fileQ1.s. Directly above this code there should be a comment that appears exactly as follows: // Question 1(b) (c) The C code below shows the clear screen( ) subroutine that is used to erase the contents[7 marks] of the pixel buffer: void clear_screen() { int x, y; for (x = 0; x < 320; x++) for (y = 0; y < 240; y++) plot_pixel (x, y, 0); } Note that this code calls the plot pixel subroutine from part (b). For this part of the question you are to write equivalent code for the clear screen( ) subroutine in the ARM assembly language. As stated in the previous parts of this question, you must follow the ARM PCS rules (described above) when writing your subroutine code. Start your subroutine with the label (all capitals): CLEAR_SCREEN: Page 3 of 14 Write the code in your fileQ1.s. Directly above this code there should be a comment that appears exactly as follows: // Question 1(c) (d) The C code below shows the draw line(. . .) subroutine that is used to draw a horizontal line[4 marks] in the pixel buffer. The line is drawn from pixel (x0, y) to pixel (x1, y). void draw_line(int x0, int x1, int y, int color) { int x; for (x = x0; x <= x1; x++) plot_pixel (x, y, color); } Note that this code calls the plot pixel subroutine from part (b). For this part of the question you are to write equivalent code in the ARM assembly language for the draw line subroutine. Start your subroutine with the label (all capitals): DRAW_LINE: You must follow the ARM PCS rules when writing your subroutine code, as described in the previous parts of this question. Important: you must code your subroutine so that its parameters are provided exactly as fol- lows: register R0 has the x0 coordinate, register R1 has the x1 coordinate, register R2 has the y coordinate, and register R3 has the color. Write the code in your fileQ1.s. Directly above this code there should be a comment that appears exactly as follows: // Question 1(d) (e) The C code on the following page provides a main programwhich calls the subroutines describe d[8 marks] in parts (a d). The horizontal line “animated” by this main program is white in color and extends from x-coordinates 100 to 220. Page 4 of 14 int main(void) { int x_0, x_1, y, y_dir; clear_screen (); // blank the screen x_0 = 100; x_1 = 220; y = 0; y_dir = 1; draw_line (x_0, x_1, y, 0xFFFF); // horizontal white line while (1) { wait_for_vsync (); draw_line (x_0, x_1, y, 0); // erase the line y = y + y_dir; // change line position if ((y == 0) || (y == 239)) y_dir = -y_dir; draw_line (x_0, x_1, y, 0xFFFF); // new white line } } For this part of the question you are to write equivalent code for this main program in the ARM assembly language. Your MAIN program is required to follow the ARM PCS rules, in the same way as your sub- routines from previous parts of the question. In particular your MAIN program should assume that the general-purpose registers R0-R3 may be modified by any subroutine that is called, but general-purpose registers R4-R12 will be preserved across subroutine calls. Write the code in your fileQ1.s. Directly above this code there should be a comment that appears exactly as follows: // Question 1(e) Make sure that you have included useful comments in your code (for all parts of this question), so that a grader of your question will be able to award part marks in the case that your code does not work correctly. Submit the file Q1.s file to the assignment labelled Question 1. Page 5 of 14 2. This question is about assembly-language code and interrupts. Note: Different from Question 1, you[25 marks] will submit individual files for each part of this question, to separateQuercus assignments, which are labelled Question 2a, Question 2b, and Question 2c. Note: A short video demonstration of a complete solution for all parts of this question can be found at https://youtu.be/jPMutBfX19o (a) You are to write an assembly-language program that works as follows: it reads the SW switch[8 marks] port and lights up a seven-segment display corresponding to the value read on SW2 0. For example, if SW2 0 = 000, then the digit 0 is shown on HEX0. If SW2 0 = 001, then the digit 1 is displayed on HEX1, and so on, up to the digit 5 which would be shown on HEX5 if SW2 0 = 101. Once a digit has been displayed, it should remain displayed even if SW is subsequently changed. Recall that the seven-segments displays are connected to the two registers: 0xFF200020 ... HEX06-0 ... HEX16-0 ... HEX36-0 Address 07 6815 142431 30 0xFF200030 ... HEX26-0 1623 22 ... HEX46-0 ... HEX56-0 07 6815 142431 30 1623 22 Data register Data register 0 1 2 3 4 5 6 Segments Unused Also recall from the lab exercises in this course that you cannot perform store operations to individual bytes in these registers—you can only store 32-bit words. Hence, the code for your solution to this question can use STR instructions to write to the HEX display ports, but cannot use STRB to write to these ports. Write your code in a file named Q2a.s and submit this file to the Quercus assignment labelled Question 2a. (b) For this part you are to write an assembly-language program that flashes LEDR0 on and off ev-[11 marks] ery 0.5 seconds. Your code should have a main program that writes to the LEDR port and your program should use interrupts to implement the required 0.5 second time intervals. To create in- terrupts every 0.5 seconds use the A9 Private Timer, which has a base address of 0xFFFEC600. This timer is described in Section 2.4.1 of the DE1-SoC Computer documentation, which can be found on the Quercus home page for this course, by following the link Laboratory Exercises and then ARMMaterials. Use this timer to make a delay of 0.25 seconds. Page 6 of 14 To configure the ARM processor’s generic interrupt controller (GIC) use the code that was pro- vided along with Lab Exercise 6. Write the code for this part in a file named Q2b.s and submit this file to the Quercus assignment labelled Question 2b. (c) For this part you are to augment your program from part (a) to add the following functionality:[6 marks] When the SW switches are set to select a particular digit (from 0 to 5), you are to flash this digit on and off every 0.5 seconds. Implement the required 0.5 second time intervals using interrupts from the same timer that you used in part (b) of this question. Important: once a digit has been selected once, it must remain displayed even if SW has been subsequently changed. Also Important: only the digit that is currently selected by SW is allowed to flash on/off. Marks will be deducted if multiple digits flash on/off. Write the code for this part in a file named Q2c.s and submit this file to the Quercus assignment labelled Question 2c. Page 7 of 14 3. This question is about C code. In this question you will submit individual files for each part of this[25 marks] question, to separate Quercus assignments, which are labelled Question 3a, Question 3b, Question 3c and Question 3d. Note: A short demonstration of a working solution for all parts of this question can be found at https://youtu.be/Mofcc8QAbMY. (a) For this part you are to write a C program that displays the characters ECE243 on the hex-[5 marks] adecimal displays HEX5 - HEX0. The message should flash on/off at a rate of approximately 0.5 seconds. Implement the required delay between showing, and blanking the characters in the display by using a software delay loop - do not use a hardware timer for this part of the ques- tion. Write the code for this part in a file named Q3a.c and submit it to the Quercus assignment labelled Question 3a. (b) For this part you are to write a C program that turns on one light at a time on the LEDR port.[6 marks] You should start by lighting up only LEDR0, then only LEDR1, then only LEDR2, and so on, to LEDR9, and then returning back to LEDR0. The effect created by your program should be that a light appears to scroll across the LEDR port. The speed at which the lights are scrolled should be controlled by using the Interval Timer in the DE1-SoC Computer. This timer has the base address 0xFF202000 and is described in Section 2.11 of the DE1-SoC Computer documentation. Use this timer to make a delay of 0.25 seconds. Use polled-I/O to wait for the timer to expire—do not use interrupts! You should be able to control the direction in which the lights are scrolled by using the KEY port. Each time any KEY is pressed and released, the direction of scrolling should be reversed. Write the code for this part in a file named Q3b.c and submit this file to the Quercus assignment labelled Question 3b. (c) For this part you are to create a scrolling message on the seven-segment displays HEX5 - HEX0.[8 marks] Your C program should display the message U of t ECE-243 and should scroll the message in the right-to-left direction across the displays. The letters in the message can be constructed as Control the speed of scrolling by using the same timer as in part (b), with a timer delay of 0.5 seconds. Use polled-I/O; do not use interrupts. You should be able to control the displays using the KEY port. When the message is currently scrolling, then pressing and releasing any KEY should stop the scrolling so that the HEX displays are static. Now pressing and releasing any KEY should restart the scrolling, etc. Write the code for this part in a file named Q3c.c and submit this file to the Quercus assignment labelled Question 3c. (d) For this part you are to augment your solution from part (c) to provide additional features using[6 marks] the pushbutton KEYs, as follows: KEY0 should start/stop the scrolling (as was done for any KEY in part (c)), KEY1 should double the scrolling speed, KEY2 should halve the scrolling speed, and KEY3 should reverse the direction of scrolling. Write the code for this part in a file named Q3d.c and submit this file to the Quercus assignment labelled Question 3d. Page 8 of 14 Page 9 of 14 4. [25 Marks] All of your answers to this question must be placed into the spreadsheet file Q4_Answer.csv that is provided with this question in the Quercus assignment labelled ‘Question 4.’ You should download that file, enter your answers into it using a spreadsheet p rogram, then save your answers back into this file, and uploaded it back into this same Quercus assignment. You can use any spreadsheet program such as Microsoft Excel, Apple Numbers, or Google Sheets. When saving the file, do not change its file type—use the .csv format for your answers. In addition to this spreadsheet file, for questions 4(c) and 4(d), you must also provide your separate ‘rough work’ that clearly illustrates the process that you worked through to arrive at your answers. These steps must be present to gain full marks. There should be one rough work file for each of Question 4(c) and 4(d). The name of these two files should be Q4cRoughWork and Q4dRoughWork. These files can be either a spreadsheet (.csv or .xlsx or .xls type), or a photograph of written rough work (.jpg or .pdf type). Note that you should submit all of these files at the same time, using the ‘add another file’ functionality during the submission process on Quercus. You may make as many submissions as you wish over the assessment period, but make sure you always submit all files. Only the final submission will be graded. This question is about processor caches. An engineer is designing a cache memory as part of a memory system and is trying to decide between using a Direct-Mapped cache and 4-way Set Associative cache. The engineer has decided to determine which one is best by seeing how well each cache does, in terms of hit rate, under the following exact specifications: • The processor address bus is 16 bits wide • Each word in the processor (the processor data bus width) is 8 bits (1 byte) • The cache (whichever kind is chosen) will have the following properties: o The total amount of the data in the cache is 16 bytes (= 16 words, as above) o The cache line size is 2 words (which is 2 bytes because each word is one byte); so, the memory block size is also 2 words; this also implies that there is a total of 8 lines in the cache o There is a Valid (V) bit and a Dirty (D) bit for each line o The cache is of the ‘write-back’ variety • The direct-mapped cache is fully specified by the above information • The associative cache has the following additional specifications: o It is a 4-way set associative cache. Note: for the specifications above, this implies there are just two sets. o If a line has to be evicted from the cache, it is the line that was used the longest time ago. This scheme is often referred to as the ‘Least Recently Used’ replacement policy. Page 10 of 14 First, some basic set-up questions that will help you answer the bigger questions: a. [1.5 marks] Consider the 16-bit address that the processor sends to the memory system. For the direct-mapped cache, determine which of these 16 bit(s) (one or more of bits A0 through A15) provide the following information: i. The word in the cache line (and memory block) being accessed ii. The line in the cache where the accessed block would reside iii. The Tag bits for this block Place these three answers into the answer spreadsheet file Q4_Answer.csv in the cells indicated (under ‘Address Bits’) for Question 4(a). b. [1.5 marks] Consider the 16-bit address that the processor sends to the memory system. For the 4-way set associative cache (which has just two sets), determine which of these 16 bit(s) (one or more of bits A0 through A15) provide the following information: i. The word in the cache line (and memory block) being accessed ii. The Set in the cache that will be used for the accessed block iii. The Tag bits for this block Place these three answers into the answer spreadsheet file Q4_Answer.csv in the cells indicated (under ‘Address Bits’) for Question 4(b). Now, in parts (c) and part (d) you are asked to determine the contents of the two types of caches after a sequence of memory accesses by the processor, and the hit rates of each cache for that sequence. Table 1 below gives the contents of main memory at the beginning, prior to any memory accesses. This is the state of the memory at the beginning of your analysis of both caches. Table 2 below gives the sequence of memory accesses made by the processor. Some of these accesses may be for instruction fetches, some are for data reads, and some for data writes. For writes, Table 2 also gives the data that is to be written into the word. The cache is used for all reads (instruction fetches and data reads) and writes. Page 11 of 14 Address (Hex) Data (Hex) Address (Hex) Data (Hex) 1000 A0 1010 B0 1001 A1 1011 B1 1002 A2 1012 B2 1003 A3 1013 B3 1004 A4 1014 B4 1005 A5 1015 B5 1006 A6 1016 B6 1007 D0 1017 B7 1008 D1 1018 B8 1009 D2 1019 B9 100A D3 101A BA 100B D4 101B BB 100C D5 101C BC 100D D6 101D BD 100E D7 101E BE 100F D8 101F BF Table 1 - Memory contents before start Access Number Address (Hex) Read (R) or Write (W) Value if Write 1 1000 R 2 1001 R 3 1007 R 4 100E R 5 100A W 1 6 101F R 7 1002 W 2 8 100F R 9 100C R 10 1018 W 3 11 1014 R 12 1015 R 13 1019 R 14 1016 R 15 1008 R Table 2 - Memory access sequence Page 12 of 14 (c) (i) [8 marks] Determine the contents of the direct-mapped cache after the sequence of memory accesses given in Table 2 have been completed, with the initial memory contents as given in Table 1. This includes the Data, Tag, Valid and Dirty Bits. The Data and Tag must be given in hexadecimal. For the Valid and Dirty Bits, only show those bits which are ‘1’, and leave those that are ‘0’ blank for easier visibility. Assume that the cache is empty at the start, meaning all Valid bits are ‘0’ at the start. Place your answer into the spreadsheet file Q4_Answer.csv as indicated in that file for Question 4(c)(i). A visualization of that table is given below for your reference. Line # Word 1 (Hex) Word 0 (Hex) Tag (Hex) D V 0 1 2 3 4 5 6 7 You are required to hand in your rough work for this question, and it should clearly illustrate the process that you worked through to arrive at your answers. You should submit your rough work as described at the beginning of this question, in a file named Q4cRoughWork. This file can be either a spreadsheet (.csv or .xlsx or .xls type), or a photograph of written rough work (.jpg or .pdf type). Make sure that any picture of your rough work is clear and in focus. (c) (ii) [3 marks] For the complete sequence of memory accesses in Table 2, determine the number of hits, number of misses and the hit rate for the direct-mapped cache. Place these three answers into the answer spreadsheet file Q4_Answer.csv as indicated for Question (c) (ii). Your rough work (described above) should clearly indicate which specific accesses were hits and misses. Page 13 of 14 (d) (i) [8 marks] Here you are asked to do the same task as in part (c), but for the 4-way Set Associative cache specified above. Determine the contents of the 4-way set associative cache (noting again that it has just two sets) described above after the sequence of memory accesses given in Table 2 have been completed, including the Data, Tag, Valid and Dirty Bits. As before, the initial contents of main memory are given in Table 1. The Data and Tag should again be given in hexadecimal (We note that the Tag is more complicated to represent in hex). For the Valid and Dirty Bits, only show those bits which are ‘1’, and leave those that are ‘0’ blank for easier visibility. Assume that the cache is empty at the start, meaning all Valid bits are ‘0’ at the start. Place your answer into the spreadsheet file Q4_Answer.csv as indicated in that file for Question 4(d)(i). A visualization of that table is given below for your reference. Line # Set # Word 1 (Hex) Word 0 (Hex) Tag (Hex) D V 0 1 2 3 4 5 6 7 You are required to hand in your rough work for this question, and it should clearly illustrate the process that you worked throu gh to arrive at your answers. You should submit your rough work as described at the beginning of this question, in a file named Q4dRoughWork. This file can be either a spreadsheet (.csv or .xlsx or .xls type), or a photograph of written rough work (.jpg or .pdf type). Make sure that any picture of your rough work is clear and in focus. (d) (ii) [3 marks] For the complete sequence of memory accesses in Table 2, determine the number of hits, number of misses and the hit rate for the 4-way set associative cache. Place these three answers into the answer spreadsheet file Q4_Answer.csv as indicated for Question (d) (ii). Your rough work (described above) should clearly indicate which specific accesses were hits and misses. Be sure, with each submission, that you submit three files - Q4_Answer.csv and the two rough work files. Download all of your submissions to ensure that you correctly uploaded the file that you intended. ———————————–Second Pledge —————————————- Print and submit this page: First Name Last Name Student Number As part of your assessment, please sign the following reaffirmation: I pledge upon my honour that I did not violate our Faculty’s Code of Behaviour on Academic Matters during this assessment by acting in any way that would constitute cheating, misrepresentation, or unfair- ness, including but not limited to, using unauthorized aids and assistance, impersonating another person, and committing plagiarism. I acknowledge that providing unauthorized assistance to someone else is also considered a serious academic offence. (sign your name) If you have access to a printer: print this page, fill in your name and student number, sign the pledge, and then scan/photograph the page and submit it with the file name secondpledge.jpg or secondpledge.pdf to the Quercus assignment labelled ‘First Honour Statement and Signature.’ If you do not have access to a printer: in a text file named secondpledge.txt, type your name and student number, the full pledge into this file, and type your name in place of the signature. Upload this file to the same assignment as above. Page 14 of 14
