Andrew login ID:Full Name:CS 15-213, Fall 2004Final ExamDecember 16, 2004Instructions:• Make sure that your exam has 24 pages and is not missing any sheets, then write your full name andAndrew login ID on 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 123 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 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 24Problem 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 signbit, E is exponent after biasing, and M is the significand.Part IAnswer the following problems using either decimal (e.g., 1.375) or fractional (e.g., 11/8) representationsfor 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 24Part IISuppose we want to implement this representation in C. One way to do this would be with the followingstruct. 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. Thevalue returned by div2 should follow the IEEE format restrictions that we described earlier for this 16-bitnumber. 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 ( && ) /* remaining cases */{f.frac = ;f.exps = ;}return f;}3 of 24Problem 2. (12 points):This problem concerns the way virtual addresses are translated into physical addresses. Imagine a systemwith 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 aregiven in hexadecimal.TLBIndex Tag PPN Valid0 16 13 11B 2D 11 10 0F 10F 1E 02 1F 01 111 1F 03 03 2B 11D 23 04 06 08 10F 19 15 0A 09 11F 20 16 02 13 018 12 17 0C 0B 01E 24 0Page TableVPN PPN Valid VPN PPN Valid00 17 1 10 26 001 28 1 11 17 002 14 1 12 0E 103 0B 0 13 10 104 26 0 14 2D 005 13 1 15 1B 006 0F 1 16 31 107 10 1 17 12 008 1C 0 18 23 109 25 1 19 04 00A 31 0 1A 0C 10B 16 1 1B 2B 10C 01 1 1C 1E 00D 15 1 1D 3E 10E 0C 0 1E 27 10F 14 0 1F 18 14 of 24Part 11. The diagram below shows the bits of a virtual address. Please indicate the locations of the followingfields by placing an ’X’ in the corresponding boxes of that field’s row. For example, if the virtual pageoffset were computed from the 2 most significant bits of the virtual address, you would mark the ’O’(offset) column as shown:19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0O X XO The virtual page offsetN The virtual page numberI The TLB indexT The TLB tag19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0ONIT2. The diagram below shows the format of a physical address. Please indicate the locations of thefollowing fields by placing an ’X’ in the corresponding boxes of that field’s row.O The physical page offsetN The physical page number17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0ON5 of 24Part 2For the given virtual addresses, please indicate the TLB entry accessed and the physical address. Indicatewhether the TLB misses and whether a page fault occurs. If there is a page fault, enter “-” for “PPN” andleave the physical address blank.Virtual address: 0x001231. 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 02. Address translationParameter Value Parameter ValueVPN 0x TLB Hit? (Y/N)TLB Index 0x Page Fault? (Y/N)TLB Tag 0x PPN 0x3. Physical address(one bit per box)17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0Virtual address: 0x023211. 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 02. Address translationParameter Value Parameter ValueVPN 0x TLB Hit? (Y/N)TLB Index 0x Page Fault? (Y/N)TLB Tag 0x PPN 0x3. Physical address(one bit per box)17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 06 of 24Problem 3. (14 points):Short-answer questions, two points each. Write at most one line’s worth of text to each question. Make surethat your answer is legible: use the scratch space at the top until you’re sure of your answer. We will notgrade your scratch space.A. Briefly explain why a segregated list allocator is almost always faster than an equally well-writtenexplicit freelist allocator.B. Name the most important thing a process has that a thread lacks.C. Name one advantage of increasing the page size for virtual memory. Name one disadvantage.D. Name one advantage of dynamic linking over static linking. Name one disadvantage.E. Normally, the exponent field of a floating point number is interpreted as E − bias; but in denormalizednumbers (when E = 0), it is interpreted as 0 − bias + 1. Explain why.F. In network code using sockets, what condition would cause your process to receive a SIGPIPE?G. I’m writing a code to run a large simulation. I have made changes which I hope will halve the runningtime, and I try to get timings on the program by running it on my
View Full Document
Unlocking...