概要
セルオートマトンのような簡潔な動作でありつつ直感的に編集・観察できる論理回路シミュレータを作って実際に動かしてみたい。
成果物
動くもの：
https://htsnul.github.io/pixel_automaton_logic_circuit/
コード：
https://github.com/htsnul/pixel_automaton_logic_circuit
先行事例
セルオートマトンで論理回路を実現している先行事例はあるのだが（例：Wireworld）、これらは直感的に編集・観察するのは以下の理由で難しく感じた：
- ワイヤーの交差など単純な構造の記載が複雑
- 信号が連続的ではないため論理回路でのタイミングの考慮が難しい
一方、一見ピクセルっぽい見た目の論理回路シミュレータで直感的に編集できるもあるのだが（例：Virtuall Circuit Board）、これらは実際には生成時に接続情報を解析していて、動作は簡潔ではないし、信号そのものの動きまでは観察できない。
簡潔なセルオートマトンでありつつ直感的に編集・観察できる論理回路シミュレータを作っていきたい。
信号をいい感じに動作させる
連続して伝搬していくように見える信号を扱いたい。セルオートマトンで単純に隣接セルに信号を無条件に伝搬させてしまうと、信号源が消えても既に広がった信号から信号が再度広がってしまい信号が消えなくなってしまう。
- 隣接セルが自セル向きの信号を持っていたら、そうでない隣接セルに向けて信号を持つ
とすればうまくいかないだろうか？各セルは上右下左の信号有無情報を持つ。
疑似コード：
if (ワイヤーの場合) {
信号を受けているか = (
上セルが下向きの信号を持つ ||
右セルが左向きの信号を持つ ||
下セルが上向きの信号を持つ ||
左セルが右向きの信号を持つ
);
上向き信号 = 信号を受けているか && 上セルが下向き信号を持っていない
右向き信号 = 信号を受けているか && 右セルが左向き信号を持っていない
下向き信号 = 信号を受けているか && 下セルが上向き信号を持っていない
左向き信号 = 信号を受けているか && 左セルが右向き信号を持っていない
}
信号を持っているセルの方向には信号を持たないようにすることで無限に信号が反射してしまうことを防いでいる。
試したところうまくいったように見える。信号が途絶えた場合に発生源から順に信号が消えていく。ドミノ倒しのようなイメージが近いかもしれない。
信号の交差も簡潔に表現できるようにする
信号の交差も簡潔に表現できるようにしたい。ワイヤーと同等の処理のまま、信号を水平方向と垂直方向で個別に扱えばいけそうだ。
疑似コード：
if (交差ワイヤーの場合) {
垂直方向に信号を受けているか = 上セルが下向き信号を持っている || 下セルが上向き信号を持っている
水平方向に信号を受けているか = 左セルが右向き信号を持っている || 右セルが左向き信号を持っている
上向き信号 = 垂直方向に信号を受けているか && 上セルが下向き信号を持っていない
右向き信号 = 水平方向に信号を受けているか && 右セルが左向き信号を持っていない
下向き信号 = 垂直方向に信号を受けているか && 下セルが上向き信号を持っていない
左向き信号 = 水平方向に信号を受けているか && 左セルが右向き信号を持っていない
}
交差含めワイヤーがいい感じに動作するようになった。
基本ゲートをどうするか？
基本ゲートをどう表現するかは随分悩んだ。いわゆるリレー的なものが実現できればその組み合わせで基本ゲートは実現できてしまう。しかし、
- 基本ゲートをどう実現するかは対象の仕組みに依存したもの
- 基本ゲートで抽象化された以降の世界という切り分けは綺麗
ことから、基本ゲートそのものをセルで表現する方向で調整することにした。
とはいえ、1セルのみで基本ゲートを表現しようとすると、
- セルのどの向きが入力・出力に対応するかを表現するのが難しい、または不可能
- NOT回路については他ゲートと対で使われることになる
ことから、隣接2セルの組み合わせで基本ゲートを表現することにした。
- 入力-AND
- 入力-OR
- 入力-XOR
- 出力
- 出力-NOT
この5種類で表現することにした。
セルの種類が決まってきたことで、ここまででセルの持つ情報が固まってきた。
7-6 | 5-4 | 3 | 2 | 1 | 0
+-----+---+---+---+---+- セル種類：無、ワイヤー、入力、出力のどれか
+---+---+---+---+- セルサブ種類：例えばセル種類が入力であれば、AND、OR、XORかどうか、など
+---+---+---+- 上向き信号
+---+---+- 右向き信号
+---+- 下向き信号
+- 左向き信号
8bitでセルに必要な情報が表せた。
入力セル疑似コード：
if (入力セルの場合) {
if (ANDの場合) {
信号を受けているか = (
(上セルがワイヤー ? 上セルが下向き信号を持っている : true) &&
(右セルがワイヤー ? 右セルが左向き信号を持っている : true) &&
(下セルがワイヤー ? 下セルが上向き信号を持っている : true) &&
(左セルがワイヤー ? 左セルが右向き信号を持っている : true)
)
} else if (ORの場合) {
信号を受けているか = (
(上セルがワイヤー && 上セルが下向き信号を持っている) ||
(右セルがワイヤー && 右セルが左向き信号を持っている) ||
(下セルがワイヤー && 下セルが上向き信号を持っている) ||
(左セルがワイヤー && 左セルが右向き信号を持っている)
)
} else if (XORの場合) {
信号を受けているか = (
((上セルがワイヤー && 上セルが下向き信号を持っている) ? 1 : 0) +
((右セルがワイヤー && 右セルが左向き信号を持っている) ? 1 : 0) +
((下セルがワイヤー && 下セルが上向き信号を持っている) ? 1 : 0) +
((左セルがワイヤー && 左セルが右向き信号を持っている) ? 1 : 0)
) % 2 == 1
}
上向き信号 = 信号を受けているか && 上セルが出力セルか
右向き信号 = 信号を受けているか && 右セルが出力セルか
下向き信号 = 信号を受けているか && 下セルが出力セルか
左向き信号 = 信号を受けているか && 左セルが出力セルか
}
ANDの場合、接続されているワイヤー全てが信号がある場合のみ信号を受けたとすることで、入力が3つの場合でも期待動作するようにしている。
出力セル疑似コード：
if (出力セルの場合) {
信号を受けているか = (
(上セルが入力セルか && 上セルが下向き信号を持っている) ||
(右セルが入力セルか && 右セルが左向き信号を持っている) ||
(下セルが入力セルか && 下セルが上向き信号を持っている) ||
(左セルが入力セルか && 左セルが下向き信号を持っている)
)
信号 = NOTセルの場合 ? !信号を受けているか : 信号を受けているか
上向き信号 = 信号 && 上セルが出力セルか
右向き信号 = 信号 && 右セルが出力セルか
下向き信号 = 信号 && 下セルが出力セルか
左向き信号 = 信号 && 左セルが出力セルか
}
実際の動作：
補足だが、この動作の様子では、出力-NOTセルを単体で使った場合には、信号発生源として使えることを利用している。
また、BufferやNOTについては、入力セルはここでは入力-ANDセルを使っているが、入力信号が1つであれば動作に差がないので入力-ORセルや入力-XORセルを使っても問題ない。
これで、基本ゲートが動作させられるようになった。
実装をGPU化する
ここまで具体的な実装手段には触れてきていない。特に実装に依存した話題はないからではあるが、ここまでの処理をCPUで実装してきたところやはり処理速度的な限界を感じ始めたため、GPUを利用することにした。
Webで作っていたため、WebGL、WebGL2、WebGPUなどの選択肢があったが、
- WebGPUはまだ2023年時点で枯れていない
- WebGLでは1バイトテクスチャへの書き込みを扱えないが、WebGL2なら扱える
- WebGLのGLSLではビット演算を扱えないが、WebGL2では扱える
という理由からWebGL2を使うことにした。
実装の注意点としては、読み込みテクスチャと書き込みテクスチャに同じものは使えないので、ダブルバッファリングするというところだが、これは1更新前の情報を参照するセルオートマトンの特徴とも合うため、自然とそのように実装できる。
また、少なくともシェーダは更新用と表示用は分けることになるだろう。編集機能を追加する場合は編集用シェーダも作ることになるだろう。更新は特に頻繁に行うので、できるだけ軽くしたい。
実際の性能としては、512x512のセルに対して、1フレームに100回、つまり、1秒に6000回更新ぐらいは余裕で行えるようだった。性能限界は試していないが、CPUではこの速度は難しいはずで、GPUを使ってよかった。
足し算する
半加算器、全加算器と呼ばれているもので1bitの足し算ができる。
一般的に知られている回路図をそのまま表現すればよい。
3bitになってくると以下のようになる。
最下位ビットを右に配置したほうが分かりやすいので、向きが変化しているのと、配置数が多くなったことに伴い省スペース化している点が見どころだ。
クロックを作る
コンピュータ的に手順を動作させるためにはクロックが必要になる。
一般的にNOT回路をループさせることでクロックになることが知られていて、それは本記事で扱うセルオートマトン実装でも成り立つ。
右のワイヤーだけを見ると、信号が周期的にオンオフしていることがわかる。
周期を長くしたい場合は、ワイヤーを長くしてしまえばよい。
ただし、この方法によるクロックの長周期化は信号の伝達速度が遅いセルオートマトン実装だからこその方法かもしれない。
状態を保持したい
計算過程を保存するために値を保持したい。これは最終的にいわゆるレジスターになる。
最も基本的となるものはSRラッチと呼ばれている。これも一般的な回路をそのまま表現することで実現できる。
それぞれのワイヤーでセット（S）とリセット（R）ができる。
このままでは使いづらいので、データ（D）をクロック信号が来たタイミングで保存できるようにする。
それがDラッチと呼ばれている。
データ信号に対して、そのままのものと反転したものがそれぞれ、SとRに対応して、それらがクロックが入ったときのみAND回路でSRラッチに伝わるようになっている。
回路図だけを見ると複雑になってきたが、原理が分かれば簡単だ。
Dラッチにはレジスタとして使おうとすると制限がある。Dラッチが保持する値を a としたとき、a = a + 1 的なことができない。なぜなら入力値が出力値に依存していてループして回路が不安定になってしまうからだ。
Dラッチを2つ連結させ、後続のDラッチに反転したクロックを利用すると、クロックがオフになったときに、先行Dラッチの値が後続Dラッチにコピーされ、次のクロックがオンになったときも前クロックの値が安定取得できるようになる。
（緑色の囲いは交差ワイヤーだが単純に範囲を表す装飾として使っている）
これがフリップフロップと呼ばれている。これにより、a = a + 1 的な動作が実現できるようになる。
これをコンパクト化して右が最下位ビットになるよう反転し、3bitを扱うようにしたものが以下だ。
交差部分を交差なしで組み替えることで大きくコンパクト化している。また、左上から右に進むワイヤーは起動時に各フリップフロップをリセットを制御するための専用信号になっている。信号が到達するまでの間、内部のSRラッチ部のリセットに信号が入力されるようになっている。
これで3bitの値が保持できるようになった。
シンプルなカウンター
処理を1つずつ進めるようなことをするには、カウンターが必要になる。ここまでの構成要素からだとレジスターと加算器を組み合わせればカウンターにはなるのだが、もうちょっとシンプルな構成でカウンターを作ることもできる。
レジスターに自身の出力を反転させたものを入力すると、1クロックごとにビット値を反転させることができる。
これを次のレジスターのクロック入力としつつ、そちらのレジスターでも同じく1クロックごとにビット値を反転させるようにすれば、1つずつクロック数が2倍で反転するレジスタになる。
これを必要ビット分繋げると単調増加するカウンターとなる。
これはリップルカウンターと呼ばれている。
3bit値を表示したい
3bit値の値を目に見やすい形に表示したい。
一般的に知られている、3bitデコーダー、ダイオードマトリックス、7セグメントディスプレイを再現して組み合わせれば実現できる。
先ほどのリップルカウンターの出力を繋ぐと以下のようになる。
実は7セグメントディスプレイはダイオードマトリックスを使わずとももっとシンプルな回路で実現できるが、ここでは汎用性のある構成にした。
人間にもカウンターの値が分かりやすくなった。
組み合わせてみる
ここまで出てきた要素を使って、簡単な自動計算をし結果を表示させてみる。毎クロックカウンターの値をレジスタに足していく。3bitでオーバーフローする。
少しコンピューター的なものができたような気持ちになれた。
まとめ
セルオートマトン的な簡単な動作で直感的に編集・観察できる論理回路シミュレータを作ることができ、またそこで自動計算させられるものを作ることができた。信号の動きが見れて楽しい。