Random-access stored-program machine
In theoretical computer science the random-access stored-program machine model is an abstract machine used for the purposes of algorithm development and algorithm complexity theory.
The RASP is a random-access machine model that, unlike the RAM, has its program in its "registers" together with its input. The registers are unbounded ; 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 .
Informal definition: random-access stored-program model (RASP)
Nutshell description of a RASP: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, and eventually the output data/numbers. 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. 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: Unlike the UTM, the RASP model has two sets of instructions – the state machine table of instructions 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 #18 to register #19, erasing contents of #18 in the process.5: 03 18 15 JZ 18,15 ; if is zero, jump to 15 to end the program
02 18 DEC 18 ; Decrement
01 19 INC 19 ; Increment
03 15 05 JZ 15, 5 ; If is zero, jump to 5 to repeat the loop
15: 00 H ; Halt
18: n ; Source value to copy
19: ; Destination for copy
The program-instructions available in this RASP machine will be a simple set to keep the example short:
| Instruction | Mnemonic | Action on register "r" | Action on finite state machine's Instruction Register, IR |
| INCrement | INC | +1 → r | +1 → IR |
| DECrement | DEC | -1 → r | +1 → IR |
| Jump if Zero | JZ | none | IF = 0 THEN z → IR ELSE +1 → IR |
| Halt | H | none | → IR |
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:
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:
| PC | IR | ||||||||||||||||||
| hole # → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| program, parameters → | 5 | JZ | 18 | 15 | DEC | 18 | INC | 19 | JZ | 15 | 5 | H | n | ||||||
| encoded program → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| state machine instructions ↓ | |||||||||||||||||||
| ! |
Tradition divides the state-machine's actions into two major "phases" called Fetch and Execute. We will observe below that there are "sub-phases" within these two major phases. There is no agreed-to convention; every model will require its own precise description.
Fetch phase
The state machine has access to all the registers, both directly and indirectly. So it adopts #1 as "the program counter" PC. The role of the program counter will be to "keep the place" in the program's listing; the state machine has its own state register for its private use.Upon start, the state machine expects to find a number in the PC—the first "Program-Instruction" in the program.
The point of the above detour is to show that life is much easier when the state machine has access to two kinds of indirect copy:
- copy indirect from i and direct to j: CPY ⟪h⟫,
- copy direct from i and indirect to j: CPY,⟪h⟫
| PC | PIR | ||||||||||||||||||||
| hole # → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| program, parameters → | 5 | JZ | 18 | 15 | DEC | 18 | INC | 19 | JZ | 15 | 5 | H | n | ||||||||
| encoded program → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||||
| step | state machine instructions ↓ | ||||||||||||||||||||
| 1 | fetch_instr: | CPY ⟪1⟫, | 5 i | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n |
Parse phase
Now that the number of the program-instruction is in register #2 -- the "Program-Instruction Register" PIR—the state machine proceeds to decrement the number until the IR is empty:If the IR were empty before decrement then the program-instruction would be 0 = HALT, and the machine would jump to its "HALT" routine. After the first decrement, if the hole were empty the instruction would be INC, and the machine would jump to instruction "inc_routine". After the second decrement, the empty IR would represent DEC, and the machine would jump to the "dec_routine". After the third decrement, the IR is indeed empty, and this causes a jump to the "JZ_routine" routine. If an unexpected number were still in the IR, then the machine would have detected an error and could HALT.
| PC | IR | ||||||||||||||||||||
| hole # → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| program, parameters → | 5 | JZ | 18 | 15 | DEC | 18 | INC | 19 | JZ | 15 | 5 | H | n | ||||||||
| encoded program → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||||
| state machine instructions ↓ | |||||||||||||||||||||
| CPY ⟪1⟫, | 5 i | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | |||||||||
| JZ 2,halt | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | n | |||||||
| 3 | DEC 2 | 5 | 2 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 4 | JZ 2,inc_routine: | 5 | 2 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 5 | DEC 2 | 5 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 6 | JZ 2,dec_routine | 5 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 7 | DEC 2 | 5 | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 8 | JZ 2, JZ_routine | 5 | 0 ! | ||||||||||||||||||
| halt: | HALT | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| inc_routine: | etc. | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| dec_routine: | etc. | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n | ||||||
| 9 | JZ_routine: | etc. | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | n |