This lecture is based on the paper:

The Input/Output Complexity of Sorting and Related Problems

# Memory models

When talking about high performance computing, it is not only about optimising the runtime of the algorithm but also about how long it takes to transfer memory to complete the algorithm. Most algorithm classes work in a simple ‘fast memory’ model, where you have instant access to an infinitely large memory. This is a fairly unreasonable model—whilst some operating systems try to automatically handle memory for you, it is still inefficient compared to adapting your algorithm for the specific computer you are using.

The most basic memory model which is not the above is called the ‘von Neumann model’. This has a processor with a limited fast memory cache next to it (of size $Z$ words), and an infinite slow main memory slightly further away. In this model, we want to limit the number of data transfers between slow and fast memory. This model follows some rules:

1. Local data rule: The processor may only compute on data in fast memory.

2. Block transfer rule: Slow-fast transfers in blocks of size $L$ words.

As we load in blocks of $L$ words, you may have to consider ‘data alignment’. This means if you are loading an array of $n$ elements, if $n$ is not divisible by $L$ then you may have to do extra transfers. Or if your data is sitting within a larger block of data, your start address might not align with $L$-sized block boundaries - so you might require extra transfers even if $n$ is divisible by $L$. When $n$ is sufficiently large - we don’t really care about this.

So there are two main costs we now will care about:

• Work: $W(n)$ is the number of computations needed to complete the algorithm.

• Transfers (I/O complexity): $Q(n,Z,L)$ is the number of $L$-sized slow-fast transfers.

Our goals then become two fold:

1. Work optimality: We want to minimize $W(n)$ (achieve work-optimality).

2. High computational intensity: We want to maximise intensity:

To know how to balance these we need to know more about the system we are working on. Suppose one operation takes $\tau$ time/op - so the compute time for our algorithm is $T_{comp} := \tau W(n)$. Next suppose we take $\alpha$ time/word transfer time - so the transfer time for our algorithm is $T_{mem} := \alpha L Q(n,Z,L)$. If we can perfectly overlap these the overall run time would be $T \geq \max(T_{comp}, T_{mem})$. We can reformulate this in terms of the idealised run time $T_{comp}$:

In this we defined a new term $B := \alpha / \tau$ ops/word, what we will call the ‘machine balance’. It is measured in the number of operations the CPU can do per word transferred from the slow to fast memory. This balance then affects how much we want to prioritise the intensity, as we will see later.

There is a second measure of performance called the ’normalised performance’ of the algorithm. Let $W_{\ast}$ be the best possible work time in the ‘pure model’ where we don’t have any memory considerations. Then the normalised performance is:

This is really saying, how bad is the memory model algorithm in comparison to what is best if memory wasn’t an issue - ratios close to 1 are good. Using what we have above we can get a bound for this:

Notice here that the intensity only effects the ratio when $I(n,Z,L) < B$. This gives us our tradeoff between improving $W(n)$ and $I(n,Z,L)$. For example, if $I(n,Z,L) > B$ there is no point increasing it at the expense of $W(n)$ because it will not improve our normalised performance.

for i = 0 to n-1:
  // read A[i,:]
  for j = 0 to n-1:
    // read C[i,j], B[:,j]
    for k=0 to n-1:
      C[i,j] += A[i,k] * B[k,j]
    // store C[i,j]

Though this is a bit sad, as we are having to transfer $O(n^3)$ words when there is only really $O(n^2)$ data. Can we do better?

Let’s say we have some $b$ dividing $n$ (i.e., $b \mid n$) then we can rewrite

This means we can compute matrix multiplication in blocks. Let $M_{i,j}$ be the $b \times b$ sub-block of $M$ with the top-left corner being $i,j$. Then using the above we can write:

for i = 0 to n-1 by b:
  for j = 0 to n-1 by b:
    // let C_{i,j} be the b x b block.
    for k=0 to n-1 by b:
      // read A_{i,k}, B_{k,j}
      C_{i,j} += A_{i,k} * B_{k,j}
    // store C_{i,j}

Here notice that $b$ really depends on the size of the $Z$ ($b = \sqrt{Z/3}$) - we can pick it to be optimal for this particular architecture. Therefore we can optimize our algorithms for the architecture we are running on.

# Summary

Whilst this memory model is over-simplified compared to real hardware, it sets out the concepts that will be used in subsequent lectures.