# Section 6: Midterm Review

## Introduction

In this Section, we'll be working on select questions from the Midterm Question Bank to help prepare you for the Midterm on Thursday.

When you're finished with the questions we've included on this page, here are the solutions, pulled from the Midterm Question Bank answers.

# IO and Caching

## IO-2. Caches and reference strings

If you haven't covered direct-mapped vs. fully-associative caches in class yet, feel free to skip the first two questions.

QUESTION IO-2A. True or false: A direct-mapped cache with N or more slots can handle any reference string containing ≤N distinct addresses with no misses except for cold misses.

QUESTION IO-2B. True or false: A fully-associative cache with N or more slots can handle any reference string containing ≤N distinct addresses with no misses except for cold misses.

Consider the following 5 reference strings.

Name String
α 1
β 1, 2
γ 1, 2, 3, 4, 5
δ 2, 4
ε 5, 2, 4, 2

QUESTION IO-2C. Which of the strings might indicate a sequential access pattern? Circle all that apply.

 α β γ δ ε None of these

QUESTION IO-2D. Which of the strings might indicate a strided access pattern with stride >1? Circle all that apply.

 α β γ δ ε None of these

The remaining questions concern concatenated permutations of these five strings. For example, the permutation αβγδε refers to this reference string:

 1, 1, 2, 1, 2, 3, 4, 5, 2, 4, 5, 2, 4, 2.

We pass such permutations through an initially-empty, fully-associative cache with 3 slots, and observe the numbers of hits.

QUESTION IO-2E. How many cold misses might a permutation observe? Circle all that apply.

 0 1 2 3 4 5 Some other number

Under LRU eviction, the permutation αβεγδ observes 5 hits as follows. (We annotate each access with “h” for hit or “m” for miss.)

 1m; 1h, 2m; 5m, 2h, 4m, 2h; 1m, 2h, 3m, 4m, 5m; 2m, 4h.

QUESTION IO-2F. How many hits does this permutation observe under FIFO eviction?

QUESTION IO-2G. Give a permutation that will observe 8 hits under LRU eviction, which is the maximum for any permutation. There are several possible answers. (Write your answer as a permutation of αβγδε. For partial credit, find a permutation that has 7 hits, etc.)

QUESTION IO-2H. Give a permutation that will observe 2 hits under LRU eviction, which is the minimum for any permutation. There is one unique answer. (Write your answer as a permutation of αβγδε. For partial credit, find a permutation that has 3 hits, etc.)

## IO-4. IO caching and strace

Elif Batuman is investigating several program executables left behind by her ex-roommate Fyodor. She runs each executable under `strace` in the following way:

```strace -o strace.txt ./EXECUTABLE files/text1meg.txt > files/out.txt
```

Help her figure out properties of these programs based on their system call traces.

QUESTION IO-4A. Program `./mysterya`:

```open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x8193000
brk(0x81b5000)                          = 0x81b5000
write(1, "A", 1)                        = 1
write(1, "\n", 1)                       = 1
write(1, "A", 1)                        = 1
write(1, "'", 1)                        = 1
write(1, "s", 1)                        = 1
...
```

Circle at least one option in each column.

 Sequential IO Reverse sequential IO Strided IO No read cache Unaligned read cache Aligned read cache No write cache Write cache Cache size 4096 Cache size 2048 Cache size 1024 Other

QUESTION IO-4B. Program `./mysteryb`:

```open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x96c5000
brk(0x96e6000)                          = 0x96e6000
write(1, "A\nA's\nAA's\nAB's\nABM's\nAC's\nACTH'"..., 2048) = 2048
...
```

Circle at least one option in each column.

 Sequential IO Reverse sequential IO Strided IO No read cache Unaligned read cache Aligned read cache No write cache Write cache Cache size 4096 Cache size 2048 Cache size 1024 Other

QUESTION IO-4C. Program `./mysteryc`:

```open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x9064000
brk(0x9085000)                          = 0x9085000
fstat64(3, {st_mode=S_IFREG|0664, st_size=1048576, ...}) = 0
lseek(3, 1046528, SEEK_SET)             = 1046528
write(1, "oR\ntlevesooR\ns'yenooR\nyenooR\ns't"..., 2048) = 2048
lseek(3, 1044480, SEEK_SET)             = 1044480
write(1, "ehR\neehR\naehR\ns'hR\nhR\nsdlonyeR\ns"..., 2048) = 2048
lseek(3, 1042432, SEEK_SET)             = 1042432
write(1, "\ns'nailitniuQ\nnailitniuQ\nnniuQ\ns"..., 2048) = 2048
lseek(3, 1040384, SEEK_SET)             = 1040384
write(1, "rP\ndilsymerP\ns'regnimerP\nregnime"..., 2048) = 2048
...
```

