第8回分

ブースのアルゴリズム

Xは初め以外符号を考慮しないように見えるのですが，floatでも，回路は別でも手法は似たようなもので(セレクタでは大変そうですが)できるのですか．

実は最後の全体構成(部分積の和のところ)で符号が効いてきます。

Nが奇数のときは，式が変わったりするのですか．

基本的にはブースの方法はNが偶数の場合しか適用しませんね。

QNが補数になるのがわからなかった．

補数→2の補数、のことですよね。 QN=1のときは、マイナスをつける=2の補数をとる、という意味です。

実際のALUでは，加算と乗算を1つのブロックで表していますがこれもやはりシグナルで機能を切り替えているということなのですか．

そういうことになります。

Y→Zjを求める部分を含めると並列乗算回路と比べてどのくらい早くなるのですか．加算回数1/2はやはり効率的ですか．

その加算(部分積の和)の回数が半分、というのがかなり効果的で、ほぼ2倍になる、と考えてよいと思います。具体的な比較例は次回紹介します。

Yを切り替えることによって，どれだけ何がやりやすくなったのかわからなかった．

Yjを求めるところで、乗算をしなくてもシフトと加算(2の補数を求める)だけでできる、というのがポイントです。

YとYjがたくさん出てきてどっちがどっちかわからなくなりそう．

ぜひ整理してみましょう。

Yj=y2j+y2j-1-2y2j+1とは何なのかわかりませんでした．また，これは演算量が増えるのではないでしょうか．

Yjは、そのように置くと、うまくいく、という意味ですね。で、見かけ上演算は増えるように見えるのですが、求められるYjは、実はBTDで比較的単純な論理回路で求められますし、それから必要なZjも、シフトとマイナス(2の補数)だけで求められるので、実はそれほど演算量は増えません。それよりも、部分積の段数が半分になる効果の方が大きいです。

0～(N-2)/2とはなんですか．

Zj部分積を足すのが、j=0～(N-2)/2ですから、N/2個、という意味でした。

y2j，y2j-1，y2j+1の組み合わせが8通りしかないことは計算する上で意味があるのですか．

真理値表から、Q1、Q2、QNを求めることができるので、比較的単純な論理回路だけで済む、というのがメリットになります。

ZがZjのN/2個の加算で求められるという点がよくわからなかったので復習したい．

ぜひ。

ブースのアルゴリズムは並列乗算器の改良型ですか．それともと独立したべつの手法なのですか．Yjを求める時点で加算している点において計算量は増えるのでは．Xの段数増は速度に影響はないのですか．応用で演算が早くなりそうな気がします．

ブースの方法は、並列乗算器の改良というより、まったく別の方法、と考えたほうがよさそうです。 Yjの演算量の増加は、前述の通り、結果としてそれほど大きくありません。

演算時間∝0(N)の書き方に違和感がありました．どの変数に対して比例というもので∝はどう読めばいいのですか．

たしかにちょっとへんな書き方ですね。「演算時間～O(N)」というところでしょうか。 ∝は、比例、という意味ですね。

ブースのアルゴリズムの唐突なYの導出方法が気になります．また，複雑でついていけません．なぜ演算時間が半分になるのですか．

たしかにYjの導出は、唐突ですが、結果としてうまくいく、ということでお許しください。 Yj→Zjを加算する回数がN/2ですむので、演算時間が(ほぼ)半分になります。

乗数が整数でなく，小数点を含むもの(例1.5)でもブースのアルゴリズムは有効なのですか．

実数を、固定小数点であらわすのであれば、そのまま使えそうです。浮動小数点表現の場合は、いろいろと面倒なことが増えますね。 (指数部は加算する、仮数部を丸める、など)

ブースのアルゴリズムはIntelなどでも使われているのですか．乗算の高速化には他に何がありますか．

Intelのプロセッサの中の乗算器が何かはわかりませんが、結構使われていそうな気はします。乗算器の高速化は、次回も少し触れますが、いろいろと独立な手法があって、いくつかを組み合わせる、ということになります。

並列回路がブースのアルゴリズムよりよい点はありますか．

構成が規則的で単純、というぐらいで、実はあまりないんじゃないかと思います。

ブースのアルゴリズムでX=-2^(N-1)xn-1＋∑xn2^nとなるのがわからないです(おかしい気がします)．

最後のΣの中のxn・2^nは、xi・2^i、でしょうか。もしそうであれば、間違っていないはずですが・・・

3次のブースのアルゴリズムは乗算器に用いればもっと高速化できるのですか．

たしかに部分積の段数は減るのですが、デコード部分の複雑度が増すので、結果としてあまり効果はなさそうです。

ブースのアルゴリズムを使うと並列乗算回路より回路規模は大きくなるのですか．

いえ、結果として部分積の段数が半分になりますので、回路規模は(一般には)小さくなります。

その他

高速化のためには長い式と努力が必要なのだとしみじみ感じられる授業でした．

たしかにそうですね。

一枚の黒板に書くことが少なすぎて前の黒板を消すペースが速いと感じました．

ちょうど区切りが悪くて、確かにそういうところが多かったですね。気をつけます。

講義前半の部分を復習する必要があると思う．

ぜひがんばってください。

最後の方でたくさんの表・式が出てきたので，整理しながらやってくれるとわかり易かった．

いろいろと整理しながら進めたつもりだったのですが、いかんせん式や真理値表が多いので、整理しきれませんでした。すいません。練り直してみます。

Yjもなんとか理解できましたが，100％ではないです．

ぜひノートを読み返してみてください。

レポートでカルノー図以外の出し方がわかりませんでした．

それは、ぜひ論理回路の復習を・・・

レポートの模範解答ってありますか．

用意したいと思います。

戻る