It's a test, need an expert to help at the required time period and do the test together.
Final_CSE120_qs.docx Q1 Suppose there are 3 cache designs Design 1: Direct-mapped cache. Each cache block is 1 byte. Cache has 10-bits for index and 6-bits for tag field. Design 2: 2-way set associative cache. Each cache block is 1 word (4 bytes). Cache has 7-bits for index and 7-bits for tag field. Design 3: fully associative cache with 256 cache blocks. Each cache block is 1 word. Cache has a 14-bit tag. a. What is the size of each cache? The size here comprises only the cached data (excluding tag bits or valid/dirty bits) b. How many total number of bits (or Kibits) does each cache need to store tags? c. Which cache design has the maximum number of conflict misses? Which has the least? Make sure to upload readable image of your work! a. Design1: Index=10bits. Therefore, no of blocks=2^10=1Ki. Cache size= 1Ki * 1 B = 1KiB. Design2: Index =7bits. No. of blocks= 2^7 * 2 = 256 (*2 because of the 2 way SA cache). Cache size = 256 * 4B = 1KiB Design3: No. of blocks=256. Cache size =256 * 4 B = 1KiB b. Design 1: 6-bits for tag field. Total tag space= 6 * no. of blocks= 6* 1Ki= 6Kibits Design 2: 7-bits for tag field. Total tag space= 7 * no. of blocks = 7 * 256= 1792 bits = (1782/1024) Kibits=1.75 Kibits Design 3: Cache has a 14-bit tag. Total tag space = 14 * no. of blocks=14* 256= 3.5 Kibits c. A direct mapped cache will have the maximum number of conflict misses, therefore it will be Design 1. Design 3 (Fully associative) will have 0 conflict misses This question(c) won’t feature in F2022 fnal exam Q2 This question examines the accuracy of 1-bit dynamic branch predictors for the following repeating patterns (e.g., in a loop) of branch outcomes. Answer each question (1-4) for each sequence (a-b): (a) T, T, T, T, NT (b) T, NT, NT, NT, NT 1. What is the accuracy (“score card” in lec 15-16) of a 1-bit dynamic predictor for these sequences of branch outcomes (a and b) provided we encounter this branch outcome sequence only once? Assume this predictor starts in the "Predict not taken" state for both a and b. Make sure to upload readable image of your work! You will need to show the prediction behavior using the following table format: Branch Prediction Actual Branch behavior Prediction Accuracy 1. (a) Branch Prediction Actual Branch behavior Prediction Accuracy NT T ❌ T T ✔ T T ✔ T T ✔ T NT ❌ Score card= 3/5 (b) Branch Prediction Actual Branch behavior Prediction Accuracy NT T ❌ T NT ❌ NT NT ✔ NT NT ✔ NT NT ✔ Score card=3/5 Q3 This question examines the accuracy of 2-bit dynamic branch predictors for the following repeating patterns (e.g., in a loop) of branch outcomes. Answer each question (1-4) for the following sequence T, T, T, T, NT 1. What is the accuracy (“score card” in lec 15-16) of the 2-bit predictor for this sequence of branch outcomes provided we encounter this branch outcome sequence only once, assuming that the predictor starts off in the “Strongly Predict Not Taken” state (SNT)? 2. What is the accuracy (“score card” in lec 15-16) of a 2-bit predictor if the pattern is repeated forever? Assume this predictor starts in the “Strongly Predict Not Taken” state (SNT). Make sure to upload readable image of your work! You will need to show the prediction behavior using the following table format: Branch Prediction Actual Branch behavior Prediction Accuracy 1. Branch Prediction Actual Branch behavior Prediction Accuracy SNT T ❌ WNT T ❌ WT T ✔ ST T ✔ ST NT ❌ Score card= 2/5 2. 1st pass already covered. 2nd pass: Branch Prediction Actual Branch behavior Prediction Accuracy WNT T ❌ WT T ✔ ST T ✔ ST T ✔ ST NT ❌ Score card= 3/5 3rd pass: Branch Prediction Actual Branch behavior Prediction Accuracy WT T ✔ ST T ✔ ST T ✔ ST T ✔ ST NT ❌ Score card= 4/5 Henceforth the pattern repeats. Therefore, for n passes, the score card is: (2 +3+ (n-2)*4)/ (5*n) .In infinity limit, this becomes 4/5 Q4 Given the following processor configuration of P1. Assume base CPI=1 without memory stalls; assume L1 hit occurs within base CPI. L1 access time=1 cycle (accounted for within base CPI), L1 miss rate=10%. L2 access time=10 cycles, L2 miss rate=40%. L3 access time=50 cycles, L3 miss rate=80%, Main memory access time = 100 cycles. 80% of instructions access L1 data cache. 1. Find the AMAT of P1 2. Find the overall CPI of P1 Make sure to upload readable image of your work! 1. AMAT = 1 + 0.1*10 + 0.1*0.4*50 + 0.1*0.4*0.8*100 = 7.2 cycles 2. Data cache access cycles d= 1 + 0.8*(0.1*10 + 0.1*0.4*50 + 0.1*0.4*0.8*100 )= 5.96 cycles CPI = Additional Cycles spent in accessing instruction + d = 0.1*10 + 0.1*0.4*50 + 0.1*0.4*0.8*100 +d = 12.16 cycles Q5 A 4-processor systems implements cache coherence with a snoopy MSI protocol. For each access in the sequence below (to the same BLOCK address), list the coherence states (M/S/I) for each processor’s cache after the access. Assume all the cache states begin in the Invalid (I) state. Event P1 state P2 state P3 state P4 state I I I I P1 reads P1 writes P2 reads P4 reads You may only upload an image of the completed table shown above. You do not need to show any other accompanying work. Event P1 state P2 state P3 state P4 state I I I I P1 reads S I I I P1 writes M I I I P2 reads S S I I P4 reads S S I S Q6 While executing a program, if the program references a page which is not available in the main memory then it is known as? a. Page Fault b. Demand Paging c. Page Miss d. Page Fragmentation Q7 Swap Space exists in ___________ a. Main Memory b. Secondary memory c. virtual memory d. TLB Q8 You are given a problem that can be solved in parallel using a group of coprocessors. Assume that 80% of the problem is parallelizable. If your target speedup is 4, what is the total number of coprocessors needed? a. 4 b. 8 c. 12 d. 16 Amdahl’s Law: 4 = 1/ [ 0.2 + 0.8/X] => 0.8/X + 0.2 = 0.25 => X = 16 Q9 For the MSI protocol, we use state values of the two state bits, V(Valid) and D (Dirty) to determine whether the block is Modified, Shared or Invalid. V indicates when the cache block is Valid and D indicates when the cache block is dirty (after a write) respectively. What are the most likely values of V and D bits for each state (M, S, I) that a cache block is in? a. M: V=1,D=1; S: V=1, D=0 ; I: V=0, D=X ; b. M: V=1,D=1; S: V=1, D=0 ; I: V=0, D=0 ; c. M: V=1,D=0; S: V=1, D=x ; I: V=0, D=X ; d. M: V=1,D=0; S: V=1, D=x ; I: V=1, D=0 ; Q10 When a Page Fault is encountered during a Virtual Address translation to Physical Address, either hardware or software can be used to handle the page fault. True/False Q11` In a Virtual Address translation to Physical Address, the main reason we use the Write Back scheme instead of Write Through in our caches is because: a. Disk memory access time takes millions of cycles compared to a few cycles at cache level b. Write Through is very costly to implement compared to write back c. The replacement of a translation in the TLB (in the event of a Page Fault) is incompatible with the Write Through strategy. d. The Write Through strategy needs buffers for speedup which makes it incompatible with a Virtual Memory Address translation