15
$\begingroup$

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).

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ can guess, but $N=$? found a case given as speedup $B^{\rm{polylog}(B)}$, sufficient? $\endgroup$ – vzn Feb 7 '13 at 6:07
  • $\begingroup$ It has to be in terms of $M$ for my purposes, unfortunately. I'd be interested in the reference though. $\endgroup$ – SamM Feb 7 '13 at 16:24
  • $\begingroup$ wikipedia on cache oblivious algorithms. fyi there is some subtlety in this fields notation. p7 footnote of Demaine says in this area, $N$ is problem size & sometimes $n = N/B$ where $n$ is number of blocks, "but the lower case notation seems to have fallen out of favor". you use $n$ above and alternatively $N$ apparently both as input size. think you should at least standardize in your question. $\endgroup$ – vzn Feb 7 '13 at 20:00
  • $\begingroup$ I edited it for consistency. $N$ is the size of the input, and $n$ is only used for matrix multiplication because the running time for that problem is generally defined in terms of an $n\times n$ matrix (i.e. $N = n^2$) $\endgroup$ – SamM Feb 7 '13 at 20:06
  • $\begingroup$ do not see cases of this after scanning the literature. maybe there is no such ref? maybe there is some case to be made that any such algorithm might be complex and therefore hard to theoretically analyze to obtain such a speedup...? or maybe it would have to be contrived...? or, maybe it is not possible? could there be an idea that random access to memory is the worst case possible? seems like the increase for speed is linear in $M$ for that case...? or, maybe some fractal pattern of access to memory is worst case? this line of study is only a little more than a decade old.... $\endgroup$ – vzn Feb 7 '13 at 22:28
3
+150
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm afraid I don't follow some of your arguments. If $M= \Omega(N)$, any problem in external memory is trivial. As I mentioned, $M = O(\log N)$ is somewhat silly as that means memory has only a constant number of words (possible but not how external memory is generally examined). I see what you're saying that there was exponential gain, but that doesn't say anything about intermediate values. For example, optimal Partition in external memory is the min of two terms (essentially if everything fits in memory we do something entirely different than if it doesn't). Can you rule that out? $\endgroup$ – SamM Feb 9 '13 at 15:36
  • 1
    $\begingroup$ I don't understand why any problem in external memory is trivial if $M = \Omega(N)$. If $M=N/2$ and the algorithm takes, exponential time, you might be forced to swap back and forth between (so to speak) the two halves of the memory an exponential number of times. $\endgroup$ – user8477 Feb 9 '13 at 16:18
  • $\begingroup$ Ah, of course you're right about the constant factor being important. That makes a lot of sense; this is certainly a good starting point. $\endgroup$ – SamM Feb 9 '13 at 16:44
  • $\begingroup$ I don't have any argument for intermediate values. At a very superficial level, I guess that some backtracking algorithms would have an exponential dependence on the memory size because I/O operations would be required at nodes of lower depth in the search tree. This dependence would apply to intermediate values. This says nothing about the inherent complexity of the problem, of course. Also, if you have $M=\omega(\log N)$, the pigeonhole (cycling) argument given above would still yield a gain of $T(N)/2^M$ where $T(N)$ is the time complexity of the problem. $\endgroup$ – user8477 Feb 9 '13 at 16:54
-4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ In your first point, what would "more theoretical analysis" even mean? A TM doesn't have a $k$-level memory hierarchy. The ideal-cache model is easy and natural to work with, and has been experimentally proven to be a useful model with respect to memory behavior on real systems. $\endgroup$ – Juho Feb 10 '13 at 20:13
  • $\begingroup$ the TM model is the basic model of TCS and "bridge thms" between its complexity hierarchy (time/space, basic complexity classes such as P/NP etc) with cache oblivious algorithms apparently remain to be mapped out. the external memory models & related cache oblivious models are basically attempting to model real-world performance characteristics & the literature is not so far interested in greater theoretical abstractions such as asked by the question. $\endgroup$ – vzn Feb 10 '13 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.