ビットシリアル SIMD シミュレータ

## 目的

通常、我々が目にする機械（パソコン、携帯電話、家電製品など）は多いと 64bit,
少ない場合でも 8bit のデータバス幅の CPU を使用しています。

しかし、世の中には 1bit の CPU というのもあります。

かつて、「複数ビット幅の CPU で動作する計算機と複数の 1bit CPU とを比較すると後者の方がコストパフォーマンス面で有利である」という理由で超並列計算機の CPU として採用されていた時代もありました（[参考](https://en.wikipedia.org/wiki/Serial_computer)）。

実装コストが低さは FPGA 上で並列計算機を構成するのにも適しているのではないかと考えました。とはいえ 1bit CPU などというものを触った経験がないので、まずはシミュレータを作って動かしてみます。ネタばらしをすると、コネクションマシン(CM-1)のビットシリアルプロセッサを真似ています。

## ALU

３入力ビットー２出力ビットの ALU を用います。
入力ビット数・出力ビット数が少ないので、この ALU の演算内容はこの上なくユニバーサルな形式です。つまり、３入力ビットのあらゆる組み合わせ（といっても８通りしかない）について、２出力がどうなるかを２つの真理値表で与えます。
![ALU.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/412308/f0daa462-f2df-5a6f-04b5-8ab8c72ef977.png)


コネクションマシンは 16 個のビットシリアルプロセッサを 1 チップに実装していましたが、ここでは 64 個のプロセッサの ALU を一つの関数で書いています。少なくとも 64 個のプロセッサを同時に SIMD で動かす想定です。


```python
def alu64(a, b, f, op_s, op_c):
    u'''
    A, B, F の値と真理値表を元に S, C の値を決定する。
    Args:
        a : A レジスタ (64bit) の値
        b : B レジスタ (64bit) の値
        f : F レジスタ (64bit) の値
        op_s : S を決定する真理値表 (8bit)
        op_c : C を決定する真理値表 (8bit)
    Return:
        真理値表に従って決定した値 S, C
    '''
    # A, B, F をデコード
    selector = [0] * 8
    selector[0] = ~a & ~b & ~f
    selector[1] = ~a & ~b &  f
    selector[2] = ~a &  b & ~f
    selector[3] = ~a &  b &  f
    selector[4] =  a & ~b & ~f
    selector[5] =  a & ~b &  f
    selector[6] =  a &  b & ~f
    selector[7] =  a &  b &  f
    # 真理値表に従って S, C を決定
    s = 0
    c = 0
    for i in range(0, 8):
        if (op_s & (1 << i)) != 0:
            s |= selector[i]
        if (op_c & (1 << i)) != 0:
            c |= selector[i]
    return s, c
```
コネクションマシンの場合、フラグレジスタ上の値が 0 か 1 かで値を更新する・しないを切り替える機能があります。これを用いて、複数ある CPU をそれぞれ別の処理に割り当てることも可能です。

```python
def context_switch(x, y, context, context_value):
    u'''context の各ビットを context_value と比較し、
    一致するなら x のビットを、一致しないなら y のビットを採用した値を返す。
    Args:
        x : 64bit の値
        y : 64bit の値
        context: 各ビットの条件分岐を表す 64bit 値
        context_value : context が 1 のとき x を採用するなら True
    Returns:
        context, context_value に従って採用した x または y の
        各ビットからなる 64bit 値
    '''
    return ((context & x) | (~context & y)
            if context_value else
            (~context & x) | (context & y))
```
CPU は３つの ALU サイクルで動作します。

* LOADA - メモリ上の値を A レジスタに読み込み、参照フラグ値を読み込む。同時に真理値表の一方を保持する。
* LOADB - メモリ上の値を B レジスタに読み込み、条件フラグ値を読み込む。同時に真理値表のもう一方を保持する。
* STORE - 保持した真理値表に従って値を生成し、A レジスタ読み込み元メモリに書き戻す。同時にフラグ値を更新する。

ということが巷にあるコネクションマシンの解説書に書いてあったので、それに従ってメソッド m_load_a, m_load_b, m_store として実装しました。
また、CPU なのでリセットも必要でしょう。フラグレジスタを 0 クリアする処理として reset メソッドを実装しました。

get_flag64 / set_flag64 は外部からフラグレジスタを読み書きするためのメソッドです。
フラグレジスタの一つはルータとの入出力として使う予定です。1 bit しかない値を入出力に使うのは奇異に感じられるかもしれません。しかし、この CPU は独立して動作することはできず、外部から LOADA / LOADB / STORE のサイクルで外部のコントローラから呼び出してもらう必要があります。このコントローラはルータに対しても「CPU がデータを送りたいのでよろしく」とタイミングを指示できるので、その指示に合わせて CPU 側からデータを書き込むようにコントローラが CPU を操作すればよいわけです。受信についても同様です。
また、ビットマップディスプレイを用意してフラグの特定ビットを表示するとデバッグ(特にルータがらみのデバッグ)に便利です。大量にプロセッサを並べたものを俯瞰するのは GUI 上での表示なしでは厳しいものがあります。

```python
class Processor64:
    def __init__(self, memory):
        u'''64 CPU 分のインスタンスを作成する。
        Args:
            memory : 外部メモリ
        '''
        self._memory = memory  # 外部メモリ
        self._flags = [0] * 64  # フラグレジスタ (64bit * 64)
        # 以下、演算動作のための内部レジスタ
        self._reg_addr_a = 0
        self._reg_a = 0  # メモリから読み出した値 A (64bit)
        self._reg_b = 0  # メモリから読み出した値 B (64bit)
        self._reg_f = 0  # フラグから読み出した値 F (64bit)
        self._wire_s = 0  # ALU 計算結果 S (64bit) デバッグ用
        self._wire_c = 0  # ALU 計算結果 C (64bit) デバッグ用
        self._reg_context = 0  # コンテキスト判断値 (64bit)
        self._reg_op_s = 0  # ALU に与えられる真理値表 (8bit)
        self._reg_op_c = 0  # ALU に与えられる真理値表 (8bit)
    def dump_flags(self):
        u'''フラグレジスタの値を表示する。
        '''
        for i in range(0, len(self._flags)):
            if self._flags[i] == 0:
                continue
            print('flag[{:2x}]: {:064b}'.format(
                i, self._flags[i] & 0xffffffffffffffff))
    def dump_regs(self):
        u'''レジスタの値を表示する。
        '''
        print('      A : {:064b}'.format(self._reg_a & 0xffffffffffffffff))
        print('      B : {:064b}'.format(self._reg_b & 0xffffffffffffffff))
        print('      F : {:064b}'.format(self._reg_f & 0xffffffffffffffff))
        print('      S : {:064b}'.format(self._wire_s & 0xffffffffffffffff))
        print('      C : {:064b}'.format(self._wire_c & 0xffffffffffffffff))
        print(' context: {:064b}'.format(
            self._reg_context & 0xffffffffffffffff))
    def dump_ops(self):
        u'''真理値表の値を表示する。
        '''
        print('A B F | S C')
        print('-----------')
        for a in range(0, 2):
            for b in range(0, 2):
                for f in range(0, 2):
                    i = (a << 2) | (b << 1) | f
                    print('{} {} {} | {} {}'.format(
                        a, b, f,
                        1 if self._reg_op_s & (1 << i) else 0,
                        1 if self._reg_op_c & (1 << i) else 0))
    def dump(self):
        u'''デバッグダンプ。
        '''
        self.dump_flags()
        self.dump_regs()
        self.dump_ops()
    def reset(self):
        u'''フラグレジスタをリセットする。
        '''
        self._flags = [0] * 64
    def get_flag64(self, read_flag):
        u'''フラグレジスタ上の値を 64 プロセッサ分まとめて返す。
        Args:
            read_flag : 読み出すフラグレジスタを指定するインデックス
        Returns:
            読み出した値 (64bit)
        '''
        return self._flags[read_flag]
    def set_flag64(self, write_flag, value64):
        u'''フラグレジスタ上の値を 64 プロセッサ分まとめて設定する。
        Args:
            write_flag : 読み出すフラグレジスタを指定するインデックス
            value64 : 設定する値 (64bit)
        '''
        self._flags[write_flag] = value64
    def m_load_a(self, addr, read_flag, op_s):
        u'''
        LOADA : read memory operand A, read flag operand, latch one truth table
        Args:
            addr : A レジスタに読み込むメモリのアドレス
            read_flag : F レジスタに読み込むフラグのインデックス
            op_s : ALU に与える S 真理値表 (8bit)
        '''
        self._flags[0] = 0  # 0 番目のフラグの値は常に 0
        self._reg_addr_a = addr
        self._reg_a = self._memory[addr]
        self._reg_f = self._flags[read_flag]
        self._reg_op_s = op_s
    def m_load_b(self, addr, context_flag, op_c):
        u'''
        LOADB : read memory operand B, read condition flag, latch other truth table
        Args:
            addr : B レジスタに読み込むメモリのアドレス
            context_flag : context レジスタに読み込むフラグのインデックス
            op_c : ALU に与える C 真理値表 (8bit)
        '''
        self._reg_b = self._memory[addr]
        self._reg_context = self._flags[context_flag]
        self._reg_op_c = op_c
    def m_store(self, write_flag, context_value):
        u'''
        STORE : store memory operand A, store result flag
        Args:
            write_flag : C 値書き込み先フラグのインデックス
            context_value : 条件分岐の条件値 (True/False)
        '''
        self._wire_s, self._wire_c = alu64(
            self._reg_a, self._reg_b, self._reg_f,
            self._reg_op_s, self._reg_op_c)
        s = context_switch(self._wire_s, self._reg_a,
                           self._reg_context, context_value)
        c = context_switch(self._wire_c, self._flags[write_flag],
                           self._reg_context, context_value)
        self._memory[self._reg_addr_a] = s
        self._flags[write_flag] = c
```

## おわりに

このあとさらに、ルータ、LED パネル風ディスプレイを実装してライフゲームが動くようにしたいと思っています。

実装しました → [1bit CPU でライフゲーム](https://qiita.com/tadashi9e/items/0d696fea8364db29db6c)

Python で Verilog-HDL ソースを生成するツールなども世の中にはあるので、いずれ FPGA 上で動かすことも可能かもしれません。