Tri is my name for a full trinary computing environment, for lack of a better term. Essentially it consists of a number of subcomponents that would together build up to run a simple shell on an FPGA softcore, including compiler and operating system. In this post, I’m going to give some background information about trinary computing and a brief overview of the instruction set architecture of the system, arguably the most central part of the Tri ‘project’.

What is trinary?

Trinary is an alternative base for computing. Practically all computers use binary, meaning that all data is represented as strings of zeroes and ones. Trinary adds a third option, -1, often denoted as i, so 10i is 26. To be pedantic, this is called balanced trinary, another possibility is using unbalanced ternary and switching -1 for 2. Ternary is another word for trinary, maybe more common in academic contexts.

Why trinary?

Mostly out of personal interest, though there seem to be some technical advantages as well. I don’t know much about fotonics, but there are some indications that optical computing naturally lends itself to trinary, as might superconductive computing. There are also more theoretical arguments for why 3 is a more economical base than 2.

triscv

triscv is the name of instruction set architecture, ISA, and it is a specification of how each instruction maps to individual trits (“trinary bits”, i.e. 10i). For the most part I’ve followed riscv, I have a small set of core instructions and some extensions. I do have a couple more esoteric features, namely

1. Arbitrary logic operations.
2. Address space tagging.
3. Extended lr/sc (or, conversely, limited transactional memory)

Arbitrary logic operations

Arbitrary logic operations refers to the fact that all logical operations can be though of as mappings, and we can code those mappings into trits. For instance, imagine the string 1i0. We can split this string into three trits, with the first trit tells us what to map i to, the second what to map 0 to, and the third what to map 1 to. So if I give you the string 1i0, and I give you 0, you can look at the middle trit and give me back i. As an example, the identity operation (i.e. “do nothing”) can be written down as i01.

1i0 can be read as:
You give me i, I give you 1
You give me 0, I give you i
You give me 1, I give you 0

This can be extended to operations with two inputs, we just need a string of length nine. Now the first input tells us which group of three trits to look at, and the second input tells us which trit in this group to look at. This string can be embedded in an instruction fairly easily, and the hardware implementation is fairly cheap at just a couple muxes. This gives us a huge number of possible logical operations, 19683 in total, that can be experimented with. Binary logical operations are more limited in number and there’s a known “good enough” subset of the most commonly used ones, but I’m not aware of any similar consensus for trinary logical operations, so I thought it better to keep all options open. There may also be some usecases for compressing two or more “traditional” binary operations into a single “custom” operation, though how useful or significant this actually is remains to be seen.

Address space tagging

Loosely based off of the CODOMS architecture. I’m interested in using migrating threads as the primary inter-process communication (IPC) method in the operating system, and address space tagging is one way to speed up thread migration.

Thread migration is an alternative form of IPC, where instead of sharing memory or sending messages to eachother, processes communicate by temporarily moving threads between eachother, taking some amount of data with them in the process. This method has some interesting properties for scheduling and can be very fast, even on conventional hardware. I actually wrote my Bachelor’s Thesis on this topic, but it’s unfortunately in Finnish.

Address space tagging is essentially letting multiple processes share a common virtual memory address space, with each process only being able to access memory regions that have the same tag as the process itself. Additionally, there is typically a separate instruction that jumps between these tagged processes, allowing the thread migration to happen in userspace, completely without intervention from the kernel. This could make inter-process communication almost as fast as regular procedure calls, allowing for a safe and fast operating system.

I have written an experimental kernel, targeting riscv, that implements thread migration. It’s still rather crude, as are most of my things, but it can boot on real hardware and does run some simple test programs. I’m envisioning that the trinary OS would fairly closely match this kernel.

Extended lr/sc

This one I’m so far the least sure about, but effectively instead of a single ‘reserved’ address, there’s an architecture specific one. Currently, I’m imagining that at least three words of data should be reserved, which would be enough to implement double compare-and-swap, which in turn could be used to implement a (reasonably) efficient hybrid transactional memory. Extra words effectively means more assembly instructions, which could incur overheads in some lock-free algorithms, but a (reasonably) fast transactional memory could be better for some more complex algorithms.

The hardware implementation is still a bit unclear, and atomic operations are notoriously difficult, but there is some pre-existing literature for similar experimental systems using a small data cache that gets activated when a thread enters a critical region and that then ensures atomicity. Dunno yet.

Final words

I haven’t yet published the actual spec (or its working drafts, whatever you want to call them) anywhere, though I intend to do so reasonably soon. It is part of a repository that also implements the assembler, disassembler and simulator, so when I do publish the spec, there should also be tools to help get familiar with it.