目的
65536 個 の 1bit CPU を東西南北方向に結合した計算機のシミュレータ上でライフゲームのシミュレーションを行います。
前提
1bit CPU はビットシリアル SIMD シミュレータで示したものです。これをルータ・ビットマップディスプレイと結合した計算機のシミュレータの形にしました。
ビットマップディスプレイ
コネクションマシンの前面には LED が並んでいます（コネクションマシンは LED がピカピカ光るなんだかかっこいい計算機として有名です）。
これに倣って、各 1bit CPU の状態をドット一つで表示する画面を作りました。65536 個の PE（1bit CPU）があるので、二次元平面上だと 256×256 になります。
コネクションマシンは赤色 LED を使っていましたが、今は RGB フルカラーも可能な時代です。とはいえフルカラーにする必然性もないので 8 色（RGB 各 1 bit）としています。
ビットマップディスプレイの操作は、1bit CPU からはルータを介してドットの R/G/B それぞれについてデータを送ることで行います。
この画面上でライフゲームを動かすことを当面の目標としました。
ルータ
1bit CPU の 64 個のフラグの一つをルータとデータのやりとりをする目的に用いることにして、このフラグをルータデータフラグと呼ぶことにします。ルータデータフラグは半分 PE に属していて半分ルータに属しているようなイメージになります。
これを東西南北方向の直接結合網ルータのクラスとして作成しました。ライフゲームが実現できればよい、という程度にルータの機能は以下のように単純化しました：
- 東西南北方向に並んだ 1bit CPU のルータデータフラグの値を、東西南北方向にコピー（ローテート）する
- 東西南北方向の東西を x 軸、南北を y 軸として、指定された x, y 座標にある 1bit CPU のルータデータフラグの値を設定する（初期データ投入用）
- 東西南北方向に並んだ 1bit CPU のルータデータフラグの値を、RGB 8 色 256×256 のディスプレイ画面に送る（可視化）
コントローラ
PE ができるのは PE が保持しているデータの操作のみです。コントローラがプログラムを解釈して PE にマイクロ命令として伝えます。あるいはルータに対してデータの配送を指示します。
1bit CPU 上でのライフゲームの実現
ライフゲームは以下の手順で実行します。
- 準備
まずは、パターンファイルを読み込みます。パターンファイルの読み込み処理についてはライフゲームのパターンファイルフォーマットで作成したものを用いました。
読み込んだパターンが「生」の位置にある PE のルータデータフラグを 1 に設定します。この処理は PE ではなくコントローラ側で行います。
- 実行
各ステップについて以下を順に行います：
- PE 上のメモリ配置を決定します。周囲のビットをカウントするための領域（若干余裕を持って 10 bit）、現在のセル状態（「生」または「死」の 1bit）、次のセル状態を保持する領域（1bit）の合計 12 bit です。あとの説明に便利なので、カウント領域はアドレス 0 から始まることにします。
- 確保したメモリをクリアします。各 PE に対して 1bit 毎命令を発行して行います。
- 最初にルータデータフラグの値をメモリの現在セル状態領域にコピーします。
- カウンタを初期化します。一般的なカウンタだと二進数で
0000
0001
0010
0011
:
と進めていくところですが、ここではちょっと変わったことをします。
1000000000
1100000000
1110000000
:
と 1 の並びがカウンタ +1 の度に伸びていく形です。10 ビット用意しても０〜９までしか数えられませんが、特に問題はないでしょう。
初期状態に合わせて、アドレス 0 の値を 1 に設定します。
- ルータを使って、各 PE に周囲の PE のフラグ=1 の数を数えさせます。
ある特定の PE に着目して、その周囲にフラグ=1 がいくつあるのか数えます。
下の図で、△が着目している PE で、周囲の赤い部分が数える対象の部分です。
| ○ | ○ | ○ | ○ | ○ |
| ○ | ○ | ○ | ○ | ○ |
| ○ | ○ | △ | ○ | ○ |
| ○ | ○ | ○ | ○ | ○ |
| ○ | ○ | ○ | ○ | ○ |
まず、ルータに対して、全体のデータを S(南) 方向への移動を指示します。
| ○ | ○ | ○ | ○ | ○ |
| ○ | ○ | ○ | ○ | ○ |
| ○ | ○ | △ | ○ | ○ |
| ○ | ○ | ○ | ○ | ○ |
| ○ | ○ | ○ | ○ | ○ |
着目している PE について、この操作でもともと一つ北にあったフラグの値が自分の位置に移動してきたことになります。自分の位置に来たフラグの値を見て、その値が 1 ならカウンタのアドレス 1 の値を 1 に設定します。0 なら元のまま（アドレス 0 の値のみが 1）です。
| ○ | ○ | ○ | ○ | ○ |
| ○ | ○ | ○ | ○ | ○ |
| ○ | ○ | △ | ○ | ○ |
| ○ | ○ | ○ | ○ | ○ |
| ○ | ○ | ○ | ○ | ○ |
次に、ルータに対して全体のデータを E(東) 方向への移動を指示します。
| ○ | ○ | ○ | ○ | ○ |
| ○ | ○ | ○ | ○ | ○ |
| ○ | ○ | △ | ○ | ○ |
| ○ | ○ | ○ | ○ | ○ |
| ○ | ○ | ○ | ○ | ○ |
この操作でももともと北西にあったフラグの値が自分の位置に移動してきたことになります。さきほどと同様に、自分の位置にあるフラグが 1 ならカウンタのビットを一つ 1 に変えます。
| ○ | ○ | ○ | ○ | ○ |
| ○ | ○ | ○ | ○ | ○ |
| ○ | ○ | △ | ○ | ○ |
| ○ | ○ | ○ | ○ | ○ |
| ○ | ○ | ○ | ○ | ○ |
さらに、N-N-W-W-S-S と動かしてカウントすると、元の位置から見た周囲８方向の位置にあったフラグの値 1 の数（隣接生存セル数）を、メモリ上のビット 1 の並びに変換できることになります。
- カウントした隣接生存セル数をデコードします。「デコード」とここで言っているのは、数えた数に対応するビット位置のみ 1、ほかは 0 とすることです。
1000000000 → 1000000000（アドレス 0 のみ 1）
1100000000 → 0100000000（アドレス 1 のみ 1）
1110000000 → 0010000000（アドレス 2 のみ 1）
:
これであとの処理が楽になります。この処理は、隣接するビットの XOR（排他的論理和）をとることで実現できます。コントローラは PE に各メモリアドレスの XOR を順次指示します。カウンタを敢えて二進数にせずビット 1 の数にしたのはこの処理を簡単にするためです。
- いよいよライフゲームのルールに従って次の値を決めます。
- 隣接生存セルの数が 2 なら、その座標のセルの元の状態が「生」なら「生」、「死」なら「死」
- 隣接生存セルの数が 3 なら、その座標のセルは元の状態に依らず無条件に「生」
これを以下のように実行します。
(アドレス 2 の値が1 ∧ 元のセルが「生」である) ∨ (アドレス 3 の値が1)
このビット演算を PE に指示します。演算結果は、一旦次セル状態のメモリ領域に反映します。
- 次セル状態をルータデータフラグの値に反映（コピー）します。
これで、ビット演算のみでライフゲームが実現できました。
実行結果と感想
1bit PE × 64 個のチップを Python でシミュレーションするクラスを 1024 個並べて実際にこれを実装してみました。
所詮はシミュレータなので当然遅いだろうと思っていたのですが、想像通りライフゲームの一ステップの画面更新に 1 秒程度かかります。ロジックが正しいということは確認できたので不満はなかったのですが「もしこれを C++ で実装してみたらどのくらいの性能になるのだろう？」という疑問が湧いてきました。
C++ での再実装
ビットシリアル SIMD シミュレータ を C++ で書き直してみました。性能を出したかったので「1bit PE を 64 個束ねたものを 64bit 符号なし整数で実現する」という形でなく「65536 PE をサイズ 1024 の 64bit 符号なし整数で実装する」という形にしました。SIMD であるため、すべての PE は一斉に同時に同じアドレスにアクセスしますが、ここでアクセスされるメモリ領域を連続にとることでランダムアクセスを削減したいと考えたためです。
ルータも処理コストが高そうなので同じ C++ のソース内に NewsRouter クラスとして実装してしまいました。
PE 実装部分、ルータ実装部分以外は実装コストと性能との兼ね合いで、あるいは今後も手が入るであろうことから Python のままとしています。
実装にあたっては Python でプロトタイピング済みなので特に問題になる箇所はなく、むしろ Python で書いていて最上位ビットが 1 になる場合のビットシフト演算結果の不自然さ（結果が負数になる）、型を明示できないことへの違和感などが解消されて快適でした。
実行性能は言うまでもなく満足できる結果で、画面描画のボトルネックに比べると PE・ルータ部分の実行コストは気にならないレベルにまで高速化できました。
まとめ
- ビットシリアル SIMD シミュレータに書いた形式の 1bit CPU を 256×256 の二次元メッシュで 65536 個結合した並列計算機のシミュレータを作りました。
- 256×256 のトーラス領域上でのライフゲームを 1bit CPU 上でのビット演算と 256×256 の二次元結合網上での通信で実装しました。https://github.com/tadashi9e/mpp_lifegame
セル・オートマトン専用計算機のシミュレータが出来上がったので、気が向いたらライフゲーム以外のセル・オートマトンを実装してみるかもしれません。
あるいは、ルータ部分をハイパーキューブ結合に変えたり、あるいはもっと汎用性の高いパケットベースのルーティングを実装してみたりするのも面白そうです。