Frigo's cache-oblivious algorithms paper

Question

I am reading Frigo's "Cache-Oblivious Algorithms" paper and I need help understanding his cache complexity expressions for the base cases.

He starts on page 3 with "An $s \times s$ submatrix is stored on $\Theta (s + s^2/ \mathcal{B})$ cache lines. I can see the reason for $s^2/ \mathcal{B}$ is because we have $s^2$ numbers in total and we can fit $\mathcal{B}$ worlds per line. But where is the other $s$ coming from? Is this because we need to store $s$ pointers to each of the $s$ rows of the matrix?

Matrix Multiplication

Next, we have the matrix multiplication algorithm. First, I like to confirm when do we actually get a cache miss.

1. If the matrix is small, does that mean it is already in cache and we never miss?

2. If divide and conquer is needed, then is the matrix brought into cache when it is small enough so that is why we have cache misses at that point?

Here, in the base case (Case I), it says we need $\Theta ( (mn + np +mp)/\mathcal{B})$. I can see the reason here being we just have the total number of entries in each matrix, divided by how many can fit in one cache line.

But after that, I don't see how the other cases come about. For example, in Case II, if $n, p \in [\alpha \sqrt{ \mathcal{M}}, \sqrt{ \mathcal{M}}]$, then the $n \times p$ size matrix B can be brought into cache and it will occupy $np/\mathcal{B}$ cache lines, but what are the $n$, $m$, and 1 in the expression of equation (5) 's base case for?

In Case III, equation 6 shows the base case if $m \in [\alpha \sqrt{ \mathcal{M}}, \sqrt{ \mathcal{M}}]$ then the base case cache complexity is $\Theta (1 +m)$. Is this $m$ the $m$ cache lines for this matrix? What happened to the $n \times p$ matrix B? Is it already in cache. If so, didn't we also incur cache misses before loading it?

Then finally, isn't Case IV the same as Case I's base case? Why is there a 1 in the $\Theta$?.

Matrix Transpose

Next, the paper discusses matrix transpose. Here, in Case I, I can see $2mn/\mathcal{B}$ is the number of lines in cache needed to store a total of $m \times n$ entries in the matrix. But what is the 1 overhead for?

Then, for Case II, it says "The output array consists of nm elements in $m$ rows"...However, I thought the output matrix $B$ defined above has $n$ rows!? Where is the $m$ rows coming from?

Then a bit later in the paragraph, we get that since $n \geq \alpha \mathcal{B} /2$, the cache complexity is $O(1+m)$. Is this because

\begin{align*} n \geq \alpha \mathcal{B}/2 \to m + nm/\mathcal{B} \geq m + \alpha /\mathcal{B} =O(1+m) ? \end{align*}

Finally, in Case III, equation (8), when the matrix A is small, it is $m \times n$, so it will take $mn/\mathcal{B}$ cache lines...but again, why this $m$ and $n$ in $O(m +n + mn/\mathcal{B})$?

Answer 1

The version of the paper I am reading does not contain that statement on page 3 that you quote, "An $s \times s$ submatrix is stored in $\Theta(s+s^2/B)$ cache lines." However, it does state that the authors are going to consider matrix multiplication in the case the matrix is stored in row-major order.

In that layout, matrix location $(i,j)$ is stored at memory location $m*i + j$, where $m$ is the number of columns in the matrix. If $m \geq B$ where $B$ is the cache line size, successive rows of an $s \times s$ submatrix will occupy distinct cache lines.

As such, there are at least $s$ lines occupied. As you noted, there are at least $s^2/B$ cache lines occupied, since there are $s^2$ elements and only $B$ fit in a cache line. So, the value is $\Theta(\max(s, s^2/B))$ when $m \geq B$, and in Landau notation, maximum and sum are interchangeable.