Circle at least one option in each column.

 Sequential IO Reverse sequential IO Strided IO No read cache Unaligned read cache Aligned read cache No write cache Write cache Cache size 4096 Cache size 2048 Cache size 1024 Other

QUESTION IO-4D. Program `./mysteryd`:

```open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x9a0e000
brk(0x9a2f000)                          = 0x9a2f000
fstat64(3, {st_mode=S_IFREG|0664, st_size=1048576, ...}) = 0
lseek(3, 1048575, SEEK_SET)             = 1048575
lseek(3, 1048574, SEEK_SET)             = 1048574
lseek(3, 1048573, SEEK_SET)             = 1048573
...
lseek(3, 1046528, SEEK_SET)             = 1046528
write(1, "oR\ntlevesooR\ns'yenooR\nyenooR\ns't"..., 2048) = 2048
lseek(3, 1046527, SEEK_SET)             = 1046527
lseek(3, 1046526, SEEK_SET)             = 1046526
...
```

Circle at least one option in each column.

 Sequential IO Reverse sequential IO Strided IO No read cache Unaligned read cache Aligned read cache No write cache Write cache Cache size 4096 Cache size 2048 Cache size 1024 Other

QUESTION IO-4E. Program `./mysterye`:

```open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x93e5000
brk(0x9407000)                          = 0x9407000
...
write(1, "A\nA's\nAA's\nAB's\nABM's\nAC's\nACTH'"..., 1024) = 1024
...
```

Circle at least one option in each column.

 Sequential IO Reverse sequential IO Strided IO No read cache Unaligned read cache Aligned read cache No write cache Write cache Cache size 4096 Cache size 2048 Cache size 1024 Other

QUESTION IO-4F. Program `./mysteryf`:

```open("files/text1meg.txt", O_RDONLY)    = 3
brk(0)                                  = 0x9281000
brk(0x92a3000)                          = 0x92a3000
write(1, "A", 1)                        = 1
write(1, "\n", 1)                       = 1
write(1, "A", 1)                        = 1
...
write(1, "A", 1)                        = 1
write(1, "l", 1)                        = 1
write(1, "t", 1)                        = 1
write(1, "o", 1)                        = 1
write(1, "n", 1)                        = 1
...
```

Circle at least one option in each column.

 Sequential IO Reverse sequential IO Strided IO No read cache Unaligned read cache Aligned read cache No write cache Write cache Cache size 4096 Cache size 2048 Cache size 1024 Other

## IO-6. Caching

Assume that we have a cache that holds four pages. Assume that each letter below indicates an access to a page. Answer the following questions as they pertain to the following sequence of accesses.

```E D C B A E D A A A B C D E
```

QUESTION IO-6A. What is the hit rate assuming an LRU replacement policy?

QUESTION IO-6B. What pages will you have in the cache at the end of the run?

QUESTION IO-6C. What is the best possible hit rate attainable if you could see into the future?

## IO-8. Reference strings

The following questions concern the FIFO (First In First Out), LRU (Least Recently Used), and LFU (Least Frequently Used) cache eviction policies.

Your answers should refer to seven-item reference strings made up of digits in the range 0–9. An example answer might be “1231231”. In each case, the reference string is processed by a 3-slot cache that’s initially empty.

QUESTION IO-8A. Give a reference string that has a 1/7 hit rate in all three policies.

QUESTION IO-8B. Give a reference string that has a 6/7 hit rate in all three policies.

QUESTION IO-8C. Give a reference string that has different hit rates under LRU and LFU policies, and compute the hit rates.

String:

LRU hit rate:

LFU hit rate:

QUESTION IO-8D. Give a reference string that has different hit rates under FIFO and LRU policies, and compute the hit rates.

String:

FIFO hit rate:

LRU hit rate:

QUESTION IO-8E. Now let's assume that you know a reference string in advance. Given a 3-slot cache and the following reference string, what caching algorithm discussed in class and/or exercises would produce the best hit rate, and would would that hit rate be?

