Beyond 0 and 1: A mixed radix design and verification workflow for modern ternary computers

Abstract

For more than 80 years digital computers use the radix-2 or binary computer alphabet as their lowest symbolic and physical representation. This doctrine of computing is presumed in every modern computer. The radix economy theorem derives that radix-3 or ternary is however the optimal radix. Ternary is the first radix in the Multiple-Valued Logic (MVL) family that enables symmetrical arithmetic using the balanced ternary notation. The ongoing challenge is to engineer devices, circuits and systems that can physically represent three logic levels with competitive power, performance, area and cost metrics. For flash storage and communication MVL is already the industry standard, but logic remains binary. Ever since Dennard scaling stopped in 2005, binary computing is struggling to overcome the increasing power wall, memory wall and Electronic Design and Automation (EDA) wall. A unified MVL compute paradigm can theoretically address these challenges, making it a prime candidate for the beyond-CMOS era.

This article-based thesis is structured in three parts. In the first part binary computing is discussed. The historical reasoning for this choice as well as the current scaling challenges that impede its future were reviewed. The part concludes with a review of several fundamental and engineering limits that are rarely cited but highly relevant when considering another radix such as Shannon’s noisy channel theorem and Rent’s rule.

In the second part ternary computing is discussed. A brief overview of radix-3 theory and literature is presented. A novel radix comparison methodology is proposed to improve fairness. Historical efforts to build ternary computers were reviewed which started in the 1950’s. A categorization of the main benefits of balanced ternary is presented across 7 application domains. The part concludes with an overview of the critique on radix-3.

In the third part practical aspects of ternary computing are discussed: multi-stable devices and EDA tooling. For devices, non-volatile ternary memory control with commercially available memristors was studied. A novel open source software tool uMemristorToolbox and hardware platform for multi-state memristor programming were developed. The experiments confirm that ternary memory with memristors is both feasible and low-cost.

Lastly, EDA tooling and workflows for ternary logic chips are discussed. The open source software tool Mixed Radix Circuit Synthesizer (MRCS) was developed, the first browserbased EDA tool to design and verify binary, ternary and hybrid (mixed radix) circuits. It features a novel MVL circuit synthesis algorithm with HSPICE and verilog output targeting CMOS and multi-threshold CNTFET. The tool was used to design REBEL-2, a novel balanced ternary CPU with RISC-V-like ISA. Four MRCS designs have been tested on a FPGA and submitted for tape-out using the Openlane ASIC workflow.