3値CPUへの道

# 3値CPUへの道
　ここ二ヶ月程、3値CPUについて模索してきました。アメリカ語の文献もいろいろ読んだので、この場をお借りしてアウトプットしたいと思います。シミュレータの都合でCPUは作れませんでしたが、基礎回路やフリップフロップ、四則演算等はできました。

## 1 . モチベーション
　なぜ3値CPUが存在すると便利なのかを紹介します。

### 1 .1 . BitNet
・BitNetとは、Microsoftによって開発された大規模言語モデルです。
・浮動小数点数で行っていた演算を、1 bit(-1, 0, 1)に量子化することで**計算速度の向上**と**メモリ使用量の削減**を目指したものになります。
・現状、BitNetは2進数の演算器(CPU, GPU)で実行されています。

BitNetの論文でも触れられていますが、**1 bit(-1, 0, 1)で演算を行うハードウェア**が開発されることで、BitNetは更なる計算速度の向上が見込まれます。

### 1 .2 . ED法
・ED法とは、金子勇さんが開発したニューラルネットワークのアルゴリズムです。
・2024年にQiitaでED法を見直す動きがありました。
・ED法を3値化(-1, 0, 1)に拡張することで、上手くいけば処理の高速化が見込まれるという記事がありました。

### 1 .3 . ビットサイズあたりの情報量
　2進法の場合、N bitで表現できる数は$0\sim 2^{N}-1$ですが、3進法だと$0\sim 3^{N}-1$になります。つまり、同じ数を表現しようとした場合は3進法の方がビットサイズが小さく済むということになります。ビットサイズの低下は回路的な素子数の減少、ひいてはプログラムの高速な実行に繋がっていきます。

## 2 . コンセプト
・現代のハードウェアは(0, 1)で動作していますが、研究され尽くしているために技術的な限界が来ています。そこで、(-1, 0, 1)で動作するハードウェアを作成することで、**新たな道を切り開く**ことができます。
・理想的には、製造コストや消費電力が現行のハードウェアを上回ることが望ましいです。
・シミュレーション上で実用段階まで進めば、自然と~~金の亡者~~スポンサーが憑きます。やったね！

~~お金ください！！！~~

## 3 . 平衡3進法
　回路を構成するにあたり、平衡3進法というものを採用しました。2進法や普通の3進法と比較して、いくつかの利点があります。

### 3 .1 . 平衡3進法とは
・(0, 1, 2)のみですべての数を表現するのが3進法ですが、負の側にも重みを振って(-1, 0, 1)のみですべての数を表現するものを平衡3進法と呼びます。
・同様なものに、平衡5進法や平衡7進法があります。
・記法には様々あり、$(-1, 0, 1)=(\bar{1}, 0, 1)=(\text{T},0,1)$などが一般的です。
・符号ビット無しで負数を表現することができます。
・切り捨てと四捨五入の結果が同じです。
・ドナルド・クヌースのように「おそらく、あらゆる記数法の中で最も美しい」と言う者もいます。

### 3 .2 . 整数の表現
```math
\begin{array}{|c|c|c|c|}
\hline
10進数 & 平衡3進数 & 10進数 & 平衡3進数\\ \hline
0 & 000 & 0 & 000 \\ \hline
1 & 001 & -1 & 00\bar{1} \\ \hline
2 & 01\bar{1} & -2 & 0\bar{1}1 \\ \hline
3 & 010 & -3 & 0\bar{1}0 \\ \hline
4 & 011 & -4 & 0\bar{1}\bar{1} \\ \hline
5 & 1\bar{1}\bar{1} & -5 & \bar{1}11 \\ \hline
\end{array}
```

### 3 .3 . 少数の表現
```math
\begin{align}
10&=(101.000)_{bal3}=9^1+3^0+1^1+\left(\frac{1}{3}\right)^0+\left(\frac{1}{9}\right)^0+\left(\frac{1}{27}\right)^0 \\
-\frac{1}{9}&=(0.0\bar{1})_{bal3}=9^0+3^0+1^0+\left(\frac{1}{3}\right)^0-\left(\frac{1}{9}\right)^1+\left(\frac{1}{27}\right)^0 \\
0.5&\fallingdotseq(0.111)_{bal3}=9^0+3^0+1^1+\left(\frac{1}{3}\right)^1+\left(\frac{1}{9}\right)^1+\left(\frac{1}{27}\right)^1 \\
2.3&\fallingdotseq(1\bar{1}.10\bar{1})_{bal3}=9^0+3^1-1^1+\left(\frac{1}{3}\right)^1+\left(\frac{1}{9}\right)^0-\left(\frac{1}{27}\right)^1 \\
\end{align}
```

