程序代写代做代考 arm C cache assembly Carnegie Mellon

Carnegie Mellon
15-213: M20 Midterm Review Session Anja and Josh Z

Carnegie Mellon
Agenda
■ Review midterm problems ■Cache
■Assembly
■Stack
■Floats, Arrays, Structs (time permitting)
■ Q&A for general midterm problems

Carnegie Mellon
Reminders
■ Exam This Friday
■ Cheat sheet: ONE 81⁄2 x 11 in. sheet, both sides. Please use only English! Make a copy prior to midterm. No practice problems!

Carnegie Mellon
Problem 1: Cache
■ Things to remember/put on a cheat sheet because please don’t try to memorize all of this:
■ Direct mapped vs. n-way associative vs. fully associative ■Tag/Set/Block offset bits, how do they map depending on cache
size?
■ LRU policies

Carnegie Mellon
Problem 1: Cache
A. Assume you have a cache of the following structure: a. 32-byte blocks
b. 2 sets
c. Direct-mapped
d. 8-bit address space
e. The cache is cold prior to access
B. What does the address decomposition look like? 00 000 000

Carnegie Mellon
Problem 1: Cache
Address
Set
Tag
H/M
Evict? Y/N
0x56
0x6D
0x49
0x3A

Carnegie Mellon
Problem 1: Cache
Address
Set
Tag
H/M
Evict? Y/N
0101 0110
0110 1101
0100 1001
0011 1010

Carnegie Mellon
Problem 1: Cache
Address
Set
Tag
H/M
Evict? Y/N
0101 0110
0
01
M
N
0110 1101
0100 1001
0011 1010

Carnegie Mellon
Problem 1: Cache
Address
Set
Tag
H/M
Evict? Y/N
0101 0110
0
01
M
N
0110 1101
1
01
M
N
0100 1001
0011 1010

Carnegie Mellon
Problem 1: Cache
Address
Set
Tag
H/M
Evict? Y/N
0101 0110
0
01
M
N
0110 1101
1
01
M
N
0100 1001
0
01
H
N
0011 1010

Carnegie Mellon
Problem 1: Cache
Address
Set
Tag
H/M
Evict? Y/N
0101 0110
0
01
M
N
0110 1101
1
01
M
N
0100 1001
0
01
H
N
0011 1010
1
00
M
Y

Carnegie Mellon
Problem 1: Cache
A. Assume you have a cache of the following structure: a. 2-way associative
b. 4 sets, 64-byte blocks
B. What does the address decomposition look like? … 0 0 0 0 0 0 0 0 0 0 0 00 00 0

Carnegie Mellon
Problem 1: Cache
B. Assume A and B are 128 ints and
cache-aligned. Assume the cache dimensions given on the previous slide
(4 sets, 64-byte blocks, 2 way assoc.).
a. What is the miss rate of pass 1?
b. What is the miss rate of pass 2?
int get_prod_and_copy(int *A, int *B) {
int length = 64;
int prod = 1;
// pass 1
for (int i = 0; i < length; i+=4) { prod*=A[i]; } // pass 2 for (int j = length-1; j > 0; j-=4) {
A[j] = B[j];
}
return prod;
}

Carnegie Mellon
Problem 1: Cache
B. Pass 1: Only going through 64 ints with step size 4. Each miss loads 16 ints into a cache line, giving us 3 more hits before loading into a new line.
int get_prod_and_copy(int *A, int *B) {
int length = 64;
int prod = 1;
// pass 1
for (int i = 0; i < length; i+=4) { prod*=A[i]; } // pass 2 for (int j = length-1; j > 0; j-=4) {
A[j] = B[j]; }
return prod;
}

Carnegie Mellon
Problem 1: Cache B. Pass 1: 25% miss
int get_prod_and_copy(int *A, int *B) {
int length = 64;
int prod = 1;
// pass 1
for (int i = 0; i < length; i+=4) { prod*=A[i]; } // pass 2 for (int j = length-1; j > 0; j-=4) {
A[j] = B[j]; }
return prod;
}

