# In cache-oblivious algorithms, how is recursive reduction of data performed?

From wikipedia:

"Typically, a cache-oblivious algorithm works by a recursive divide and conquer algorithm, where the problem is divided into smaller and smaller subproblems. Eventually, one reaches a subproblem size that fits into cache, regardless of the cache size."

(Is this recursive subdivision manual, or automated? Assuming automated...)

In what way must one produce code in order for it to be suitable for reduction to a cache-oblivious form? Does this rely on the specific implementation of recursive reduction applicable in one's given case?

Another way of putting the question is, would I need to write my code in a special way in order for some automated parser to run through the code and optimise it for cache-oblivious access?

P.S. I'm trying to get a handle on how to approach writing code for practical optimisation using the methods noted in the literature.

• Cache-obliviousness is a property of the algorithm: an algorithm is either CO or not. There is not general recipe to produce CO algorithms out of algorithms that are not CO. What wiki says is just an observation that usually CO algorithms are recursive. However, not all recursive algorithms are CO, and it is up to you as an algorithm designed to prove the CO property holds. – Sasho Nikolov Dec 2 '13 at 23:32
• @SashoNikolov: do you think of algorithms as working over a fixed computational model? I suppose "cache-oblvious" only makes sense in a setting where there is cache... – Andrej Bauer Dec 3 '13 at 9:31
• @AndrejBauer Usually one fixes a computational model with a cache, similar to RAM with external memory. The main parameters of the cache are block size (data are always transferred in blocks) and height. Then the goal is to design an algorithm which is oblivious to the parameters of the cache but still incurs optimal cache misses, up to constants. If you have such an optimal CO algorithm, it turns out that optimality is robust to the exact model. For example, it would use a multi-level memory hierarchy optimally as well. – Sasho Nikolov Dec 3 '13 at 16:31
• Both to OP, and to @AndrejBauer, Prokop's MS thesis is a good reference: supertech.csail.mit.edu/papers/Prokop99.pdf – Sasho Nikolov Dec 3 '13 at 16:37

From the paper entitled "Cache-Oblivious Mesh Layouts" (Yoon et al):

The cache miss ratio function (CMRF), pl, is a function that relates the cache miss ratio to an edge span, l. The CMRF always lies within the interval [0;1]; it is exactly 0 when there are no cache misses, and equals 1 when every access results in a cache miss. We alter the layouts using a local permutation that reorders a small subset of the vertices. The local permutation changes the edge span of edges that are incident to the affected vertices (see Fig. 3).

The data granularity is repeatedly reduced in software until the "atoms" are small enough to fit cache. The lower bound on data structure granularity is reached as soon as the cache miss ratio reaches zero: beyond this point, further reduction becomes unnecessary. For any given target environment, at runtime, we proceed to reduce the size of data set atoms until they are small enough that the miss ratio reaches zero.

This (often recursive) reduction / linearisation is explored in the MIT OCW lessons on Cache Oblivious algorithms (this lesson and the following one).

Perhaps other approaches exist(?), but it makes sense to me that an algorithm oblivious to block size B would use this sort of approach, in general.

Usually it is in the form of a space filling curve to store the data.

Say you have a table with both SSN and Birthday fields. Storing the data in either order would result in bad cache behavior for queries depending on the other field.

The solution to get cache oblivious queries is to store the data in a z-curve, http://en.wikipedia.org/wiki/Z-order_curve I.e. sort the data on both SSN for your X dimension and on Birthday for your Y dimension and store it in Z order.

Great talk by Kmett a few weeks ago on using this technique for real world data sets.