ハードウェアシミュレータその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を作ってみたいところ。