Carnegie Mellon
Problem 1: Cache
B. Pass 2: Our cache is the same size as our working set! Due to cache alignment, we won’t evict anything from A, but still get a 1:3 miss:hit ratio for B.
int get_prod_and_copy(int *A, int *B) {
int length = 64;
int prod = 1;
// pass 1
for (int i = 0; i < length; i+=4) { prod*=A[i]; } // pass 2 for (int j = length-1; j > 0; j-=4) {
A[j] = B[j];
}
return prod;
}

Carnegie Mellon
Problem 1: Cache
B. Pass 2: For every 4 loop iterations, we get all hits for accessing A and 1 miss for accessing B, which gives us 1⁄8 miss.
int get_prod_and_copy(int *A, int *B) {
int length = 64;
int prod = 1;
// pass 1
for (int i = 0; i < length; i+=4) { prod*=A[i]; } // pass 2 for (int j = length-1; j > 0; j-=4) {
A[j] = B[j];
}
return prod;
}

Carnegie Mellon
Problem 1: Cache B. Pass 2: 12.5% miss
int get_prod_and_copy(int *A, int *B) {
int length = 64;
int prod = 1;
// pass 1
for (int i = 0; i < length; i+=4) { prod*=A[i]; } // pass 2 for (int j = length-1; j > 0; j-=4) {
A[j] = B[j];
}
return prod;
}

Carnegie Mellon
Problem 2: Assembly
■ Typical questions asked
■ Given a function, look at assembly to fill in missing portions
■ Given assembly of a function, intuit the behavior of the program
■ (More rare) Compare different chunks of assembly, which one
implements the function given?
■ Important things to remember/put on your cheat sheet:
■ Memory Access formula: D(Rb,Ri,S)
■ Distinguish between mov/lea instructions
■ Callee/Caller save regs
■ Condition codes and corresponding eflags

Carnegie Mellon
Problem 2: Assembly ■ Katherine TODO: pick one

Carnegie Mellon
Problem 2: Assembly

Carnegie Mellon
Problem 2: Assembly
Let’s trace through the code!

Carnegie Mellon
Problem 2: Assembly
%eax is d
d

Carnegie Mellon
Problem 2: Assembly
d
Keep this in mind…

Carnegie Mellon
Problem 2: Assembly
x > z(?)
d
cmp %edx (z), %edi (x)
ja is “Jump if (dest) above (src)” i.e. jump if x > z
Don’t want to memorize jump variants? Hmmmm……

Carnegie Mellon
Problem 2: Assembly
z x >i
No other “+ 2” in assembly e is %r8d, i = z in %rdx
d

Carnegie Mellon
Problem 2: Assembly
z x >i
e << y y is in %rsi, e is in %r8d d Where did %cl come from? Carnegie Mellon Problem 2: Assembly z x >i e << y e >> (y – 1)
What’s in %r9d? %rsi – 1 i.e. y – 1
d

Carnegie Mellon
Problem 2: Assembly
z x >i
e << y e >> (y – 1)
d
d is in %eax, e is in %r8d
d+ e

Carnegie Mellon
Problem 2: Assembly
z x >i
i++
e << y e >> (y – 1) d+ e
d
What’s left?
Increment loop counter

Carnegie Mellon
Problem 2: Assembly
z x > i i++
e << y e >> (y – 1) d+ e
d

Carnegie Mellon
Problem 3: Stack
■ Important things to remember:
■ Stack grows towards lower addresses
■ %rsp = stack pointer, always point to “top” of stack ■ Push and pop, call and ret
■ Stack frames: how they are allocated and freed ■Which registers used for arguments? Return values? ■ Little endianness
■ ALWAYS helpful to draw a stack diagram!!
■ Stack questions are like Assembly questions on steroids

Carnegie Mellon
Problem 3: Stack Consider the following code:
Hints:
● strcpy(char *dst,
char *src) copies the string at address src (including the terminating ‘\0’ character) to address dst.
● Keep endianness in mind!
● Table of hex values of
characters in
“midtermexam”
Assumptions:
● %rsp = 0x800100 just
before caller() calls
foo()
● .LC0 is at address
0x400300

