Exponential Speedup in External Memory 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 &gt; 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).
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.