## 4 . 基礎回路
　平衡3進法には5種類のNOTと4種類のビット演算があります。CMOSをベースとした回路を構成し、シミュレーション上での動作を確認しました。

LTspiceによるシミュレーションについてはこちら↓
https://github.com/metaphysical-bard/Tproject

### 4 .0 . CMOS
CMOSではゲート・ソース間電圧により半導体のON-OFF状態を制御しています。
![cmos.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/b4c85f81-a0d0-48a4-aa56-93fcdf994575.png)

### 4 .1 . NOT_10T
$A=0$のときに電流が上から下に流れるため、抵抗を挟んでいます。
![not.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/bf36e11c-ee5e-4c1d-835c-e8a29d6e3230.png)

### 4 .2 . NOT_110(not_n_0)
![not110.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/f8288c96-fa56-4f10-aea4-d558411b18a7.png)

### 4 .3 . NOT_100(not_n_-5)
![not100.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/4006f90c-48e4-4aeb-8167-dbbf9fbe9672.png)

### 4 .4 . NOT_00T(not_p_5)
![not00T.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/dc88a60e-40de-4024-b3c3-e2e8b876ad39.png)

### 4 .5 . NOT_0TT(not_p_0)
![not0TT.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/661b8b14-2f52-4ba6-8af5-3cd4df34f8ac.png)

### 4 .6 . NAND
平衡三進法におけるANDはMINとしての働きを持ちます。
![nand.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/c087736a-dec7-4e09-a199-4c13cf001ca5.png)

### 4 .7 . NOR
平衡三進法におけるORはMAXとしての働きを持ちます。
![nor.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/ee5ab4cf-79fb-4fac-b79c-f1ed03ca342c.png)

### 4 .8 . NCONS
![ncons.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/b7cd564a-7e81-40c5-9056-8a15e0b8f042.png)

### 4 .9 . NANY
![nany.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/ed8c64dd-0914-4750-adc1-748f79633fd3.png)

## 5 . 四則演算
2進法と同様の手法を流用できる部分もあります。

プログラムによるシミュレーションはこちら↓
https://github.com/metaphysical-bard/TBIT_M

### 5 .1 . 和
半加算器
```math
%\oplus\otimes⊠⊞
\begin{align}
S&=A\oplus B=(A⊞B⊞\overline{A⊠B})⊞\overline{A⊠B}\\
C&=A⊠B\\　
\end{align}
```

全加算器
![全加算器.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/3a9b322a-b3b6-4088-9edb-53c204a87fee.png)

全加算器を用いたN bit加算器の構成は2進法のものと同じであるため、**キャリー先読み**や**キャリー予測**などの高速化手法も使えます。

### 5 .2 . 差
加算とNOTの組み合わせで減算を行えます。
```math
A-B=A+(-B)=A+\overline{B}
```

### 5 .3 . 積
```math
A\otimes B=\overline{\overline{A\times B}\times A+B}
```
→2進数と同様に、筆算を解くようにビットシフトさせていくことで、N bitの積を求められます。

### 5 .4 . 商
→2進数と同様にニュートン-ラプソン法やゴールドシュミット法を用います。

ゴールドシュミット法による2進法との比較を行いました。

<details><summary>プログラム</summary>