Carnegie Mellon
Problem 3: Stack Consider the following code:
Hints:
● strcpy(char *dst,
char *src) copies the string at address src (including the terminating ‘\0’ character) to address dst.
● Keep endianness in mind!
● Table of hex values of
characters in
“midtermexam”
Assumptions:
● %rsp = 0x800100 just before caller() calls foo()
● .LC0 is at address 0x400300
%rsp = 0x800100
= 0x400300

Carnegie Mellon
Problem 3: Stack
Question 1: What is the hex value of %rsp just before strcpy() is called for the first time in foo()?
Hints:
● Step through the program
instruction by instruction
from start to end
● Draw a stack diagram!!!
● Keep track of registers too
Start
%rsp = 0x800100
End
= 0x400300

Problem 3: Stack
Arrow is instruction that will execute NEXT
Carnegie Mellon
Question 1: What is the hex value of %rsp just before strcpy() is called for the first time in foo()?
%rsp
0x800100
%rdi
.LC0
%rsi
0x15213
%rsp = 0x800100
0x8000f8
0x8000f0
0x8000e8
0x8000e0
0x8000d8
0x8000d0
0x8000c8
0x8000c0
End
= 0x400300
0x800100
0x8000b8

0x800100
0x8000f8
0x8000f0
0x8000e8
0x8000e0
0x8000d8
0x8000d0
0x8000c8
0x8000c0
0x8000b8
Carnegie Mellon
Problem 3: Stack
Question 1: What is the hex value of %rsp just before strcpy() is called for the first time in foo()?
%rsp
0x8000f8
%rdi
.LC0
%rsi
0x15213
?
ret address for foo()
End
= 0x400300

Problem 3: Stack
Hint: $24 in decimal = 0x18 Question 1: What is the hex value of %rsp just before strcpy() is called for the first time in foo()?
0x800100
0x8000f8
0x8000f0
0x8000e8
0x8000e0
0x8000d8
0x8000d0
0x8000c8
0x8000c0
0x8000b8
Carnegie Mellon
%rsp
0x8000e0
%rdi
.LC0
%rsi
0x15213
?
ret address for foo()
?
?
?
End
= 0x400300

Carnegie Mellon
Problem 3: Stack
Question 1: What is the hex value of %rsp just before strcpy() is called for the first time in foo()?
%rsp
0x8000e0
%rdi
.LC0
%rsi
0xdeadbeef
End
= 0x400300
0x800100
0x8000f8
0x8000f0
0x8000e8
0x8000e0
0x8000d8
0x8000d0
0x8000c8
0x8000c0
0x8000b8
?
ret address for foo()
?
?
?

0x800100
0x8000f8
0x8000f0
0x8000e8
0x8000e0
0x8000d8
0x8000d0
0x8000c8
0x8000c0
0x8000b8
Carnegie Mellon
Problem 3: Stack
Question 1: What is the hex value of %rsp just before strcpy() is called for the first time in foo()?
%rsp
0x8000d8
%rdi
.LC0
%rsi
0xdeadbeef
?
ret address for foo()
?
?
?
ret address for foo()
End
= 0x400300

Carnegie Mellon
Problem 3: Stack
Question 1: What is the hex value of %rsp just before strcpy() is called for the first time in foo()?
%rsp
0x8000c0
%rdi
.LC0
%rsi
0xdeadbeef
End
= 0x400300
0x800100
0x8000f8
0x8000f0
0x8000e8
0x8000e0
0x8000d8
0x8000d0
0x8000c8
0x8000c0
0x8000b8
?
ret address for foo()
?
?
?
ret address for foo()
?
?
?

Problem 3: Stack
Question 1: What is the hex value of %rsp just before strcpy() is called for the first time in foo()?
Carnegie Mellon
Answer!
End
= 0x400300
%rsp
%rdi
%rsi
0x8000c0
0x8000c0
.LCO
0x800100
0x8000f8
0x8000f0
0x8000e8
0x8000e0
0x8000d8
0x8000d0
0x8000c8
0x8000c0
0x8000b8
?
ret address for foo()
?
?
?
ret address for foo()
?
?
?

