One instruction set computer
From Wikipedia, the free encyclopedia
- OISC redirects here. For the Anglo-Saxon king, see Oisc of Kent.
The One Instruction Set Computer is a single machine language opcode which is sufficient to produce a Turing complete machine. Although such a computer could be taken as the logical conclusion of reduced instruction set computing, the single instruction computer is generally considered a thought experiment to show how small an instruction set could be made while still retaining the properties of a universal computer.
Contents |
[edit] Subtract and branch if negative
Subtracts the contents of memory location a from the contents of b, storing the result back into b, and then, if the result was negative or zero, transferring control to the location specified by the address stored in c.
[edit] Example 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[b] - memory[a];
if (memory[b] > 0)
program_counter += 3;
else
program_counter = c;
}
An equivalent self-interpreter can be found here. Due to the nature of the 'subleq' instruction, this is also an example of a situation where self-modifying code must be used in order to achieve the desired result.
[edit] Common instructions
Subtract and branch if negative abbreviated as subleq.
Unconditional branch:
Z is a location previously initialized to contain 0.
JMP c == subleq Z, Z, c
(The branch is unconditional regardless of whether Z previously contained 0, but to prevent overwriting the contents of Z, a special reserved location should be used.)
In any instruction, the conditional branch can be suppressed by pointing it at the instruction that would have been executed next in any case. If the parameter c is missing, it is implied that this is the case.
Addition can be performed as reversed subtraction:
ADD a, b == subleq a, Z
subleq Z, b
subleq Z, Z
(Here all the branches have been suppressed.) The first instruction computes the negation of a and stores it in location Z. The second instruction subtracts -a from 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 ≤0 relation. 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:...
[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
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 Jones wrote an essay on this architecture for ACM [2] describing his architecture and how it worked. [3]
The Transport Triggered Architectures can be seen as a kind of move architecture. [4]
[edit] MAXQ
The only commercially available microcontroller that is build upon a transfer-triggered architecture is MAXQ from Dallas/Maxim semiconductor. It uses a single MOVE instruction and achieves 1 MIPS per MHz performance. The transfer map which represents all possible destinations for its MOVE instruction can be seen at http://media.maxim-ic.com/images/appnotes/3222/3222-08.gif. One may think that programming an OISC computer is difficult. MAXQ hides this inconvenience by using the transfer map. There are virtual instructions eg. 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"[5].