“12341425321521”

## IO-9. Caching: Access times and hit rates

Recall that x86-64 instructions can access memory in units of 1, 2, 4, or 8 bytes at a time. Assume we are running on an x86-64-like machine with 1024-byte cache lines. Our machine takes 32ns to access a unit if the cache hits, regardless of unit size. If the cache misses, an additional 8160ns are required to load the cache, for a total of 8192ns.

QUESTION IO-9A. What is the average access time per access to access all the data in a cache line as an array of 256 integers, starting from an empty cache?

QUESTION IO-9B. What unit size (1, 2, 4, or 8) minimizes the access time to access all data in a cache line, starting from an empty cache?

QUESTION IO-9C. What unit size (1, 2, 4, or 8) maximizes the hit rate to access all data in a cache line, starting from an empty cache?

# Data Representation

## DATAREP-3-5. Hello Kitty

This problem locates 8-bit numbers horizontally and vertically in the following 16x16 image. Black pixels represent 1 bits and white pixels represent 0 bits. For horizontal arrangements, the most significant bit is on the left as usual. For vertical arrangements, the most significant bit is on top.

Examples: The 8-bit number 15 (hexadecimal 0x0F, binary 0b00001111) is located horizontally at 3,4, which means X=3, Y=4.

• The pixel at 3,4 is white, which has bit value 0.
• 4,4 is white, also 0.
• 5,4 is white, also 0.
• 6,4 is white, also 0.
• 7,4 is black, which has bit value 1.
• 8,4, 9,4, and 10,4 are black, giving three more 1s.
• Reading them all off, this is 0b00001111, or 15.

15 is also located horizontally at 7,6.

The 8-bit number 0 is located vertically at 0,0. It is also located horizontally at 0,0 and 1,0.

The 8-bit number 134 (hexadecimal 0x86, binary 0b10000110) is located vertically at 8,4.

QUESTION DATAREP-3A. Where is 3 located vertically? (All questions refer to 8-bit numbers.)

QUESTION DATAREP-3B. Where is 12 located horizontally?

QUESTION DATAREP-3C. Where is 255 located vertically?

Shintaro Tsuji wants to represent the image in computer memory. He stores it in an array of 16-bit unsigned integers:

`uint16_t cute[16];`

Row Y of the image is stored in integer `cute[Y]`.

QUESTION DATAREP-4A. What is `sizeof(cute)`, 2, 16, 32, or 64?

QUESTION DATAREP-4B. `printf("%d\n", cute[0]);` prints `16384`. Is Shintaro’s machine big-endian or little-endian?

Now that Shintaro has represented the image in memory as an array of `uint16_t` objects, he can manipulate the image using C. For example, here’s a function.

```void swap(void) {
for (int i = 0; i < 16; ++i)
cute[i] = (cute[i] << 8) | (cute[i] >> 8);
}```

Running `swap` produces the following image:

Shintaro has written several other functions. Here are some images (A is the original):

For each function, what image does that function create?

QUESTION DATAREP-5A.

```void f0() {
for (int i = 0; i < 16; ++i)
cute[i] = ~cute[i];
}```

QUESTION DATAREP-5B.

```void f1() {
for (int i = 0; i < 16; ++i) {
cute[i] = ((cute[i] >> 1) & 0x5555) | ((cute[i] << 1) & 0xAAAA);
cute[i] = ((cute[i] >> 2) & 0x3333) | ((cute[i] << 2) & 0xCCCC);
cute[i] = ((cute[i] >> 4) & 0x0F0F) | ((cute[i] << 4) & 0xF0F0);
cute[i] =  (cute[i] >> 8)           |  (cute[i] << 8);
}
}```

QUESTION DATAREP-5C.

```void f2() {
char *x = (char *) cute;
for (int i = 0; i < 16; ++i)
x[2*i] = i;
}```

#### For “fun”

The following programs generated the other images. Can you match them with their images?

