【Elixirで学ぶCS】ElixirでそれっぽいALUが実装できるまで

なにこれ(3度目

Elixirでコンピューターサイエンスを学ぶシリーズの第3弾で以下記事の続編です
www.okb-shelf.work

この本を参考に勉強しつつコードを書いています

並行コンピューティング技法 ―実践マルチコア/マルチスレッドプログラミング

相変わらず内容に結構つまづいている
今、土日はだいたいこの本 + cousera使ってcsを勉強している
内容的には最初の方はよりレイヤーが深い話なので挫折しやすいってのがよく分かる
確かに論理ゲートとかいきなり言われてもなぁとは思いつつ、挫折しつつ何とか続いている

なんとか2章の終わりのALUまでを実装できたのでまとめておく

ALUについて

一言でいうとCPUのコアになる演算を行う部分
xとyの入力をリセットしたり、反転させたり、足し合わせたりってことやらが可能

このALUを利用してCPUは演算を行なっている
詳しい仕組みやなぜこの回路でALUが動作するのかという説明は行わない

上記で紹介した書籍などを参考にしてほしい
自分は全テストケースが通ったからOK程度の認識でいる

前回から追加したゲート

先に予備知識となる「sel」について説明する
selは何も難しいものではなくて、入力のどちらを採用するか(0or1)を回路に伝えるためのものである

# sel = 0のとき
input = [x, y]
sel = 0
out = x

# sel = 1のとき
input = [x, y]
sel = 1
out = y

ALUを実現するために、新たなゲートが必要になるのでざっくりと説明しておく

• Mux回路 -> 複数の入力(x, yの2つ)からselの値を使用して1つを選択
• Dmux回路 -> 受け取った値をどの位置に通すかを選択

Mux回路については先ほど紹介している & イメージがしやすいと思うが
Dmux回路の説明は言語の限界があるので許して欲しい
Mux回路同様に具体的な値の動き方を見てみる

# sel = 0のとき
val = 1
sel = 0
out = [1, 0]

# sel = 0のとき
val = 1
sel = 1
out = [0, 1]

先ほど説明する際に使用した「位置」という言葉はリストのindex位置だと思ってくれれば良い
入力された値をどのindexに格納して次に渡すかをDmux回路で行なっている

ElixirでMux回路とDmux回路を実装する

まずはシンプルにElixirのパターンマッチを使用して簡易なものを作成してイメージを確かめる

defmodule SimpleMux do
  def mux([a, _b], 0), do: a
  def mux([_a, b], 1), do: b
  def dmux(x, 0), do: {x, 0}
  def dmux(x, 1), do: {0, x}
end

Elixirっぽくていいね。異世界転生かってぐらいのチート実装
それぞれの回路でselのパターンは2種類しかないので楽勝

簡単なテストを実行しておく
まずはMux回路について

mux_test= [
  SimpleMux.mux([0,0], 0) == 0,
  SimpleMux.mux([0,0], 1) == 0,
  SimpleMux.mux([1,0], 0) == 1,
  SimpleMux.mux([1,0], 1) == 0,
  SimpleMux.mux([0,1], 0) == 0,
  SimpleMux.mux([0,1], 1) == 1,
  SimpleMux.mux([1,1], 0) == 1,
  SimpleMux.mux([1,1], 1) == 1,
]
IO.inspect(mux_test)
# [true, true, true, true, true, true, true, true]

次にDmux回路について

dmux_test = [
  SimpleMux.dmux(0, 0) == {0, 0},
  SimpleMux.dmux(0, 1) == {0, 0},
  SimpleMux.dmux(1, 0) == {1, 0},
  SimpleMux.dmux(1, 1) == {0, 1}
]

IO.inspect(dmux_test)
# [true, true, true, true]

しかし、この方法はゲート理論の実装から逸れたものになってしまうのでNG(Elixirごめんな)
なのでnotやandなどの他の回路を使って実装する。回路図はぐぐってね
実装は以前より引き続き使用しているRogicalGateモジュールに追加した

defmodule RogicalGate do
  def nand(1, 1), do: 0
  def nand(_x, _y), do: 1
  def or_(x, y), do: nand(nand(x, x), nand(y, y))
  def not_(x), do: nand(x, x)
  def and_(x, y), do: not_(nand(x,y))
  def xor_(x, y), do: or_(and_(x,not_(y)), and_(not_(x),y))
  def mux([x, y], sel) do
    not_sel = not_(sel)
    or_(and_(x, not_sel), and_(y, sel))
  end
  def dmux(x, sel) do
    not_sel = not_(sel)
    {and_(x, not_sel), and_(x, sel)}
  end
end

先ほどのテストを流用。同じことなのでまとめて行う

mux_test= [
  RogicalGate.mux([0,0], 0) == 0,
  RogicalGate.mux([0,0], 1) == 0,
  RogicalGate.mux([1,0], 0) == 1,
  RogicalGate.mux([1,0], 1) == 0,
  RogicalGate.mux([0,1], 0) == 0,
  RogicalGate.mux([0,1], 1) == 1,
  RogicalGate.mux([1,1], 0) == 1,
  RogicalGate.mux([1,1], 1) == 1,
]

dmux_test = [
  RogicalGate.dmux(0, 0) == {0, 0},
  RogicalGate.dmux(0, 1) == {0, 0},
  RogicalGate.dmux(1, 0) == {1, 0},
  RogicalGate.dmux(1, 1) == {0, 1}
]

IO.inspect(mux_test)
# [true, true, true, true, true, true, true, true]
IO.inspect(dmux_test)
# [true, true, true, true]

理論をキッチリ守ることが出来た
次にMux回路とDmux回路をnbit対応させる
実装には以前より使用しているNbitRogicalGateを使用しているが、少し内容を変更している
回路の関数をnbitに対応させるヘルパー関数を用意してmux回路用の変換関数を追加した

defmodule NbitRogicalGate do
  # [x,y]のような入力を2つ受ける回路の変換関数
  def nbit_converter(inputs, gate_func), do: Enum.map(inputs, fn [x, y] -> gate_func.(x, y) end)
  # [x]のような入力を1つ受ける回路(not)の変換関数
  def nbit_not(inputs, gate_func), do: Enum.map(inputs, fn x -> gate_func.(x) end)
  # [[x,y],sel]のような入力を2つ(リストとsel)受ける回路(mux)の変換関数
  def nbit_mux(inputs, gate_func), do: Enum.map(inputs, fn [[x,y], sel] -> gate_func.([x,y], sel)  end)

  def nand(inputs), do: nbit_converter(inputs, &RogicalGate.nand/2)
  def not_(inputs), do: nbit_not(inputs, &RogicalGate.not_/1)
  def or_(inputs), do: nbit_converter(inputs, &RogicalGate.or_/2)
  def and_(inputs), do: nbit_converter(inputs, &RogicalGate.and_/2)
  def xor_(inputs), do: nbit_converter(inputs, &RogicalGate.xor_/2)

  # ここに追加したよ~
  def mux(inputs), do: nbit_mux(inputs, &RogicalGate.mux/2)
  def dmux(inputs), do: nbit_converter(inputs, &RogicalGate.dmux/2)
end

動作を確認

res = NbitRogicalGate.mux([[[1,0], 0], [[0,0], 1], [[0,1], 1], [[1,1], 1]])
IO.inspect(res)
# [1, 0, 1, 1]

res_dmux = NbitRogicalGate.dmux([[1,0], [0,1], [1,1], [0,0]])
IO.inspect(res_dmux)
# [{1, 0}, {0, 0}, {0, 1}, {0, 0}]

良い感じっぽい
準備もそこそこ出来たのでALUの実装に移る

ALUの実装の前に...

ALUの内部構造について、ざっくりと触れておく
ALUは以下の値を受け取って値の演算を行う関数になる
(nはビット数-1とする。16bitの時は15 -> 0..15)

それぞれの入力値についてまとめる

• x[0..n] -> 入力値x群
• y[0..n] -> 入力値y群
• zx(0or1 -> sel) -> xの値を全て0にするかどうか
• nx(0or1 -> sel) -> xの値を全て反転するかどうか
• zy(0or1 -> sel) -> yの値を全て0にするかどうか
• ny(0or1 -> sel) -> yの値を全て反転するかどうか
• f(0or1 -> sel) -> and(x, y)とadd(x, y)のどちらを採用するか
• no(0or1 -> sel) -> 出力値を反転するかどうか

zxはおそらくzero_x, nxはnot_xの略だと思っている
で何？ってなると思うので4bitの演算の動きをサンプルデータを追って見ていく
これで少しはイメージを掴んでもらえればと思う

# 入力値xとy
x = [0,1,1,0]
y = [1,0,0,0]

# sel値
zx = 0
nx = 1
zy = 1
ny = 1
f = 0
no = 1

# xのデータに対しての変換
# zx = 0より(0にしない)
x = [0,1,1,0]

# nx = 1より(値を反転)
x = [1,0,0,1]

# yのデータに対しての変換
# zy = 1より(0にする)
y = [0,0,0,0]

# ny = 1より(値を反転)
y = [1,1,1,1]


# この時点でのxとyの値 -------------
x = [1,0,0,1]
y = [1,1,1,1]
# -----------------------------------

# f = 0より and(x, y)を採用
# こんな感じで処理していく
# [and(1,1), and(0,1), and(0,1), and(1,1)
fout = [1,0,0,1]

# no = 1よりfoutを反転
out = [0,1,1,0]

と、こんな感じで特に難しいことをやっているわけではない
このselの組み合わせで演算に必要なパターン18種が全て表現可能だそう
やっぱり考えた人が天才すぎる...

最終的な出力値のoutと別にzrとngという2つの出力値がある
zrは出力値に1が含まれていれば0を返す
ngは最上位bit(一番上の桁)が1なら1を返す

これでALUの実装の準備が本当に整った
さっそく上記の処理を論理ゲートを使って実装してみる

ALUの実装

先にコードの全体をお見せする
演算を行うメインの関数はcompute関数になる
他の関数については下記で説明をする

defmodule ALU do
  def lst_converter(x, y), do: Enum.map(Enum.zip(x, y), fn {a, b} -> [a, b] end)
  def lst_converter(x, y, sel), do: Enum.map(Enum.zip(x, y), fn {a, b} -> [[a, b], sel] end)
  def val_creater(val, len), do: Enum.map(1..len, fn _ -> val end)
  def compute(x, y, zx, nx, zy, ny, f, no) do
    nxout = common_calc_gate(x, zx, nx)
    nyout = common_calc_gate(y, zy, ny)

    merge_nx_ny = lst_converter(nxout, nyout)
    xandyout = NbitRogicalGate.and_(merge_nx_ny)
    xaddyout = NbitAdder.nbit_adder(merge_nx_ny)

    input_f = lst_converter(xandyout, xaddyout, f)
    fout = NbitRogicalGate.mux(input_f)
    not_fout = NbitRogicalGate.not_(fout)
    merge_fout = lst_converter(fout, not_fout, no)
    out = NbitRogicalGate.mux(merge_fout)
    ng = Enum.at(out, 0)
    zr = if Enum.member?(out, 1), do: 0, else: 1
    {out, zr, ng}
  end
  def common_calc_gate(lst, zero_key, not_key) do
    false_ = val_creater(0, length(lst))
    inputs = lst_converter(lst, false_, zero_key)
    mux_out = NbitRogicalGate.mux(inputs)
    not_out = NbitRogicalGate.not_(mux_out)

    inputs_out = lst_converter(mux_out, not_out, not_key)
    NbitRogicalGate.mux(inputs_out)
  end
end

補助関数について

演算をよしなに進めるためにリストの構造を変化させるlst_converter関数とval_creater関数をそれぞれ実装している
lst_converter関数は2つのリストを以下のように変換している

x = [1,0,1,1]
y = [1,1,1,0]

converted = lst_converter(x, y)
# [[1, 1], [0, 1], [1, 1], [1, 0]] 

# selがある場合(引数が3つの方にマッチ)
x = [1,0,1,1]
y = [1,1,1,0]
sel = 0

converted = lst_converter(x, y, sel)
# [[[1, 1], 0], [[0, 1], 0], [[1, 1], 0], [[1, 0], 0]] 

val_creater関数は受け取った値を指定サイズ分のリストにして返す

val = 1
len = 8
created = val_creater(val, len)
# [1, 1, 1, 1, 1, 1, 1, 1]

ALUのメイン実装

先ほど説明したzx -> nxとzy -> nyの処理は全く同じ処理なので
common_calc_gateという関数で一般化している
論理ゲートでifの動きを再現したい時はmuxを使えば上手くいく

def common_calc_gate(lst, zero_key, not_key) do
    false_ = val_creater(0, length(lst))
    inputs = lst_converter(lst, false_, zero_key)
    # 全て0のリストと入力リストのどちらを採用するか
    mux_out = NbitRogicalGate.mux(inputs)
    not_out = NbitRogicalGate.not_(mux_out)

    # zxもしくはzyの出力を反転するかどうか
    inputs_out = lst_converter(mux_out, not_out, not_key)
    NbitRogicalGate.mux(inputs_out)
  end

次にcommon_calc_gate関数を通して出力された2つのリストからandとaddを実行する
あとはfとnoのselを考慮して先ほどと同じ仕組みでifをmuxで再現する
ngとzrについてはEnumを使って算出しているが、参考にしたコードでもスライス使ってたので良しとした
zrの方だけOrで書き直してもいいかもしれない

defmodule ALU do
  def compute(x, y, zx, nx, zy, ny, f, no) do
    nxout = common_calc_gate(x, zx, nx)
    nyout = common_calc_gate(y, zy, ny)

    # リストを整形
    merge_nx_ny = lst_converter(nxout, nyout)

    # andとaddを計算
    xandyout = NbitRogicalGate.and_(merge_nx_ny)
    xaddyout = NbitAdder.nbit_adder(merge_nx_ny)

    # リストを整形
    input_f = lst_converter(xandyout, xaddyout, f)

    # andかaddのどちらを採用するか
    fout = NbitRogicalGate.mux(input_f)
    not_fout = NbitRogicalGate.not_(fout)
    merge_fout = lst_converter(fout, not_fout, no)

    # 値を反転するかどうか(sel: no)
    out = NbitRogicalGate.mux(merge_fout)

    # ngとzrの値を取得
    ng = Enum.at(out, 0)
    zr = if Enum.member?(out, 1), do: 0, else: 1
    {out, zr, ng}
  end

今回作成するALUはオーバーフローに対応させないため 以前実装した加算器からオーバーフローの対応を一時的に抜いておく

defmodule NbitAdder do
  #再帰関数: リストが空になったら終了
  # accumにcarryの追加をしないように変更
  # defp _nbit_adder([], carry, accum), do: [carry] ++ accum
  defp _nbit_adder([], _carry, accum), do: accum
  defp _nbit_adder([[a1, b1] | tail], carry, accum) do
    {c0, s0} = full_adder(a1, b1, carry)
    _nbit_adder(tail, c0, [s0] ++ accum)
  end
end

一応、ALUの実装は出来たのでやはりテストコードを実行する

x = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
y = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

test1 = [
  ALU.compute(x,y,1,0,1,0,1,0) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,1,1,1,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
  ALU.compute(x,y,1,1,1,0,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,0,0,1,1,0,0) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,1,1,0,0,0,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,0,0,1,1,0,1) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,1,1,0,0,0,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,0,0,1,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,1,1,0,0,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
  ALU.compute(x,y,0,1,1,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
  ALU.compute(x,y,1,1,0,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,0,0,1,1,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,1,1,0,0,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],0,1},
  ALU.compute(x,y,0,0,0,0,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,0,1,0,0,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
  ALU.compute(x,y,0,0,0,1,1,1) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,0,0,0,0,0,0) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,0,1,0,1,0,1) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1}
]

