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

今回は除算器。割り算である。
割り算はものすごく単純に考えると、引き算を繰り返す処理になる。最後、引きすぎた場合に1回分戻して余りを求めることになるが、この手法を引き戻し法と言う。
ハードウェアで割り算をする場合、引き算を繰り返すのは非常に効率が悪いので、掛け算と同様にシフトした値を引くようにして計算回数を抑える。んでも結局、ビット数分の計算は必要になり、それをクロック単位でまわすと単純計算で32bitの除算に32クロックかかることになる。このアルゴリズムRadix-2と言うらしいが難しいことはよくわからない。2ビットずつ処理する(Radix-4)ようにするとクロックは半分になるが、0倍〜3倍の値を計算して減算する必要があるのでそれなりに重くなる。この問題を解決するのにSRT法なる計算方式があって、現在のCPUはSRT法によるRadix-4で実装されているらしい。H8マイコンなんかを調べてみると32bitの除算で22クロックなので、やはりそうなのだろう。また、昔話題になったPentiumの除算バグの原因もSRT法まわりのようだ。インテルは最近のCPUではRadix-16で割り算するらしいので更に速い。
さて、シミュレータ上で割り算をするのにそういった難しいことをする必要は無いので、加算器をアホほど直列接続して1クロック除算を実現してみようと思う。実際の回路でこんなことをするとクロックがアホほど下がるし規模もアホほど大きくなるしで恐ろしく非効率になるのでオススメできない。

2bitの割り算

まずはビット幅固定で作ってみることにする。割り算のイメージは掛け算と同様に筆算である。最上位から順に引き算してみて、引けたら引き、引けなかったら引かずに、次の桁の計算に移る。加算器で減算する場合、キャリー出力は引けたら1になるので、これをマルチプレクサに突っ込んで次の値を選択する。また、同様にキャリー出力を並べると商が求まる。最後に残った値が剰余になる。

# 符号なし2bit除算器
class Divider2
  def initialize
    # 入力線
    @buf0 = Buffer.new(2) # 被除数
    @buf1 = Buffer.new(2) # 除数

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

    # 被除数
    @dividend = [opl] + @buf0.o

    # 除数をシフトした配列を作る
    @divisor = [@buf1.o + [opl], [opl] + @buf1.o]

    # 除算は加算器で行う
    @adder = [Adder.new(3), Adder.new(3)]

    # 1段目の減算
    @adder[0].x = oph
    @adder[0].d = [@dividend, @divisor[0].map{|d|~d}]

    # 引けたかどうかで次の段の値を選択する(減算なのでキャリー出力1の場合に引けたと考える)
    @mux1 = Mux1_n.new(3)
    @mux1.s = @adder[0].c
    @mux1.d = [@adder[0].o, @dividend]

    # 2段目の減算
    @adder[1].x = oph
    @adder[1].d = [@mux1.o, @divisor[1].map{|d|~d}]

    # 引けたかどうかで結果を選択する
    @mux2 = Mux1_n.new(3)
    @mux2.s = @adder[1].c
    @mux2.d = [@adder[1].o, @mux1.o]

    # adderのキャリー出力が商になり、mux2の出力が剰余になる。
    @q = @adder.map{|a|a.c}

  end

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

  def q # 商
    @q
  end

  def r # 剰余
    @mux2.o[1,2]
  end

  def inspect
    "dividend = " + @dividend.map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    "divisor[0] = " + @divisor[0].map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    "divisor[1] = " + @divisor[1].map{|o|"#{HLHASH[o.get]}"}.join + "\n" +  
    "mux1 = " + @mux1.o.map{|o|"#{HLHASH[o.get]}"}.join + "\n" + 
    "adder[1].o = " + @adder[1].o.map{|o|"#{HLHASH[o.get]}"}.join + "\n" +  
    "adder[0].c = " + "#{HLHASH[@adder[0].c.get]}"+ "\n" +  
    "adder[1].c = " + "#{HLHASH[@adder[1].c.get]}"+ "\n" +  
    "q = " + q.map{|o|"#{HLHASH[o.get]}"}.join +  "\n" + 
    "r = " + r.map{|o|"#{HLHASH[o.get]}"}.join
  end
end

_vcc = Line.new
_gnd = Line.new
vcc = _vcc.o
gnd = _gnd.o
s0 = Line.new
s1 = Line.new
s2 = Line.new
s3 = Line.new
dividend = [s1.o, s0.o]
divisor = [s3.o, s2.o]

divider = Divider2.new
divider.d = [dividend, divisor]

_vcc.d = H
_gnd.d = L

# 3 / 2
s1.d = H
s0.d = H

s3.d = H
s2.d = L

