A one instruction set computer (OISC), sometimes called an ultimate reduced instruction set computer (URISC), is an abstract machine that uses only one instruction – obviating the need for a machine language opcode.[1][2][3] With a judicious choice for the single instruction and given infinite resources, an OISC is capable of being a universal computer in the same manner as traditional computers that have multiple instructions.[2] OISCs have been recommended as aids in teaching computer architecture[1][2] and have been used as computational models in structural computing research.[3]
Contents |
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.
There exists a class of universal computers with one instruction based on bit manipulation such as bit copying or bit inversion. Since their memory model is the same as memory structure used in real computers, those bit manipulation machines are equivalent to real computers rather than to Turing machines.
Common choices for the single instruction are:
Only one of these instructions is used in a given implementation. Hence, there is no need for an opcode to identify which instruction is to be executed; the choice of instruction is inherent in the design of the machine, and an OISC is typically named after the instruction it uses (e.g. an SBN OISC[2], the SUBLEQ language[3], etc.). Each of the above instructions can be used to construct a Turing-complete OISC.
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).
Wikis
Search
subleq a, b, c ; Mem[b] = Mem[b] - Mem[a]
; if (Mem[b] ≤ 0) goto c
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.
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.
It is possible to synthesize many types of higher-order instructions using only the subleq instruction.
Unconditional branch:
JMP c == subleq Z, Z, c ; Z is a location previously set to contain 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. 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: ...
The following program (written in pseudocode) emulates the execution of a subleq-based OISC:
integer memory[], program_counter, a, b, c
program_counter = 0
while (program_counter >= 0):
a = memory[program_counter]
b = memory[program_counter+1]
c = memory[program_counter+2]
if (a < 0 or b < 0):
program_counter = -1
else:
memory[b] = memory[b] - memory[a]
if (memory[b] > 0):
program_counter = program_counter + 3
else:
program_counter = c
This program assumes memory[] to be indexed by nonnegative integers; consequently, for a subleq instruction (a, b, c), the program interprets a < 0, b < 0, or an executed branch to c < 0 as a halting condition. Similar interpreters written in a subleq-based language (i.e. self-interpreters, which may use self-modifying code as allowed by the nature of the subleq instruction) can be found in the external links below.
There is a compiler called Higher Subleq written by Oleg Mazonka that compiles a simplified C program into subleq code. [4]
Subtraction is not the only operation upon which Turing completeness can be achieved in similar to subleq instruction. Other operations such as addition and increment can be used for OISC models (see, for example, Addleq and P1eq).
The subneg instruction ("SUbtract and Branch if NEGative"), also called SBN, is defined similarly to subleq:
subneg a, b, c ; Mem[b] = Mem[b] - Mem[a]
; if (Mem[b] < 0) goto c
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.
It is possible to synthesize many types of higher-order instructions using only the subneg instruction. For simplicity, only one synthesized instruction is shown here to illustrate the difference between subleq and subneg.
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;
Unconditional branching is assured only if Z initially contains 0 (or a value less than the integer stored in POS). A follow-up instruction is required to clear Z after the branching, assuming that the content of Z is supposed to be maintained as 0.
In a Reverse Subtract and Skip if Borrow (RSSB) instruction, 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.[2]
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
A "move machine", also called a transport triggered architecture CPU, has only one instruction:
move a to b ; Mem[b] := Mem[a]
sometimes written as:
a -> b ; Mem[b] := Mem[a]
This instruction moves the contents of one memory location to another memory location. Arithmetic is performed using a memory-mapped Arithmetic Logic Unit (ALU), 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, describing his version of this architecture, its implementation and evaluation.[5]
The only commercially available microcontroller built upon a transfer-triggered architecture is MAXQ from Maxim Integrated Products.[6][7] It uses a single move instruction and achieves 1 MIPS performance. MAXQ hides the apparent inconvenience of an OISC by using a transfer map that represents all possible destinations for the move instructions.[8]
|
||||||||||||||||||||||||||||
OISC (One-Instruction Set Computer) is a RISC (Reduced Instruction Set Computer), which number of instructions is reduced to one, obviating the need for a processor opcode. It has been shown that such computer has the same computational power as any other computer.
|
|