　ゴールドシュミット法の収束回数は除数によって決定されるため、ビットサイズと除数をループで回して収束回数を計算しました。平均の計算やグラフの作成はエクセルで行いました。
```c++
#include <iostream>
#include "tmath_M.hpp"

tmath_M::bits DIV_count(tmath_M::bits& a, tmath_M::bits& b, unsigned long long* num) {
	assert(a.size() == b.size() && a.size() >= 2 && b.value() != 0);
	tmath_M::bits d(a.size());
	tmath_M::bits ra = d.data() + a.data() + d.data();
	tmath_M::bits rb = d.data() + b.data() + d.data();

	d = a.size() * 3;
	d[a.size() * 2 + 1] = '1';
	while (rb.value() != (std::pow(2, a.size() * 2) - 1)) {
		auto [r, c] = SUB(d, rb);
		ra = MUL(ra, r).data().substr(a.size(), a.size() * 3);
		rb = MUL(rb, r).data().substr(b.size(), b.size() * 3);
		(*num)++;
	}
	d = a.size() * 3;
	d[0] = '1';
	auto [s, c] = ADD(ra, d);
	ra = s.data().substr(0, a.size());
	return ra;
}

tmath_M::tbits DIV_count(tmath_M::tbits& a, tmath_M::tbits& b, unsigned long long* num) {
	assert(a.size() == b.size() && a.size() >= 2 && b.value() != 0);
	if (b.value() == 1) return a;
	tmath_M::tbits d(a.size());
	tmath_M::tbits ra = d.data() + a.data() + d.data();
	tmath_M::tbits rb = d.data() + b.data() + d.data();
	d = a.size() * 3;
	d[a.size() * 2 + 1] = '1';
	d[a.size() * 2 + 0] = 'T';
	while (rb.value() != std::pow(3, a.size() * 2)) {
		auto [r, c] = SUB(d, rb);
		ra = MUL(ra, r).data().substr(a.size(), a.size() * 3);
		rb = MUL(rb, r).data().substr(b.size(), b.size() * 3);
		(*num)++;
	}
	tmath_M::tbit cmp_a = '0';
	for (int i = a.size(); i < a.size() * 2; i++) { cmp_a = (cmp_a + ra[i]) + (cmp_a.n10T() * ra[i]); }
	ra = ra.data().substr(0, a.size());
	tmath_M::tbit cmp_ra = '0';
	for (int i = 0; i < a.size(); i++) { cmp_ra = (cmp_ra + ra[i]) + (cmp_ra.n10T() * ra[i]); }
	if (cmp_a.data == 'T' && cmp_ra.data == '1') {
		d = a.size();
		d[0] = '1';
		auto [s, c] = SUB(ra, d);
		ra = s;
	}
	return ra;
}

int main() {
	unsigned long long co;

	for (int n = 2; n < 13; n++) {
		std::cout << n << " bit :" << std::endl;
		tmath_M::bits a = n;
		tmath_M::bits b = n;
		tmath_M::bits d = n; d[0] = '1';
		b = n;
		for (int x = 0; x < (std::pow(2, n) / 1); x++) {
			if (b.value() != 0) {
				co = 0;
				DIV_count(a, b, &co);
				std::cout << " " << co;
			}
			auto [s, c] = tmath_M::ADD(b, d); b = s;
		}
		std::cout << std::endl;
	}

	for (int n = 2; n < 9; n++) {
		std::cout << n << " tbit :" << std::endl;
		tmath_M::tbits a = n;
		tmath_M::tbits b = n;
		tmath_M::tbits d = n; d[0] = '1';
		b = n;
		for (int x = 0; x < (std::pow(3, n) / 2); x++) {
			if (b.value() != 0) {
				co = 0;
				DIV_count(a, b, &co);
				std::cout << " " << co;
			}
			auto [s, c] = tmath_M::ADD(b, d); b = s;
		}
		std::cout << std::endl;
	}

	system("pause");
	return 0;
}
```
</details>

・同じ数字を扱った場合、2進法の方が反復数が少なくて済みます。
![maxvalue-meaniterations.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/92e7a8c4-bb8f-483d-8a62-d211a1f14eea.png)

・同じビット数の場合、平衡三進法の方が一度の反復でより高い精度補償ができます。
![bit-mean.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/31dabe3a-ce15-4a2f-8104-d7da7d56cf01.png)

## 6 . 記憶回路
LTspiceによるシミュレーションについてはこちら↓
https://github.com/metaphysical-bard/Tproject

### 6 .1 . D-FF
クロック同期で値を保持する回路です。
![D-FF.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/e675c95f-604f-45bd-a643-cfc73085e79f.png)

### 6 .2 . RS-FF
sで1, -1をセットします。rが0, -1のときにリセット(0をセットする)という動作です。
![RS-FF.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/3fb152ea-a1cb-4934-aff0-8a875fc90aff.png)

