Andrew login ID:Full Name:Recitation Section:CS 15-213, Spring 2009Exam 2Tuesday, April 7th, 2009Instructions:• Make sure that your exam is not missing any sheets, then write your full name, Andrew login ID, andrecitation section (A–J) on the front.• Do not write any part of your answers outside of the space given below each question. Writeclearly and at a reasonable size. If we have trouble reading your handwriting you will receiveno credit on that problem.• The exam has a maximum score of 100 points.• The problems are of varying difficulty. The point value of each problem is indicated. Pile up the easypoints quickly and then come back to the harder problems.• This exam is OPEN BOOK. You may use any books or notes you like. No calculators or otherelectronic devices are allowed.• Good luck!1 (20):2 (15):3 (15):4 (15):5 (10):6 (25):TOTAL (100):Page 1 of 12Problem 1. (20 points):In this problem, you will perform cache analysis for three code sequences. Assume a very small directmapped 16 byte data cache with two cache lines. We assume a float requires 4 bytes. Drawing the cachehelps.For each code sequence, we assume a cold cache and that the array X is cache aligned (that is, X [0] isloaded into the the beginning of the first cache line. All other variables are held in registers.Recall that miss rate is defined as#misses#accesses.1. Code 1:float X[8], t = 0;for(int j = 0; j < 2; j++)for(int i = 0; i < 8; i++)t += X[i];Answer the following:(a) Miss rate:(b) What types ot types of locality does this code have with respect to this cache?2. Code 2:float X[8], t = 0;for(int j = 0; j < 2; j++){for(int i = 0; i < 7; i += 2)t += X[i];for(int i = 1; i < 8; i += 2)t += X[i];}Answer the following:(a) Miss rate:(b) What types ot types of locality does this code have with respect to this cache?3. Code 3:float X[8], float t = 0;for(i = 0; i < 2; i++)for(k = 0; k < 2; k++)for(j = 0; j < 4; j++)t += X[j + i*4];Page 2 of 12Answer the following:(a) Miss rate:(b) What types ot types of locality does this code have with respect to this cache?4. Changing Cache:All three code fragments above perform the same computation. Assume you could change the codeany way you want to perform the same computation and also change the cache as you wish.(a) What is the minimum number of cache misses achievable?(b) How would the cache look like to achieve this?Page 3 of 12Problem 2. (15 points):1. If a direct mapped cache is 8KB in size, and has 32 byte cache blocks, how many lines are there ineach set?(a) 256(b) 64(c) 32(d) 12. You have a 32-bit virtual memory system with 4KB page frames, with a TLB with 4 sets, each ofwhich is 8-way set associative. How many bits of the virtual address form the TLBi (TLB index)?(a) 2(b) 4(c) 8(d) 123. Which of these features in a system best justifies the use of a two level page table structure, as opposedto a one level page table structure?(a) Small page sizes(b) Frequent memory accesses(c) High degree of spatial locality in programs(d) Sparse memory usage patterns4. Which section of an ELF file contains the compiled functions from a program?(a) .data(b) .rodata(c) .text(d) .bss5. Which of the following is true?(a) Every signal that is sent is also received(b) Signals are always received immediately since they cause an interrupt(c) Signals can only be received after a context switch(d) Signals can only be received upon returning from system modePage 4 of 126. Consider a theoretical computer architecture with 50-bit virtual addresses and 16kb pages. What isthe maximum number of levels of page tables that could be used in the virtual memory system?(a) 16(b) 36(c) 2(d) 507. Which blocks the signal SIGKILL?(a) signal(SIGKILL, SIG IGN);(b) sigfillset(&set); sigprocmask(SIGBLOCK, set);(c) a and b(d) none of the above8. Which of the following will reduce the number of compulsory (cold) cache misses in a program?(a) Increasing the associativity(b) Increasing line size(c) Both a & b(d) None of the above9. Linkers can take as input which of the following file types? (circle all correct answers)(a) .c(b) .o(c) .a(d) .s10. Blocking matrix-matrix multiplication can increase what type(s) of locality?(a) Temporal(b) Spatial(c) Both11. Give two functions that don’t return (two completely different functions, not variations of one).Page 5 of 12Problem 3. (15 points):Suppose we have the following two .c files:alarm.cint counter;void sigalrm_handler (int num) {counter += 1;}int main (void) {signal(SIGALRM, &sigalrm_handler);counter = 2;alarm(1);sleep(1);counter -= 3;exit(counter);return 0;}fork.cint counter;void sigchld_handler(int num) {int i;wait(&i);counter += WEXITSTATUS(i);}int main (void) {signal(SIGCHLD, &sigchld_handler);counter = 3;if (!fork()) {counter++;execl("alarm", "alarm", NULL);}sleep(2);counter*= 3;printf("%d\n", counter);exit(0);}Assume that all system calls succeed and that all C arithmetic statements are atomic.The files are compiled as follows:gcc -o alarm alarm.cgcc -o fork fork.cSuppose we run ./fork at the terminal. What are the possible outputs to the terminal?Page 6 of 12Problem 4. (15 points):Harry Q. Bovik builds and runs a C program from the following two files:----------------------------------------main.c:#include <stdio.h>long a = 1;const long b = 2;long c;long d = -1;int main(int argc, char*argv[]) {printf("a: %p\nb: %p\nc: %p\nd: %p\n", &a, &b, &c, &d);printf("%ld\n", c);return 0;}----------------------------------------data.c:unsigned int c[2] = {...};----------------------------------------And sees this output:a: 0x601020b: 0x400650c: 0x601030d: 0x6010284294967297Harry was expecting the variables to be in order, one after another. Obviously, he was very wrong. Helphim figure out what’s happening using your knowledge of linking and executable layouts. Be specific butconcise with your answers.(a) How many symbols does main.c generate in the executable program’s symbol table?(b) What are the strong symbols from main.c, and what are the weak symbols from main.c?Page 7 of 12(c) Note the address of b. Why is it far removed from the addresses of the other variables?(d) Why is c located after d in memory, even though it’s before d in Harry’s program?(e) Note the output given by the final printf. Was Harry compiling and running the code on x86 or x86-64?How do you know?(f) Given that 4294967297 = 232+ 1, what would be output byprintf("{%d, %d}", c[0], c[1]);if it were executed in data.c?Page 8 of 12Problem 5. (10 points):Assume a System that has1. A
View Full Document
Unlocking...