Random-access stored-program machine

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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)].

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)].

5: 03 18 15 JZ 18,15 ; if [18] is zero, jump to 15 to end the program 02 18 DEC 18 ; Decrement [18] 01 19 INC 19 ; Increment [19] 03 15 05 JZ 15, 5 ; If [15] is zero, jump to 5 to repeat the loop (use Halt to simulate unconditional jump) 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: 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 ⟪h ⟫, ; CPY ,⟪h ⟫ } 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: 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.

Parse phase

Now that the number of the program-instruction (e.g. 3 = "JZ") 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 (for example).

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378824778 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001378824778 · captured 1791271796.0 · version history

Cite this page as: encyclopegia.org, “Random-access stored-program machine”, snapshot enwiki-001378824778. https://encyclopegia.org/a/random-access-stored-program-machine

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.