ハードウェアシミュレータその１５

今回のネタは乗算。掛け算である。
最近の多くのCPUには乗算命令が装備されているが、乗算回路は規模が大きくなりがちなので、昔はそんなもの無いか、多くのクロックを消費して実行する形だった。さすがに足し算を延々繰り返すような実装はしないだろうが、シフトと加算を繰り返すような感じだろう。
2進数の乗算は筆算のイメージで考えればシフトと加算で処理できるのがわかる。乗算回路の基本はそれで、こことかを見ると丁寧に解説されている。簡潔で難しいがWikipediaでもよい。
つまりビット幅に応じてシフタと加算器を大量に作れば乗算は1発で結果を出すこともできるわけで、最近のCPUではそのような回路により1クロックで結果を出す。らしい。シミュレータ上の回路も別に規模や速度は意識していないので同様に1クロックで処理できるように構成する。

シフトした値を作る回路

シフトするのは前にシフタを作ったのでそれを使えばいいのだが、固定幅の固定回数シフトなのでバレルシフタを使う必要もなく、それ以前に出力ピン配列をずらせばいいだけなので、乗算回路に埋め込んでしまうことにする。

# 符号なし乗算器
class Multiplier
  def initialize(bit_width)
    # 入力線
    @buf0 = Buffer.new(bit_width)
    @buf1 = Buffer.new(bit_width)

    # L固定の出力ピン
    opl = OutputPin.new(L)

    # シフトした配列を作る
    @buf = Array.new(bit_width) do |i|
      tmp1 = [opl] * (bit_width * 2) # Lの出力ピンをbit_width*2だけ並べた配列
      tmp2 = @buf0.o.map{|b|b & @buf1.o[bit_width - i - 1]} # buf0の各bitとbuf1の1bitのandを取る
      tmp1[bit_width - i, bit_width] = tmp2 # tmp1配列の一部をtmp2に差し替える
      tmp1
    end
  end

  def d=(v)
    @buf0.d = v[0]
    @buf1.d = v[1]
  end

  def inspect
    @buf[0].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    @buf[1].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    @buf[2].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    @buf[3].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    @buf[4].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    @buf[5].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    @buf[6].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    @buf[7].map{|o|"#{HLHASH[o.get]}"}.join + "\n"
  end
end

_vcc = Line.new
_gnd = Line.new
vcc = _vcc.o
gnd = _gnd.o

mult = Multiplier.new(8)
mult.d = [[vcc, vcc, gnd, vcc, vcc, vcc, vcc, vcc], # d1
          [vcc, gnd, vcc, vcc, gnd, vcc, vcc, vcc]] # d0

_vcc.d = H
_gnd.d = L

p mult
#=> LLLLLLLLHHLHHHHH
#=> LLLLLLLHHLHHHHHL
#=> LLLLLLHHLHHHHHLL
#=> LLLLLLLLLLLLLLLL
#=> LLLLHHLHHHHHLLLL
#=> LLLHHLHHHHHLLLLL
#=> LLLLLLLLLLLLLLLL
#=> LHHLHHHHHLLLLLLL

という感じでシフトした値を生成しておいて、あとはこれらを全部ガシャーンと加算すればできあがりである。内部のバッファはinitialize時に回路を構成するために使っているが、d=で構成するようにすれば必要なくなる。シミュレータの効率を上げる必要性がでてきたらそういった修正を入れていくことである程度は対処できそうである。同様の考えでシフタの効率も改善できそうだ。

加算回路

加算はAdderクラスを使えばよい。例えば8個の値を加算するなら7個のAdderを直列に接続すればいいが、ツリー状に構成することで段数を減らせる。ハードウェアは並列に動作できるので段数が減ると結果が出るまでの時間が減る。入力の変化による影響範囲が減るのでシミュレータの効率も良くなると思われる。たぶんだけど。

require './hsim'

# 符号なし乗算器
class Multiplier
  def initialize(bit_width)
    # 入力線
    @buf0 = Buffer.new(bit_width)
    @buf1 = Buffer.new(bit_width)

    # L固定の出力ピン
    opl = OutputPin.new(L)

    # シフトした配列を作る
    buf = Array.new(bit_width) do |i|
      tmp1 = [opl] * (bit_width * 2) # Lの出力ピンをbit_width*2だけ並べた配列
      tmp2 = @buf0.o.map{|b|b & @buf1.o[bit_width - i - 1]} # buf0の各bitとbuf1の1bitのandを取る
      tmp1[bit_width - i, bit_width] = tmp2 # tmp1配列の一部をtmp2に差し替える
      tmp1
    end

    # シフトした値を加算するための加算器
    @adder = Array.new(Math.log(bit_width, 2)){|i|Array.new(2**i){Adder.new(bit_width*2)}}
    @adder.last.each.with_index do |adder, i|
      adder.d = [buf[i * 2], buf[i * 2 + 1]]
      adder.x = opl
    end
    (1...(@adder.size)).each do |i|
      @adder[i-1].each.with_index do |adder, j|
        adder.d = [@adder[i][j * 2].o, @adder[i][j * 2 + 1].o]
        adder.x = opl
      end
    end
  end

  def d=(v)
    @buf0.d = v[0]
    @buf1.d = v[1]
  end

  def o
    @adder[0][0].o
  end

  def inspect
    o.map{|o|"#{HLHASH[o.get]}"}.join
  end