Problem 3: Stack
Question 2: What is the hex value of buf[0] when strcpy() returns?
%rsp
%rdi
%rsi
0x8000c0
0x8000c0
.LC0
0x800100
0x8000f8
0x8000f0
0x8000e8
0x8000e0
0x8000d8
0x8000d0
0x8000c8
0x8000c0
0x8000b8
Carnegie Mellon
?
ret address for foo()
?
?
?
ret address for foo()
?
?
?
= 0x400300

Carnegie Mellon
%rsp
0x8000c0
%rdi
0x8000c0
%rsi
.LC0
Problem 3: Stack
Question 2: What is the hex value of buf[0] when strcpy() returns?
0x800100
?
0x8000f8
ret address for foo()
0x8000f0
?
0x8000e8
?
0x8000e0
?
0x8000d8
ret address for foo()
0x8000d0
?
0x8000c8
0x8000c0
‘d’
‘i’
‘m’
0x8000b8
c7 c2 c1 c0
= 0x400300

Carnegie Mellon
%rsp
0x8000c0
%rdi
0x8000c0
%rsi
.LC0
Problem 3: Stack
Question 2: What is the hex value of buf[0] when strcpy() returns?
0x800100
?
0x8000f8
ret address for foo()
0x8000f0
?
0x8000e8
?
0x8000e0
?
0x8000d8
ret address for foo()
0x8000d0
?
0x8000c8
?
?
?
?
‘\0’
‘m’
‘a’
‘x’
0x8000c0
‘e’
‘m’
‘r’
‘e’
‘t’
‘d’
‘i’
‘m’
0x8000b8
c7 c2 c1 c0
= 0x400300

Carnegie Mellon
%rsp
0x8000c0
%rdi
0x8000c0
%rsi
.LC0
Problem 3: Stack
Question 2: What is the hex value of buf[0] when strcpy() returns?
0x800100
?
0x8000f8
ret address for foo()
0x8000f0
?
0x8000e8
?
0x8000e0
?
0x8000d8
ret address for foo()
0x8000d0
?
0x8000c8
?
?
?
?
‘\0’
‘m’
‘a’
‘x’
0x8000c0
‘e’
‘m’
‘r’
‘e’
‘t’
‘d’
‘i’
‘m’
0x8000b8
c3 buf[0] c0
= 0x400300

Carnegie Mellon
Problem 3: Stack
buf[0] = =
(as int)= 0x7464696d
‘t’
‘d’
‘i’
‘m’
0x800100
?
0x8000f8
ret address for foo()
0x8000f0
?
0x8000e8
?
0x8000e0
?
0x8000d8
ret address for foo()
0x8000d0
?
0x8000c8
?
?
?
?
‘\0’
‘m’
‘a’
‘x’
0x8000c0
‘e’
‘m’
‘r’
‘e’
‘t’
‘d’
‘i’
‘m’
0x8000b8
buf[0]
74
64
69
6d

Carnegie Mellon
%rsp
0x8000c0
%rdi
0x8000c0
%rsi
.LC0
Problem 3: Stack
Question 3: What is the hex value of buf[1] when strcpy() returns?
0x800100
?
0x8000f8
ret address for foo()
0x8000f0
?
0x8000e8
?
0x8000e0
?
0x8000d8
ret address for foo()
0x8000d0
?
0x8000c8
?
?
?
?
‘\0’
‘m’
‘a’
‘x’
0x8000c0
‘e’
‘m’
‘r’
‘e’
‘t’
‘d’
‘i’
‘m’
0x8000b8
c7 buf[1] c4 buf[0]
= 0x400300

Carnegie Mellon
Problem 3: Stack
buf[1] = =
(as int)= 0x656d7265
‘e’
‘m’
‘r’
‘e’
0x800100
?
0x8000f8
ret address for foo()
0x8000f0
?
0x8000e8
?
0x8000e0
?
0x8000d8
ret address for foo()
0x8000d0
?
0x8000c8
?
?
?
?
‘\0’
‘m’
‘a’
‘x’
0x8000c0
‘e’
‘m’
‘r’
‘e’
‘t’
‘d’
‘i’
‘m’
0x8000b8
buf[1]
65
6d
72
65

