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). Such universal computers are the logical conclusion of reduced instruction set computing, although the concept has been 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 mutatis mutandis. 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:
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:
STO 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 memory location 0.
[edit] Example
To set x to the value of y minus z:
RSSB x RSSB x RSSB x RSSB z RSSB x RSSB temp RSSB temp RSSB temp RSSB temp RSSB y RSSB temp RSSB temp RSSB x RSSB temp RSSB temp RSSB temp RSSB temp
[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 [2]), 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 an ultimate RISC (URISC) machine during the 80s 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, please refer to "APPLICATION NOTE 3222 Introduction to the MAXQ Architecture"[3].
[edit] References
[edit] External links
- Mark II OISC Self-Interpreter Possibly the first-ever OISC self-interpreter.
- SBN Computer
- SUBLEQ compiler and emulator
- SUBLEQ variants; interpreters in SUBLEQ and Python
- http://esolangs.org/wiki/Subleq
|
||||||||||||||
