One instruction set computer
Encyclopedia
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
. 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. OISCs have been recommended as aids in teaching computer architecture and have been used as computational models in structural computing research.
, 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.
Currently known OISC can be roughly separated into three broad categories:
Transport Triggered Architecture (TTA) is a design in which computation is a side effect of data transport. Usually some memory registers (triggering ports) within common address space, perform an assigned operation when the instruction references them. For example, in an OISC utilizing a single memory-to-memory copy instruction, this is done by triggering ports performing arithmetic and instruction pointer jumps when writing into them.
Bit Manipulating Machines is the simplest class. A bit copying machine, called BitBitJump, copies one bit in memory and passes the execution unconditionally to the address specified by one of the operands of the instruction. This process turns out to be capable of universal computation (i.e. being able to execute any algorithm and to interpret any other universal machine) because copying bits can conditionally modify the code ahead to be executed. Another machine, called the Toga computer, inverts a bit and passes the execution conditionally depending on the result of inversion. Yet another bit operating machine, similar to BitBitJump, copies several bits at the same time. The problem of computational universality is solved in this case by keeping predefined jump tables in the memory.
Arithmetic based Turing-complete Machines use an arithmetic operation and a conditional jump. Unlike the two previous classes which are universal computers, this class is universal and Turing-complete in its abstract representation. The instruction operates on integers which may also be addresses in memory. Currently there are several known OISCs of this class, based on different arithmetic operations: addition – Addleq, decrement – DJN, increment – P1eq, and subtraction – Subleq. The latter is the oldest, the most popular and, arguably, the most efficient.
Only one of these instructions is used in a given implementation. Hence, there is no need for an opcode to identify which instruction to execute; 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, the SUBLEQ language, etc.). Each of the above instructions can be used to construct a Turing-complete OISC.
This article presents only subtraction-based instructions among those that are not transport triggered. However it is possible to build Turing complete machine using an instruction based on other arithmetic operations, e.g., addition. For example, one variation known as DLN (Decrement and jump if not zero) has only two operands and uses decrement as the base operation. For more information see Subleq derivative languages.
Pseudocode
:
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 internal 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:
subleq2 a, b ; Mem[a] = Mem[a] - ACCUM
; ACCUM = Mem[a]
; if (Mem[a] ≤ 0) goto b
Although this uses only two (instead of three) operands per instruction, correspondingly more instructions are then needed to effect various logical operations.
Unconditional branch:
JMP c subleq Z, Z, c ; Z is a location previously set to contain 0
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 b, Z, L1
subleq Z, Z, OUT
L1: subleq Z, Z
subleq Z, b, c
OUT: ...
Subleq2 can also be used to synthesize higher-order instructions, although it generally requires more operations for a given task. For example no fewer than 10 subleq2 instructions are required to flip all the bits in a given byte:
NOT a subleq2 tmp ; tmp = 0 (tmp = temporary register)
subleq2 tmp
subleq2 minus_one ; acc = -1
subleq2 a ; a' = a + 1
subleq2 Z ; Z = - a - 1
subleq2 tmp ; tmp = a + 1
subleq2 a ; a' = 0
subleq2 tmp ; load tmp into acc
subleq2 a ; a' = - a - 1 ( = ~a )
subleq2 Z ; set Z back to 0
) 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 that memory[] is 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-interpreter
s, 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.
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.
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 must be maintained as 0.
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.
# 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
move a to b ; Mem[b] := Mem[a]
sometimes written as:
a -> b ; Mem[b] := Mem[a]
Arithmetic is performed using a memory-mapped arithmetic logic unit
and jumps are performed using a memory-mapped program counter
.
A commercial transport triggered architecture microcontroller has been produced called MAXQ, which hides the apparent inconvenience of an OISC by using a "transfer map" that represents all possible destinations for the move instructions.
Abstract machine
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory...
that uses only one instruction – obviating the need for a machine language opcode
Opcode
In computer science engineering, an opcode is the portion of a machine language instruction that specifies the operation to be performed. Their specification and format are laid out in the instruction set architecture of the processor in question...
. 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. OISCs have been recommended as aids in teaching computer architecture and have been used as computational models in structural computing research.
Machine architecture
In a Turing-complete modelTuring machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
, 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.
Currently known OISC can be roughly separated into three broad categories:
- Transport Triggered Architecture Machines;
- Bit Manipulating Machines;
- Arithmetic Based Turing-Complete Machines.
Transport Triggered Architecture (TTA) is a design in which computation is a side effect of data transport. Usually some memory registers (triggering ports) within common address space, perform an assigned operation when the instruction references them. For example, in an OISC utilizing a single memory-to-memory copy instruction, this is done by triggering ports performing arithmetic and instruction pointer jumps when writing into them.
Bit Manipulating Machines is the simplest class. A bit copying machine, called BitBitJump, copies one bit in memory and passes the execution unconditionally to the address specified by one of the operands of the instruction. This process turns out to be capable of universal computation (i.e. being able to execute any algorithm and to interpret any other universal machine) because copying bits can conditionally modify the code ahead to be executed. Another machine, called the Toga computer, inverts a bit and passes the execution conditionally depending on the result of inversion. Yet another bit operating machine, similar to BitBitJump, copies several bits at the same time. The problem of computational universality is solved in this case by keeping predefined jump tables in the memory.
Arithmetic based Turing-complete Machines use an arithmetic operation and a conditional jump. Unlike the two previous classes which are universal computers, this class is universal and Turing-complete in its abstract representation. The instruction operates on integers which may also be addresses in memory. Currently there are several known OISCs of this class, based on different arithmetic operations: addition – Addleq, decrement – DJN, increment – P1eq, and subtraction – Subleq. The latter is the oldest, the most popular and, arguably, the most efficient.
Instruction types
Common choices for the single instruction are:- Subtract and branch if less than or equal to zero
- Subtract and branch if negative
- Reverse subtract and skip if borrow
- Move (used as part of a transport triggered architecture)
Only one of these instructions is used in a given implementation. Hence, there is no need for an opcode to identify which instruction to execute; 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, the SUBLEQ language, etc.). Each of the above instructions can be used to construct a Turing-complete OISC.
This article presents only subtraction-based instructions among those that are not transport triggered. However it is possible to build Turing complete machine using an instruction based on other arithmetic operations, e.g., addition. For example, one variation known as DLN (Decrement and jump if not zero) has only two operands and uses decrement as the base operation. For more information see Subleq derivative languages.
Subtract and branch if less than or equal to zero
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).Pseudocode
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
:
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 internal accumulator
Accumulator (computing)
In a computer's central processing unit , an accumulator is a register in which intermediate arithmetic and logic results are stored. Without a register like an accumulator, it would be necessary to write the result of each calculation to main memory, perhaps only to be read right back again for...
, 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:
subleq2 a, b ; Mem[a] = Mem[a] - ACCUM
; ACCUM = Mem[a]
; if (Mem[a] ≤ 0) goto b
Although this uses only two (instead of three) operands per instruction, correspondingly more instructions are then needed to effect various logical operations.
Synthesized instructions
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, Zsubleq 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, L1subleq Z, Z, OUT
L1: subleq Z, Z
subleq Z, b, c
OUT: ...
Subleq2 can also be used to synthesize higher-order instructions, although it generally requires more operations for a given task. For example no fewer than 10 subleq2 instructions are required to flip all the bits in a given byte:
NOT a subleq2 tmp ; tmp = 0 (tmp = temporary register)
subleq2 tmp
subleq2 minus_one ; acc = -1
subleq2 a ; a' = a + 1
subleq2 Z ; Z = - a - 1
subleq2 tmp ; tmp = a + 1
subleq2 a ; a' = 0
subleq2 tmp ; load tmp into acc
subleq2 a ; a' = - a - 1 ( = ~a )
subleq2 Z ; set Z back to 0
Emulation
The following program (written in pseudocodePseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
) 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 that memory[] is 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-interpreter
Self-interpreter
A self-interpreter, or metainterpreter, is a programming language interpreter written in the language it interprets. An example would be a BASIC interpreter written in BASIC...
s, which may use self-modifying code
Self-modifying code
In computer science, self-modifying code is code that alters its own instructions while it is executing - usually to reduce the instruction path length and improve performance or simply to reduce otherwise repetitively similar code, thus simplifying maintenance...
as allowed by the nature of the subleq instruction) can be found in the external links below.
Compilation
There is a compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
called Higher Subleq written by Oleg Mazonka that compiles a simplified C program into subleq code.
Subtract and branch if negative
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.
Synthesized instructions
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 must be maintained as 0.
Reverse subtract and skip if borrow
In a Reverse Subtract and Skip if Borrow (RSSB) instruction, the accumulatorAccumulator (computing)
In a computer's central processing unit , an accumulator is a register in which intermediate arithmetic and logic results are stored. Without a register like an accumulator, it would be necessary to write the result of each calculation to main memory, perhaps only to be read right back again for...
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
Program counter
The program counter , commonly called the instruction pointer in Intel x86 microprocessors, and sometimes called the instruction address register, or just part of the instruction sequencer in some computers, is a processor register that indicates where the computer is in its instruction sequence...
is mapped to memory location 0. The accumulator is mapped to memory location 1.
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
Transport triggered architecture
A transport triggered architecture uses only the move instruction, hence it was originally called a "move machine". This instruction moves the contents of one memory location to another memory location:move a to b ; Mem[b] := Mem[a]
sometimes written as:
a -> b ; Mem[b] := Mem[a]
Arithmetic is performed using a memory-mapped arithmetic logic unit
Arithmetic logic unit
In computing, an arithmetic logic unit is a digital circuit that performs arithmetic and logical operations.The ALU is a fundamental building block of the central processing unit of a computer, and even the simplest microprocessors contain one for purposes such as maintaining timers...
and jumps are performed using a memory-mapped program counter
Program counter
The program counter , commonly called the instruction pointer in Intel x86 microprocessors, and sometimes called the instruction address register, or just part of the instruction sequencer in some computers, is a processor register that indicates where the computer is in its instruction sequence...
.
A commercial transport triggered architecture microcontroller has been produced called MAXQ, which hides the apparent inconvenience of an OISC by using a "transfer map" that represents all possible destinations for the move instructions.
See also
- Turing tarpitTuring tarpitA Turing tarpit is any programming language or computer interface that allows for a great deal of flexibility in function but is difficult to learn and use because it offers little or no support for common tasks...
- Complex instruction set computerComplex instruction set computerA complex instruction set computer , is a computer where single instructions can execute several low-level operations and/or are capable of multi-step operations or addressing modes within single instructions...
(CISC) - Reduced instruction set computerReduced instruction set computerReduced instruction set computing, or RISC , is a CPU design strategy based on the insight that simplified instructions can provide higher performance if this simplicity enables much faster execution of each instruction. A computer based on this strategy is a reduced instruction set computer...
(RISC) - Minimal instruction set computerMinimal instruction set computerMinimal Instruction Set Computer is a processor architecture with a very small number of basic operations and corresponding opcodes. Such instruction sets are commonly stack based rather than register based to reduce the size of operand specifiers. Such a stack machine architecture is inherently...
(MISC) - Zero instruction set computerZero Instruction Set ComputerIn computer science, ZISC stands for Zero Instruction Set Computer, which refers to a chip technology based on pure pattern matching and absence of instructions in the classical sense...
(ZISC) - No instruction set computer (NISC)
External links
- Subleq on the esoteric programming languages wiki – Interpreters, compilers, examples and derivative languages
- Laboratory subleq computer – FPGA implementation using VHDL
- The Retrocomputing Museum – SBN emulator and sample programs
- Laboratory SBN computer – Implemented with 7400 series7400 seriesThe 7400 series of transistor-transistor logic integrated circuits are historically important as the first widespread family of TTL integrated circuit logic. It was used to build the mini and mainframe computers of the 1960s and 1970s...
integrated circuits - RSSB on the esoteric programming languages wiki – Interpreters and examples
- Dr. Dobb's 32-bit OISC implemention – Transport triggered architecture on an FPGA using VerilogVerilogIn the semiconductor and electronic design industry, Verilog is a hardware description language used to model electronic systems. Verilog HDL, not to be confused with VHDL , is most commonly used in the design, verification, and implementation of digital logic chips at the register-transfer level...
- Introduction to the MAXQ Architecture – Includes transfer map diagram