Carnegie Mellon
Problem 3: Stack
Question 4: What is the hex value of %rdi at the point where foo() is called recursively in the successful arm of the if statement?
This is before the recursive call to foo()
= 0x400300

Carnegie Mellon
Problem 3: Stack
Question 4: What is the hex value of %rdi at the point where foo() is called recursively in the successful arm of the if statement?
■ This is before the recursive call to foo()
■ Going backwards, %rdi was loaded in caller()
■ %rdi = $.LC0 = 0x400300
(based on hint)
loaded %rdi
= 0x400300

Carnegie Mellon
Problem 3: Stack
Question 5: What part(s) of the stack will be corrupted by invoking caller()? Check all that apply.
■ return address from foo() to caller()
■ return address from the recursive call to
foo()
■ strcpy()’s return address
0x800100
?
0x8000f8
ret address for foo()
0x8000f0
?
0x8000e8
?
0x8000e0
?
0x8000d8
ret address for foo()
0x8000d0
?
0x8000c8
?
?
?
?
‘\0’
‘m’
‘a’
‘x’
0x8000c0
‘e’
‘m’
‘r’
‘e’
‘t’
‘d’
‘i’
‘m’
0x8000b8
■ there will be no corruption
The strcpy didn’t overwrite any return addresses, so there was no corruption!

Carnegie Mellon
Bonus Coverage: Float
■ Things to remember/ put on your cheat sheet: ■ Floating point representation (-1)s M 2E
■ Values of M in normalized vs denormalized
■ Difference between normalized, denormalized and special
floating point numbers
■ Rounding
■ Bit values of smallest and largest normalized and denormalized
numbers

Carnegie Mellon
Bonus Coverage: Float
A. Consider a floating point representation with 1 sign bit, 2 exponent bits and 3 fraction bits. Convert the following numbers into their floating point representation.
a) 31/8 s E Step 1: Convert the fraction into the form (-1) M 2 s= 0
M = 31/16 (M should be in the range [1.0, 2.0) for normalised numbers)
E= 1

Carnegie Mellon
Bonus Coverage: Float
A. Consider a floating point representation with 1 sign bit, 2 exponent bits and 3 fraction bits. Convert the following numbers into their floating point representation.
a) 31/8
Step 2: Convert M into binary and find value of exp s= 0
M = 31/16 (M should be in the range [1.0, 2.0) for normalised numbers)
E= 1

Carnegie Mellon
Bonus Coverage: Float
A. Consider a floating point representation with 1 sign bit, 2 exponent bits and 3 fraction bits. Convert the following numbers into their floating point representation.
a) 31/8
Step 2: Convert M into binary and find value of exp s= 0
M = 31/16 => 1.1111
bias = 2k-1 – 1 (k is the number of exponent bits) = 1 E = 1 => exponent = 1 + bias = 2

Carnegie Mellon
Bonus Coverage: Float
A. Consider a floating point representation with 1 sign bit, 2 exponent bits and 3 fraction bits. Convert the following numbers into their floating point representation.
a) 31/8
Step 3: Find the fraction bits and exponent bits s= 0
M = 1.1111 => fraction bits are 1111 exponent bits are 10

