Andrew ID (print clearly!):Full Name:15-213/18-213, Fall 2011Exam 1Tuesday, October 18, 2011Instructions:• Make sure that your exam is not missing any sheets, then write your Andrew ID and full name on thefront.• This exam is closed book, closed notes (except for 1 double-sided note sheet). You may not use anyelectronic devices.• 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 66 points.• The problems are of varying difficulty. The point value of each problem is indicated. Good luck!1 (08):2 (08):3 (08):4 (04):5 (10):6 (08):7 (10):8 (04):9 (06):TOTAL (66):Page 1 of 15Problem 1. (8 points):Multiple choice. Write your answer for each question in the following table:1 2 3 4 5 6 7 81. What is the minimum (most negative) value of a 32-bit two’s complement integer?(a) −232(b) −232+ 1(c) −231(d) −231+ 12. What is the difference between the mov and lea instructions?(a) lea dereferences an address, while mov doesn’t.(b) mov dereferences an address, while lea doesn’t.(c) lea can be used to copy a register into another register, while mov cannot.(d) mov can be used to copy a register into another register, while lea cannnot.3. After executing the following code, which of the variables are equal to 0?unsigned int a = 0xffffffff;unsigned int b = 1;unsigned int c = a + b;unsigned long d = a + b;unsigned long e = (unsigned long)a + b;(Assume ints are 32 bits wide and longs are 64 bits wide.)(a) None of them(b) c(c) c and d(d) c, d, and ePage 2 of 154. Assume a function foo takes two arguments. When calling foo(arg1, arg2), which is thecorrect order of operations assuming x86 calling conventions and that foo must allocate stack space(implies that we must save the %ebp)?(a) push arg1, push arg2, call foo, push %ebp(b) push arg1, push arg2, push %ebp, call foo(c) push arg2, push arg1, call foo, push %ebp(d) push arg2, push arg1, push %ebp, call foo5. Which one of the following statements is NOT true?(a) x86-64 provides a larger virtual address space than x86.(b) The stack disciplines for x86 and x86-64 are different.(c) x86 uses %ebp as the base pointer for the stack frame.(d) x86-64 uses %rbp as the base pointer for the stack frame.6. Consider a 4-way set associative cache (E = 4). Which one of the following statements it true?(a) The cache has 4 blocks per line.(b) The cache has 4 sets per line.(c) The cache has 4 lines per set.(d) The cache has 4 sets per block.(e) None of the above.7. Which one of the following statements about cache memories is true?(a) Fully associative caches offer better latency, while direct-mapped caches have lower miss rates.(b) Fully associative caches offer lower miss rates, while direct-mapped caches have better latency.(c) Direct-mapped caches have both better miss rates and better latency.(d) Both generally have similar latency and miss rates.8. Consider an SRAM-based cache for a DRAM-based main memory. Neglect the possibility of othercaches or levels of the memory hierarchy below main memory. If a cache is improved, increasingthe typical hit rate from 98% to 99%, which one of the following would best characterize the likelydecrease in typical access time?(a) 0%(b) 1%(c) 10%(d) 100%Page 3 of 15Problem 2. (8 points):Integer encoding. Fill in the blanks in the table below with the number described in the first column of eachrow. You can give your answers as unexpanded simple arithmetic expressions (such as 15213+ 42); youshould not have trouble fitting your answers into the space provided.For this problem, assume a 6-bit word size.Description NumberUmaxTmin(unsigned) ((int) 4)(unsigned) ((int) -7)(((unsigned) 0x21) << 1) & 0x3F)(int) (20 + 12)12 && 4(! 0x15) > 16Page 4 of 15Problem 3. (8 points):Floating point encoding. Consider the following 5-bit floating point representation based on the IEEEfloating point format. This format does not have a sign bit – it can only represent nonnegative numbers.• There are k = 3 exponent bits. The exponent bias is 3.• There are n = 2 fraction bits.Recall that numeric values are encoded as a value of the form V = M × 2E, where E is the exponent afterbiasing, and M is the significand value. The fraction bits encode the significand value M using either adenormalized (exponent field 0) or a normalized representation (exponent field nonzero). The exponent Eis given by E = 1 − Bias for denormalized values and E = e − Bias for normalized values, where e is thevalue of the exponent field exp interpreted as an unsigned number.Below, you are given some decimal values, and your task it to encode them in floating point format. Inaddition, you should give the rounded value of the encoded floating point number. To get credit, you mustgive these as whole numbers (e.g., 17) or as fractions in reduced form (e.g., 3/4). Any rounding of thesignificand is based on round-to-even, which rounds an unrepresentable value that lies halfway betweentwo representable values to the nearest even representable value.Value Floating Point Bits Rounded value9/32 001 00 1/4393/1615/2Page 5 of 15Problem 4. (4 points):Functions. I never learned to properly comment my code, and now I’ve forgotten what this function does.Help me out by looking at the assembly code and reconstructing the C code for this recursive function. Fillin the blanks:unsigned mystery1(unsigned n) {if(________)return 1;elsereturn 1 + mystery1(________);}mystery1:pushl %ebpmovl %esp, %ebpsubl $8, %espcmpl $0, 8(%ebp)jne .L2movl $1, -4(%ebp)jmp .L3.L2:movl 8(%ebp), %eaxshrl %eaxmovl %eax, (%esp)call mystery1addl $1, %eaxmovl %eax, -4(%ebp).L3:movl -4(%ebp), %eaxleaveretPage 6 of 15Problem 5. (10 points):Stack discipline. Consider the following C code and assembly code for a recursive function:int gcd(int a, int b) 0x08048394 <+0>: push %ebp{ 0x08048395 <+1>: mov %esp,%ebpif(!b) 0x08048397 <+3>: sub $0x10,%esp{ 0x0804839a <+6>: mov 0x8(%ebp),%eaxreturn a; 0x0804839d <+9>: mov 0xc(%ebp),%ecx} 0x080483a0 <+12>: test %ecx,%ecx0x080483a2 <+14>: je 0x80483b7 <gcd+35>return gcd(b, a % b); 0x080483a4 <+16>: mov %eax,%edx} 0x080483a6 <+18>: sar $0x1f,%edx0x080483a9 <+21>: idiv %ecx0x080483ab <+23>: mov %edx,0x4(%esp)0x080483af <+27>: mov %ecx,(%esp)0x080483b2 <+30>: call 0x8048394 <gcd>0x080483b7 <+35>: leave0x080483b8 <+36>: retImagine that a program makes the procedure call gcd(213, 18). Also imagine that prior to the invoca-tion, the value of %esp is 0xffff1000—that
View Full Document
Unlocking...