The TOGA computer

by Marc Scibetta 20/02/2010


Table of content

Abstract

An original computer called TOGA is developed. The TOGA is 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. It uses two operands a memory address where a data of one bite is stored and program address. The size of an instruction is therefore the sum of the data space size and the program space size. Although a unique instruction is used, the language form by this instruction is demonstrated to be Turing complete, i.e. it has the ability to solve any arbitrary computable function. The architecture of the TOGA is extremely simple and can be implemented in hardware with a minimum of transistor. It can also be easily emulated in software.

Keywords RISC, OISC, URISC, TOGA, Turing complete

Introduction

The Reduced Instruction Set Computer (RISC) is implemented in many current microprocessors and microcontrollers. It has demonstrated its superiority over Complex Instruction Set Computer (CISC) in many applications. The main advantages are a faster instruction decoding, reduced complexity and better use of pipelining. The size of an instruction depends on the number of available instruction and operand size. Depending on the computer architecture, instruction size can be fixed or variable. Examples of RISC with limited instruction set are the MuP21 and the PIC10F200. The MuP21 has only 25 instructions and each instruction is 20 bit long. The PIC10F200 has 33 instructions and instruction length of 12 bit.

Esoteric computers concept that use one instruction are called the One Instruction Set Computer (OISC). The usual instruction is subleq(a,b,c). The instruction subtracts a from b, stores the result in b, and then transfers control to the address in c if the b was less or equal to a. The size of the instruction is equal to sum of the three arguments size (twice the data space size and once the program space size).

In this document an original and esoteric OISC computer called TOGA is developed. The TOGA concept developed here is purely academic and might have no practical use because many instructions are needed to do simple operation. However, the TOGA has a very simple architecture and the number of transistor to make a TOGA is extremely limited. Therefore, its performance relative to the number of transistor might still be interesting. For example a huge number of TOGA could easily be integrated in a single chip and massive parallelization could make this concept attractive.

The TOGA concept

The TOGA computer is a minimalist and esoteric computer. It uses two operands a memory address where a data of one bite is stored and program address. The size of an instruction is therefore the sum of the data space size and the program space size. Although a unique instruction is used, the language form by this instruction is demonstrated to be Turing complete, i.e. it has the ability to solve any arbitrary computable function.

The data address size and program address size can be selected arbitrarily and should be adjusted to the available memory. The size of a word in the data memory is 1 bit. The computer could be Harvard or Von Newman architecture depending on the hardware implementation.

The TOGA illustrated here use the Harvard architecture. It has a 10 bit data address size and 12 bit program address size that can address 1024 bit of data and 4096 instructions. Generalization to larger or smaller address or program size or to Von Newman architecture is straightforward.

The TOGA has one register. This register is a 12 bit program counter register (pc) allowing to address the program memory (pm).

Additional special register mapped in the data space may be needed to implement additional hardware features such as timer, interrupt, general purpose IO, computed goto, indirect addressing…

The unique instruction is TOGA(a,b). It stand for TOGle a And branch to b if result of the togle operation is true (1). It translate into


dm[a]=!dm[a];if(dm[a]) pc=b; else pc++;

At reset the pc register is reset. Any code is an arbitrary suite of TOGA(a,b).

The TOGA in hardware

The TOGA computer can be implemented in hardware using standard components. The schematic of the hardware is given in Figure 1. pc is a counter with reset and parallel initialization. pm is a RAM or ROM that contain the program and dm is a RAM that contain the data. The ROM ΅-instruction is a ROM that contains micro instructions alternatively a state machine could be used.

schematic hardware

Figure 1: Schematic hardware of the TOGA.

The TOGA emulated in software

The TOGA machine can easily be emulated in software. The following c++ code will emulate the TOGA machine.


#define	PC_SIZE 12
#define	W_SIZE 10

typedef struct {unsigned int a,b;} Instruction;

int main(void){
   Instruction  pm[1<< PC_SIZE]={{0,0},{1,0},{1,0}};
   bool         dm [1<< W_SIZE];
   unsigned int pc=0;

   for(;;){
      pc&=(1<< PC_SIZE)-1;
      pm[pc].a&=(1<< W_SIZE)-1;
      pm[pc].b&=(1<< PC_SIZE)-1;
      dm[pm[pc].a]=!dm[pm[pc].a];
      if(dm[pm[pc].a]) pc=pm[pc].b; else pc++;
   }
   return(0);
}

The TOGA assembler language

To transform algorithm into mnemonic code, the following assembler language is introduced. The assembler code can easily be translated into mnemonic code and can be more easily interpreted than a list of mnemonic. The syntactic definition of assembler language is based on the ISO/IEC 14997 EBNF metalanguage and the separators used are explained in Table 3.

symbolfunction
-except
,concatenate
|or definition separator
=defining
;definition terminator
' ... 'atomic quote
? ... ?special sequence
( ... )group
[ ... ]optional
{ ... }repeat sequence

Table 3: Interpretation of the symbol used in the EBNF metalanguage.


