41
$\begingroup$

In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and analyse algorithms.

As a result, we have dozen of algorithms for, e.g., SORT-problem for different models of computation. Unfortunately, we even cannot be sure that an implementation of an algorithm with running time O(n) in a word RAM with bit-vector operations allowed will run faster than an an implementation of an algorithm with running time O(n⋅logn) in a word RAM (I am talking about "good" implementations only, of course).

So, I want to understand which of existing models is "the best" for designing algorithms and I am looking for an up-to-date and detailed survey on models of computation, which gives pros and cons of models and their closeness to reality.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Cross-posted on MathOverflow (mathoverflow.net/questions/44558/…), though redirected here. $\endgroup$
    – Dave Clarke
    Nov 2, 2010 at 17:22
  • $\begingroup$ @Tatiana, Good question, What do you mean by "the best"? Do you mean a model with theoretical run-time that is close to the "real" run-time? $\endgroup$
    – Mohammad Al-Turkistany
    Nov 2, 2010 at 17:24
  • 8
    $\begingroup$ If you're looking to accurately model "real" running times, then it seems that it might be important to accurately model caches. In particular, modern computing has many layers of caching (CPU, RAM, Disk, etc...) with some layers being orders of magnitude in slower than others; it is not out of the question for an algorithm's "real" runtime to be determined by the number of cache misses. Anecdotally, I've heard that one reason that barrier methods in linear programming perform so well despite their poor theoretical guarantees is because they are often quite cache-efficient. $\endgroup$
    – mhum
    Nov 2, 2010 at 22:59
  • 4
    $\begingroup$ As far as I can tell, as mhum says, the biggest discrepancies of the predicted running times in the word RAM model and the real running times generally arise because of data retrieval ... the wrong variables are in cached memory and the retrieval time slows down enormously because of this. There have been a number of attempts to model this with a theoretical hierarchical-memory model, and I don't believe that any of these attempts have been very successful, because the models end up being too complicated to easily work with. $\endgroup$
    – Peter Shor
    Nov 3, 2010 at 15:00
  • 2
    $\begingroup$ If you have an algorithm that you think might be useful in practice, and you want to see it actually used, the best thing you can do to ensure this is to implement it or get somebody else to implement it (even if it's not a good enough implementation to be incorporated into practical software). For a case study in this, look at the history of the LZW data compression algorithm. In fact, there's probably no point in trying to figure how caching affects the algorithm unless it's one which people are interested in implementing; otherwise nobody will pay any attention to your results. $\endgroup$
    – Peter Shor
    Nov 5, 2010 at 18:21

6 Answers 6

Reset to default
30
$\begingroup$

I have always considered the standard Word RAM model to be "the best" in your sense. Everybody who learned to program in a language like C (or any loose equivalents like Java, etc) has precisely this model in mind when they think of a computer.

Of course, you sometimes need generalizations depending on the regimes in which you work. The external memory model is an important one to keep in mind. It applies not only when you work with disks, but also in understanding (forcing you to care about) cache. Of course, treating it too seriously can also lead to nonsensical results, since the pure external memory model doesn't count computation. Another generalization of the Word RAM is to parallelism, but there we are all a bit confused at the moment :)

An algorithm with an $O(n)$ running time will certainly run faster than one with $O(n \lg n)$ running time. It is a mathematical fact that the former is faster for large $n$ :) Your problem size may simply not be large enough for this to matter. Since you bring up sorting, let me assure you it will be very hard to beat radix sort with a comparison-based algorithm for reasonable $n$.

A final remark on algorithms and "reality": always keep in mind what you're trying to achieve. When we work in algorithms, we are trying to solve the hardest problems out there (e.g. SAT on 50 variables, or sorting a billion numbers). If you're trying to sort 200 numbers or solve SAT on 20 variables, you don't need any fancy algorithm. That's why most algorithms in reality are kind of trivial. This doesn't say anything bad about algorithmic research — we just happen to be interested in that unusual 1/1000 of the real problems that happen to be hard...

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank for your answer. I want to understand, which generalizations are worth adding to word RAM. Can we describe a model, which will include all these tricks like bit-vector operations, parallelism, caches, and still be simple? $\endgroup$
    – Tatiana Starikovskaya
    Nov 3, 2010 at 13:24
11
$\begingroup$

There is no one totally satisfactory computational model in which to analyse algorithms sadly, even in what one might consider a traditional setting. That is assuming all data is readily accessible and the working space is effectively unbounded.

