Andrew login ID Full Name CS 15 213 Fall 2004 Final Exam December 16 2004 Instructions Make sure that your exam has 24 pages and 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 123 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 any other electronic or wireless device Good luck 1 10 2 12 3 14 4 6 5 8 6 8 7 8 8 9 9 9 10 13 11 10 12 6 13 10 TOTAL 123 1 of 24 Problem 1 10 points Consider the following 16 bit floating point representation based on the IEEE floating point format There is a sign bit in the most significant bit The next k 7 bits are the exponent The exponent bias is 63 The last n 8 bits encode the significand Numeric values are encoded in this format as a value of the form V 1 s M 2E where s is the sign bit E is exponent after biasing and M is the significand Part I Answer the following problems using either decimal e g 1 375 or fractional e g 11 8 representations for numbers that are not integers For denormalized numbers A What is the smallest value E of the exponent after biasing B What is the largest value M of the significand For normalized numbers A What is the smallest value E of the exponent after biasing B What is the largest value E of the exponent after biasing C What is the smallest value M of the significand D What is the largest value M of the significand 2 of 24 Part II Suppose we want to implement this representation in C One way to do this would be with the following struct The 16 bit float is stored as two unsigned chars assumed to be 8 bits each typedef struct unsigned char exps unsigned char frac float16 You are now asked to finish implementing a function that takes a float16 and divides it by 2 The value returned by div2 should follow the IEEE format restrictions that we described earlier for this 16 bit number You may assume that the argument f is non negative float16 div2 float16 f save copies so we can modify struct fields unsigned char frac f frac unsigned char exps f exps check for infinity and NaN if exps in that case division gives us same number f frac frac f exps exps check for denormalized numbers if exps f frac f exps check for a normalized number that becomes denormalized if exps f frac f exps if f frac f exps remaining cases return f 3 of 24 Problem 2 12 points This problem concerns the way virtual addresses are translated into physical addresses Imagine a system with the following parameters Virtual addresses are 20 bits wide Physical addresses are 18 bits wide The page size is 4096 bytes The TLB is 2 way set associative with 16 total entries The contents of the TLB and the first 32 entries of the page table are shown as follows All numbers are given in hexadecimal Index 0 1 2 3 4 5 6 7 TLB Tag PPN 16 13 1B 2D 10 0F 0F 1E 1F 01 11 1F 03 2B 1D 23 06 08 0F 19 0A 09 1F 20 02 13 18 12 0C 0B 1E 24 Valid 1 1 1 0 1 0 1 0 1 1 1 1 0 1 0 0 Page Table VPN PPN Valid VPN PPN Valid 00 17 1 10 26 0 01 28 1 11 17 0 02 14 1 12 0E 1 03 0B 0 13 10 1 04 26 0 14 2D 0 05 13 1 15 1B 0 06 0F 1 16 31 1 07 10 1 17 12 0 08 1C 0 18 23 1 09 25 1 19 04 0 0A 31 0 1A 0C 1 0B 16 1 1B 2B 1 0C 01 1 1C 1E 0 0D 15 1 1D 3E 1 0E 0C 0 1E 27 1 0F 14 0 1F 18 1 4 of 24 Part 1 1 The diagram below shows the bits of a virtual address Please indicate the locations of the following fields by placing an X in the corresponding boxes of that field s row For example if the virtual page offset were computed from the 2 most significant bits of the virtual address you would mark the O offset column as shown 19 O O N I T 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 X X The virtual page offset The virtual page number The TLB index The TLB tag 19 18 17 16 15 O N I T 2 The diagram below shows the format of a physical address Please indicate the locations of the following fields by placing an X in the corresponding boxes of that field s row O N The physical page offset The physical page number 17 16 15 14 13 12 11 10 9 O N 5 of 24 8 7 6 5 4 3 2 1 0 Part 2 For the given virtual addresses please indicate the TLB entry accessed and the physical address Indicate whether the TLB misses and whether a page fault occurs If there is a page fault enter for PPN and leave the physical address blank Virtual address 0x00123 1 Virtual address one bit per box 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 2 Address translation Parameter VPN TLB Index TLB Tag Value 0x 0x 0x Parameter TLB Hit Y N Page Fault Y N PPN Value 0x 3 Physical address one bit per box 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 12 11 10 9 8 7 6 5 4 3 2 1 0 6 5 4 3 2 1 0 Virtual address 0x02321 1 Virtual address one bit per box 19 18 17 16 15 14 13 2 Address translation Parameter VPN TLB Index TLB Tag Value 0x 0x 0x Parameter TLB Hit Y N Page Fault Y N PPN Value 0x 3 Physical address one bit per box 17 16 15 14 13 12 11 10 9 6 of 24 8 7 Problem 3 14 points Short answer questions two points each Write at most one line s worth of text to each question Make sure that your answer is legible use the scratch space at the top until you re …
View Full Document
Unlocking...