______________________________ Your Name (first last) ______________________________ ← Name of person on left (or aisle) UC Berkeley CS61C Fall 2018 Midterm _____________________________ TA name ______________________________ SID ______________________________ Name of person on right (or aisle) → Fill in the correct circles & squares completely…like this: ⬤ (select ONE), and ⬛(select ALL that apply) Quest-clobber questions: Q2, Q3a, Q4 Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems. You say "I know, I'll use floating point!" Now you have 2.0001341678 problems. Then you say "I know, I'll solve it with threads!". have Now problems. two youQ1) Float, float on… (6 points; a,b 1pt; c,d 2pts) Consider an 8-bit “minifloat” SEEEEEMM (1 sign bit, 5 exponent bits, 2 mantissa bits). All other properties of IEEE754 apply (bias, denormalized numbers, ∞, NaNs, etc). The bias is -15. a) How many NaNs do we have? __________ b) What is the bit representation (in hex) of the next minifloat bigger than the minifloat represented by the hexadecimal value is 0x3F? __________ c) What is the bit representation (in hex) of the encoding of -2.5? __________ d) What does should_be_a_billion() return? (assume we always round down to 0) __________ minifloat should_be_a_billion() { minifloat sum = 0.0; for (unsigned int i = 0; i < 1000000000; i++) { sum = sum + 1.0; } return sum; } Q2) How can I bring you to the C of madness... (4 points) On the quest, you saw mystery, which should really have been called is_power_of_2, since it took in an unsigned integer and returned 1 when the input was a power of 2 and 0 when it was not. Well, it turns out we can write that in one line! What should the blanks be so that it works correctly? (Hint: start at iii and iv and think about how the bit pattern of two related numbers is special if N is a power of 2) int is_power_of_2(unsigned int N) { return (N != 0) ___ (N ____ (N ___ ____)); } /* ^ is bitwise xor, ~ is bitwise not */ i ii iii iv i ii iii iv ◯ | ◯ |! ◯ & ◯ &! ◯ || ◯ ||! ◯ && ◯ &&! ◯ ^ ◯ ^! ◯ ~ ◯ ~! ◯ | ◯ |! ◯ & ◯ &! ◯ || ◯ ||! ◯ && ◯ &&! ◯ ^ ◯ ^! ◯ ~ ◯ ~! ◯ – ◯ + ◯ * ◯ 0 ◯ 1 ◯ 2Q3) Cache money, dollar bills, y’all. (18 points; a-c 2pts d-g 3pts) We have a 32-bit machine, and a 4 KiB direct mapped cache with 256B blocks. We run the following code from scratch, with the cache initially cold, to add up the values of an uninitialized array to see what was there. uint8_t addup() { uint8_t A[1024], sum = 0; // 8-bit unsigned touch(A); for (int i = 0; i < 1024; i++) { sum += A[i]; } return sum - 1; } void touch(uint8_t *A) { // Touch random location // in A between first and // last elements, inclusive A[random(0, 1023)] = 0; } // e.g.,random(0,2)⇒ 0,1,or 2 a) Assume sum has the smallest possible value after the loop. What would addup return? __________ b) Let A = 0x100061C0. What cache index is A[0]? __________ c) Let A = 0x100061C0. If the cache has a hit at i=0 in the loop, what is the maximum value random could have returned? __________ For d and e, assume we don’t know where A is, and we run the code from scratch again. d) What’s the fewest number of cache misses caused by the loop? __________ e) What’s the most number of cache misses caused by the loop? __________ f) If we change to a fully associative LRU cache, how would c, d, e’s values change? (select ONE per col) c: ◯up ◯down ◯same d: ◯up ◯down ◯same e: ◯up ◯down ◯same g) When evaluating your code’s performance, you find an AMAT of 4 cycles. Your L1 cache hits in 2 cycles and it takes 100 cycles to go to main memory. What is the L1 hit rate? __________%Q4) RISC-V business: I’m in a CS61C midterm & I’m being chased by Guido the killer pimp... (14 points) a) Write a function in RISC-V code to return 0 if the input 32-bit float = ∞, else a non-zero value. The input and output will be stored in a0, as usual. (If you use 2 lines=3pts. 3 lines=2 pts) isNotInfinity: _________________________ _________________________ _____ a0, ______, ______ ret (the rest of the question deals with the code on the right) Consider the following RISC-V code run on a 32-bit machine: done: li a0, 1 ret fun: beq a0, x0, done addi sp, sp, -12 addi a0, a0, -1 sw ra, 8(sp) sw a0, 4(sp) sw s0, 0(sp) jal fun mv s0, a0 lw a0, 4(sp) jal fun add a0, a0, s0 lw s0, 0(sp) lw ra, 8(sp) addi sp, sp, 12 ret b) What is the hex value of the machine code for the underlined instruction labeled fun? (choose ONE) ◯0xFE050EEA ◯0xFE050EE3 ◯0xFE050CE3 ◯0xFE050FE3 ◯0xFE050EFA ◯0xFE050FEA c) What is the one-line C disassembly of fun with recursion, and generates the same # of function calls: uint32_t fun(uint32_t a0) { return ______________________________________________ } d) What is the one-line C disassembly of fun that has no recursion (i.e., see if you can optimize it): uint32_t fun(uint32_t a0) { return ______________________________________________ } e) Show the call and the return value for the largest possible value returned by (d) above: