Andrew login ID:Full Name:CS 15-213, Spring 2003MAKEUP - Final ExamMay 7, 2003Instructions:• Make sure that your exam has 25 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 114 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 (9):2 (11):3 (10):4 (5):5 (12):6 (8):7 (25):8 (12):9 (15):10 (4):11 (6):12 (9):TOTAL (114):1 of 25Problem 1. (9 points):Assume we are running code on an 8-bit machine using two’s complement arithmetic for signed integers.Short integers are encoded using 4 bits. Sign extension is performed whenever a short is cast to an int.For this problem, assume that all shift operations are arithmetic. All constants are ints. Fill in the emptyboxes in the table below.int i = -6;unsigned ui = i;short s = -7;unsigned short us = s;Note: TMax denotes the largest positive two’s complement int and TMin denotes the minimum negativetwo’s complement int. Please use only hex notation (i.e. not binary) for ‘Hex Representation’.Expression Decimal Representation Hex Representation27 27-16 −16ii >> 2ui(int) s(int)(6 ˆ s)(int) usTMaxTMin2 of 25Problem 2. (11 points):Consider the following 7-bit floating point representation based on the IEEE floating point format:• There is a sign bit in the most significant bit.• The next 3 bits encode the exponent. The exponent bias is 3.• The last 3 bits encode the significand.• The representation encodes numbers of the form: V = (−1)s× M × 2E, where M is the significandand E the integer value of the exponent.• The rounding mode is round-to-even.Please fill in the table below. You do not have to fill in boxes with ”——” in them. If a number is NAN orinfinity, you may disregard the M, E, and V fields below. However, fill the Description and Binary fieldswith valid data.Here are some guidelines for each field:• Description - A verbal description if the number has a special meaning• Binary - Binary representation of the number• M - Significand (same as the M in the formula above)• E - Exponent (same as the E in 2E)• V - Fractional Value representedPlease fill the M , E, and V fields below with rational numbers (fractions) rather than decimals orbinary decimalsDescription Binary M E V—— 0 101 0101781 111 111158+ 1Farthest from zero Negative NormalizedClosest to zero Negative Denormalized3 of 25Problem 3. (10 points):This problem tests your understanding of assembly code, control flow and multidimensional array layout.Consider the following assembly code for a procedure loopy:loopy:pushl %ebpmovl %esp, %ebppushl %esipushl %ebxmovl 8(%ebp), %ebxmovl $1, %edxmovl $0, %ecxcmpl %ebx, %ecxjge .L33movl $arr, %esi.L35:leal 0(,%ecx,8), %eaxaddl %ecx, %eaximull (%esi,%eax,4), %edxincl %ecxcmpl %ebx, %ecxjl .L35.L33:movl %edx, %eaxpopl %ebxpopl %esipopl %ebpretA. For each register listed, indicate which C variable(s) from the C source on the next page (i, tmp,arr, n it can hold during the lifetime of the function. If the register is not used to hold a variable on thenext page, then write in “none.” Note that there is not necessarily a one-to-one correspondence betweenvariables and registers.%eax%ebx%ecx%edx%esi%edi%ebp4 of 25 Continued ...(Question 3 cont’d)B. Based on the assembly code, fill in the blanks below in loopy’s C source code. (Note: you may onlyuse symbolic variables from the source code in your expressions below. Do not use register names.)int arr[5][____];int loopy(int n){int i;int tmp = ____;for(i = 0; __________; ______){tmp = ___________________arr[____][0];}return _______;}5 of 25Problem 4. (5 points):Consider the following C declarations:typedef struct{union {char d;short s;} u;char c;double *dptr;char buf[2];} final;Using the templates below (allowing a maximum of 24 bytes), indicate the allocation of data for structs oftype final. Mark off and label the areas for each individual element (arrays and unions may be labeled asa single element). Cross hatch the parts that are allocated, but not used, and be sure to clearly indicatethe end of the structure. Assume the Linux alignment rules discussed in class.final:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+| |+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+What would the following program print out?int main(){printf("%d\n",sizeof(final));}Output:6 of 25Problem 5. (12 points):In this problem, we will compare the best-case and worst-case scenarios for a memory access in a virtualmemory subsystem. You will want to pay careful attention to the following information about the availablefeatures of the subsystem:• No hardware caches (besides a Translation Lookaside Buffer) are present.• The system uses a 3-Level Page Table. The page directory (1st level page table) address is stored as aphysical address in a special register on the processor. The page directory is always in main memory.All page tables store physical addresses.• The Translation Lookaside Buffer (TLB) takes 1ns to query.• An access to main memory given a physical address costs 20ns.• A page fault costs 6ms. After a page fault, the page’s address translation is inserted into the TLB.• Assume that the processor restarts the address translation after a page fault.1. What is the best case data lookup time? NOTE: This is the time that elapses between when theprocessor presents a virtual address to the memory subsystem and when the word at that address hasbeen loaded/stored to/from a register.Answer:____________ ms __________ ns2. If the second level page-table is in main memory, what is the worst case data lookup time? Assumeno individual page faults more than once (for example, other processes will not interfere with thememory access).Answer:____________ ms __________ ns7 of 25Problem 6. (8 points):The following problem deals with memory allocation schemes. You have seen several ways to manage heapblocks. This problem deals with the buddy allocation scheme. In the buddy scheme, the heap
View Full Document
Unlocking...