tab                 = ? ISO 6429 character Horizontal Tabulation ? ;
new line            = ? ISO 6429 character Line Feed ?;
letter              = ’a’ | ’b’ | ’c’ | ’d’ | ’e’ | ’f’ | ’g’ | ’h’ | ’i’ | ’j’ | ’k’ | ’l’ | ’m’ | ’n’ | ’o’ | ’p’ | ’q’ | ’r’ | ’s’ | ’t’ | ’u’ | ’v’ | ’w’ | ’x’ | ’y’ | ’z’ | ’A’ | ’B’ | ’C’ | ’D’ | ’E’ | ’F’ | ’G’ | ’H’ | ’I’ | ’J’ | ’K’ | ’L’ | ’M’ | ’N’ | ’O’ | ’P’ | ’Q’ | ’R’ | ’S’ | ’T’ | ’U’ | ’V’ | ’W’ | ’X’ | ’Y’ | ’Z’;
digit               = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';
other char          = ' ' | '!' | '"' | '#' | '$' | '%' | '&' | ''' | '(' | ')' | '*' | '+' | ',' | '-' | '.' | '/' | ':' | ';' | '<' | '=' | '>' | '?' | '@' | '[' | '\' | ']' | '^' | '_' | '`' | '{' | '|' | '}' | '~';
gap                 = tab | new line | ' ';
comment 1           = '/*',{tab | new line | letter | digit | other char }-'*/','*/';
comment 2           = '//', {tab | letter | digit | other char }, new line;
text                = { tab | new line | letter | digit | other char };
code                = (text – (comment 1 | comment 2))-gap;
mnemonics           = 'TOGA';
identifier          = letter | digit | '_' ,{letter | digit | '_'};
instruction         = mnemonics,'(';,identifier,',',identifier,')' | identifier, [instructions] ;
instructions        = '(',instruction,{',',instruction},')';
label	instruction = [identifier, ':'], [instruction];
identifiers         = '(',identifier,{',',identifier},')';
macro               = identifier,[identifiers] '={', {label instruction, ';'}, '}';
code                = {macro, ';'},{label instruction,';'};

Compilation of assembler code to mnemonic list

To translate assembler code to mnemonic list the following procedure should be followed.

  1. remove comment
  2. remove gap
  3. replace all macro by their definition. Label defined inside a macro is local and needs to be renamed using a unique name.
  4. replace label by the mnemonic value according to program line

Turing completeness of the TOGA instruction set

To demonstrate that the TOGA instruction set is Turing complete, it is sufficient to demonstrate that one Turing complete language can be emulated by TOGA instructions. The selected Turing complete language is the 4 instructions SCAB Computer. The following TOGA assembler code demonstrates that the SCAB Computer can be emulated with TOGA instructions and therefore that TOGA is a Turing complete language.


clr(x)={label: TOGA(x,label);};             //if x is false the instruction is performed twice is else the instruction is perform once
set(x) = {TOGA(x,end);TOGA(x,end);end:};    //if x is false the first and second instruction are performed else only the first instruction is performed
goto(label) = {TOGA(tmp,label);TOGA(tmp,label);};   //unconditional branch to label
goto(label,x) = {TOGA(x,next);next: TOGA(x,label);};   //conditional branch to label if x is true without changing the value in x;
move_x_to_y(x,y)={goto(label,x);clr(y);goto(end);label: set(y);end:} //copy x into y without changing the value in x

Indirect addressing and computed goto

Indirect addressing and computed goto are not necessary to have a Turing complete machine. However it allows to reduce significantly code size and to increase efficiency. In a Von Newman architecture indirect addressing and computed goto can be achieved through self modifying code. The principle is to modify some code to allow addressing some data or to branch to a program line than the modified code is executed.

To achieve indirect addressing and computed goto in a TOGA Harvard architecture, the hardware need to be modified. The TOGA instruction does not need to be modified. Special data address (ID) and program address (ID) can be defined. When those addresses are used in a TOGA instruction, the actual address are the one stored in special registers IND and INP that are mapped at the top of data memory.

The implementation of indirect addressing is illustrated with 10 bit data address size and 12 bit program address size. Data located at the top of the data memory is a mapping of special registers IND and INP. Additional special register mapped in the data space may be needed to implement additional hardware features such as timer, interrupt, general purpose IO…


#define	PC_SIZE 12
#define	W_SIZE 10
#define	ID ((1<<W_SIZE)-1)
#define	IP ((1<<PC_SIZE)-1)
typedef struct {unsigned int a,b;} Instruction;

int main(void){
   Instruction  pm[1<< PC_SIZE]={{W_SIZE+PC_SIZE,0},{W_SIZE+PC_SIZE+1,0},{W_SIZE+PC_SIZE+1,0}};
   bool         dm [1<< W_SIZE];
   unsigned int pc=0,a,b,i;

   for(;;){
      pc&=(1<< PC_SIZE)-1;
      pm[pc].a&=(1<< W_SIZE)-1;
      pm[pc].b&=(1<< PC_SIZE)-1;
      if(pm[pc].a==ID) {
         for(i=0,a=0;i< W_SIZE;i++){
            a+=dm[i]<< i;
         }
      }
      else a=pm[pc].a;
      if(pm[pc].b==IP) {
         for(i=0,b=0;i< PC_SIZE;i++){
            b+=dm[W_SIZE+i]<<i;
         }
      }
      else b=pm[pc].b;

      dm[a]=!dm[a];
      if(dm[a]) pc=b; else pc++;
   }
   return(0);
}

Conclusion

The TOGA is an esoteric computer concept. The TOGA is a one instruction set computer (OISC). It uses two operands a memory address where a data of one bite is stored and program adress. The size of an instruction is therefore the sum of the data space size and the program space size. Although a unique instruction is used, the language form by this instruction is demonstrated to be Turing complete, i.e. it has the ability to solve any arbitrary computable function. The architecture of the TOGA is extremely simple and can be implemented in hardware with a minimum of transistor. It can also be easily emulated in software.


Top of page