p divider
#=> dividend   = LHH
#=> divisor[0] = HLL
#=> divisor[1] = LHL
#=> mux1       = LHH
#=> adder[1].o = LLH
#=> adder[0].c = L
#=> adder[1].c = H
#=> q = LH
#=> r = LH

被除数の最上位ビットと除数の最下位ビットが重なるところから計算が始まるので、2ビット同士の割り算は3ビット幅の加算器が必要となる。dividendからdivisor[0]を引いて、その結果からdivisor[1]を引いて、そのキャリー出力がqとなり、残った値がrとなる。3/2は1余り1である。

可変長除算器

さて、ではこれをそのまま可変幅に対応してみる。こんな手法で32bit除算器とか作ると32個の63bit加算器が直列に並ぶことになるので、もし仕事でこんなん作ったらその場でクビ宣告されても文句は言えない。

# 符号なし除算器
class Divider
  def initialize(bit_width)
    @bit_width = bit_width
    # 入力線
    @buf0 = Buffer.new(bit_width) # 被除数
    @buf1 = Buffer.new(bit_width) # 除数

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

    # 被除数
    dividend = [opl] * (bit_width * 2 - 1)
    dividend[bit_width - 1, bit_width] = @buf0.o

    # 除数をシフトした配列を作る
    divisor = Array.new(bit_width) do |i|
      tmp = [opl] * (bit_width * 2 - 1)
      tmp[i, bit_width] = @buf1.o
      tmp
    end

    # 減算器を構成する
    @adder = Array.new(bit_width){Adder.new(bit_width * 2 - 1)}
    @mux = Array.new(bit_width){Mux1_n.new(bit_width * 2 - 1)}
    @adder[0].x = oph
    @adder[0].d = [dividend, divisor[0].map{|d|~d}]
    @mux[0].s = @adder[0].c
    @mux[0].d = [@adder[0].o, dividend]
    
    (1..(@adder.size-1)).each do |i|
      @adder[i].x = oph
      @adder[i].d = [@mux[i - 1].o, divisor[i].map{|d|~d}]
      @mux[i].s = @adder[i].c
      @mux[i].d = [@adder[i].o, @mux[i - 1].o]
    end

    @q = @adder.map{|a|a.c}
  end

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

  def q
    @q
  end

  def r
    @mux.last.o[-@bit_width..-1]
  end

  def inspect
    q.map{|o|"#{HLHASH[o.get]}"}.join + "\n" +
    r.map{|o|"#{HLHASH[o.get]}"}.join
  end
end

_vcc = Line.new
_gnd = Line.new
vcc = _vcc.o
gnd = _gnd.o
s0 = Line.new
s1 = Line.new
s2 = Line.new
s3 = Line.new
s4 = Line.new
s5 = Line.new
s6 = Line.new
s7 = Line.new
d0 = Line.new
d1 = Line.new
d2 = Line.new
d3 = Line.new
d4 = Line.new
d5 = Line.new
d6 = Line.new
d7 = Line.new
dividend = [s7.o, s6.o, s5.o, s4.o, s3.o, s2.o, s1.o, s0.o]
divisor = [d7.o, d6.o, d5.o, d4.o, d3.o, d2.o, d1.o, d0.o]

divider = Divider.new(8)
divider.d = [dividend, divisor]

_vcc.d = H
_gnd.d = L

# 255 / 10
s7.d = H
s6.d = H
s5.d = H
s4.d = H
s3.d = H
s2.d = H
s1.d = H
s0.d = H

d7.d = L
d6.d = L
d5.d = L
d4.d = L
d3.d = H
d2.d = L
d1.d = H
d0.d = L

p divider
#=> LLLHHLLH # 25
#=> LLLLLHLH # 5

現実的な話

実際のところ、CPU用に除算器を作るとなるとこんな方法はありえなくて、1クロック内の計算時間を短くしないとCPUのクロックが上がらない。なので、除算は複数クロックに分割するように作ることになる。いずれSRT法によるRadix-4も実装してみたいところだが、それはずっと先の話だろう。
今は遅くても現実的でなくてもいいからシミュレータ上で使える計算の回路が必要なのである。
あと、加算器も相当手抜きで、最もシンプルにだらだら繋いでしまっているが、キャリーの伝播のせいで全加算器の直列接続となっている。キャリー計算は別回路でするキャリー先読みというテクニックがあり、本来ならそういう回路を構成するべきなんだろうと思う。まあ、これもずっと先の話。
ともあれ、符号あり除算がまだ無いけどほぼ四則演算が揃ったということで、これらを使える命令セットを考えて前回の4bitCPUよりもうちょい機能のあるCPUを作ってみたいところ。