実装結果と考察

と同様に，Pentium 4 1.7 GHz，メモリ容量が512MB，OS が FreeBSD 5.4，コン パイラが gcc 3.4.2 である．R1IKM，R2IKM，R3IKM とexflib の演算時間を比較 したグラフを図4.16に示す．グラフの x 軸と y 軸はそれぞれ乗算ビット長と演算

2^0 2^2 2^4 2^6 2^8 2^10 2^12 2^14 2^16 2^18

2^0 2^2 2^4 2^6 2^8 2^10 2^12

time [ns]

bit

R3IKM R2IKM R1IKM exflib

図4.16 IKM とソフトウェア Karatsuba乗算 (exflib)の速度比較

時間を対数で表している．また，図中の破線は傾き 1.58 の直線であり，Karatsuba アルゴリズムによる演算時間の理論値を示している．グラフから，exflib の測定値は 理論値に近いことがわかる．また，R1IKM，R2IKM，R3IKM の測定値もまた理論 値に近い．このことから，再帰の回数を増やした場合でも，ソフトウェアに対する性 能比はほぼ一定であることがわかる．ただし，再帰の回数を増やすと，PPG，ACC 内部のバッファの容量が増えるため面積は増加する．また，図から，基本ビット長が 大きいほど高い性能が得られ，基本ビット長を 32，64，128にした IKMは，ソフト ウェアと比較してそれぞれ約 5，10，30 倍の性能を持つことがわかる．この時，表 4.14の中で最も大きい面積は，基本ビット長を 128 にした R3IKM の 10.9mm² で あり，十分に実現可能な大きさである．

表 4.14 から，基本ビット長を 128 とした 1024 ビット R3IKM の消費エネル ギーは，663nJ(=1874mW×353.9ns) であることがわかる．一方，ソフトウェアの 場合，Pentium 4 1.7GHz の消費電力は約 63W であり[48]，856 ビット(10進256 桁)の乗算に要する計算時間が約 6366ns であった．したがって，消費エネルギーは 401µJ(=63W×6366ns)となり，ハードウェアの約 600 倍であることがわかった．

次に，R1IKM，R2IKM，R3IKM について，基本ビット長を変化させた場合の面 積の変化をグラフにしたものを図 4.17に示す．グラフの x 軸は乗算ビット長を対

2^-10 2^-8 2^-6 2^-4 2^-2 2^0 2^2 2^4 2^6 2^8 2^10

2^2 2^4 2^6 2^8 2^10 2^12

area [mm^2]

bit

x-bit R1IKM x/2-bit WTM (for R1IKM) x-bit R2IKM x/4-bit WTM (for R2IKM) x-bit R3IKM x/8-bit WTM (for R3IKM)

図4.17 乗算ビット長x に対する各IKM の面積変化

数で，y 軸は面積を対数で表している．図中の□，○，△はそれぞれ，基本乗算器 のビット長を 4 から 128 にしたときの R1IKM，R2IKM，R3IKM の面積を表し ている．また，■，●，▲はそれぞれ，R1IKM，R2IKM，R3IKM に使われている WTM の面積を表している．したがって，横軸 x に対してそれぞれビット長 x/2， x/4，x/8 における WTM の面積を意味している．

図4.17からわかるように，各 IKM の面積は，ビット長が大きくなるにしたがっ て，それぞれ内部で用いられている WTM の面積に近づいている．この理由につい て考察する．IKMの面積の内訳は主に WTM，PPG Buffer，ACC Buffer，加算器 である．これらについて個別に考察する．まず，各バッファのエントリ数は再帰の回 数のみに依存する．よって，再帰の回数を変えずに基本ビット長を増やした場合，そ の数は変わらない．ただし，エントリ長は増加する．よって，PPG Bufferと ACC

Buffer の面積は O(n) である．加算器の面積については明らかに O(n) である．各

IKM の内部で用いられている WTM の面積については図から O(n^1.70) であること がわかる．本来のWTM における面積の理論値はO(n²)である．この差は，合成時 に速度優先の制約条件を与えたためであると考える．実際に面積優先で合成した結 果，面積は O(n^1.90) であり．理論値に近いものとなった．よって，これらの構成要 素のなかで最も高いオーダを持つのが WTM であり，乗算桁数が大きくなったとき に WTM の面積が支配的になるため，図のように WTM と，その WTM を用いた IKM の面積の差は小さくなる．また，基本乗算器のビット長を変えずに再帰の回数 を増やした場合の面積増加については図から O(n) であることがわかる．