Problem 7 - Operating Systems

Consider a CPU with cache memory such that access time to the cache memory is $t_c$, the access time to the main memory is $t_m$, the time to transfer a word from the main memory to the cache is $t_t$, and the time to execute a loop when a data is in the cache is $t_r$. Estimate the average memory access time in calculating the inner product of sufficiently long vectors. Here, the block (line) length of the cache memory is assumed to be $b$.

We calculate the inner product thanks to the following loop

inner_product := 0;
for i := 1 to vector_length do
begin
inner_product := inner_product + vector_1[i] * vector_2[i];
end;

and we suppose that the vectors are not in the cache at the beginning, so that the first access to the arrays will be a miss. We denote the length of the vectors by $B$. The first step in the computation will cost

$$T_0 = 2(t_c + t_m + b t_t)$$

to get the two vectors from the main memory or, more precisely, the first part of each of them, whose length will be the length of a block in the cache, that is $b$. For the next $b$ steps, we'll just need to access the cache, leading to a time

$$T_1 = 2bt_r$$

until the next miss where the following parts of the vectors will have to be drawn from the memory. We'll have to go through $\lceil \frac{B}{b} \rceil$ of these misses, leading to a total time of:

$$T = 2 \lceil B/b \rceil (t_c + t_m + b t_t) + 2 B t_r.$$