The Trillium Architecture

Part of http://www.cs.uiowa.edu/~jones/ternary/
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Abstract

The Trillium instruction set is designed for a small ternary computer with a 9-trit word and a 19,682 word address space. This architecture is comparable to some of the smaller 16-bit minicomputers of the 1960s and 1970s, and it might be suitable for a microcontroller or programmable interface processor in modern terms.

Warning: The material presented here is very preliminary. First posting on the web, Nov. 21, 2017.


Note, the first proposed Trillium architecture was a deliberate homage to the DEC PDP-11. An implementation would have been difficult to pipeline, so that version was abandoned at the end of 2017.


Data Representation

The basic 9-trit word has the following format:

080706 050403 020100
value

This value can be interpreted as an unsigned ternary value:

0000000003=00027 =010
2222222223=ZZZ27 =+19,68310

Alternatively, the value can be interpreted as a 3's-complement signed ternary value:

1111111123=DDE27 =–9,84110
2222222223=ZZZ27 =–110
0000000003=00027 =010
1111111113=DDD27 =+9,84110

In the event that balanced ternary is needed, to convert a value to from 3's complement form to balanced form, just add the bias, 1111111113 (DDD27 or +9,841) and reinterpret the trit values 0 as –, 1 as 0, and 2 as +. To convert balanced ternary to 3's complement, reverse the process.

One word may also be used to hold a 9-bit ternary coded binary (TCB) number. Each trit has a value of either 0 or 1, corresponding to the value of one binary bit. There are fast algorithms for conversion from TCB to ternary, so generally, conversion should be done early.

Instruction Format

One word can hold one machine instruction (or at least the first word of a multi-word instruction), formatted as follows:

080706 050403 020100
op r addr

The instruction word contains the following fields:

op
The opcode field, 3 trits specifying one of 27 basic instructions.

r
The register field. The majority of data manipulation instructions operate on the designated registerr, but some instructions use this field for other purposes.

addr
The address field. For most instructions, this specifies the memory address on which the instruction operates, but some instructions use it for other purposes such as holding small constants.

Assembly Format

In the Trillium assembly language, instructions are written as

label:  opcode  r,addr ; comment

Labels are always followed by a colon, and comments, if present, are always preceeded by a semicolon, as with the classic MACRO-11 assembly language for the PDP-11.

Addressing Modes

For instructions that use the addr field to address memory, this field is broken down as follows:

03020100
m x

The m field specifies the addressing mode. This, in turn, contols the interpretation of the x field, which may refer to an index register. The addressing modes specified by the m field are:

m = 22: Register mode, x
In register mode, the x field designates the register to be used as a second operand.

m = 21:

m = 20:

m = 12: Register indirect mode, *x
In register indirect mode, the x field designates the register that holds the memory address of the operand.

m = 11: Autoincrement mode, *x++
In autoincrement mode, the x field is used as in register indirect mode, but in addition, after use, it is incremented.

m = 10: Autodecrement mode, *--x
In autodecrement mode, the x field is used as in register indirect mode, but in addition, before use, it is decremented.

m = 02: Indexed mode, x->disp
In indexed mode, the x field specifies an index register. The displacement is taken from the next successive word after the instruction.

m = 01:
m = 00:

Addressing relative to the program counter

Because the program counter is part of the register set, autoincrement addressing using the program counter allows an immediate operand to be fetched from the instruction stream immediately after the instruction word. This mode should not be used with the store instruction.

Addressing relative to stack pointers

Because stack pointers are held in registers, autoincrement and autodecrement addressing can be used to push and pop operands on the stack.

Assembly Format

In the Trillium assembly language, the source and destination addressing modes are specified as follows:

label:  op    r5,r6     ; operate on r5 and r6 with register mode
        op    r1,*r2    ; operate on r1 and r2 with register indirect mode
        op    r3,*r4++  ; operate on r3 and r4 with autoincrement mode
        op    r7,*--r8  ; operate on r3 and r4 with autodecrement mode

Registers

There are 9 registers, of which 7 are the general-purpose operand registers r1 to r7.

   080706 050403 020100
