Andrew login ID:Full Name:CS 15-213, Spring 2003Exam 2April 10, 2003Instructions:• Make sure that your exam is not missing any sheets, then write your full name and Andrew login IDon the front.• Write your answers in the space provided below the problem. If you make a mess, clearly indicateyour final answer.• The exam has a maximum score of 77 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. You may not use a calculator,laptop or other wireless device. Good luck!1 (8):2 (10):3 (9):4 (20):5 (8):6 (6):7 (8):8 (8):TOTAL (77):Page 1 of 16Problem 1. (8 points):Here’s a familiar function that returns the nth fibonacci number:int fibo(int n) {if (n == 0)return 0;if (n == 1)return 1;if (n == 2)return 1;return fibo(n-1) + fibo(n-2);}This implementation is way too slow. Which of the following are the two main contributing factors? (Circlethe correct answer)(a) There are two recursive calls per iteration.(b) There are too many if checks before the actual recursion.(c) The overhead of a recursion (calling functions) is too high as compared to the actual work done.(d) The recursive calls only goes down by 1 or 2 each round. (i.e. n − 1 and n − 2)You have been hired recently to create the world’s fastest fibonacci number generator to be run on a IntelPentium III just like our fish machines.You wrote your first draft as shown below. Assume n takes only natural numbers.int fibo2(int n) {int x = 0;int y = 1;int tmp, i;if (n < 2)return n;for (i = 2; i <= n; ++i) {tmp = y;y = x + y;x = tmp;}return y;}Page 2 of 16This program gave a terrific improvement over the recursive implementation. However, unsatisfied withthe result, you seek to further improve the program. Consider the following two alternatives, fibo3 andfibo4. Assume n to be very large (e.g. > 10000).int fibo3(int n) {int x = 0;int y = 1;int i;if (n < 2)return n;for (i = 2; i <= n; i+=2) {x = x + y;y = x + y;}if (i == n+1)return y;return x;}Is fibo3 faster than fibo2? Yes NoWhy? Please give short answers (one sentence and/or indicative keywords will suffice)Page 3 of 16Here’s another one:int fibo4(int n) {int p = 0; int q = 1; int r = 1; int s = 2;int k = 3; int l = 5; int m = 8; int o = 13;int i;if (n < 2) return n;if (n == 2) return r;if (n == 3) return s;if (n == 4) return k;if (n == 5) return l;if (n == 6) return m;if (n == 7) return o;for (i = 8; i <= n; i+=8) {p = m + o;q = o + p;r = p + q;s = q + r;k = r + s;l = s + k;m = k + l;o = l + m;}if (i == n+1) return o;if (i == n+2) return m;if (i == n+3) return l;if (i == n+4) return k;if (i == n+5) return s;if (i == n+6) return r;if (i == n+7) return q;return p;}Is fibo4 faster than fibo3? Yes NoWhy? Please give short answers (one sentence and/or indicative keywords will suffice)Page 4 of 16Problem 2. (10 points):The following problem concerns basic cache lookups.• The memory is byte addressable.• Memory accesses are to 1-byte words (not 4-byte words).• Physical addresses are 12 bits wide.• The cache is 4-way set associative, with a 2-byte block size and 32 total lines.In the following tables, all numbers are given in hexadecimal. The Index column contains the set indexfor each set of 4 lines. The Tag columns contain the tag value for each line. The V column contains thevalid bit for each line. The Bytes 0–1 columns contain the data for each line, numbered left-to-right startingwith byte 0 on the left.The contents of the cache are as follows:4-way Set Associative CacheIndex Tag V Bytes 0–1 Tag V Bytes 0–1 Tag V Bytes 0–1 Tag V Bytes 0–10 30 1 4E 47 4B 0 1A D6 77 1 5A B3 EA 0 OD C31 09 1 F8 88 AF 1 CA 4A 6C 0 8B 58 47 1 3A 172 80 1 4B 59 3B 0 84 0D A6 1 B4 5B EE 1 FF 753 C4 1 77 CF 77 0 61 DC 3A 1 6B D5 C3 0 1A 9F4 0D 0 87 2A 66 1 CE 64 7D 1 4E AF D6 0 89 295 E3 1 30 E8 3F 1 1E E8 B4 0 E2 5F 84 1 59 C06 60 0 93 2B 35 0 56 46 D4 1 64 CD FE 0 CA 987 A7 1 B2 9B 1B 0 1F 0E 35 1 9E 44 08 0 04 12Part 1The box below shows the format of a physical address. Indicate (by labeling the diagram) the fields thatwould be used to determine the following:CO The block offset within the cache lineCI The cache indexCT The cache tag11 10 9 8 7 6 5 4 3 2 1 0Page 5 of 16Part 2For the given physical address, indicate the cache entry accessed and the cache byte value returned in hex.Indicate whether a cache miss occurs.If there is a cache miss, enter “-” for “Cache Byte returned”.Physical address: EE4A. Physical address format (one bit per box)11 10 9 8 7 6 5 4 3 2 1 0B. Physical memory referenceParameter ValueCache Offset (CO) 0xCache Index (CI) 0xCache Tag (CT) 0xCache Hit? (Y/N)Cache Byte returned 0xPhysical address: B4AA. Physical address format (one bit per box)11 10 9 8 7 6 5 4 3 2 1 0B. Physical memory referenceParameter ValueCache Offset (CO) 0xCache Index (CI) 0xCache Tag (CT) 0xCache Hit? (Y/N)Cache Byte returned 0xPage 6 of 16Problem 3. (9 points):This problem tests your understanding of memory bugs. Each of the code sequences below may or may notcontain memory bugs. The code all compiles without warnings or errors. If you think there is a bug, pleasecircle YES and indicate the type of bug from the list below of memory bugs. Otherwise, if you think thereare no memory bugs in the code, please circle NO.Bugs:1. buffer overflow error2. memory leak3. dereference of possibly bad pointer4. incorrect use of free5. incorrect use of realloc6. misaligned access to memory7. Other memory bugA. typedef struct _stackelem* StackElem;struct _stackelem {void* ptr;StackElem next;};typedef struct _stack* Stack;struct _stack {StackElem top;};void* popptr(Stack s){void* ret;if (s == NULL) return NULL;if (s->top != NULL) {ret = s->top->ptr;s->top = s->top->next;return ret;}return NULL;}NO YES Type of bug(s):Page 7 of 16B. void readints(int* count, int* vals){int i;scanf("%d\n", count);vals = malloc(*count * sizeof(int));for (i = 0; i<*count; i++) {scanf("%d\n", vals+i);}}void caller(void){int count;int* vals;/* some stuff */readints(&count, vals);/* some more stuff *//* all done with inputs */free(vals);}NO YES Type of bug(s):C. struct IntList {int val;struct IntList* next;};struct IntList*addToList(struct IntList* old, int v){struct IntList* newone;newone = malloc(sizeof(struct IntList));newone->val = v;newone->next = old;return newone;}NO YES Type of bug(s):Page 8 of 16Problem 4. (20
View Full Document
Unlocking...