Carnegie Mellon
Bonus Coverage: Float
A. Consider a floating point representation with 1 sign bit, 2 exponent bits and 3 fraction bits. Convert the following numbers into their floating point representation.
a) 31/8
Step 4: Take care of rounding issues Current number is 0 10 111 1 <= excess bit Carnegie Mellon Bonus Coverage: Float A. Consider a floating point representation with 1 sign bit, 2 exponent bits and 3 fraction bits. Convert the following numbers into their floating point representation. a) 31/8 Step 4: Take care of rounding issues Current number is 0 10 111 1 <= excess bit Guard bit (last bit kept) = 1 Round bit (first bit removed) = 1 Sticky bit (OR of other removed bits) = 0 I.e. same distance between 111 and “000”, so round up to even (add 1 to the fraction bits). Carnegie Mellon Bonus Coverage: Float A. Consider a floating point representation with 1 sign bit, 2 exponent bits and 3 fraction bits. Convert the following numbers into their floating point representation. a) 31/8 Step 4: Take care of rounding issues Current number is 0 10 111 1 <= excess bit Adding 1 overflows the floating bits, so we increment the exponent bits by 1 and set the fraction bits to 0 Carnegie Mellon Bonus Coverage: Float A. Consider a floating point representation with 1 sign bit, 2 exponent bits and 3 fraction bits. Convert the following numbers into their floating point representation. a) 31/8 Step 4: Take care of rounding issues Result is 0 11 000 <= Infinity! Carnegie Mellon Bonus Coverage: Float A. Consider a floating point representation with 1 sign bit, 2 exponent bits and 3 fraction bits. Convert the following numbers into their floating point representation. b) -7/8 Carnegie Mellon Bonus Coverage: Float A. Consider a floating point representation with 1 sign bit, 2 exponent bits and 3 fraction bits. Convert the following numbers into their floating point representation. b) -7/8 s E Step 1: Convert the fraction into the form (-1) M 2 s= 1 M = 7/4 E = -1 Carnegie Mellon Bonus Coverage: Float A. Consider a floating point representation with 1 sign bit, 2 exponent bits and 3 fraction bits. Convert the following numbers into their floating point representation. b) -7/8 Step 2: Convert M into binary and find value of exp s= 1 M = 7/4 => 1.11
bias = 2k-1 – 1 (k is the number of exponent bits) = 1 E = -1 => exponent = -1 + bias = 0

Carnegie Mellon
Bonus Coverage: Float
A. Consider a floating point representation with 1 sign bit, 2 exponent bits and 3 fraction bits. Convert the following numbers into their floating point representation.
b) -7/8
Step 2: Convert M into binary and find value of exp s= 1
M = 7/4 => 1.11 <= (We assumed M was in the range [1.0, 2.0). Need to update the value of M) bias = 2k-1 - 1 (k is the number of exponent bits) = 1 E = -1 => exponent = -1 + bias = 0 <= denormalized! Carnegie Mellon Bonus Coverage: Float A. Consider a floating point representation with 1 sign bit, 2 exponent bits and 3 fraction bits. Convert the following numbers into their floating point representation. b) -7/8 Step 2: Convert M into binary and find value of exp s= 1 M = 7/8 => 0.111 <= M should be in the range [0.0, 1.0) for denormalized numbers so we divide it by 2 exp = 0 Carnegie Mellon Bonus Coverage: Float A. Consider a floating point representation with 1 sign bit, 2 exponent bits and 3 fraction bits. Convert the following numbers into their floating point representation. b) -7/8 Step 3: Find the fraction bits and exponent bits s= 1 M = 0.111 => Fraction bits = 111 exp bits = 00
Result = 1 00 111

Carnegie Mellon
Bonus Coverage: Float
B. Consider a floating point representation with 1 sign bit, 2 exponent bits and 3 fraction bits. Convert the following numbers into their floating point representation.
a) 0 10 101 s= 0
exp = 2 => E = exp – bias = 1 (normalized)
M = 1.101 (between 1 and 2 since it is normalised) Result = 2*1.101 = 2*(13/8) = 13/4

Carnegie Mellon
Bonus Coverage: Arrays
IMPORTANT POINTS + TIPS:
● Remember your indexing rules! They’ll take
you 95% of the way there.
● Be careful about addressing (&) vs. dereferencing (*)
● You may be asked to look at assembly!
● Feel free to put lecture/recitation/textbook examples
in your cheatsheet.

Carnegie Mellon
Bonus Coverage: Arrays
Good toy examples (for your cheatsheet and/or big brain):
●
A can be used as the pointer to the first array element: A[0] Type Value
val
val[2]
*(val + 2)
&val[2]
val + 2
val + i

