Andrew login ID Full Name CS 15 213 Spring 2003 Exam 2 April 10 2003 Instructions Make sure that your exam is not missing any sheets then write your full name and Andrew login ID on the front Write your answers in the space provided below the problem If you make a mess clearly indicate your 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 easy points 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 16 Problem 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 Circle the 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 Intel Pentium 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 16 This program gave a terrific improvement over the recursive implementation However unsatisfied with the result you seek to further improve the program Consider the following two alternatives fibo3 and fibo4 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 No Why Please give short answers one sentence and or indicative keywords will suffice Page 3 of 16 Here s another one int fibo4 int n int p 0 int q 1 int k 3 int l 5 int i if n 2 if n 2 if n 3 if n 4 if n 5 if n 6 if n 7 for i 8 p m q o r p s q k r l s m k o l return return return return return return return int r 1 int m 8 int s 2 int o 13 n r s k l m o i n i 8 o p q r s k l m if i n 1 if i n 2 if i n 3 if i n 4 if i n 5 if i n 6 if i n 7 return p return return return return return return return o m l k s r q Is fibo4 faster than fibo3 Yes No Why Please give short answers one sentence and or indicative keywords will suffice Page 4 of 16 Problem 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 index for each set of 4 lines The Tag columns contain the tag value for each line The V column contains the valid bit for each line The Bytes 0 1 columns contain the data for each line numbered left to right starting with byte 0 on the left The contents of the cache are as follows Index 0 1 2 3 4 5 6 7 Tag 30 09 80 C4 0D E3 60 A7 V 1 1 1 1 0 1 0 1 4 way Set Associative Cache Tag V Bytes 0 1 Tag V 4B 0 1A D6 77 1 AF 1 CA 4A 6C 0 3B 0 84 0D A6 1 77 0 61 DC 3A 1 66 1 CE 64 7D 1 3F 1 1E E8 B4 0 35 0 56 46 D4 1 1B 0 1F 0E 35 1 Bytes 0 1 4E 47 F8 88 4B 59 77 CF 87 2A 30 E8 93 2B B2 9B Bytes 0 1 5A B3 8B 58 B4 5B 6B D5 4E AF E2 5F 64 CD 9E 44 Tag EA 47 EE C3 D6 84 FE 08 V 0 1 1 0 0 1 0 0 Bytes 0 1 OD C3 3A 17 FF 75 1A 9F 89 29 59 C0 CA 98 04 12 Part 1 The box below shows the format of a physical address Indicate by labeling the diagram the fields that would be used to determine the following CO The block offset within the cache line CI The cache index CT The cache tag 11 10 9 8 7 6 5 4 3 2 1 0 Page 5 of 16 Part 2 For 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 EE4 A Physical address format one bit per box 11 10 9 8 7 6 5 4 3 2 1 0 2 1 0 B Physical memory reference Parameter Cache Offset CO Cache Index CI Cache Tag CT Cache Hit Y N Cache Byte returned Value 0x 0x 0x 0x Physical address B4A A Physical address format one bit per box 11 10 9 8 7 6 5 4 3 B Physical memory reference Parameter Cache Offset CO Cache Index CI Cache Tag CT Cache Hit Y N Cache Byte returned Value 0x 0x 0x 0x Page 6 of 16 Problem 3 9 points This problem tests your understanding of memory bugs Each of the code sequences below may or may not contain memory bugs The code all compiles without warnings or errors If you think there is a bug please circle YES and indicate the type of bug from the list below of memory bugs Otherwise if you think there are no memory bugs in the code please circle NO Bugs 1 buffer overflow error 2 memory leak 3 dereference of possibly bad pointer 4 incorrect use of free 5 incorrect use of realloc 6 misaligned access to memory 7 Other memory bug A typedef struct stackelem …
View Full Document
Unlocking...