```void f3() {
for (int i = 0; i < 16; ++i)
cute[i] &= ~(7 << i);
}```
```void f4() {
swap();
for (int i = 0; i < 16; ++i)
cute[i] <<= i/4;
swap();
}```
```void f5() {
for (int i = 0; i < 16; ++i)
cute[i] = -1 * !!(cute[i] & 64);
}```
```void f6() {
for (int i = 0; i < 8; ++i) {
int tmp = cute[15-i];
cute[15-i] = cute[i];
cute[i] = tmp;
}
}```
```void f7() {
for (int i = 0; i < 16; ++i)
cute[i] = cute[i] & -cute[i];
}```
```void f8() {
for (int i = 0; i < 16; ++i)
cute[i] ^= cute[i] ^ cute[i];
}```
```void f9() {
for (int i = 0; i < 16; ++i)
cute[i] = cute[i] ^ 4080;
}```

## DATAREP-10. Sizes and alignments

Assume a 64-bit x86-64 architecture unless explicitly told otherwise.

Write your assumptions if a problem seems unclear, and write down your reasoning for partial credit.

QUESTION DATAREP-10A. Use the following members to create a struct of size 16, using each member exactly once, and putting `char a` first; or say “impossible” if this is impossible.

1. `char a;` (we’ve written this for you)
2. `unsigned char b;`
3. `short c;`
4. `int d;`
```struct size_16 {
char a;

};
```

QUESTION DATAREP-10B. Repeat Part A, but create a struct with size 12.

```struct size_12 {
char a;

};
```

QUESTION DATAREP-10C. Repeat Part A, but create a struct with size 8.

```struct size_8 {
char a;

};
```

QUESTION DATAREP-10D. Consider the following structs:

```struct x {
T x1;
U x2;
};
struct y {
struct x y1;
V y2;
};
```

Give definitions for T, U, and V so that there is one byte of padding in `struct x` after `x2`, and two bytes of padding in `struct y` after `y1`.

# Assembly

## ASM-2. Assembly

Here is some x86 assembly code.

``` f:
movl a, %eax
movl b, %edx
andl \$255, %edx
subl %edx, %eax
movl %eax, a
retq
```

QUESTION ASM-2A. Write valid C code that could have compiled into this assembly (i.e., write a C definition of function `f`), given the global variable declarations “`extern unsigned a, b;`.” Your C code should compile without warnings. REMINDER: You are not permitted to run a C compiler, except for the C compiler that is your brain.

QUESTION ASM-2B. Write different valid, warning-free C code that could have compiled into that assembly. This version should contain different operators than your first version. (For extra credit, use only one operator.)

QUESTION ASM-2C. Again, write different valid, warning-free C code that could have compiled into that assembly. In this version, `f` should have a different type than in your first version.

## ASM-4. Assembly language

The next four questions pertain to the following four code samples.

 f1 ```f1: subq \$8, %rsp call callfunc movl  %eax, %edx leal 1(%rax,%rax,2), %eax      testb \$1, %dl jne .L3 movl  %edx, %eax shrl \$31, %eax addl  %edx, %eax sarl  %eax .L3: addq \$8, %rsp ret ``` f3 ```f3: subq \$8, %rsp call callfunc subl \$97, %eax cmpb \$4, %al ja .L2 movzbl  %al, %eax jmp *.L4(,%rax,8) .L4: .quad .L3 .quad .L9 .quad .L6 .quad .L7 .quad .L8 .L3: movl \$42, %edx jmp .L5 .L6: movl \$4096, %edx jmp .L5 .L7: movl \$52, %edx jmp .L5 .L8: movl \$6440, %edx jmp .L5 .L2: movl \$0, %edx jmp .L5 .L9: movl \$61, %edx .L5: movl \$.LC0, %esi movl \$1, %edi movl \$0, %eax call __printf_chk addq \$8, %rsp ret .LC0: .string "Sum = %d\n" ``` f2 ```f2: pushq  %rbx xorl  %ebx, %ebx .L3: movl  %ebx, %edi addl \$1, %ebx call callfunc cmpl \$10, %ebx jne .L3 popq  %rbx ret ``` f4 ```f4: subq \$40, %rsp movl \$1, (%rsp) movl \$0, 16(%rsp) .L2: leaq 16(%rsp), %rsi     movq  %rsp, %rdi call callfunc movl 16(%rsp), %eax     cmpl  %eax, (%rsp) jne .L2 addq \$40, %rsp ret ``` Now answer the following questions. Pick the most likely sample; you will use each sample exactly once. QUESTION ASM-4A. Which sample contains a for loop? QUESTION ASM-4B. Which sample contains a switch statement? QUESTION ASM-4C. Which sample contains only an if/else construct? QUESTION ASM-4D. Which sample contains a while loop?