Exponential Speedup in External Memory

Question

Background

The external memory, or DAM model, defines the cost of an algorithm by the number of I/Os it performs (essentially, the number of cache misses). These running times are generally given in terms of $M$, the size of memory, and $B$, the number of words that can be transferred to memory at one time. Sometimes $L$ and $Z$ are used for $B$ and $M$ respectively.

For example, sorting requires a cost of $\Theta(N/B\log_{M/B} N/B)$ and naive matrix multiplication requires $\Theta(n^3/B\sqrt{M})$.

This model is used to analyze "cache-oblivious algorithms", which do not have knowledge of $B$ or $M$. Generally the goal is for the cache-oblivious algorithm to perform optimally in the external memory model; this is not always possible, as in the Permutation problem for example (shown in Brodal, Faderberg 2003). See this writeup by Erik Demaine for a further explanation of cache-oblivious algorithms, including discussions of sorting and matrix multiplication.

We can see that changing $M$ causes a logarithmic speedup for sorting and a polynomial speedup for matrix multiplication. (This result is originally from Hong, Kung 1981 and actually predates both cache obliviousness and the formalization of the external memory model).

My question is this:

Is there any case where the speedup is exponential in $M$? The running time would be something like $f(N,B)/2^{O(M)}$. I am particularly interested in a cache-oblivious algorithm or data structure that fits this description but would be happy with a cache-aware algorithm/data structure or even a best-known lower bound.

It is generally assumed in most models that the word size $w = \Omega(\log N)$ if $N$ is the input size and clearly $M > w$. Then a speedup of $2^M$ gives a polynomial speedup in $N$. This makes me believe that if the problem I'm looking for exists, it is not polynomial. (Otherwise we can change the cache size by a constant to obtain a constant number of I/Os, which seems unlikely).

Answer 1

I am not sure I understood the question. But it seems to me that under the assumption that $PSPACE$ contains problems requiring exponential time, such problems would fulfill your requirements, since if $M$ is $O(\log N)$ you would need an exponential number of I/O operations (since you can't "stay" in the same memory block of size $O( \log N)$ more than a polynomial number of steps without going into a cycle) and if $M=N$ you would only need a linear number of I/O operations. Also, concerning your observation that such a problem cannot belong to $P$, it is correct if the speedup must hold for values of $M$ that are $\Omega(N)$ (since it would mean we have an exponential number of operations). But if the speedup only applies to smaller values of $M$, intuitively I believe this is not true, because I feel it should be possible to design a problem that is in fact the concatenation of smaller problems of size $O(\log N)$ each requiring exponential time in its own size, and an exponential number of I/O operations (that is, $poly (N)$, since $poly(N)$ is exponential in $O(\log N)$). In practice I believe $PSPACE$-complete problems such as $TQBF$ fulfill your condition.

Answer 2

this question appears to veer into terra incognita ie unexplored territory. after some thinking & review here are some thoughts/ideas on this apparently very difficult/subtle question which hopefully will be intelligent but are not meant to be definitive.

Demain who you cite writes, "the principle idea [of cache oblivious algorithms] is simple: design external-memory algorithms without knowing $B$ and $M$. But this simple idea has several surprisingly powerful consequences."

it also appears to have surprisingly subtle implications. it appears hard to analyze this model for extremal behavior and it appears nobody has done this so far. there are some surveys and they seem to survey the entire field so far. this is not surprising given the field is only ~1 decade old.

• the model does not appear to have been translated to Turing machines yet where more strict/formal/theoretical/general/standard analysis may be possible. the whole concept of Big-Oh notation and its implications and intuitions such as irrelevance of constants is not necessarily automatically carrying in this area of cache oblivious algorithms. for example the model already seems to be working with constants $B,M$ which measure exact memory sizes. it appears the field does not have a set of basic axioms of its dynamics so far.

• TMs were invented in 1936 by Turing and the Hartmanis-Stearns time/space hierarchy theorems (which you are somewhat alluding to in this question) were discovered in 1965. thats a remarkable ~3 decades yet the time/space hierarchy theorems are now considered somewhat elementary and taught in undergraduate classes. there does not seem to be corresponding hierarchy theorems established in this model yet, and how to do that is not a trivial problem. this model actually seems to have more "moving parts" than the standard Turing machine (which already has a rather fiendishly complex dynamics), ie is like an augmented Turing machine.

• another idea is to convert this external memory model to TMs somehow, which again does not appear to show up in the literature/surveys on cache oblivious algorithms, and maybe see how the Hartmanis-Stearns hierarchy theorems could translate. it appears to relate to a two tape TM where one tape is size 'M' and the other tape is infinite, and blocks are transferred to 'M' in sizes of 'B'. but also, a difficulty here is it is more of a RAM model than the Turing model which uses sequential access to the tape. on the other hand this could run into subtleties associated with conversions between single and multitape TMs.

• suggest attacking this problem empirically with simulations which is where the literature tends to focus on eg as in this great survey by Kumar on Cache oblivious algorithms (2003). there are many programs and papers online for cache simulations and one could possibly answer your question without a large amount of code, using some simplifications. one basic idea is to create probabilistic algorithms which access "nearby" areas of memory based on probabilities. "nearby" here is not necessarily contiguous memory, but instead an algorithm that selects random memory pages (blocks) based on keeping track of its own most recently accessed pages. suggest using power laws to determine the probability of selecting "near" pages in the "most recently accessed" list. this appears to be the key aspect that cache-based performance improvements are related to.

• heres a rough argument based on 'M' which is basically a measure of "core memory" versus disk memory. for an algorithm, one would expect as core memory increases, one only comes close [asymptotically] to a linear improvement in algorithmic speed, and adding "core memory" to get any super-linear increase in algorithm speed seems intuitively almost like exceeding the speed limit and "getting something for nothing". however, dont grasp the model well enough to prove this [but apparently no one else has either, including the authorities/founders/experts].

• this cache-oblivious algorithm literature has focused on P algorithms and did not see any case at all of an analysis of a non-P algorithm so far and perhaps none exists. this could possibly be because the analysis is too difficult! in which case, questions about extremal behavior may go unanswered in this field in the long term.

• it does not even seem intuitively clear, or possibly at all studied yet, about how "small" complexity algorithms such as in L, or "big" algorithms such as non-P (eg Expspace etc) behave in this model. the model is measuring memory locality, which seems to be fundamentally different, but intertwined with, time and space hierarchies.

• there is a somewhat obscure measurement of Turing machine complexity called "reversal complexity" with some study, results, and papers that might be related. basically the TM can cover a certain amount of time and space, but reversals are a somewhat independent measurement of the tape head during the computation. it seems that "high reversals" might be related to "high memory locality" because in both cases the tape head is tending to stay in a "smaller" region versus moving into larger regions.

• this question and model reminds me of Amdahls law and suspect some kind of yet-undiscovered similar law related to diminishing returns or balances/tradeoffs might hold or be applicable in this area. rough reasoning: cache oblivious algorithm theory is looking at a balance/tradeoff between a finite "local" memory and a cost-based external "infinite" disk. this is basically two resources that behave "in parallel" and there is likely some kind of optimal tradeoff between them.