by Marc Scibetta 20/02/2010
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
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 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 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.
Figure 1: Schematic hardware of the TOGA.
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);
}
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.
| symbol | function |
|---|---|
| - | 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,';'};
To translate assembler code to mnemonic list the following procedure should be followed.
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 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);
}
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.