THE AUSTRALIAN NATIONAL UNIVERSITY Final Examination – June 2021 ENGN2219 Computer Architecture and Simulation Sample Final Examination Study Period: 15 minutes Time Allowed: 180 minutes Permitted Materials: Open Book Total Marks: 100 Answer all questions. Please ensure that you have carefully read the instructions provided in the Git repository’s README file. Good luck! Did you Fork the exam repo before cloning? Question 1 [15 marks] (Q1.txt)The logic circuit below represents a lock system for a safe. A, B, and C represent switches on the front of the safe that can be set to zero or one. The door of the safe will unlock when both key signals have the value 1. (a) Write a truth table for the status of the safe door (0 for locked, 1 for unlocked) in terms of the inputs A, B, and C. [8 marks] (b) Consider the situation when one of the three inputs is broken, and can only be set to 0. There are three possible states you need to consider(A, B, or C, broken). Is there a combination of values for A, B, and C such that the safe is guarenteed to be open if any one of the inputs is broken? [7 marks] ENGN2219 Final Semester Exam 2021 Page 2 of 9 Question 2 [20 marks] (a) (sum squares.S)Translate the following C function sum squares into equivalent assembly. The use of registers must satisfy the ARM calling convention. You should write square as a seperate function, and call it from within sum squares, same as the original C code does. 1 int square(int x){ 2 return x*x; 3 } 4 5 6 int sum_squares(int n){ 7 int total = 0; 8 for(int i=0; i < n; i++){ 9 total = total + square(i); 10 } 11 return total; 12 } [10 marks] (b) (foo.c)Translate the following assembly function foo into an equivalent C function using the prototype int foo(int n); 1 @input r0 = n 2 @output r0 3 foo: 4 mov r1, 0 5 mov r2, 1 6 foo_loop: 7 add r2, r1, r2 8 sub r1, r2, r1 9 subs r0, 1 10 bne foo_loop 11 foo_done: 12 mov r0, r1 13 bx lr [10 marks] ENGN2219 Final Semester Exam 2021 Page 3 of 9 Question 3 [15 marks] (a) (Q3.txt) What are the key features of Monte Carlo simulation? Given a biased coin, how would you go about determining the probability of the result of a coin flip being heads using this approach?? [5 marks] (b) (Q3.txt) You are given the weather data for Canberra over the past ten years. Using this data, you are asked to predict the weather in Canberra for the coming month. Will you use interpolation or regression techniques for this purpose? Explain your reasoning. [5 marks] (c) (particle.py) You are given the following data that represents the motion of a particle: Time (s) 0 1 2 3 5 8 13 17 20 24 Distance (m) 1 0 -3 4 96 609 3264 7872 13281 23713 Compute quadratic and cubic fits for the data using regression techniques. Use the forward difference approximation approach to calculate the velocity and acceleration of the particle. Plot all four (the regression data, the velocity and acceleration) on the same graph against time. Also plot the original data using green circles. Give the graph appropriate labels, a title, and a legend. [5 marks] ENGN2219 Final Semester Exam 2021 Page 4 of 9 Question 4 [20 marks] All answers for this question should be written in Q4/src/q4.c. Below is an attempt at writing a function that computes the length of a string. As written, it has three different bugs. The lines on which the bugs are labelled. 1 int length_string(char* ptr) 2 { 3 count = 0; //bug A 4 while (ptr != 0){ //bug B 5 count += 1; 6 *ptr += 1; //bug C 7 } 8 return count; 9 } (a) Identify the three different bugs in this piece of code. Clearly state what the buggy lines should be replaced with, and fill out the function template below with the corrected version of the function. Write your answer in the indicated comment blocks inside Q4/src/q4.c 1 /* 2 Bug A: 3 TODO ??? 4 */ 5 6 /* 7 Bug B: 8 TODO ??? 9 */ 10 11 /* 12 Bug C: 13 TODO ??? 14 */ [5 marks] (b) Write out the length string function with all bugs removed, using the following template. Give an example of how to correctly call this function from c main. 1 int length_string(char* ptr) 2 { 3 // TODO: Insert the code from above , 4 // and fix the bugs. 5 } 6 7 // This gives us a pointer to the start of 8 // the .data section in main.S 9 char* hello = (char*) 0x20000000; 10 11 void c_main (){ 12 // TODO: Give an example of calling the length_string function 13 } [5 marks] (c) Explain how the correct version of the length string function works. [5 marks] (d) Suppose we fix some bugs and not others, as stated below. Describe as precisely as possible what the function will do when called as follows. ENGN2219 Final Semester Exam 2021 Page 5 of 9 If the code does not even compile, or the behavior is undefined, state as such, and why. If it is relevant to your answer, you may assume that the input to the function is a pointer to a string "Hello", which is stored at the beginning of the .data section, that is, at memory address 0x20000000. 1 /* 2 We fix all bugs except bug A: 3 TODO ??? 4 */ 5 6 /* 7 We fix all bugs except bug B: 8 TODO ??? 9 */ 10 11 /* 12 We fix all bugs except bug C: 13 TODO ??? 14 */ [5 marks] ENGN2219 Final Semester Exam 2021 Page 6 of 9 Question 5 [15 marks] Big Numbers Sometimes it’s required for the computer to be able to operate on numbers that are too large to fit inside a register (called bignums). Usually we can only operate directly on 32-bit integers, but sometimes integers can be larger than that. We’d like to create a data structure to store a 128-bit integer in memory. (a) In Q5/bignum.txt, describe a data structure that can be used to store a 128-bit unsigned integer, that is, the integer n being stored satisfies 0 ≤ n < 2128. Briefly justify how your data structure works. [5 marks] (b) In Q5/src/main.S, to demonstrate your data-structure, show how the following number would be encoded using your data structure. 264 + 1 = 0x1 00000000 00000001 [3 marks] (c) In Q5/src/main.S, write a function add_bignum take takes three inputs: 1. r0 : The memory address of a 128-bit unsigned integer (encoded using your data structure) in memory, called X. 2. r1 : Another memory address of a 128-bit unsigned, called Y . 3. r2 : A memory address. The function should compute the sum X + Y , and store the result encoded as a 128-bit unsigned integer at the address described in r2. You need not worry about the case that X +Y is too large to store as a 128-bit integer. (Hint: How do you add large numbers by hand? The devboard can add 32-bit numbers, how can you use this to add 128-bit integers?) [8 marks] ENGN2219 Final Semester Exam 2021 Page 7 of 9 Question 6 [15 marks] File: Q6/src/main.S For this question you need to create a program which finds integer multiples of a number in an array of numbers. A number n is a divisor of m if m can be divided by n without a remainder. If n is a divisor of m, then it follows that m is an integer multiple of n. Examples: 3 is a divisor of 12, as 12 can be divided by 3 without a remainder. 12 is clearly an integer multiple of 3, as 3 ∗ 4 = 12. 5 is not a divisor of 13, as 13 divided by 5 has a remainder. 5 can not be multiplied by an integer to get 13. Your task in this question is to write two functions: • is divisor: Check if the number in r0 it is divisible by the value in r1 without a remainder. Return 1 in r0 if the value is a divisor, otherwise return 0. Inputs: r0 Value r1 Divisor Outputs: r0 Result • find multiples: Using the is divisor function, copy every number in the input array for which r1 is a divisor, and write them to the output array. An example input and output list is provided in the question’s main.S file. Inputs: r0 Data array address r1 Divisor r2 Result array address Note that your program must work with sequences of any reasonable length, and must work for any reasonable value in r1. Please write the is divisor function before writing find multiples. The sequence is terminated with the number 0. Note also that the input numbers are stored as bytes in data array, and your result should be stored as bytes in result array. ENGN2219 Final Semester Exam 2021 Page 8 of 9 ENGN2219 Final Semester Exam 2021 Page 9 of 9
欢迎咨询51作业君