Random access stored program machine


Random access stored program machine

In theoretical computer science the Random Access Stored Program (RASP) machine model is an abstract machine used for the purposes of algorithm development and algorithm complexity theory.

The RASP is a Random Access Machine (RAM) model that, unlike the RAM, has its program in its "registers" together with its input. The registers are unbounded (infinite in capacity); whether the number of registers is finite is model-specific. Thus the RASP is to the RAM as the Universal Turing machine is to the Turing machine. The RASP is an example of the von Neumann architecture whereas the RAM is an example of the Harvard architecture.

The RASP is closest of all the abstract models to the common notion of computer. But unlike actual computers the RASP model usually has a very simple instruction set, greatly reduced from those of CISC and even RISC processors to the simplest arithmetic, register-to-register "moves", and "test/jump" instructions. Some models have a few extra registers such as an accumulator.

Together with the Register machine, the RAM, and the pointer machine the RASP makes up the four common sequential machine models, called this to distinguish them from the "parallel" models (e.g. parallel random access machine) [cf. van Emde Boas (1990)] .

Informal definition: Random Access Stored Program model (RASP)

Nutshell description of a RASP::The RASP is a Universal Turing Machine (UTM) built on a Random access machine RAM chassis.

The reader will remember that the UTM is a Turing machine with a "Universal" finite-state table of instructions that can interpret any well-formed "program" written on the tape as a string of Turing 5-tuples, hence its universality. While the classical UTM model expects to find Turing 5-tuples on its tape, any program-set imaginable can be put there given that the Turing machine expects to find them -- given that its finite-state table can interpret them and convert them to the desired action. Along with the program, printed on the tape will be the input data/parameters/numbers (usually to the program's right), and eventually the output data/numbers (usually to the right of both, or intermingled with the input, or replacing it). The "user" must position the Turing machine's head over the first instruction, and the input must be placed in a specified place and format appropriate to both the program-on-tape and the finite-state machine's instruction-table.

The RASP mimics this construction: it places the "program" and "data" in the holes (registers). But unlike the UTM the RASP proceeds to "fetch" its instructions in a sequential manner, unless the conditional test sends it elsewhere.

A point of confusion: two sets of instructions: Like the UTM, the RASP model has two sets of instructions -- the state machine table of instructions (the "interpreter") and the "program" in the holes. The two sets do not have to be drawn from the same set.

An example of a RAM working as a RASP

The following example of a program will move the contents of register (hole) #18 to register (hole) #19, erasing contents of #18 in the process. The "program"-instructions will be a simple set to keep the example short::Target RASP program-instructions:::{ INC h; DEC h; JZ h,xxx }

To ease the example we will equip the "state machine" of the RAM-as-RASP with the primitive instructions drawn from the same set, but augmented with two indirect copy instructions::RAM state machine instructions:::{ INC h; DEC h; JZ h,xxx; CPY <a>>,a>; CPY a>,<a>> }

As the RASP machine's state machine interprets the program in the registers, what exactly will the state machine be doing? The column containing the exclamation mark ! will list in time sequence the state machine's actions as it "interprets" -- converts to action -- the program:

Execute phase, JZ_routine

Now the state machine knows what program-instruction to execute; indeed it has jumped to the "JZ_routine" sequence of instructions. The JZ instruction has 2 operands -- (i) the number of the register to test, and (ii) the address to go to if the test is successful (the hole is empty).

(i) Operand fetch -- which register to test for empty?: Analogous to the fetch phase, the finite state machine moves the contents of the register pointed to by the PC, i.e. hole #6, into the Program-Instruction Register PIR #2. It then uses the contents of register #2 to point to the register to be tested for zero, i.e. register #18. Hole #18 contains a number "n". To do the test, now the state machine uses the contents of the PIR to indirectly copy the contents of register #18 into a spare register, #3. So there are two eventualities (ia), register #18 is empty, (ib) register #18 is not empty. (ia): If register #3 is empty then the state machine jumps to (ii) Second operand fetch -- fetch the jump-to address.

(ib): If register #3 is not empty then the state machine can skip (ii) Second operand fetch. It simply increments twice the PC and then unconditionally jumps back to the instruction-fetch phase, where it fetches program-instruction #8 (DEC).

(ii) Operand fetch -- jump-to address. If register #3 is empty, the state machine proceeds to use the PC to indirectly copy the contents of the register it points to (#8) into "itself". Now the PC holds the jump-to address 15. Then the state machine unconditionally goes back to the instruction fetch phase, where it fetches program-instruction #15 (HALT).

References

Often both the RAM and RASP machines are presented together in the same article. See Register machine and Random access machine for references;


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • 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… …   Wikipedia

  • Magnetoresistive random access memory — Computer memory types Volatile RAM DRAM (e.g., DDR SDRAM) SRAM In development T RAM Z RAM TTRAM Historical Delay line memory Selectron tube Williams tube Non volatile …   Wikipedia

  • Register machine — In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine. All the models are Turing equivalent. Contents 1 Overview 2 Formal definition 3 …   Wikipedia

  • Turing machine equivalents — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

  • Abstract machine — An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in Automata theory. Abstraction of computing processes is used in both the computer science and computer engineering… …   Wikipedia

  • Pointer machine — In theoretical computer science a pointer machine is an atomistic abstract computational machine model akin to the Random access machine.Depending on the type, a pointer machine may be called a linking automaton, a KU machine, an SMM, an… …   Wikipedia

  • Counter machine reference model — The Counter machine s reference model is a set of choices and conventions to be used with the Counter machine and other model variants of the Register machine concept. It permits comparisons between models, and serves a didactic function with… …   Wikipedia

  • Counter machine — A counter machine is an abstract machine used in formal logic and theoretical computer science to model computation. It is the most primitive of the four types of register machines. A counter machine comprises a set of one or more unbounded… …   Wikipedia

  • Manchester Small-Scale Experimental Machine — Replica of the Small Scale Experimental Machine (SSEM) at the Museum of Science and Industry in Castlefield, Manchester …   Wikipedia