Carnegie Mellon
Bonus Coverage: Arrays
Good toy examples (for your cheatsheet and/or big brain):
● A can be used as the pointer to the first array element: A[0]
val
val[2]
*(val + 2)
&val[2]
val + 2
val + i
Type
int * int
int
int *
int *
int *
2
Value
x
2
x + 8
x + 8
x + (4 * i)

Carnegie Mellon
Bonus Coverage: Arrays
Good toy examples (for your cheatsheet and/or big brain):
● A can be used as the pointer to the first array element: A[0]
Accessing methods:
● val[index]
● *(val + index)
val
val[2]
*(val + 2)
&val[2]
val + 2
val + i
Type
int *
int
2
Value
x
2
int
int *
int *
int *
x + 8
x + 8
x + (4 * i)

Carnegie Mellon
Bonus Coverage: Arrays
Good toy examples (for your cheatsheet and/or big brain):
● A can be used as the pointer to the first array element: A[0]
val
val[2]
*(val + 2)
&val[2]
val + 2
val + i
Type
int *
int
2
Value
x
2
Accessing methods:
● val[index]
● *(val + index)
int
int *
int *
int *
x + 8
x + 8
x + (4 * i)
Addressing methods:
● &val[index] ● val + index

Carnegie Mellon
Bonus Coverage: Arrays
Nested indexing rules (for your cheatsheet and/or big brain):
● Declared: T A[R][C]
● Contiguous chunk of space (think of multiple arrays lined up next
to each other)

Carnegie Mellon
Bonus Coverage: Arrays
Nested indexing rules (for your cheatsheet and/or big brain):
● Arranged in ROW-MAJOR ORDER – think of row vectors ● A[i] is an array of C elements (“columns”) of type T

Carnegie Mellon
Bonus Coverage: Arrays
Nested indexing rules (for your cheatsheet and/or big brain):

Carnegie Mellon
Bonus Coverage: Arrays Consider accessing elements of A….
Compiles
Bad Deref?
Size (bytes)
int A1[3][5]
int *A2[3][5]
int (*A3)[3][5]
int *(A4[3][5])
int (*A5[3])[5]

Carnegie Mellon
Bonus Coverage: Arrays Consider accessing elements of A….
int A1[3][5]
int *A2[3][5]
int (*A3)[3][5]
int *(A4[3][5])
int (*A5[3])[5]
Compiles Bad Deref?
Y N
Size (bytes)
3*5*4 = 60

Carnegie Mellon
Bonus Coverage: Arrays Consider accessing elements of A….
Compiles
Bad Deref?
N
Size (bytes)
3*5*(4) = 60
3*5*(8) = 120
int A1[3][5] Y
int *A2[3][5]
int (*A3)[3][5]
int *(A4[3][5])
int (*A5[3])[5]
Y
N

Carnegie Mellon
Bonus Coverage: Arrays Consider accessing elements of A….
Compiles
Bad Deref?
N
N
Size (bytes)
3*5*(4) = 60
3*5*(8) = 120
1*8 = 8
int A1[3][5]
int *A2[3][5]
int (*A3)[3][5]
int *(A4[3][5])
int (*A5[3])[5]
Y
Y
Y
N

Carnegie Mellon
Bonus Coverage: Arrays Consider accessing elements of A….
Compiles
Bad Deref?
N
N
N
Size (bytes)
3*5*(4) = 60
3*5*(8) = 120
1*8 = 8
3*5*(8) = 120
int A1[3][5]
int *A2[3][5]
int (*A3)[3][5]
int *(A4[3][5])
int (*A5[3])[5]
Y
Y
Y
Y
N
A4 is a pointer to a 3×5 (int *) element array

Carnegie Mellon
Bonus Coverage: Arrays Consider accessing elements of A….
Compiles
Bad Deref?
N
N
N N
Size (bytes)
3*5*(4) = 60
3*5*(8) = 120
1*8 = 8
3*5*(8) = 120
3*8 = 24
int A1[3][5]
int *A2[3][5]
int (*A3)[3][5]
int *(A4[3][5])
int (*A5[3])[5]
Y
Y
Y Y
Y
N
A5 is an array of 3 elements of type (int *)

