One instruction set computer

From Wikipedia, the free encyclopedia

Computer science portal

A One Instruction Set Computer (OISC) is an abstract machine that uses only one instruction (obviating the need for a machine language opcode). ^{[1] [2] [3]} OISC is sometimes called an Ultimate Reduced Instruction Set Computer (URISC), ^[1][2]. Since OISC is a subclass of RISK, which is in turn a subclass of microprocessors, it is required to be of Linear bounded automaton computational class. Some of OISC languages are easily extended in abstraction to be Turing-complete. These universal computers have been recommended as aids in teaching computer architecture ^[1][2] and have been used as computational models in structural computing research^[3].

[edit] Machine Architecture

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.

[edit] Instruction Types

Common choices for the single instruction are:

• Subtract and branch if less than or equal to zero
• Subtract and branch if negative
• Move bit to bit and jump
• Reverse subtract and skip if borrow
• Triggered Move

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.). These instructions can be used to construct a Turing-complete OISC, with the exception of "Move bit to bit and jump". This one requires access to the bits inside memory cells, and since the memory cells are bit addresses, the OISC is not able to operate on unlimited memory.

[edit] 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:

    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.

[edit] 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, 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: ...

[edit] Emulation

The following C language program emulates the execution of a subleq based OISC:

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] Compilation

There is a compiler called Higher Subleq that compiles a program written in a simplified C language into subleq code. ^[4]

[edit] 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.

[edit] 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 is supposed to be maintained as 0.

[edit] Move bit to bit and jump

The move bit to bit and jump (BitBitJump) instruction is possibly the simplest OISC language. It is similar to a Subtract-and-branch construction except that operands work in the bit address space and the meaning of the instruction is to copy the bit addressed by a into the bit addressed by b and jump the execution control to the address c. Computations are possible due to the fact that the code is able to modify itself.^[5] An assembler and emulator are available for BitBitJump.^[6] BitBitJump belongs to Linear bounded automaton computational class.

[edit] Reverse subtract and skip if borrow

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.

[edit] 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

[edit] Triggered Move

This section may require cleanup to meet Wikipedia's quality standards. Please improve this section if you can. (September 2009)

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, The Ultimate RISC, published as ACM SIGARCH Computer Architecture News 16, 3 (June 1988) 48-55 describing his architecture and how it worked.

The only commercially available microcontroller built upon a transfer-triggered architecture is MAXQ from Maxim Integrated Products.^[7][8] 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.^[9]

[edit] References

1. ^ ^{a b c} Univ. of Waterloo URISC: F. Mavaddat and B. Parhami, URISC: The Ultimate Reduced Instruction Set Computer, Int'l J. Electrical Engineering Education, Vol. 25, No. 4, pp. 327-334, October 1988. This paper considers "a machine with a single 3-address instruction as the ultimate in RISC design (URISC)". Without giving a name to the instruction, it describes an SBN OISC and its associated assembly language, emphasising that this is a universal (i.e., Turing-complete) machine whose simplicity recommends it in the classroom.
2. ^ ^{a b c d} Computer Architecture: A Minimalist Perspective, The Springer International Series in Engineering and Computer Science , Vol. 730, Gilreath, William F., Laplante, Phillip A., 2003, ISBN 978-1-4020-7416-5. Intended for researchers, computer system engineers, computational theorists and students, this book provides an in-depth examination of various OISCs, including SBN and (tiggered) MOVE. It attributes SBN to W. L. van der Poel (1956).
3. ^ ^{a b c} A Grand Unified Theory for Structural Computing, by Peter J Nürnberg, Uffe K. Wiil, and David L. Hicks, pp 1-16 in the collected papers Metainformatics, International Symposium, MIS 2003, Graz, Austria, September 17-20, 2003, Revised Papers, David L. Hicks (Ed.). Lecture Notes in Computer Science 2003, Springer 2004, ISBN 3-540-22010-0. This research paper focusses entirely on a SUBLEQ OISC and its associated assembly language, using the name SUBLEQ for "both the instruction and any language based upon it".
4. ^ Higher Subleq compiler
5. ^ Mazonka, Oleg (2009), Bit Copying - The Ultimate Computational Simplicity, Cornell University Library, pp. 1-16, arXiv:0907.2173v1, http://arxiv.org/pdf/0907.2173v1 
6. ^ BitBitJump assembler and emulator
7. ^ MAXQ RISC Microcontrollers
8. ^ Introduction to the MAXQ Architecture
9. ^ MAXQ transfer map

[edit] External links

This section may require cleanup to meet Wikipedia's quality standards. Please improve this section if you can. (September 2009)

• The Retrocomputing Museum
• OISC Implementation with subleq
• The Linux Coffee Howto describes a use for an embedded OISC
• Mark II OISC Self-Interpreter Possibly the first-ever OISC self-interpreter.
• Redcode interpreter for RSSB
• The Ultimate RISC One Instruction Computing
• SBN Computer
• SUBLEQ compiler and emulator
• Subleq on the Esoteric Programming Language Wiki
• RSSB on the Esoteric Programming Language Wiki
• Computer Architecture: A Minimalist Perspective (CAAMP) A computer architecture book that focuses and examines the one instruction set computer architecture in depth.
• C Compiler into Subleq on esolangs