One-instruction set computer

Uses your system voice; voice and rate in settings.

Snapshot

≈ 9 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

A one-instruction set computer (OISC), sometimes referred to as 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 arbitrarily many 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. The first carbon nanotube computer is a 1-bit one-instruction set computer (and has only 178 transistors).

A one-instruction set computer (OISC), sometimes referred to as 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 arbitrarily many resources, an OISC is capable of being a universal computer in the same manner as traditional computers that have multiple instructions.

How it works

OISCs have been recommended as aids in teaching computer architecture and have been used as computational models in structural computing research. The first carbon nanotube computer is a 1-bit one-instruction set computer (and has only 178 transistors). Instruction 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.

Impact

The result is stored in both the accumulator and the memory location, and the second operand specifies the branch address: Instruction 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. subleq Z, Z, c Addition can be performed by repeated subtraction, with no conditional branching; e.g., the following instructions result in the content at location being added to the content at location : subleq a, Z subleq Z, b subleq Z, Z The first instruction subtracts the content at location from the content at location (which is 0) and stores the result (which is the negative of the content at ) in location .

The second instruction subtracts this result from , storing in this difference (which is now the sum of the contents originally at and ); the third instruction restores the value 0 to . A copy instruction can be implemented similarly; e.g., the following instructions result in the content at location getting replaced by the content at location , again assuming the content at location is maintained as 0: 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: 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: subleq2 tmp ; tmp = 0 (tmp = temporary register) subleq2 tmp subleq2 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 int 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): program_counter += 3 else: program_counter = c This program assumes that is indexed by nonnegative integers.

Consequently, for a instruction ( , , ), the program interprets , , or an executed branch to as a halting condition. Similar interpreters written in a -based language (i.e., self-interpreters, which may use self-modifying code as allowed by the nature of the instruction) can be found in the external links below. A general purpose SMP-capable 64-bit operating system called Dawn OS has been implemented in an emulated Subleq machine. The OS contains a C-like compiler.

Some memory areas in the virtual machine are used for peripherals like the keyboard, mouse, hard drives, network card, etc. Basic applications written for it include a media player, painting tool, document reader and scientific calculator. A 32-bit Subleq computer with a graphic display and a keyboard called Izhora has been constructed by Yoel Matveyev as a large cellular automaton pattern.

Instruction subneg a, b, c Mem[b] = Mem[b] - Mem[a] if (Mem[b] subneg POS, Z, c where and are locations previously set to contain 0 and a positive integer, respectively; Unconditional branching is assured only if initially contains 0 (or a value less than the integer stored in ). A follow-up instruction is required to clear after the branching, assuming that the content of must be maintained as 0.

Instruction subneg s, m, r, j (* subtrahend, minuend, result and jump addresses *) Mem[r] = Mem[m] - Mem[s] if (Mem[r] melzak X, Y, Z, n, y if (Mem[X] multiply: melzak P, ONE, S, stop ; Move 1 counter from P to S. If not possible, move to stop. melzak S, Q, ANS, multiply, multiply ; Move q counters from S to ANS. Move to the first instruction. stop: where the memory location P is p, Q is q, ONE is 1, ANS is initially 0 and at the end pq, and S is a large number.

He mentions that it can easily be shown using the elements of recursive functions that every number calculable on the arithmetic machine is computable. A proof of which was given by Lambek on an equivalent two instruction machine : X+ (increment X) and X− else T (decrement X if it not empty, else jump to T). Instruction rssb x ACCUM = Mem[x] - ACCUM Mem[x] = ACCUM if (ACCUM First, move z to the destination location x.

RSSB temp # Three instructions required to clear acc, temp [See Note 1] 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 [See Note 2] [Note 1] If the value stored at "temp" is initially a negative value and the instruction that executed right before the first "RSSB temp" in this routine borrowed, then four "RSSB temp" instructions will be required for the routine to work. [Note 2] If the value stored at "z" is initially a negative value then the final "RSSB x" will be skipped and thus the routine will not work.

Instruction movx a, b (also written a -> b) OP = GetOperation(Mem[b]) Mem[b] := OP(Mem[a], Mem[b]) The operation performed is defined by the destination memory cell. Some cells are specialized in addition, some other in multiplication, etc. So memory cells are not simple store but coupled with an arithmetic logic unit (ALU) setup to perform only one sort of operation with the current value of the cell.

Some of the cells are control flow instructions to alter the program execution with jumps, conditional execution, subroutines, if-then-else, for-loop, etc... 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.

Instruction cryptoleq a, b, c Mem[b] = O 1 (Mem[a], Mem[b]) if O 2 (Mem[b]) ≤ 0 IP = c else IP = IP + 3 where a, b and c are addressed by the instruction pointer, IP, with the value of IP addressing a, IP + 1 point to b and IP + 2 to c. In Cryptoleq operations and are defined as follows: \begin{array}{lcl} O_1(x,y) & = & x^{-1} y \,\bmod\, N^2 \end{array} \begin{array}{lcl} O_2(x) & = & \left \lfloor \frac{x-1}{N} \right \rfloor \end{array} The main difference with Subleq is that in Subleq, simply subtracts from and equals to .

Cryptoleq is also homomorphic to Subleq, modular inversion and multiplication is homomorphic to subtraction and the operation of corresponds the Subleq test if the values were unencrypted. A program written in Subleq can run on a Cryptoleq machine, meaning backwards compatibility. However, Cryptoleq implements fully homomorphic calculations and is capable of multiplications.

Multiplication on an encrypted domain is assisted by a unique function G that is assumed to be difficult to reverse engineer and allows re-encryption of a value based on the operation: G(x,y) = \begin{cases} \tilde{0}, & \text{if }O_2(\bar{x})\text{ }\leq 0 \\ \tilde{y}, & \text{otherwise} \end{cases} where \tilde{y} is the re-encrypted value of and \tilde{0} is encrypted zero. is the encrypted value of a variable, let it be , and \bar{x} equals .

The multiplication algorithm is based on addition and subtraction, uses the function G and does not have conditional jumps nor branches. Cryptoleq encryption is based on Paillier cryptosystem. Dr.

Dobb's 32-bit OISC implementation – transport triggered architecture (TTA) on an FPGA using Verilog Introduction to the MAXQ Architecture – includes transfer map diagram OISC-Emulator – graphical version TrapCC (recent Intel x86 MMUs are actually Turing-complete OISCs.) Izhora – Yoel Matveyev's Subleq computer built as a cellular automation SBN simulator – simulator and design inspired by CARDboard Illustrative Aid to Computation One-bit Computing at 60 Hertz – intermediate between a computer and a state machine The NOR Machine info on building a CPU with only one Instruction SUBLEQ eFORTH A complete Forth interpreter running on the SUBLEQ OISC.

Cryptoleq Cryptoleq resources repository CAAMP Computer Architecture A Minimalist Perspective SICO – Single Instruction COmputer: a variant of SUBLEQ using unsigned integers

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378622205 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

17 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.