Andrew login ID Full Name CS 15 213 Spring 2002 Final Exam May 9 2002 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 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 use a calculator but no laptops or other wireless devices Good luck 1 7 2 9 3 8 4 8 5 15 6 10 7 9 8 5 9 8 10 9 TOTAL 86 Page 1 of 22 Problem 1 7 points In this problem you will complete a function that converts float to int without explicit use of a conversion operator The following information may prove useful The IEEE float type uses 1 bit for sign 8 bits for the exponent with a bias of 127 and 23 bits for the fraction Your function should truncate floating pointing numbers i e round toward zero For example Since you are writing the conversion function you may not use the built in type conversion facilities of C You may not use relational operators and so on taking floating point arguments Keep in mind that C does not allow the use of bitwise operators on floating point types In the event of overflow or infinity you should return the largest INT MAX or smallest INT MIN representable integer as appropriate NaN not a number should be converted to 0 The following is the framework for the conversion function Fill in the blank lines with an appropriate C expression union conv float f unsigned long u int float2int float f union conv conv unsigned long u int sign exp frac shift conv f f u conv u if sign 1 else sign 1 exp frac if zero or denormalized return 0 if if NaN return 0 else if sign 0 Inf return INT MAX else return INT MIN Page 2 of 22 Add implicit 1 x in normalized representation frac 1 23 compute decimal point position i e total right shift needed shift if shift 0 if shift 32 return 0 else return sign frac shift else if shift 32 if sign 0 return INT MAX else return INT MIN return sign frac shift Page 3 of 22 Problem 2 9 points Part 1 Given the assembly for the function mystery1 fill in the corresponding function in C mystery1 push ebp mov esp ebp push ebx sub 0x18 esp movl 0x0 ecx movl 0x0 ebx L1 cmp 0xc ebp ebx jl L2 jmp L3 L2 mov 0x8 ebp eax mov eax ebx 4 edx add edx ecx incl ebx jmp L1 L3 mov ecx eax pop ebx mov ebp esp pop ebp ret int mystery1 int A int n int i int mystery answer 0 for answer i 0 i n i answer mystery A i return answer mystery Page 4 of 22 Part 2 mystery2 push ebp mov esp ebp sub 0x18 esp mov 0x8 ebp edx mov 0xc ebp ecx cmp ecx edx jge L1 add 0xfffffff8 esp sub edx ecx push ecx push edx call mystery2 add 0x10 esp jmp L3 L1 cmp ecx edx jle L2 add 0xfffffff8 esp push ecx sub ecx edx push edx call mystery2 add 0x10 esp jmp L3 L2 mov edx eax L3 mov ebp esp pop ebp ret A What would the following function call return x mystery2 6 4 x answer 2 B What is the mystery2 function computing Page 5 of 22 Problem 3 8 points This question is testing your understanding of the stack frame structure Part I The following memory image embeds a binary tree with root node at 0x804961c Please draw the logical organization of the tree in the same format as the shown example Please indicate the address and key value in hexidecimal of all the tree nodes and the pointers from parent nodes to child nodes The declaration of the tree node structure is as follows struct tree node int key struct tree node left struct tree Node right Addr 0x8049a4c Key 45 address of the root node tree node root Addr 0x8049a6c Key 10 Addr 0x8049a34 Key 70 Example binary tree Memory image address value 0x80495f8 0x0000000c 0x80495fc 0x00000000 0x8049600 0x00000000 0x8049604 0x0000001f 0x8049608 0x080495f8 0x804960c 0x08049610 0x8049610 0x00000022 0x8049614 0x00000000 0x8049618 0x00000000 0x804961c 0x00000037 0x8049620 0x08049604 0x8049624 0x08049628 0x8049628 0x0000003c 0x804962c 0x00000000 0x8049630 0x08049634 0x8049634 0x0000004e 0x8049638 0x00000000 0x804963c 0x00000000 Page 6 of 22 Part II The following function traverses the binary tree to locate the node with a given key value 1 struct tree node search struct tree node node 2 int value 3 4 if node key value 5 return node 6 else if node key value 7 if node left NULL 8 return NULL 9 else return search node left value 10 11 else 12 if node right NULL 13 return NULL 14 else return search node right value 15 16 Suppose we call search root 0x4e Fill in the blanks the value of these memory location so that it shows the stack when the execution is at line 5 More space than needed is provided You can assume that the stack stores only arguments return address and the ebp register value The value of ebp is 0xbffff880 when the program calls the function Write rtn addr for return addresses Address 0xbffff800 0xbffff7fc 0xbffff7f8 0xbffff7f4 0xbffff7f0 0xbffff7ec 0xbffff7e8 0xbffff7e4 0xbffff7e0 0xbffff7dc 0xbffff7d8 0xbffff7d4 0xbffff7d0 0xbffff7cc 0xbffff7c8 0xbffff7c4 Value 0x4e 0x804961c rtn addr Page 7 of 22 Problem 4 8 points In this problem you will compare the performance of direct mapped and way associative caches for the initialization of 2 dimensional array of data structures Both caches have a size of bytes The direct mapped cache has byte lines while the way associative cache has byte lines You are given the following definitions typedef struct float position float velocity 3 float forces 3 particle t adjacent particle t particle t cloth 32 32 register int i j k Also assume that sizeof float and sizeof particle t 4 sizeof float 4 surface begins at memory address 0 Both caches are initially empty The array is stored in row major order Variables i j k are stored in registers and any access to these variables does not cause a cache miss A What fraction of the writes in the following code will result in a miss in the direct mapped cache for i 0 i 32 i for j 0 j 32 j for k 0 k 3 k cloth i j forces k 0 Miss rate for writes to surface B Using code in part A what fraction of the writes will result in a miss in the 4 way associative cache Miss rate for writes to surface Page 8 of 22 C What fraction of the writes in the following …
View Full Document
Unlocking...