Minecraft Redstone D-CCA Multiple&Division(part2)

こんにちはヽ(^0^)ノ

この記事はpart1の続きなので、読んでなければ先ずpart1から見て欲しいです。

乗除算について解説していきます。

この連続加算器は6tick周期でパイプライン演算をしているので時刻毎に割り当てられた6個の連続加算を同時並行でできるが、乗除算を行う際はそのうち2区画を使っておこなう(工夫すれば3個同時並行でできる)。

以後tickはrstickのことを指すとする。

昔私は乗除算をこのDCCA(decimal carry cancel adder)上で同じ手法でできる方法を思いついたので解説する。DCCAの桁数は上限の13桁が出力の限界だが、理論上最大誤差が50(最下位桁が1の位として)出るので出力の有効数字は11桁であるが、平均的な誤差は10程度で済む。

この計算機では小数点の位置をあまり自由に動かすことが出来ないため、入出力の形式は

$A×B\cdots 0≦ A\lt 10, 0≦B\lt 10,0\lt AB\lt 100$ 、有効数字 $12$ 桁

$A÷B\cdots 0≦A\lt 10 ,0\lt B\lt 10,0\lt A÷B \lt 10$

先ず除算 $X÷Y$ について見るが、手順は筆算ベースであり、 $X=6.91、Y=2.73$ を例に取って見ていく(ちなみに $B_{12}=-\frac{691}{2730}$ はベルヌーイ数)

f:id:AkaGhef:20200715222214j:image

中段の $1450,85$ などの数字は部分剰余と言い、無限小数である場合は部分剰余を割る操作を永遠と繰り返すことになるが、計算機は途中で打ち切る。簡単の為に加算器は13桁ではなく6桁とし、小数点は無視する。 $A$ は部分剰余で初期値は被除数 $X$ 、Bを除数 $Y$ (をシフトしたもの)、 $I$ は商をカウントするためのインクリメント[デクリメント]の $±1$ であり、 $O$ は(暫定的な)商で、初期値は $0$ ある。筆算と少し違う点が、次の段の部分剰余を求める際に $A$ から $B×(0〜9)$ を引くのでは無く、 $A$ から $B$ を何回か引いて行う点であり、乗算を使わずに済み、 $0～9$ の値を見積もる必要が無い。
$AからB$ を引く度に $OにI$ を足すことで商をカウントしている。これを繰り返し $A$ から $B$ を引きすぎたら一旦 $B$ を $A$ に足して修正して、 $OからI$ を引いてカウントをバックしている。これで次の段の部分剰余が求まるので、 $BとI$ を1つシフトダウンしてまた次の段の部分剰余を求める操作を行う。ループは以下の手順。

(1)AからBを負の数になるまで0～9回引く(赤線)
(2)引く毎に $O$ に $I$ を足し、商をカウント(赤線)
(3)Aが負の値になったら $B$ を足す(緑線)
(4) $OからI$ を引き、カウントをバック(緑線)
(5) $BとI$ を1つシフトダウン(青線)

f:id:AkaGhef:20200715222406j:image

次に乗算 $X×Y$ について、 $被乗数X=4.56、乗数Y=1.23$ を例にとって見ていく。

[筆算]

f:id:AkaGhef:20200630072408j:image

3つの数を同時に足しあげるのは計算機的に困難なので2数ずつ足しあげる筆算の書き方をしているが、雰囲気は掴んで貰えるだろう。途中で出てくる $456,5472$ の数字の段(緑矢印)を部分和と呼び、除算同様に小数点は無視する。 $A$ は乗ずる回数の書かれた数で初期値は乗数 $Y$ 、 $B$ は被乗数 $X$ (をシフトしたもの)、 $I$ は乗ずる回数を $A$ からカウントダウンするためのインクリメント[デクリメント]の $±1$ である。 $O$ は部分和の役割で、最終的に積 $X×Y$ の答えとなる。
$AからI$ を引いてカウントダウンし同時に $OにB$ を加える操作を $A$ が負になるまで行う。 $A$ が負になるとカウントし過ぎなので $AにI$ を加え、 $OからB$ を引き修正する。これで部分和が求まったので次の段の部分和を求める為に $BとI$ を1つシフトダウンする。ループをまとめると以下のようになる:

