University of California, Berkeley – College of Engineering Department of Electrical Engineering and Computer Sciences Fall 2015 Instructors: Vladimir Stojanovic, John Wawrzynek 2015-12-18 L J After the exam, indicate on the line above where you fall in the emotion spectrum between “sad” & “smiley”...!Last Name First Name Student ID Number CS61C Login cs61c- The name of your SECTION TA (please circle) Alex | Austin | Chris | David | Derek | Eric | Fred | Jason | Manu | Rebecca | Shreyas | Stephan | William | Xinghua Name of the person to your LEFT Name of the person to your RIGHT All the work is my own. I had no prior knowledge of the exam contents nor will I share the contents with others in CS61C who have not taken it yet. (please sign) Instructions (Read Me!) This booklet contains XX numbered pages including the cover page. After you finish the exam, turn in only this booklet, and not the green sheet or datapath diagram. • Please turn off all cell phones, smartwatches, and other mobile devices. Remove all hats & headphones. Place your backpacks, laptops and jackets under your seat. • You have 180 minutes to complete this exam. The exam is closed book; no computers, phones, or calculators are allowed. You may use three handwritten 8.5”x11” pages (front and back) of notes in addition to the provided green sheet. • There may be partial credit for incomplete answers; write as much of the solution as you can. We will deduct points if your solution is far more complicated than necessary. Make sure your solution is on the answer sheet for credit. MT1-1 MT1-2 MT1-3 MT1-4 MT2-1 MT2-2 MT2-3 MT2-4 MT2-5 Points Possible 8 8 12 8 9 11 9 12 5 F-1 F-2 F-3 F-4 Total Points Possible 9 8 8 11 118SID: _________________ 2/18 Clarifications during the exam: MT1 - depth question: 1. struct node * edges[] should be struct node ** edges 2. line in the prologue should read sw $ra 0($sp) 3. line after the epilogue should read lw $ra 0($sp) MT1-4: The label on Line 17 should be L2 MT2-Floating Point: real: bits 8-15. imaginary: bits 0-7 MT2-Clobbering Time: b. The cache is direct-mapped c. Memory accesses = accesses in the for loop at part I F-1: c. What is the maximum number of virtual pages a process can use?SID: _________________ 3/18 MT1-1: Potpourri – Good for the beginning… (8 points) a. True/False: i. The compiler turns C code into instructions ready to be run by a processor True False ii. The instruction addiu $t0 $t1 100000 is a TAL instruction True False iii. The linker computes the offset of all branch instructions True False b. Memory Management int global = 0; int* func() { int* arr = malloc(10 * sizeof(int)); return arr; } int main() { char* str = "hello world"; char str2[100] = "cs61c"; int* a = func(); return 0; } In what part of memory are each of the following values stored? *str: __________ str2[0]: __________ a: __________ arr: __________ arr[0]: __________ MT1-2: C-ing images through a kaleidoscope (8 points) Consider a grayscale image with a representation similar to the one you worked with in Project 4, where the image is represented by a 1-dimensional array of chars with length n x n. Fill out the following function block_tile. It returns a new, larger image array, which is the same image tiled rep times in both the x and y direction. You may or may not need all of the lines. For a better idea of what must be accomplished, consider the following example: char *image = malloc(sizeof(char) * 4); image[0] = 1; image[1] = 2; image[2] = 3; image[3] = 4; char *tiled_image = block_tile(image, 2, 2); The contents of tiled_image would then look like: tiled_image: [1, 2, 1, 2 3, 4, 3, 4 1, 2, 1, 2 3, 4, 3, 4];SID: _________________ 4/18 char *block_tile(char *block, int n, int rep) { int new_width = ________________________________________; char *new_block = malloc(________________________________________); for (int j = 0; j < new_width; j++) { for (int i = 0; i < new_width; i++) { int old_x = ________________________________________; int old_y = ________________________________________; int new_loc = ________________________________________; new_block[new_loc] = block[old_y * n + old_x]; } } ________________________________________; ________________________________________; return new_block; } MT1-3: Easy questions have no depth – this one does (12 points) We’re interested in running a depth-first search on a graph, and labeling the nodes in the order we finish examining them. Below we have the struct definition of a node in the graph, and the implementation of the function in C. struct node { int data; int label; int num_edges; struct node* edges[]; } Note that initially, all nodes in the graph have their label set to -1. The address width of our machine is 32 bits. int dfs_label(struct node* node, int counter) { if (node->label != -1) { return counter; } for (int i = 0; i < node->num_edges; ++i) { counter = dfs_label(node->edges[i], counter); } node->label = counter++; return counter; }SID: _________________ 5/18 Implement dfs_label in TAL MIPS. Assume node is in $a0 and counter is in $a1. You may not need all the lines provided. dfs_label: # prologue addiu $sp $sp ____ sw $ra ($sp) sw $s0 4($sp) sw $s1 8($sp) # base case addiu $t1 ____ ____ ____________________ ____________________ bne $t0 $t1 epilogue # loop addu $s0 ____ ____ addiu $s1 $0 0 loop: lw $t0 ____ beq ____ ____ ____ lw $a0 ____ # load edges into $a0 sll $t0 $s1 ____ ____________________ # load the next node lw $a0 ____ # into $a0 jal dfs_label addu $a1 ____ ____ addiu $s1 $s1 1 j loop fin: sw $a1 ____ ____________________ addu $v0 $0 $a1 epilogue: lw $ra ($sp) lw $s0 4($sp) lw $s1 8($sp) addiu $sp $sp ____ jr $raSID: _________________ 6/18 MT1-4: Can’t reveal this MIPS-tery (8 points) 0| Mystery: 1| add $t0, $a0, $0 2| add $t1, $a1, $0 3| 4| la $s0, L1 5| lw $s1, 12($s0) 6| addi $s2, $0, 6 7| addi $s3, $0, 0 8| addi $s4, $0, 1057 #$s4 contains 0b0100 0010 0001 9| sll $s4, $s4, 11 10| 11| L1: beq $s3, $s2, L2 12| addu $s1, $s1, $s4 13| sw $s1, 12($s0) 14| addu