第8回分

(ブースのアルゴリズム(以下ブース)関連)

ブースによって結局段数はどのくらい減るのか

ブースを用いて、本当に計算時間の短縮が出来るのか

部分積の段数は、講義中に求めたように、並列乗算器の半分になります。

ずいぶん賢いやり方だと思うが、どうやったら思いつくのだろうか

ひらめき、じゃないですかね。

乗算回路はすべてブースを使って設計されているのか

かなり多いはずです。

ブースを使った乗算器はどのような回路になるのか

それは次回のお楽しみ・・・

Nが奇数の場合でも成り立つのか

それは無理ですので、1桁増やして偶数にします。 (ただ奇数ビット数の乗算器、というのは、あまりないような・・・)

ブースを用いた場合の問題点はないのか

動作が直感的に理解しにくい、というぐらいじゃないでしょうか。

左ビットシフトを用いて除算は出来ないのか

除算は右シフト、乗算は左シフト、ですね。もちろんできます。次回お話しますが、実はブースのアルゴリズムを使った乗算器でも、部分積の中に出てくる2^2jなどをかける部分を、左シフト演算として行います。

Yjを使うと段数が半分になる理由が分からない

なかなかよくできた理屈ですので、再度、読み返してください。

(N-2)/2回計算するのにN/2段の回路で済むという過程がわからない

n=0～(N-2)/2までΣで(部分積の)和を求めるわけですから、 N/2回の(部分積の)加算を行うことになります。

ブースよりも高速な方法は無いのか

実はいろいろと工夫の仕方はあって、乗算器の3回目にお話しますが、ブースのアルゴリズムと併用できるワレスの木、という方式もあります。

ブースを使用した場合のエネルギー効率はどうなるのか

消費電力のことですかね。部分積を求める加算器(CSA)の回路規模が、並列乗算器の半分近くになりますから、消費電力も減るはずです。

ブースで1桁×1桁のような桁数の少ない計算の場合は無駄な計算をするのか

それはそのとおりですが、そのような桁数の少ない乗算器は、あまり作りません。

ブースで、Q1、Q2、Qnがあるが、QnだけなぜQnなのかが気になる

負(Negative)のN、ですね。

シフト演算や2の補数を取る操作で処理段数は増えないのか

詳しくは次回お話しますが、シフト演算は、部分積を足す加算器を「ずらして配置する」ことで行われます。また2の補数を取る操作も、巧妙につくることができます。

Zjを求める意味がわからない

それが部分積で、それを足せば、乗算の結果Zを求められるから、ですね。

｢ブース｣というのは人名なのか

そうです。

Yj=y_2j+y_2j-1-2y_2j+iを考えた人はすごいと思った

そうですね。

ZはXを左シフトするだけで出来そうなので、並列の時の半分よりも早くなるのではないか

Zjのことでしょうか。詳しくは次回お話しますが、まさにそのとおりです。

8通りの操作に分けてYjを求めるのはYjを求めてからZjを求めるのではなく、直接Zjを求めるからということなのか

詳しくは次回お話しますが、まさにそのとおりです。

部分積の段数を減らすことより乗算器の高速化に効果的な方法は何か

乗算器の構成(アーキテクチャ)のレベルでは、部分積の削減が一番です。もちろんこれとは別に、集積回路ですから、回路を構成するトランジスタの微細化(スケーリング)も有効です。

並列乗算回路の1段目はBCでないといけないのか

たしかにFAの部分は不要ですね。ただし集積回路として設計する上では、以前にもお話したように、規則的な構造、のほうが好都合ですから、BCのままにしておくのがよさそうです。

並列乗算器はCSAと同様に計算をある程度のブロックに分ければ速くなるのか

並列乗算器自体がCSAのように、部分積の和を求める過程でキャリーの伝播がありませんから、あの構成の並列乗算器自体の高速化は無理でしょうね。あえて言えば、最後の段でキャリーの伝播を吸収するところを、 RCAではなくBCLAなどを使う方法はあります。

｢論理式で書けるので速くなる｣という意味が分からない

素直にYjを加算と減算で求めると、加算器や減算器の演算時間が必要になり、また回路規模も大きくなりますが、 y_2jなどの値が0または1であることを使うと、真理値表で書くことができ、したがってブール代数の論理式として積和標準形で書くことができます。積和標準形で書かれた論理式を求める回路は、原則として論理ゲート3段分(NOTゲート＋積項をつくるANDゲート＋最後に積項の論理和をとるORゲート)でできますから、高速になる、ということです。

加算器も乗算器も高速化のための様々な手段があるのことに驚いた

よく使われる機能ブロックですから、いろんな人が知恵を絞るんでしょうね。

回路を描くのに便利なソフトは何?

個人的には、YS-Drawというソフトを愛用しています。シェアウエアではありますが、Illustratorのような機能をもち、また動作も軽快です。またMicrosoftのVisioも、なかなかよいようですね。

11/28提出分のレポートは後で返却されるのか

はい、もちろんです。来週を目標に採点がんばります。

戻る