(1) $AからI$ を負になるまで引く(赤線)
(2)引くごとに $OにI$ を足す(赤線)
(3) $A$ が負の値になったら $I$ を足す(緑線)
(4) $OからB$ を引く(緑線)
(5) $BとI$ を1つシフトダウン(青線)

[表]

f:id:AkaGhef:20200715232031j:image

乗除算の類似性と実際の回路の手順について説明していく。図や、乗除算それぞれで示したループの手順を見るとほぼ $BとI$ を入れ替えただけで、処理内容がとても似ていることが分かる。そこで連続加算器がパイプライン処理であったことを巧妙に使って、
計算機のコア内に入っている $OとA$ にタイミングよく $BとI$ を入力することで乗算と除算を使い分けることが出来る。加算器は6tick周期なのでそれと同期できるように $BとI$ を保存する外部のメモリは6tick周期で巡回するコンパレータの構造となる。
パイプライン処理で同時に3個の乗除算を行えるが本解説では1個の乗除算のみに限定し更に高速化を試みる。先程ループの手順を示したが(5)の $BとI$ をシフトダウンする際、6tick周期のメモリの場合

シフトする部分に信号が回ってくるまで待つ必要があるためシフトダウンする部分で遅延が生じて、[表]での緑,青の部分の処理をした後の赤の部分の処理に入力が間に合わない。そこでメモリを2tick周期にしてみると、連続加算器の周期が6tickで、2tickはその約数となっているため、2つのスロットに $B,I$ を入れておくと問題なく処理できる。そして $B,I$ が奇数時刻か偶数時刻にコアに入力されるかどうかで乗算と除算を切り替えられる。(これを閃いた時はまさに最適解だったのでめちゃ嬉しかった)

制御回路で実際に動かしていく方法を見る。今手元に制御回路が完成された乗除算器が無く、申し訳ないが忙しいせいで載せることが出来ない。

f:id:AkaGhef:20200715222825j:image
前回補数の項目で話をしたように、減算結果が負であるかどうかは、減算したときに最上位の繰り上がり出力(以後 $C^O$ と書く)が $C^O=1$ ならば結果は0以上である。乗算の場合 $A-I$ の減算をしたとき $C^O=1$ ならば減算結果が $0$ 以上なので次は赤色の矢印の操作を行い、減算か加算かを制御する(J)の配線をonにして次も減算を行う。逆に $C^O=0$ のとき減算結果が負なので青,緑の矢印の操作を行う、すなわち(J)の信号をoffにし次は加算モードにして、(K)に信号を送って $B,I$ を1つシフトダウンする。また除算の場合は、上記の $A-I$ を $A-B$ に読み替えると全く同様の処理であることが理解出来る。
((J)に信号を送る部分を最小遅延で行える回路の実現がかなり大変で2ヶ月も苦労したんですよね)

以上の手続きをアセンブリ風に書いてみる(だいぶ前に書いたものなので正当性怪しいのでお気持ち程度に...)

アセンブリは、デカい命令が書いてある主記憶装置、演算を行う部分、演算結果を記憶する部分(以下Acc)、の3つに分かれる。命令はadd･subで番地指定した所の値をAccに加えたり引いたり

基本番地が低い所から命令を実行していく。
loadは指定した番地から値を引き出し、Accに上書き。
atoreは指定した番地にAccの値を上書き。
jumpは指定した番地から処理を始める。
jump minusはAccの値が負ならjumpと同じことをする。
本当は無いが、面倒なのでmultipleとdivideという命令を追加し、それぞれ掛ける、割るの命令とした。

f:id:AkaGhef:20200715222648j:image