Random Access Machine
Jump to navigation
Jump to search
See: RAM, Abstract Machine, Register Machine, External Memory Model.
References
2009
- http://en.wikipedia.org/wiki/Random_Access_Machine
- In computer science, random access machine (RAM) is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers. Like the counter machine the RAM has its instructions in the finite-state portion of the machine (the so-called Harvard architecture).
- The RAM's equivalent of the Universal Turing machine -- with its program in the registers as well as its data -- is called the Random access stored program machine or RASP. It is an example of the so-called von Neumann architecture and is closest to the common notion of computer.
- Together with the Turing machine and counter machine models, the RAM and RASP models are used for computational complexity analysis. Van Emde Boas (1990) calls these three plus the pointer machine "sequential machine" models, to distinguish them from “parallel random access machine” models.
- (Schweikardt, 2009) Nicole Schweikardt. (2009). “Machine Models for Query Processing.” In: SIGMOD Record, 38(2).
- In the classical random access machine (RAM) model, the input consists of N data items, each of which can be represented by a bitstring of length O(logN). An unbounded number of data items can be stored in memory. Access to any item in memory as well as arithmetics and bitwise operations on data items can be performed in constant time.
- The basic external memory model (cf., e.g., [27]) can be viewed as a refinement of the RAM model where memory is divided into internal memory, capable of storing up to M data items, and external memory of unbounded size. Data present in internal memory can be accessed quickly (as in the RAM model). Data present in external memory can only be accessed by an operation called Input/Output communication (I/O, for short) that moves a contiguous block of B data items between internal and external memory. Initially, the N input items are stored in external memory. One typically assumes that M < N and 1 6 B 6 M/2.