In cache-oblivious algorithms, how is recursive reduction of data performed?
From the paper entitled &quot;Cache-Oblivious Mesh Layouts&quot; (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 &quot;atoms&quot; 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.