CS 61C Sample Exam.Spring 2021 FinalINSTRUCTIONSThis is your exam. Complete it either at exam.cs61a.org or, if that doesn’t work, by emailing course staff with yoursolutions before the exam deadline.This exam is intended for the student with email [email protected]. If this is not your email address,notify course staff immediately, as each exam is different. Do not distribute this exam PDF even after the exam ends,as some students may be taking the exam in a different time zone.For questions with circular bubbles, you should select exactly one choice.# You must choose either this option# Or this one, but not both!For questions with square checkboxes, you may select multiple choices.2 You could select this choice.2 You could select this one too!You may start your exam now. Your exam is due at <DEADLINE> Pacific Time.Go to the next pageto begin.Exam generated for [email protected] 2PreliminariesPlease complete and submit these questions before the exam starts.(a) What is your full name?(b) What is your student ID number?(c)If an answer requires hex input, make sure you only use capitalized letters! For example, 0xDEADBEEFinstead of 0xdeadbeef. You will be graded incorrectly otherwise! Please always add the hex (0x) andbinary (0b) prefix to your answers or you will receive 0 points. For all other bases, do not add the suffix orprefixes.Do not add units unless the problem explicitly tells you to!Some of the questions may use images to describe a problem. If the image is too small, you can click anddrag the image to a new tab to see the full image. You can also right click the image and download it orcopy its address to view it better. You can use the image below to try this. You can also click the star bythe question if you would like to go back to it (it will show up on the side bar). In addition, you are ablesee a check mark for questions you have fully entered in the sidebar. Questions will auto submit about 5seconds after you click off of them, though we still recommend you click the save button.Good luck!Exam generated for [email protected] 31. POTPOURRI(a) Q1i.You have a program that spends some percentage of its time waiting for requests and the rest of thetime performing calculations. Suppose you have 8 threads which you can use to parallelize calculations,with no overhead or non-parallelizable calculations. What is the maximum fraction of time that yoursequential program can spend on waiting for requests if we would like to achieve at least 4 timesspeedup? Leave your answer as a single simplified fraction.Exam generated for [email protected] 4(b) Q2The company you work at has a datacenter. Answer the following questions:i. Q2AA.The Mean Time Between Failures (MTBF) for this particular data center is 4000 hours. TheMean Time To Repair (MTTR) is 3 hours. What is the availability for this datacenter? Expressyour answer as a single simplified fraction.Exam generated for [email protected] 5ii. Q2BA.Your company would like to restrict the annualized failure rate to be 1% for the individualmachines in a large cluster. What does the Mean Time To Failure (MTTF) have to be to satisfythis annualized failure rate? Assume that the MTTF in this question is unrelated to that of parta. Write down your answer in years.Exam generated for [email protected] 6(c) Q3For each of the following functionalities, select the stage(s) in CALL for which the statement is true.i. Q3V2A. Replaces pseudo instructions.2 Compiler2 Assembler2 Linker2 LoaderB. Calculate all absolute addresses.2 Compiler2 Assembler2 Linker2 LoaderC. Generates parse trees.2 Compiler2 Assembler2 Linker2 LoaderD. Constructs symbol table.2 Compiler2 Assembler2 Linker2 LoaderExam generated for [email protected] 7(d) Q4Which of the following code blocks would see a performance improvement if we placed a#pragma omp forover the outer for loop? Select all that apply.i. Afor (int i = 0; i < 5000 - 3; i += 3) {a[i+2] = a[i] + a[i+1];}Bfor (int i = 0; i < 5000 - 2; i += 2) {a[i+2] *= a[i];}Cfor (int i = 0; i < 5000 - 3; i++) {a[i+2] = a[i] + a[i+1];}Dfor (int i = 0; i < 5000; i++) {a[i] = 100;}2 A2 B2 C2 D2 E. None of the aboveExam generated for [email protected] 82. Virtual Memory Caching(a) TIOAssume all systems are 32-bit.i.We’re given a system with an 4-way set associative cache of size 512 KiB with 128 B blocks. Howmany bits are allocated to the tag, index, and offset bits respectively?A. Tag:B. Index:C. Offset:D. Code AnalysisWe run the following code with our caching setup unchanged from the previous question. What isthe hit rate of the following lines of code?E. 1 #define base_arr_addr 0x123456782 #define ARR_SIZE 40963 #define I_BOUNDARY 20484 #define J_BOUNDARY 40965 #define I_STRIDE 1286 #define J_STRIDE 647 int arr[ARR_SIZE];89 uint32_t dummy_func(void) {10 //Loop 111 for (int i = 0; i < I_BOUNDARY; i += I_STRIDE) {12 for (int j = 0; j < J_BOUNDARY; j += J_STRIDE) {13 arr[i] = arr[i] + arr[j];14 }15 }1617 //Loop 318 for (int j = 0; j < J_BOUNDARY; j += J_STRIDE) {19 for (int i = 0; i < I_BOUNDARY; i += I_STRIDE) {20 arr[j] = arr[j] * arr[i];21 }22 }23 }Exam generated for [email protected] 9F. arr[i] = arr[i] + arr[j]G. arr[j] = arr[j] * arr[i]Exam generated for [email protected] 10H. NOTE: for all parts, assume changes propogate unless otherwise stated.As we’re working on running the code snippet, we realise we want to run different instances of thesame code. We choose to employ virtual memory on our memory space. We have 4 GiB of virtualmemory and 16 MiB of physical memory mapped with a single level page table with a page size of4 KiB. We choose to store 8 bits of metadata with each page table entry.I.After running one iteration of the inner loop for the code given in line, how many physical pageswill our page table take up?J.If our caching system remains as seen in question 1, how many caches would be needed to fully fitour page table? Give your answer as a decimal to two decimal places.K.We now switch our system to having a 2-level page table instead. Assuming we restart our systemand run one iteration of the inner loop, and that the VPN bits are split evenly between levels, howmany pages will our active page tables span?Exam generated for [email protected] 11(b) NOTE:due to a staff error in versioning, everyone will receive full points for this question.i.Assume now our system chooses to switch to another process. Which of the following events willoccur. Select all that apply.2 Save the page table to