One instruction set computer
From Wikipedia, the free encyclopedia
 |
It has been suggested that The Ultimate RISC (URISC) be merged into this article or section. (Discuss) |
A One Instruction Set Computer (OISC) is a Turing-complete abstract machine that uses only one instruction (obviating the need for a machine language opcode). These universal computers are used primarily as a theoretical teaching aid (e.g., URISC).
Contents |
[edit] Subtract-and-branch-if-...
Two common choices for an OISC's single instruction are as follows, with comments showing the meaning in pseudocode:
subleq a, b, c ; Mem[b] = Mem[b] - Mem[a]
; if (Mem[b] ≤ 0) goto c
subneg a, b, c ; Mem[b] = Mem[b] - Mem[a]
; if (Mem[b] < 0) goto c
where, in a Turing-complete model, each memory location can store an arbitrary integer, and — depending on the model — there may be arbitrarily many locations. The instructions themselves reside in memory as a sequence of such integers.
Thus, the subleq instruction ("SUbtract and Branch if Less than or EQual to zero") subtracts the contents at address a from the contents at address b, stores the result at address b, and then, if the result is not positive, transfers control to address c (if the result is positive, execution proceeds to the next instruction in sequence). The subneg instruction ("SUbtract and Branch if NEGative"), also called SBN, is defined similarly. In both cases the opcodes are shown only to make the distinction clear.
[edit] Synthesised instructions
In any instruction, conditional branching can be suppressed by setting the third operand equal to the address of the next instruction in sequence. If the third operand is not written, this suppression is implied.
Unconditional branch:
JMP c == subneg POS, Z, c
...
c: subneg Z, Z
where Z and POS are locations previously set to contain 0 and a positive integer, respectively; or (more simply),
JMP c == subleq Z, Z, c
For subleq, the branching is unconditional regardless of whether Z initially contains 0; but for subneg, unconditional branching is assured only if Z initially contains 0 (or a value less than the integer stored in POS), and also requires a follow-up instruction to clear Z after the branching, assuming the content of Z is supposed to be maintained as 0.
Addition can be performed by repeated subtraction, with no conditional branching; e.g., the following instructions result in the content at location a being added to the content at location b:
ADD a, b == subleq a, Z
subleq Z, b
subleq Z, Z
The first instruction subtracts the content at location a from the content at location Z (which is 0) and stores the result (which is the negative of the content at a) in location Z. The second instruction subtracts this result from b, storing in b this difference (which is now the sum of the contents originally at a and b); the third instruction restores the value 0 to Z.
A copy instruction can be implemented similarly; e.g., the following instructions result in the content at location b getting replaced by the content at location a, again assuming the content at location Z is maintained as 0:
MOV a, b == subleq b, b
subleq a, Z
subleq Z, b
subleq Z, Z
Any desired arithmetic test can be built out of the negative or ≤0 relations. For example, a branch-if-zero condition can be assembled from the following instructions:
BEQ b, c == subleq b, Z, L1
subleq Z, Z, OUT
L1:subleq Z, Z
subleq Z, b, c
OUT:...
A variant is also possible with two operands and an accumulator, where the accumulator is subtracted from the memory location specified by the first operand. The result is stored in both the accumulator and the memory location, and the second operand specifies the branch address. Although this uses only two (instead of three) operands per instruction, correspondingly more instructions are then needed to effect various logical operations.
[edit] Example subleq OISC emulator
int program_counter = 0; int memory[384]; while (program_counter >= 0) { a = memory[program_counter]; b = memory[program_counter + 1]; c = memory[program_counter + 2]; memory[b] -= memory[a]; if (memory[b] > 0) program_counter += 3; else program_counter = c; }
Equivalent self-interpreters (which use self-modifying code due to the nature of the subleq instruction) can be found in the external links below.
[edit] Reverse-subtract and skip if borrow
The accumulator is subtracted from the memory location and the next instruction is skipped if there was a borrow (memory location was smaller than the accumulator). The result is stored in both the accumulator and the memory location. The program counter is mapped to memory location 0. The accumulator is mapped to memory location 1.
[edit] Example
To set x to the value of y minus z:
# First, move z to the destination location x. RSSB temp # Three instructions required to clear acc, temp RSSB temp RSSB temp RSSB x # Two instructions clear acc, x, since acc is already clear RSSB x RSSB y # Load y into acc: no borrow RSSB temp # Store -y into acc, temp: always borrow and skip RSSB temp # Skipped RSSB x # Store y into x, acc # Second, perform the operation. RSSB temp # Three instructions required to clear acc, temp RSSB temp RSSB temp RSSB z # Load z RSSB x # x = y - z
[edit] Move
A "move machine", also called a transport triggered architecture CPU,[1] has only one instruction:
move a to b ; Mem[b] := Mem[a]
sometimes written
a -> b ; Mem[b] := Mem[a]
Moves the contents of one memory location to another memory location. Arithmetic is performed using a memory-mapped ALU (if the address width is two or more words, the ALU can be replaced by table lookups [1]), and jumps are performed using a memory-mapped program counter. A computer was made from the Wireworld cellular automaton using this design. Douglas W. Jones wrote an essay on this architecture, The Ultimate RISC, published as ACM SIGARCH Computer Architecture News 16, 3 (June 1988) 48-55 describing his architecture and how it worked.
[edit] OINC
A team at Caltech implemented a One INstruction Computer during the 70s to test IC design concepts. It implemented MOV direct, direct, with special function registers for all other operations. Researchers at the University of Waterloo designed complete hardware for such a machine during the 80s, calling it Ultimate RISC (URISC), for use in teaching computer architecture concepts.
[edit] MAXQ
The only commercially available microcontroller that is built upon a transfer-triggered architecture is MAXQ from Dallas Semiconductor, a division of Maxim Integrated Products. It uses a single MOVE instruction and achieves 1 MIPS per MHz performance. MAXQ hides the apparent inconvenience of OISC by using a transfer map, which represents all possible destinations for its MOVE instruction. There are virtual instructions, e.g. MOVE #5 PC can be seen as an instruction JMP #5. (Warning, this code syntax may not be valid.)
For more information, see [APPLICATION NOTE 3222 Introduction to the MAXQ Architecture http://www.maxim-ic.com/appnotes.cfm/appnote_number/3222].
[edit] References
[edit] External links
- Mark II OISC Self-Interpreter Possibly the first-ever OISC self-interpreter.
- Redcode interpreter for RSSB
- The Ultimate RISC One Instruction Computing
- SBN Computer
- SUBLEQ compiler and emulator
- Subleq on the Esoteric Programming Language Wiki
- RSSB on the Esoteric Programming Language Wiki
- Computer Architecture: A Minimalist Perspective (CAAMP) A computer architecture book that focuses and examines the one instruction set computer architecture in depth.
|
||||||||||||||||||||||||||||
