CS232 Fall 2006 Practice Final December 10, 20061. MIPS:Part A:Translate the function func into MIPS. Assume that the function f has already been translated. You mustobserve all calling conventions.int func(int a, int n) {if(n == 0)return a;return f(func(a, n - 1));}Part B:In a high-level language like C, it is possible for the return-type of a function to be a pointer to anotherfunction. Explain how you would write a MIPS function whose return value is the function func from Part A.Hint: Assume that the argument $a0 to your function is the address of a large chunk of memory to whichyou can write. Your function should eventually return the value $a0.2. Pipelining and ECC:This problem asks you to apply the concept of pipelining to networks. A sender encodes the data as packets(including parity bits for error detection) and transmits them over the network. The receiver inspectsthe packets and sends an acknowledgement indicating whether or not an error was detected. Thus, thetransmission process for each packet can be broken into five stages:Create (C): Create packet (data plus parity bit).Send (S): Send the packet across the network.Wait (W): Wait until an acknowledgement is received.Receive (R): Receive acknowledgement packet.Decode (D): Decode acknowledgement packet. If necessary, resend the original packet.These five tasks are handled by independent hardware, and can therefore be pipelined. The latency of eachstage is given below:Stage Latency (ms)C 1.0S 2.5W 2.0R 2.0D 0.7Part A:(a) Compute the latency of each packet and maximum throughput (in packets per second) assuming a5-stage pipeline.(b) Any packet that gets corrupted must be re-sent. If every packet has a 10% probability of gettingcorrupted, what is the expected time to send a packet?Part B:(a) Draw a pipeline diagram to indicate what the sender does when the acknowledgement indicates thatan error was detected.1CS232 Fall 2006 Practice Final December 10, 2006(b) Based on your diagram above, des cribe what the receiver must do when it detects that an error in thepacket.(c) Suppose each packet contains 8 bits hb0, b1, . . . , b7i. In the original scheme, there are 7 data bitshb0, b1, . . . , b6i and one parity bit b7, where b7is the parity of the data bits. Consider a different schemewhere each packet contains five data bits hb0, b1, . . . , b4i and three parity bits: b5, b6and b7. These bitsare computed as follows:b7= parity(hb0, b1, . . . , b4i)b6= parity(hb0, b2, b4i)b5= parity(hb1, b3i)The original scheme could not detect two errors. Show that even with this new scheme, two errorscannot be detected.3. Caches:Part A:A memory system has 32-bit byte addressable memory and a two-level c ache with the following specifications:L1 L2Data size 32 KB 256 KBBlock size 8 bytes 32 bytesAssociativity direct mapped 4-wayHit time 1 cycle 19 cyclesMiss rate 5% 2%(a) Compute the size of the following fields:L1 L2Block offsetIndex sizeTag size(b) If the AMAT of the L1 cache is 2 cycles, what is the miss penalty of the L2 cache?Part B:Consider the following MIPS code that traverses an array of $a1 bytes 30,000 times:# $a0 is the base address of the array, $a1 is its lengthli $t0, 0 # iterations of outer loopouter_loop:li $t1, 0 # iterations of inner loopmove $t2, $a0 # copy base address into $t2inner_loop:lb $t3, 0($t2) # temp = a0[t1]addi $t1, $t1, 1 # t1++addi $t2, $t2, 1bne $t1, $a1, inner_loop # repeat while t1 != a1addi $t0, $t0, 1 # t0++bne $t0, 30000, outer_loop2CS232 Fall 2006 Practice Final December 10, 2006Assume that the above program runs without interruption on a single-core machine with a split L1 cache(i.e. different data and instruction caches for L1). The L1 data cache is direct-mapped and holds N bytesof data. Your goal is to show that the above program can be used to determine N .(a) Compute an upper bound of the percentage of L1 data cache acc es se s that miss when $a1 ≤ N .(b) Compute a lower bound of the percentage of L1 data cache accesses that miss when $a1 > N .(c) You can determine the running time of the program accurately. Using your answers above, describe astrategy to determine the size of the L1 data cache.4. Virtual Memory: This question also counts towards Midterm 3.Part A:A virtual memory system has a byte-addressable memory with 9-bit virtual addresses and 6-bit physicaladdresses. The system has a two-level page table. The Level-1 table has 8 entries, each containing a pointerto a Level-2 table. Each Level-2 table has 8 entries, each containing a Physical Page Number, a valid bitand a dirty bit.(a) The page size is bytes and the total size of memory is pages.(b) The Level-1 table requires pages of memory and each Level-2 table requires pagesof memory. Explain your answer.(c) What is the maximum number of Virtual-to-Physical page number translations that can be held inmemory without causing a page fault?(d) What is the maximum number of Virtual-to-Physical page number translations that can be guaranteedto exist in memory without causing a page fault? (This is not the same as the previous answer!)Part B:Your friend HBN has discovered a serious flaw with virtual memory! Here is his argument:Consider a conditional branch statement in MIPS like beq $a0, $a1, label. We know that thetarget of the branch (i.e. label) is a PC-relative quantity indicating how far the target is locatedfrom the branch instruction. Suppose that in this branch ab ove, the target instruction is locateda few instructions after the branch.With virtual memory, this can be a serious problem. When the program is loaded into memory,suppose that the above branch instruction is the last instruction in virtual page v. Hence, thebranch target is in virtual page v + 1. Now, virtual page v might map to physical page p, butvirtual page v + 1 may not map to physical page p + 1!Hence, if we access the branch instruction from physical page p and try to “jump ahead” to physicalpage p + 1, we will get garbage.Explain why HBN is, as ever, wrong.5. Parallelization: Consider the following piece of code to compute the parity of an array of integers, wherean even number represents 0 and an odd integer represents 1:parity = 0;for(i = 0; i < N; ++i)if((array[i] % 2) == 1)parity = 1 - parity; // flip parityShow how you can parallelize this code to run faster on a machine with two processors. Be sure to indicatehow you will avoid race conditions and why your code will work c
View Full Document
Unlocking...