RS-FFの記憶保持部はNANYとNOTのみであり、NOTへと繋がるMULは1つのブロックにつき1セットあれば充分です。N bitの情報を1つのブロックとして記憶回路を構成する場合、必要な半導体の数は$6N+32$になります。

## 7 . その他の回路
LTspiceによるシミュレーションについてはこちら↓
https://github.com/metaphysical-bard/Tproject

### 7 .1 . 比較器
```math
C=\overline{\overline{A}⊞B}
```
```math
\begin{array}{|c|c|}
\hline
C&meaning\\
\hline
T&A<B\\
\hline
0&A=B\\
\hline
1&A>B\\
\hline
\end{array}
```

### 7 .2 . デコーダ
![decoder.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/7ac15ff7-4eaf-4866-9407-d3a6b0776edb.png)

### 7 .3 . カウンタ
![counter.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3005402/d9fadb67-9c90-460a-a7d7-a751ab0543b2.png)

## 8 . まとめ
　以上のように、2進法でのノウハウを用いることで平衡3進法でも様々な回路を構成することができます。茨が生い茂っている状況ではありますが、3値CPUへの道というのも視えてきたのではないでしょうか。

## 9 . 参考
・[ED法+交差エントロピーをTF/Torchで実装してみた（おまけでBitNet×ED法を検証）](https://qiita.com/pocokhc/items/603a9252d69cd7c60939)
・[三進法](https://ja.m.wikipedia.org/wiki/三進法)
・[Balanced ternary](https://en.m.wikipedia.org/wiki/Balanced_ternary)
・[3値論理回路を作ってみた【自作3進CPU】](https://rikeden.net/?p=1076)
・[Working ternary ALU](https://louis-dr.github.io/ternalu3.html)
・[Fast Ternary Addition](https://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml)
・[A Fast Balanced Ternary Adder/Subtracter](https://hackaday.io/project/164907-ternary-computing-menagerie/log/169827-a-fast-balanced-ternary-addersubtracter)
・[除算 (デジタル)](https://ja.wikipedia.org/wiki/除算_(デジタル))
・[除算・平方根の計算のためのハードウェアアルゴリズム](https://future-architect.github.io/articles/20210630b/)
・[Newton-Raphson法とGoldschmidt法(2)](https://news.mynavi.jp/techplus/article/architecture-103/)
・[ゴールドシュミット除算](https://www.weblio.jp/content/ゴールドシュミット除算)
・[Design of Unbalanced Ternary Logic Gates and Arithmetic Circuits](https://vlsijournal.com/index.php/vlsi/article/view/39)
・[Ternary Logic Gates: Advancing Computing with -1, 0, 1 Base](https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4915345)
・[Design implementations of ternary logic systems: A critical review](https://www.sciencedirect.com/science/article/pii/S2590123024010168)
・[Multiple-Valued Logic Circuit Design and Data Transmission Intended for Embedded Systems](https://arxiv.org/abs/2211.04542)
・[Ternary Toward Binary: Circuit-Level Implementation of Ternary Logic Using Depletion-Mode and Conventional MOSFETs](https://ieeexplore.ieee.org/document/10817560)
・[A balanced Memristor-CMOS ternary logic family and its application](https://arxiv.org/abs/2309.01615)
・[Energy efficient design of unbalanced ternary logic gates and arithmetic circuits using CNTFET](https://www.sciencedirect.com/science/article/pii/S1434841123000754)
・[Ternary encoder and decoder designs in RRAM and CNTFET technologies](https://www.sciencedirect.com/science/article/pii/S2772671123002929)
・[Noise tolerant and power optimized ternary combinational circuits for arithmetic logic unit](https://www.sciencedirect.com/science/article/pii/S2772671125000191)
・[Novel Design of 8T Ternary SRAM for Low Power Sensor System](https://jsstec.org/_common/do.php?a=full&b=42&bidx=3685&aidx=40818)
・[乗法的浮動小数点除算アルゴリズムの誤差限界モデル](https://www.jstage.jst.go.jp/article/jsiamt/9/2/9_KJ00002977964/_article/-char/ja/)

## むすび
以上、3値CPUについてでした。