t8 pc (r8)
t7 r7
t6 r6
t5 r5
t4 r4
t3 r3
t2 r2
t1 r1
t0 r0 (sp)

The program counter, pc or r8 always points to the next word in the instruction stream. Effectively, instruction fetches are done using autoincrement addressing relative to the program counter.

Most modern programming languages require the use of a stack; the designation of r0 as sp is therefore merely a suggestion. If it is used as a stack pointer and if push uses autoincrement addressing, the stack pointer always points to the first free word beyond the stack top. If push uses autodecrement addressing, it always points to the stack top.

The register tags t0 to t8 are only present on machines able to address more than 19,682 words of memory. These may be as simple as extra bits attached to the register when it is used for memory addressing, or as complex as segment identifiers when used with a memory management unit supporting segmenting.

Whatever their form, tags allow (at minimum) a separation of program and data space. Typically, the program counter will be tagged with the program segment while the stack pointer is tagged with the data segment. Other registers used for addressing will have values derived from either the program counter or stack pointer, and hence, will carry the appropriate tag.

Processor Status Word

080706 050403 020100
  cc

The processor status word is divided into several fields:

cc
The condition codes, giving information about the result of the most recent data manipulated by the processor. Arithmetic instructions all set the condition codes some of them also use them as an operand. Conditional instructions test the condition codes.

Condition Codes

020100
s v c

s — The sign trit.
The sign of the result of the most recent operation:
s = 0 — zero
s = 1 — positive
s = 2 — negative

v — The overflow bit.
Indicates whether the most recent operation produced a signed overflow.
v = 0 — no overflow (s is correct)
v = 1 — overflow (s is inverted)
v = 2 — ?

c — The carry trit.
The carry out of the adder for the most recent operation.
c = 0 — no carry
c = 1 — carry (also indicates unsigned overflow)
c = 2 — carry (relevant only after shift operations)

The condition codes correspond closely to the 4-bit condition codes used on the PDP-11 and copied by most more recent binary p rocessors. The s condition code encodes all useful values of the binary N and Z condition codes, while the v and c condition codes correspond to the V and C condition codes of the PDP-11.

Instructions

Store

080706 050403 020100
2 2 2 r addr
store r,addr
mode(addr) ← r

Stores the register into the addressed location, overwriting anything previously held there. Register-to-register stores do not copy the tag field along with, nor do they alter the condition codes.

Because the opcode is all twos, the program counter is register 9, and register mode addressing is mode 9, a word that is entirely 2's is a no-op. This may be of value when allowing for patching of code stored in single use PROM.

Examples

        store pc,pc     ; no-op
        store r1,*r2    ; save the r1 in the memory pointed to by r2
        store r1,*sp++  ; push r1 on an upward growing stack
        store r1,sp->x  ; save r1 x words deep in the stack

Because the program counter is a register, the store instruction can also serve as a branch instruction that does not change the current program segment:

        move    r5,pc   ; branch to the location pointed to by R5

Load

080706 050403 020100
2 2 1 r addr
load r,addr
r ← mode(addr); set cc

Loads the register from the addressed location, overwriting anything previously held there. Register-to-register loads copy the tag field along with the data, and they alter the condition codes to reflect the result as follows:

s reports the sign
v reset to 0
c reset to 0

Examples

        load  r1,r2     ; copy r2 to r1, along with its tag
        load  pc,r2     ; jump to the location pointed to by r2
        load  pc,*r2    ; indirect jump through the location pointed to by r2

Load Immediate

080706 050403 020100
2 2 0 r addr
loadi r,addr
r ← mode; set cc

Loads the register with the sign-extended 4-trit 3's complement value held in the address field, with no change to the tag. The condition codes are set to report on the loaded value:

s reports the sign
v reset to 0
c reset to 0

Examples

        loadi r1,2      ; set r1 to 2
        loadi r2,40     ; set r1 to 40 (the most positive 4-trit value)
        loadi r2,-40    ; set r1 to -40 (the most negative 4-trit value)

Assemblers should automatically convert loadi instructions with out-of-range operands to load instructions using autoincrement addressing on the program counter. So,

        loadi r2,41     ; set r1 to 41 (an out-of-range value)

