Instructions:
Andrew login ID: Full Name:
15-213/18-243, Spring 2011 Exam 1
Thursday, March 3, 2011 (v2)
Copyright By PowCoder代写 加微信 powcoder
• Make sure that your exam is not missing any sheets, then write your Andrew login ID, full name, and section on the front.
• This exam is closed book, closed notes. You may not use any electronic devices.
• 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 100 points.
• The problems are of varying difficulty. The point value of each problem is indicated. Good luck!
TOTAL (100):
Page 1 of 13
Problem 1. (12 points):
Multiple choice.
Write the correct answer for each question in the following table:
1 2 3 4 5 6 7 8 9 10
1. Consider an int *a and an int n. If the value of %ecx is a and the value of %edx is n, which of thefollowingassemblysnippetsbestcorrespondstotheCstatementreturn a[n]?
(a) ret (%ecx,%edx,4)
(b) leal (%ecx,%edx,4),%eax
(c) mov (%ecx,%edx,4),%eax ret
(d) mov (%ecx,%edx,1),%eax ret
2. Which of the following 8 bit floating point numbers (1 sign, 3 exponent, 4 fraction) represent NaN?
(a) 1 000 1111 (b) 0 111 1111 (c) 0 100 0000 (d) 1 111 0000
3. %rsp is 0xdeadbeefdeadd0d0. What is the value in %rsp after the following instruction exe- cutes?
pushq %rbx
(a) 0xdeadbeefdeadd0d4 (b) 0xdeadbeefdeadd0d8 (c) 0xdeadbeefdeadd0cc (d) 0xdeadbeefdeadd0c8
4. How many lines does a direct-mapped cache have in a set?
(a) 0 (b) 1 (c) 2 (d) 4
Page 2 of 13
5. On an x86 64 Linux system, which of these takes up the most bytes in memory?
(a) char a[7] (b) short b[3] (c) int *c
(d) float d
6. Two-dimensional arrays are stored in
(a) column-major (b) row-major
(c) diagonal-major (d) Art-major
order, to help with cache performance.
7. Which register holds the first argument when an argument is called in IA32 (32 bit) architecture?
(d) None of the above
8. What is the C equivalent of mov 0x10(%rax,%rcx,4),%rdx
(a) rdx = rax + rcx + 4 + 10
(b) *(rax + rcx + 4 + 10) = rdx (c) rdx = *(rax + rcx*4 + 0x10) (d) rdx = *(rax + rcx + 4 + 0x10)
9. What is the C equivalent of leal 0x10(%rax,%rcx,4),%rdx
(a) rdx = 10 + rax + rcx + 4
(b) rdx = 0x10 + rax + rcx*4
(c) rdx = *(0x10 + rax + rcx*4) (d) *(0x10 + rax + rcx + 4) = rdx
10. What is the C equivalent of mov %rax,%rcx
(a) rcx = rax (b) rax = rcx (c) rax = *rcx (d) rcx = *rax
Page 3 of 13
11. In x86 (IA32) an application’s stack grows from
(a) High memory addresses to low memory addresses
(b) Low memory addresses to high memory addresses
(c) Both towards higher and lower addresses depending on the action (d) Stacks are a fixed size and do not grow.
12. True or False: In x86 64 the %rbp register can be used as a general purpose register.
• True • False
Page 4 of 13
Problem 2. (17 points):
A. Convert the following from decimal to 8-bit two’s complement.
67 = -35 =
B. Please solve the following are datalab-style puzzle. Please write brief and clear comments. You may use large constants. eg. instead of saying (1 << 16), you may use 0x10000.
* reverseBytes - reverse bytes
Example: reverseBytes(0x12345678) = 0x78563412
Legal ops: ! ̃ & ˆ | + << >>
int reverseBytes(int x)
C. Assume x and y are of type int. For each expression below, give values for x and y which make the expression false, or write ”none” if the expression is always true.
• ((x ˆ y) < 0)
• (( ̃(x | ( ̃x + 1)) >> 31) & 0x1) == !x • (x ˆ (x>>31)) – (x>>31) > 0
• ((x >> 31) + 1) >= 0
• (!x | !!y) == 1
Page 5 of 13
Problem 3. (13 points):
Consider a 6-bit floating point data type with 3 exponent bits and 3 fraction bits (there is no sign bit, so the data type can only represent positive numbers). Assume that this data type uses the conventions presented in class, including representations on NaN, infinity, and denormalized values.
A. What is the bias?
B. What is the largest value, other than infinity, that can be represented?
C. What is the smallest value, other than zero, that can be represented?
D. Fill in the following table. Use round-to-even. If a number is too big to represent, use the representa- tion of infinity, and if it is too small to represent, use the representation of 0. Value should be written in decimal.
Bits Value 011 000 1
Bits 111 010
3/32 8 1/2
Page 6 of 13
Problem 4. (11 points):
Consider the following struct:
typedef struct
char a[3];
short b[3];
long double d;
int f; } JBOB;
A. Show how the struct above would appear on a 64-bit (“x86 64”) Linux machine. Label the bytes that belong to the various fields with their names and clearly mark the end of the struct. Use x’s to indicate bytes that are allocated in the struct but are not used. A long double is 16 bytes long.
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+ ||||||||||||||||| +–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+ ||||||||||||||||| +–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+ ||||||||||||||||| +–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+ ||||||||||||||||| +–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
Page 7 of 13
B. Rearrange the above fields in foo to conserve the most space in the memory below. Label the bytes that belong to the various fields with their names and clearly mark the end of the struct. Use hatch marks or x’s to indicate bytes that are allocated in the struct but are not used.
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+ ||||||||||||||||| +–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+ ||||||||||||||||| +–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+ ||||||||||||||||| +–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+ ||||||||||||||||| +–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+–+
C. HowmanybytesarewastedinpartA,insideandafterthestruct,ifthenextmemoryvalueisapointer?
D. HowmanybytesarewastedinpartB,insideandafterthestruct,ifthenextmemoryvalueisapointer?
Page 8 of 13
Problem 5. (20 points):
Assembly/C translation.
Given the following x86 assembly dump, please reconstruct the function in the provided C code.
int mystery(int (*f)(int, int), int* arr, int c)
if(_________________)
return ______________;
x = _________________;
for(i = ______________; ______________; __________)
x = ________________________________;
return x; }
(gdb) disas mystery
Dump of assembler code for function mystery:
0x080483a4
0x080483a5
0x080483a7
0x080483a8
0x080483a9
0x080483aa
0x080483ad
0x080483b0
0x080483b3
0x080483b5
0x080483b7
0x080483b9
0x080483bc
0x080483be
0x080483c3
0x080483c6
0x080483ca
0x080483cd
0x080483d0
0x080483d2
0x080483d5
0x080483d7
0x080483d9
0x080483db
0x080483dd
0x080483e0
0x080483e1
0x080483e2
0x080483e3
0x080483e4
End of assembler dump.
0xc(%ebp),%edi
0x10(%ebp),%esi
0x80483db
(%edi),%edx
0x80483d9
(%edi,%ebx,4),%eax
%eax,0x4(%esp)
%edx,(%esp)
*0x8(%ebp)
0x80483c3
Page 9 of 13
A. At address 0x080483a9 we see the instruction push %ebx. Name two things that happen as a result of executing that instruction, and explain why the instruction is necessary.
B. Assume that immediately after executing the instruction at address 0x080483a9 (push %ebx), the value of %esp is 0xffff0000. If that is the case, at which address would one find the argument f?
Page 10 of 13
Problem 6. (12 points):
Given the following function prototypes, and initial lines of IA32 assembly for each function, fill in the stack frame diagram with
• any arguments to the function foo
• the return address
• Any registers stored on the stack by the asm fragment (register names not values)
• The location on the stack pointed to by %esp and %ebp after the exection of the sub instruction.
void foo(char *a, int b);
mov %esp,%ebp
sub $0x10,$esp
Page 11 of 13
Problem 7. (15 points):
We will consider performance issues associated with caching the reads from array A. Assume other vari- ables are stored in registers. Also assume A is cache-aligned, and that the cache is cold before running the code.
Consider the following code:
#define N 128
int myst(int[] A)
int i, result;
for (i = 0; i < N; i++)
result += A[i]*A[n-i-1];
return result;
A. Consider a 64-byte, direct mapped cache with 4 sets. Fill in the values that will be stored in this cache whenthecodereachesthepointreturn result;
Page 12 of 13
B. Consider a 64-byte, two-way set associative cache with 4 sets. Fill in the values that will be stored in thiscachewhenthecodereachesthepointreturn result;Eachrectangleinthetablerepresents 4 bytes.
Page 13 of 13
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com