The multi-tape Turing machine, is certainly theoretically well specified and many algorithms have been designed and analysed in this model over the years. However, to some it does not relate closely enough to how real computers work to really be a good model to use in the 21st century. On the other hand, the word-RAM model has become popular and appears to capture more accurately the working of modern computers (operations on words not bits, constant time access to memory locations). However, there are aspects which are less than ideal. For example, there is no one word RAM model. One has to first specify which operations on words are to be allowed in constant time. There are many options for this with no single accepted answer. Second, the word size w is normally set to grow with the input size (that is at least as fast as log(n)) to allow any item in memory to be addressed using a constant number of words. This means that one has to imagine an infinite class of machines on which your algorithm is run or even worse, that the machine changes as you feed it more data. This is a disconcerting thought for the purest amongst my students at least. Finally, you get somewhat surprising complexity results with the word-RAM model which might not tally with those one learns as a student. For example, multiplication of two n-bit numbers is O(n) time in this model and simply reading in an n-bit string is a sublinear time operation all of a sudden.

Having said all that, if you just want to know if your algorithm is likely to run fast, either will do most likely :-)

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ I think that if you're eschewing bitwise or word-model arithmetic operations in an attempt to avoid the "machine grows with input size" issue, but still using a uniform-cost RAM or pointer machine, then you're just fooling yourself: those other models have the same issue. How do they index their input? The answer is: real computers run out of memory, but despite that it's still more convenient to design algorithms for them assuming they're a RAM (or maybe even better to use a model that accounts for memory hierarchy costs) than assuming they're a DFA. $\endgroup$
    – David Eppstein
    Nov 2, 2010 at 19:58
  • 4
    $\begingroup$ A RAM model that Knuth discusses, for example, costs w time to look up an address with w bits and similarly w time to add two w bit numbers (this is how he gets Theta(n log n) for the time to multiply two n-bit numbers in a RAM model without any constant time operations on words). It is interesting how the most widely accepted models have changed in the last 20 years and how many models are just never discussed at all any more. $\endgroup$
    – Simd
    Nov 2, 2010 at 20:14
9
$\begingroup$

Models are just models. I wouldn't push it too far; they tell something about some aspects of your algorithms, but not the whole truth.

I would suggest that you simply use the standard word RAM model in your analysis and implement the algorithm and see how well it performs in practice.

(Actually just implementing your algorithm without ever running it tells you already a lot about it... For one thing, it is then provably implementable.)

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Well, I have two objections. First, not so many theoreticians implement algorithms and yet we are to compare them somehow. Secondly, I want to understand what features of a computer we may add to a model not loosing its simplicity. $\endgroup$
    – Tatiana Starikovskaya
    Nov 3, 2010 at 13:11
  • 11
    $\begingroup$ David Johnson's proposed solution for this is to have more people implement algorithms -- he started ALENEX and the DIMACS Challenges to address this. I have some experience with this as well. With Ken Clarkson, I devised a randomized convex hull algorithm we thought would work well in practice. Clarkson had a summer student at Bell Labs implement it. Based on the promise of this implementation, the ideas were worked into the qhull program (written at the Geometry Center), but with some heuristic speed-ups that means the algorithm no longer has a theoretical guarantee that it runs quickly. $\endgroup$
    – Peter Shor
    Nov 3, 2010 at 15:10
7
$\begingroup$

If your computational task is more about moving data than performing (arithmetic) operations, (the data sets are huge so that they do not even fit into main memory), then the I/O-model (introduced by Aggarwal and Vitter in 1988) can be very accurate. For tasks like permuting a big array of elements in main memory, it can help to use the algorithms that are I/O-optimal (in a careful implementation).

For modern multi-core computers, the parallel variant introduced by Arge, Goodrich, Nelson and Sitchinava in 2008 can be an accurate model.

Improve this answer
$\endgroup$
0
5
$\begingroup$

If you mean "the best" computational model to make your life more complicated, then you can use Wolfram's 2-state, 3-symbol universal turing machine.

PROS: none except the sensation of walking the fine line between reason and craziness;

CONS: tons ...

:-D (only a joke, I basically agree with the previous answers ...)

Improve this answer
$\endgroup$
1
$\begingroup$

On a more theoretical note: The article Ultimate theoretical models of nanocomputers argues that the reversible 3D mesh model is the optimal physical model of computation, in the sense that no other physical model could be asymptotically faster. Physical considerations like the speed of light, Landauer's principle, and the Bekenstein bound are discussed.

To quote from the abstract:

We find that using current technology, a reversible machine containing only a few hundred layers of circuits could outperform any existing machine, and that a reversible computer based on nanotechnology would only need to be a few microns across in order to outperform any possible irreversible technology.

We argue that a silicon implementation of the reversible 3D mesh could be valuable today for speeding up certain scientific and engineering computations, and propose that the model should become a focus of future study in the theory of parallel algorithms for a wide range of problems.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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