# 2018q3 第 13 週測驗題

### 測驗 `1`

Consider the following C code:

long array[1024 * 1024];
for (int x = 0; x < 10; ++x) {
    for (int i = 0; i < 1024 * 1024; i += 1024) {
        array[i] += 1;
    }
}

Assume that all variables but array are placed into registers and that array is placed in memory such that the address of array[0] is a multiple of the cache block size (i.e. all of its block offset bits are 0). Also, assume that longs are 8 bytes and all caches are initially empty.

How many data cache misses will this C code experience on a 64KB (64 * 1024 byte) direct-mapped cache with 64B cache blocks?

==作答區==

* `(a)` 1024 + (1024 - 512) * 10
* `(b)` (1024 + (1024 - 512) * 9)
* `(c)` ((1024-64) * 10)
* `(d)` (1024 + (1024 - 64) * 9)
* `(e)` 1024
* `(f)` 10240

---

測驗 `2`

承測驗 `1`
How many data cache misses will this C code experience on a 1.5MB (1536 * 1024 byte) 3-way set associative cache with 64B cache blocks with an LRU replacement policy?

==作答區==

* `(a)` 1024 + (1024 - 512) * 10
* `(b)` (1024 + (1024 - 512) * 9)
* `(c)` ((1024-64) * 10)
* `(d)` (1024 + (1024 - 64) * 9)
* `(e)` 1024
* `(f)` 10240

---

測驗 `3`

Consider the following codes:

- [ ] Version 0

for (int k = 0; k < N; ++k) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            B[i*N+j] += A[i*N+k] * A[k*N+j];
        }
    }
}

- [ ] Version 1

for (int kk = 0; kk < N; kk+=2) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = kk; k < kk + 2; ++k) {
                B[i*N+j] += A[i*N+k] * A[k*N+j];
            }
        }
    }
}

Assuming n is very large and the compiler does not reorder or omit memory accesses to the arrays, which of the following statements are true:
Select one statement that would apply

==作答區==

* `(a)` `A[k * N + j]` has better spatial locality in version 1
* `(b)` `A[i * N + k]` has better spatial locality in version 1
* `(c)` `B[i * N + j]` has better spatial locality in version 1

---