IO.inspect(test1)
# [true, true, true, true, true, true, true, ... true, true, true, true] すべてtrue

x = [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1]
y = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1]

test2 = [
  ALU.compute(x,y,1,0,1,0,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],1,0},
  ALU.compute(x,y,1,1,1,1,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],0,0},
  ALU.compute(x,y,1,1,1,0,1,0) == {[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],0,1},
  ALU.compute(x,y,0,0,1,1,0,0) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1],0,0},
  ALU.compute(x,y,1,1,0,0,0,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],0,0},
  ALU.compute(x,y,0,0,1,1,0,1) == {[1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0],0,1},
  ALU.compute(x,y,1,1,0,0,0,1) == {[1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0],0,1},
  ALU.compute(x,y,0,0,1,1,1,1) == {[1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1],0,1},
  ALU.compute(x,y,1,1,0,0,1,1) == {[1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1],0,1},
  ALU.compute(x,y,0,1,1,1,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0],0,0},
  ALU.compute(x,y,1,1,0,1,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0],0,0},
  ALU.compute(x,y,0,0,1,1,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],0,0},
  ALU.compute(x,y,1,1,0,0,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0],0,0},
  ALU.compute(x,y,0,0,0,0,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0],0,0},
  ALU.compute(x,y,0,1,0,0,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0],0,0},
  ALU.compute(x,y,0,0,0,1,1,1) == {[1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0],0,1},
  ALU.compute(x,y,0,0,0,0,0,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],0,0},
  ALU.compute(x,y,0,1,0,1,0,1) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1],0,0},
]

IO.inspect(test2)
# [true, true, true, true, true, true, true, ... true, true, true, true] すべてtrue

いいですね。そろそろこのテスト方法はしんどくなってきたが
ライブラリなしで実行できるので割と気に入っている

とりあえず、情報学部でも何でもないがALUの実装までをElixirで出来た
Elixirの実装の前にhdlというもので実装を行なっており、hdl + Elixirで実装するため
かなり時間がかかっているが言語を変えて実装してみるというのは非常に勉強になる
Elixirの勉強になる上にcsの勉強にもなるため、この勉強法はかなりアリだと思っている

めちゃくちゃ長くなってしまった。過去最高の13000文字。どひゃー