should assemble as

        load  r2,*pc++  ; set r1 to the contents of the next word
        .word 41

====== frontier of update ======

Add

080706 050403 020100
0 1 0 a src dst
add src,dst
dstdst + src ; set cc

Adds the source operand to the destination operand, replacing the destination. The condition codes are set to report on the sum:

s reports the sign
v indicates overflow
c indicates the carry out of the adder

Examples

        add     =1,r1   ; increment r1
        add     r2,=5   ; set the condition codes according to r2 + 5
        add     r3,*r4  ; add r3 to the memory location pointed to by r4
        add-    *sp,r6  ; pop from an upward-growing stack and add to r6
        add+    *sp,r6  ; pop from a downward-growing stack and add to r6

Because the program counter is a register, the add instruction also serves as a pc-relative branch instruction. The assembler uses the dot (.) as the symbol for the current location, so subtracting this from dst, the destination address, we get the relative address suitable for use in position independent code:

        add     =dst-(.+1),pc

	add+    *pc,pc
	.word	dst-.

Subtract

              080706 050403 020100              
0 2 a src dst
sub src,dst
dstdst + (ZZZ27src) + 1 ; set cc

Subtracts the source operand from the destination operand, replacing the destination. The condition codes are set to report on the difference:

s reports the sign
v indicates overflow
c indicates the carry out of the adder
c = 0 — borrow
c = 1 — no borrow
c = 2 — never

Note the inversion of the c conditon code. This is because the Trillium uses 3's-complement arithmetic, where a – b is computed as a + (2222222223 – b) + 1. A carry out of this sum indicates that there was no borrow, that is, it indicates that a ≥ b as unsigned ternary numbers.

Examples

        sub     =1,r1   ; decrement r1
        sub     r2,=5   ; compare r2 with the constant 5
        sub     r3,*r4  ; subtract r3 from the memory location pointed to by r4
        sub-    *sp,r6  ; pop from an upward-growing stack and subtract from r6

Add With Carry

080706 050403 020100
? ? ? 1 src dst
addc src,dst
dstdst + src + c ; set cc

Adds the source operand to the destination operand, including the carry bit, replacing the destination. Unlike the regular add instruction, the only addressing mode supported for the source operand is register mode. The condition codes are set to report on the sum:

s reports the sign
v indicates overflow
c indicates the carry out of the adder

Examples

Add with carry allows high precision addition. Consider computing the 18-trit addition of r1-r2 to r3-r4, where the first register of each pair holds the least significant half:

        add     r1,r3   ; add less significant trits
        addc    r2,r4   ; add most significant trits

Consider adding the 27-trit value in r1-r3 to a 27-trit value in the memory location pointed to by r4, where the least significant word comes first in memory:

        add+    r1,*r4  ; add less significant trits
        addc+   r2,*r4  ; add middle trits
        addc    r3,*r4  ; add most significant trits
        sub     r4,=2   ; restore pointer

In the above, autoincrement addressing is used to access consecutive words of the operand in memory, and then the register is restored to its original value. After-the-fact restoration using an immediate subtract avoids the need to make a temporary copy of r4.

Subtract With Borrow

              080706 050403 020100              
? ? ? 2 src dst
subb src,dst
dstdst + (ZZZ27src) + c ; set cc

Subtracts the source operand from the destination operand, including the borrow information conveyed by the carry bit, replacing the destination. Unlike the regular subtract instruction, the only addressing mode supported for the source operand is register mode. The condition codes are set to report on the difference:

s reports the sign
v indicates overflow
c indicates the carry out of the adder
c = 0 — borrow
c = 1 — no borrow
c = 2 — never

Examples

Subtract with borrow allows high precision subtraction. Consider computing the 18-trit subtraction of r1-r2 from r3-r4, where the first register of each pair holds the least significant half:

        sub     r1,r3   ; subtract less significant trits
        subb    r2,r4   ; subtract most significant trits

Shift Left

080706 050403 020100
? ? ? 0 n dst
sl n,dst
dstdst <<3 n ; set cc

Shifts the destination operand left. A shift count of 00 is interpreted as meaning 9. Autoincrement and autodecrement modes are not applicable. The condition codes are set as follows:

