Home

Last updated: Friday 5th September 2008, 7:46 PT by AHD

The RAM Model of Computation

Machine-independent algorithm design depends upon a hypothetical computer called the Random Access Machine or RAM. Under this model of computation, we are confronted with a computer where:  

• Each "simple" operation (+, *, -, =, if, call) takes exactly 1 time step.
• Loops and subroutines are not considered simple operations. Instead, they are the composition of many single-step operations. It makes no sense for ``sort'' to be a single-step operation, since sorting 1,000,000 items will take much longer than sorting 10 items. The time it takes to run through a loop or execute a subprogram depends upon the number of loop iterations or the specific nature of the subprogram.  
• Each memory access takes exactly one time step, and we have as much memory as we need. The RAM model takes no notice of whether an item is in cache or on the disk, which simplifies the analysis.  

Under the RAM model, we measure the run time of an algorithm by counting up the number of steps it takes on a given problem instance. By assuming that our RAM executes a given number of steps per second, the operation count converts easily to the actual run time.

The RAM is a simple model of how computers perform. A common complaint is that it is too simple, that these assumptions make the conclusions and analysis too coarse to believe in practice. For example, multiplying two numbers takes more time than adding two numbers on most processors, which violates the first assumption of the model. Memory access times differ greatly depending on whether data sits in cache or on the disk, thus violating the third assumption. Despite these complaints, the RAM is an excellent model for understanding how an algorithm will perform on a real computer. It strikes a fine balance by capturing the essential behavior of computers while being simple to work with. We use the RAM model because it is useful in practice.

Every model has a size range over which it is useful. Take, for example, the model that the earth is flat.   You might argue that this is a bad model, since the earth is not flat. However, when laying the foundation of a house, the flat earth model is sufficiently accurate that it can be reliably used. Further, it is so much easier to manipulate a flat-earth model that it is inconceivable that you would try to think spherically when you don't have to.

The same situation is true with the RAM model of computation. We make an abstraction that in general is very useful. It is quite difficult to design an algorithm such that the RAM model will give you substantially misleading results, by performing either much better or much worse in practice than the model suggests. The robustness of the RAM enables us to analyze algorithms in a machine-independent way.

Reference: http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK/NODE12.HTM