end

_vcc = Line.new
_gnd = Line.new
vcc = _vcc.o
gnd = _gnd.o

mult = Multiplier.new(8)
mult.d = [[vcc, vcc, gnd, vcc, vcc, vcc, vcc, vcc], # d1 #=> 223
          [vcc, gnd, vcc, vcc, gnd, vcc, vcc, vcc]] # d0 #=> 183

_vcc.d = H
_gnd.d = L

p mult #=> HLLHHHHHLHHLHLLH #=> 40809

符号付き乗算

これは理屈がよくわかっていないのだが、符号付きの値が2の補数であれば、その特性をうまいこと使うことで筆算のイメージにちょいと細工すればできるらしい。符号はずして計算して後で符号だけ設定したらあかんの？NOTとかガシガシ入れるよりもそっちのほうが効率よさそうな気がするんだけど、ダメな理由がわからん。

require './hsim'

# 符号あり乗算器
class SignedMultiplier
  def initialize(bit_width)
    # 入力線
    @buf0 = Buffer.new(bit_width)
    @buf1 = Buffer.new(bit_width)

    # HL固定の出力ピン
    oph = OutputPin.new(H)
    opl = OutputPin.new(L)

    # シフトした配列を作る
    @buf = Array.new(bit_width) do |i|
      tmp1 = [opl] * (bit_width * 2) # Lの出力ピンをbit_width*2だけ並べた配列
      tmp2 = @buf1.o[bit_width - i - 1]
      if i == (bit_width-1) # 最後のみ
        # 先頭以外反転
        tmp2 = [@buf0.o[0] & tmp2] + @buf0.o[1..-1].map{|b|~(b & tmp2)}
      else
        # 先頭だけ反転
        tmp2 = [~(@buf0.o[0] & tmp2)] + @buf0.o[1..-1].map{|b|b & tmp2}
      end
      tmp1[bit_width - i, bit_width] = tmp2 # tmp1配列の一部をtmp2に差し替える
      if i == (bit_width-1) or i == 0 # 最初と最後
        tmp1[bit_width - i - 1] = oph
      end
      tmp1
    end

    # シフトした値を加算するための加算器
    @adder = Array.new(Math.log(bit_width, 2)){|i|Array.new(2**i){Adder.new(bit_width*2)}}
    @adder.last.each.with_index do |adder, i|
      adder.d = [@buf[i * 2], @buf[i * 2 + 1]]
      adder.x = opl
    end
    (1...(@adder.size)).each do |i|
      @adder[i-1].each.with_index do |adder, j|
        adder.d = [@adder[i][j*2].o, @adder[i][j*2+1].o]
        adder.x = opl
      end
    end
  end

  def d=(v)
    @buf0.d = v[0]
    @buf1.d = v[1]
  end

  def o
    @adder[0][0].o
  end

  def inspect
    @buf[0].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    @buf[1].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    @buf[2].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    @buf[3].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    @buf[4].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    @buf[5].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    @buf[6].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    @buf[7].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    o.map{|o|"#{HLHASH[o.get]}"}.join
  end
end

_vcc = Line.new
_gnd = Line.new
vcc = _vcc.o
gnd = _gnd.o

mult = SignedMultiplier.new(8)
mult.d = [[vcc, vcc, gnd, vcc, vcc, vcc, vcc, vcc], # d1 => -33
          [gnd, gnd, gnd, gnd, gnd, vcc, vcc, vcc]] # d- => 7

_vcc.d = H
_gnd.d = L

p mult
#=> LLLLLLLHLHLHHHHH
#=> LLLLLLLLHLHHHHHL
#=> LLLLLLLHLHHHHHLL
#=> LLLLLHLLLLLLLLLL
#=> LLLLHLLLLLLLLLLL
#=> LLLHLLLLLLLLLLLL
#=> LLHLLLLLLLLLLLLL
#=> HLHHHHHHHLLLLLLL
#=> HHHHHHHHLLLHHLLH #=> -231

うん、さっぱりわからん。でも結果は合ってるようだ。