s reports the sign of the result
v indicates overflow
c holds the last trit shifted out

In the absence of overflow, dst <<3 n = dst × 3n. In this context, overflow does not merely report that the sign of the result differs from the sign of the operand, but it also reports any loss of precision. So, if dst × 3n (computed with unlimited precision) has a sign different from dst << 3n (computed in a 9-trit word), the overflow bit will be set.

Examples

        sl      1,r1    ; multiply r1 by 3
        sl      2,*r2   ; multiply the memory location pointed to by r2 by 9
        sl      9,=0    ; set the condition codes to 000
        sl      9,=1    ; set the condition codes to 011
        sl      9,=2    ; set the condition codes to 012
        sl      8,=1    ; set the condition codes to 100
        sl      8,=2    ; set the condition codes to 210
        sl      8,=4    ; set the condition codes to 111
        sl      8,=5    ; set the condition codes to 211

Shift Right Unsigned

080706 050403 020100
? ? ? 1 n dst
sru n,dst
dstdst >>3 n ; set cc

Shifts the unsigned destination operand right. A shift count of 00 is interpreted as meaning 9. Autoincrement and autodecrement modes are not applicable. The condition codes are set as follows:

s reports the sign of the result
s = 0 — zero
s = 1 — positive
s = 2 — never
v were any nonzero trits shifted out
c holds the last trit shifted out

For unsigned right shifts, zeros are shifted in from the left, so the result is always positive or zero. In general, dst >>3 n = dst / 3n, with the unsigned result truncated toward zero. When the overflow bit is set, it indicates that the unsigned operand was not evenly divisible by the indicated power of three.

Shift Right Signed

080706 050403 020100
? ? ? 2 n dst
sru n,dst
dstdst >>3 n ; set cc

Shifts the unsigned destination operand right. A shift count of 00 is interpreted as meaning 9. Autoincrement and autodecrement modes are not applicable. The condition codes are set as follows:

s reports the sign of the result
v were any nonzero trits shifted out
c holds the last trit shifted out

For signed right shifts, the value shifted in from the left depends on the sign of the operand. Zeros are shifted in for positive operands, and twos are shifted in for negative operands. For example:

111111111 >>3 1 = 011111111 (+9841 >>3 1 = +3280)
111111112 >>3 1 = 211111111 (–9841 >>3 1 = –3281)

In general, dst >>3 n = dst / 3n, with the signed result rounded down so that the remainder is either zero or positive. When the overflow bit is set, it indicates that the unsigned operand was not evenly divisible by the indicated power of three.

Conditional Branches

The following branch instructions are named so that, following sub src,dst, which computes dst ← dst – src, the operators report on dst ? src, using the original value of src prior to the subtraction and using ? as a stand-in for a comparison operator.
beq – branch if equal
dst = src  —  s = 0

bne – branch if not equal
dst ≠ src  —  s ≠ 0

blts – branch if less than signed
dst < src  —  ((s = 2) & (v = 0)) | ((s = 1) & (v = 1))

bles – branch if less than or equal signed
dst ≤ src  —  ((s = 2) & (v = 0)) | ((s = 1) & (v = 1)) | (s = 0)

bges – branch if greater than or equal signed
dst ≥ src  —  ((s = 1) & (v = 0)) | ((s = 2) & (v = 1)) | (s = 0)

bgts – branch if greater than signed
dst > src  —  ((s = 1) & (v = 0)) | ((s = 2) & (v = 1))

bltu – branch if less than unsigned
dst < src  —  c = 0

bleu – branch if less than or equal unsigned
dst ≤ src  —  (c = 0) | (s = 0)

bgeu – branch if greater than or equal unsigned
dst ≥ src  —  (c ≠ 0)

bgtu – branch if greater than unsigned
dst > src  —  (c ≠ 0) & (s ≠ 0)

The following additional condition code tests are not typically used after comparisons:

bpos – branch if result positive
s = 1

bnpos – branch if result non-positive
s ≠ 1

bneg – branch if result negative
s = 2

bnpos – branch if result non-negative
s ≠ 2

bvr – branch if no overflow
v = 0

bvs – branch if overflow
s ≠ 0