Carnegie Mellon
Understanding Pointers & Arrays #3
int A1[3][5]
int *A2[3][5]
int (*A3)[3][5]
int *(A4[3][5])
int (*A5[3])[5]
Decl
Cmp
An
Bad
Size
⬛ Cmp: Compiles (Y/N)
⬛ Bad: Possible bad
pointer reference (Y/N)
⬛ Size: Value returned by sizeof
int A1[3][5]
int *A2[3][5]
int (*A3)[3][5]
int *(A4[3][5])
int (*A5[3])[5]
Cmp
Decl
*An
Bad
Size
Cmp
Cmp
**An
Bad
***An
Bad
Size
Size

Carnegie Mellon
Declaration
int A1[3][5]
int *A2[3][5]
int (*A3)[3][5]
int *(A4[3][5])
int (*A5[3])[5]
Allocated pointer Allocated pointer to unallocated int Unallocated pointer Allocated int Unallocated int
A1 A2/A4
A3 A5

Carnegie Mellon
Understanding Pointers & Arrays #3
int A1[3][5]
int *A2[3][5]
int (*A3)[3][5]
int *(A4[3][5])
int (*A5[3])[5]
Decl
Y
Y
Y
Y
N
N
N
N
120
8
120
24
⬛ Cmp: Compiles (Y/N)
⬛ Bad: Possible bad
pointer reference (Y/N)
⬛ Size: Value returned by sizeof
Cmp
Y
An
Bad
N
Size
60
int A1[3][5]
int *A2[3][5]
int (*A3)[3][5]
int *(A4[3][5])
int (*A5[3])[5]
Cmp
Y
Y
Y
Y
Y
Decl
*An
Bad
N
N
Y
N
N
Size
20
40
60
40
8
Cmp
Cmp
N
Y
Y
Y
Y
Y
Y
Y
Y
Y
**An
Bad
***An
Bad
–
Y
Y
Y
Y
N
N
Y
N
Y
Size
4
8
20
8
20
Size
–
4
4
4
4

Carnegie Mellon
Bonus Coverage: Arrays Sample assembly-type questions

Carnegie Mellon
Bonus Coverage: Arrays

Carnegie Mellon
Bonus! Another Cache problem
■ Consider you have the following cache: ■ 64-byte capacity
■ Directly mapped
■ You have an 8-bit address space

Carnegie Mellon
Bonus!
A. How many tag bits are there in the cache?
■Do we know how many set bits there are? What about offset
bits?
■ If we have a 64-byte direct-mapped cache, we know the number
of s + b bits there are total! ■Then t + s + b = 8 → t = 8 – (s + b) ■Thus,wehave2__t_a_g__b_it_s_!
26 = 64

Carnegie Mellon
Bonus!
B. Fill in the following table, indicating the set number based on the hit/miss pattern.
a. By the power of guess and check tracing through, identify which partition of s + b bits matches the H/M pattern.
Load
Binary Address
Set
H/M
1
1011 0011
M
2
1010 0111
M
3
1101 1001
M
4
1011 1100
H
5
1011 1001
H

Carnegie Mellon
Bonus!
B. Fill in the following table, indicating the set number based on the hit/miss pattern.
a. By the power of guess and check tracing through, identify which partition of s + b bits matches the H/M pattern.
Load
Binary Address
Set
H/M
1
1011 0011
3
M
2
1010 0111
2
M
3
1101 1001
1
M
4
1011 1100
3
H
5
1011 1001
3
H

Carnegie Mellon
Bonus!
C. How many sets are there? 2 bits → 4 sets How big is each cache line? 4 bits → 16 bytes

Carnegie Mellon
In summary…
■ Read the write-up textbook!
■ Also read the write-up lecture slides!
■ Midterm covers CS:APP Ch. 1-3, 6
■ Ask questions on Piazza! For the midterm, make them
public and specific if from the practice server!
■ G~O~O~D~~L~U~C~K

Related Posts