Instructions:
Andrew login ID: Full Name:
15-213/18-243, Spring 2011 Exam 1
Thursday, March 3, 2011 (v1)
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 x86 assembly dump, please fill in the blank lines for the function in the provided C code:
int lolwut(char *s)
int i, n; n = 0;
for(i = 0; ________________; i++)
if(________________________________)
return -1; }
n = ________________;
return ________;
080483a4
ba 00 00 00 00
ba 00 00 00 00
8d 54 50 d0
0f b6 4b 01
ba ff ff ff ff
push %ebp
mov %esp,%ebp
push %ebx
mov 0x8(%ebp),%ebx
movzbl (%ebx),%ecx
mov $0x0,%edx
test %cl,%cl
je 80483e8
lea -48(%ecx),%eax
mov $0x0,%edx
cmp $0x9,%al
jbe 80483cf
jmp 80483e3
add $0x1,%ebx
lea -48(%ecx),%eax
cmp $0x9,%al
ja 80483e3
lea (%edx,%edx,4),%edx
movsbl %cl,%eax
lea -48(%eax,%edx,2),%edx
movzbl 0x1(%ebx),%ecx
test %cl,%cl
jne 80483c5
jmp 80483e8
mov -1,%edx
mov %edx,%eax
pop %ebx
pop %ebp
Page 9 of 13
A. At address 0x080483a7 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 0x080483a7 (push %ebx), the value of %esp is 0xffff0000. If that is the case, at which address would one find the argument s?
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.
int foo(int a, int b, int c, int d);
mov %esp,%ebp
sub $0x10,$esp
Page 11 of 13
Problem 7. (15 points):
The Hit or Miss Question
Given a 32-bit Linux system that has a 2-way associative cache of size 128 bytes with 32 bytes per block. Long longs are 8 bytes. For all parts, assume that table starts at address 0x0.
long long table[4][8];
for (j = 0; j < 8; j++) {
for (i = 0; i < 4; i++) {
table[i][j] = i + j;
A. This problem refers to code sample 1. In the table below write down in each space whether that element’s access will be a hit or a miss. Indicate hits with a ’H’ and misses with a ’M’
What is the miss rate of this code sample?
Page 12 of 13
int table[4][8];
for (j = 0; j < 8; j++) {
for (i = 0; i < 4; i++) {
table[i][j] = i + j;
B. This problem refers to code sample above. In the table below write down in each space whether that element’s access will be a hit or a miss. Indicate hits with a ’H’ and misses with a ’M’
What is the miss rate of this code sample?
C. One code sample performs better than the other. Why is this?
Page 13 of 13
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com