The SCAB computer

by Marc Scibetta update 20/2/2009, Previous version

Table of content

• Abstract
• Introduction
• The SCAB concept
• The SCAB in hardware
• The SCAB emulated in software
• The SCAB assembler language
• Compilation of assembler code to mnemonic list
• Turing completeness of the SCAB instruction set
• Indirect addressing and computed goto
• Conclusion

Abstract

An original computer called SCAB is developed. The SCAB is a Reduced Instruction Set Computer (RISC). It has four instructions and does not use any operand which means that only 2 bits per instruction is needed to code all instructions. Although the instruction set and instruction size is small, the language form by its instruction set is demonstrated to be Turing complete, i.e. it has the ability to solve any arbitrary computable function. The architecture of the SCAB is extremely simple and can be implemented in hardware with a minimum of transistor. It can also be easily emulated in software.

Keywords RISC, SCAB, 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 of 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 exist with even less instructions. The minimum is only one instruction called the One Instruction Set Computer (OISC). The 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 computer called SCAB is developed that has a small instruction set and instruction size. The SCAB concept developed here is purely academic and might have no practical use because many instructions are needed to do simple operation. However, the SCAB has a very simple architecture and the number of transistor to make a SCAB is extremely limited. Therefore, its performance relative to the number of transistor might still be interesting. For example a huge number of SCAB could easily be integrated in a single chip and massive parallelization could make this concept attractive.

The SCAB concept

The SCAB computer is a minimalist and esoteric computer. It has four instructions and does not use any operand which means that only 2 bits per instruction is needed to code all instructions. Although the instruction set and instruction size is small, the language form by its instruction set 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 SCAB 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 SCAB has two registers in addition to the data address space. The first register is a 10 bit working register (w) allowing to address the data memory (dm) and the second is a 12 bit program counter register (pc) allowing to address the program memory (pm).

Data located at the top of the data memory is a mapping of special registers. The top of the data memory contains the 2 registers documented in Table 1. 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…

Table 1: Register mapped at the top of the data memory.

The data memory is a vector of bit named dm. dm[0] contains the least significant bit of wl and dm[9] contains the most significant bit of wl.

The four instructions are documented in Table 2. The set and clear instructions set and clear respectively the bit in the data memory at location w then increment w and pc. The arm instruction copy wl in the register w, the register wl is cleared and pc is incremented. The branch instruction increment pc if the bit in the data memory at location w is set otherwise the register pcl is copied in pc.

At reset the pc register is reset. Any code is an arbitrary suite of mnemonic S, C, A and B.

Table 2: Instruction list.

The SCAB in hardware

The SCAB computer can be implemented in hardware using standard components. The schematic of the hardware is given in Figure 1. w and pc are counter with reset and parallel initialization. wl and pcl are standard register. decode is a ROM that contain micro instructions.

Figure 1: Schematic hardware of the SCAB.

The SCAB emulated in software

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

#define	PC_SIZE 12
#define	W_SIZE 10

typedef enum {S,C,A,B} Instruction;

int main(void){
   Instruction  pm[1<< PC_SIZE]={A,A,C,S,C,S,A,C,C,C,C,C,C,C,C,C,C,C,C,A,A,B};
   bool         dm [1<< W_SIZE];
   unsigned int w,pc=0,i;

   for(;;){
      pc&=(1<< PC_SIZE)-1;
	  w&=(1<< W_SIZE)-1;
      switch(pm[pc]){
         case S: dm[w]=true;w++;pc++;break;
         case C: dm[w]=false;w++;pc++;break;
         case A: for(i=0,w=0;i< W_SIZE;i++){if(dm[i])w+=1<< i; dm[i]=false;}; pc++;break;
         case B: if(dm[w]) pc++;
                 else for(i=0,pc=0;i< PC_SIZE;i++) if(dm[W_SIZE+i]) pc+=1<< i;
      }
   }

   return(0);
}

The SCAB 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.

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           = ' " ', {'S' | 'C' | 'A' | 'B'}, ' " ';
identifier          = letter | digit | '_' ,{letter | digit | '_'};
instruction         = mnemonics | identifier, [instructions] | identifier, '+', identifier ;
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 addition of two mnemonic by a mnemonic representing the addition. E.g "CSS"+"CCS"="CSCS".
5. replace label by the mnemonic value according to program line
6. replace the remaining addition

Turing completeness of the SCAB instruction set

To demonstrate that the SCAB instruction set is Turing complete, it is sufficient to demonstrate that one Turing complete language can be emulated by SCAB instructions. The selected Turing complete language is the One Instruction Set Computer (OISC). The 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 following SCAB assembler code demonstrates that the subleq instruction can be emulated with SCAB instructions and therefore that SCAB is a Turing complete language.

pcl={"CSCS";};              //define pcl
wl(x) = {"AA";x;};          //macro to initialize wl to the literal value x
sto(y,x)={wl(x);"A";y;};    //store literal y at memory location x
clr(x)={sto("C",x);};       //clear bit at location x
set(x) ={sto("S",x);};      //set bit at location x
bra(label)={sto(label,pcl);"AAB"};                           //branch to label
bifc(label, x)={ sto(label,pcl);wl(x);"AB";};                //branch to label if bit at location x is clear
bifs(label, x)={bifc(end,x);bra(label);end:;};               //branch to label if bit at location x is set
cpy(x,y)={bifc(label,x);set(y);bra(end);label:clr(y);end:;}; //copy bit from location x to location y
not(x)= {bifc(label,x);clr(x);bra(end);label:set(x);end:;};  //negate 
subleq(a,b,c)={bifc(a0,a);bifs(c0,b);set(b);bra(c);c0:clr(b);bra(c);a0:bifc(b,c);}; //can be generalized to word larger than one bit

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 SCAB Harvard architecture, the hardware need to be modified. Four additional register wlatch, pclatch, wc, pcc are mapped in the data space. When the bit wlatch or pclatch are set, the content of wc or pcc is copied to wl or pcl respectively.

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. The top of the data memory contains the 6 registers documented in Table 4. Additional special register mapped in the data space may be needed to implement additional hardware features such as timer, interrupt, general purpose IO…

Table 4: Register mapped at the top of the data memory for indirect addressing and computed goto.

The list of Mnemonic is identical but when wlatch or pclatch are set, it triger the copy of wc and pcc in wl and pcl register (See Table 5).

Table 5: Instruction list taking into account indirect addressing and computed goto..

Similarly an interpreter can be constructed with the following c++ code.

#define PC_SIZE 12
#define W_SIZE 10
typedef enum {S,C,A,B} Instruction;
int main(void){
  Instruction  pm[1<< PC_SIZE]={A,A,C,S,C,S,A,C,C,C,C,C,C,C,C,C,C,C,C,A,A,B};
  bool         dm [1<< W_SIZE];
  unsigned int w,pc=0,i;
  for(;;) {
     pc&=(1<< PC_SIZE)-1;
     w&=(1<< W_SIZE)-1;
     switch(pm[pc]) {
        case S:
			if(w==W_SIZE+PC_SIZE){
				for(i=0;i< W_SIZE;i++) dm[i]=dm[i+W_SIZE+PC_SIZE+2];
			}
			if(w==W_SIZE+PC_SIZE+1){
				for(i=0;i< PC_SIZE;i++) dm[i+W_SIZE]=dm[i+2*W_SIZE+PC_SIZE+2];
			}
           dm[w]=true;
           w++;
           pc++;
           break;
        case C:
           dm[w]=false;
           w++;
           pc++;
           break;
        case A:
           for(i=0,w=0;i< W_SIZE;i++) {
              if(dm[i]) w+=1<< i;
              dm[i]=false;
           };
           pc++;
           break;
        case B:
           if(dm[w])
              pc++;
           else
              for(i=0,pc=0;i< PC_SIZE;i++)
                 if(dm[W_SIZE+i]) pc+=1<< i;
     }
  }
  return(0);
}

Conclusion

The SCAB is an esoteric computer concept. It has four instructions and does not use any operand which means that only 2 bits per instruction is needed to code all instructions. Although the instruction set is small, the language is Turing complete.