著者

矢崎 俊志 Syunji Yazaki

出版者

電気通信大学

巻号頁・発行日

2006-03-23

---

本論文は,一般的な汎用プロセッサのビット長を大きく上回る多倍長数の乗算をハードウェアで実現する方法について述べる.多倍長数の演算は高精度の数値計算や素数判定,カオス計算,暗号計算など,多様なアプリケーションに利用されている.多倍長演算はその性質から,多くの時間を必要とする.特に,頻繁に利用される乗算は演算のボトルネックとなり得る.多倍長乗算においてはO(n^2^) の筆算式乗算よりも効率よく乗算を行う様々なアルゴリズムが存在する.代表的なものとして,O(n^1.58^) のKaratsuba 2-way 法,O(n^1.465^) のKaratsuba 3-way 法,O(n^1.404^) のKaratsuba 4-way 法,O(n^1.365^) のKaratsuba 5-way 法,O(n^1.63^) の法算法,O(n log n log log n) の高速フーリエ変換(Fast Fourier Transform, FFT) 法がある.これらの中で,オーダの上で最も高速なのはFFT 法である.しかし,FFT 法は,複素数演算のオーバヘッドが大きく数百から数万ビットの演算における実質的な性能はKaratsuba 法よりも低い.このことから,現在もっとも利用されているアルゴリズムはKaratsuba 法である.ただし,数百万桁の乗算においてはFFT 法の方が高速である.現在,これらの多倍長乗算はソフトウェアによって実現されている.一方,多倍長乗算のハードウェア実装に関する研究としては,ガロア体上の乗算を行うものが多く報告されているが,整数の乗算に関するものはごくわずかである.特にFFT 乗算のハードウェア実装に関する研究は知られていない.本研究の目的は,FFT 法を用いた比較的大きな桁数の多倍長乗算とKaratsuba法を用いた比較的小さな桁数の多倍長乗算をそれぞれハードウェア実装し,ソフトウェアとの比較を行うことでその性能やコストを明らかにすることである. FFT 法のハードウェア実装においては,最大値どうしの乗算が最大の誤差をあたえることに着目し,乗算に必要な精度を求め,それを保証するデータ長でFFT 乗算器をCMOS 0.18μm テクノロジを用いて構成した.その結果,16 進数2^13^ 桁の乗算において,IEEE754 の64 ビット浮動小数点表現を用いた場合と比較して面積を60%,最大遅延時間を26% 削減したFFT 乗算器を実装することができた.さらに最適なパイプライン化を行った結果,同世代のテクロノジで設計されたPentium4 1.7GHz 上で実行したFFT 乗算と比較して16 進数2^5^ から2^13^ の範囲で,19.7倍から34.3 倍,平均で25.7 倍の性能を実現することができた.この時の面積は9.05mm^2^ であった.また,FFT 乗算とKaratsuba 乗算の性能が逆転する16 進数2^21^ 桁の乗算においては35 倍の性能を実現した.この時の面積は16.1mm^2^ であった.実際に,16 進数2 桁のFFT 乗算器を2.8mm 角のカスタムチップで試作し,その結果から,より大きな桁のFFT 乗算器も現実に実装可能であることを示した. Karatsuba 乗算器の実装においては2 つの設計選択肢として組み合わせ回路で行うRKM (Recursive Karatsuba Multiplier) と順序回路で行うIKM (Iterative Karatsuba Multiplier) を構成した.CMOS 0.18μm テクノロジを用いてこれらを実装した結果,2^9^ ビット以上の乗算においてRKM の面積は標準的な乗算回路であるWallace Tree 乗算器(Wallace Tree Multiplier, WTM) より小さくなることがわかった.2^9^ ビットにおける面積は30mm^2^ であった.また,最大遅延時間は常に WTM の方が短かった.このことから,性能コスト比においてRKM よりWTMの方が優れていることがわかった.したがって,IKM で用いる基本乗算器としてはWTM を用いる方が良い.IKM に関しては,再帰の回数をそれぞれ1,2,3 としたR1IKM,R2IKM,R3IKM を実装した.さらにそれぞれについて,基本乗算器のビット長(基本ビット長) を4 から128 ビットとするIKM を実装し,その性能,面積,電力を評価した.その結果,基本ビット長を32,64,128 ビットにしたIKMは,ソフトウェア実装exflib と比較してそれぞれ約5,10,30 倍の性能を実現できることを示した.この時,最も大きい面積は,基本ビット長を128 ビットにしたR3IKM の10.9mm^2^ であった.同じR3IKM について消費エネルギーを評価したところ汎用プロセッサと比較して1/600 であることがわかった.全体を通して,ハードウェアとソフトウェアいずれにおいても,FFT 乗算とKaratsuba 乗算は2 進2^23^ 桁(16 進数2^21^) 付近で性能が逆転することがわかった. 2 進2^23^ 桁においてハードウェア実装とソフトウェア実装の性能比はいずれのアルゴリズムについても約30 倍であった.またこのとき,面積はそれぞれ2^12^mm^2^ と16mm^2^ であった.ただし,FFT 乗算器の面積に外部メモリは含まれていない.これらの結果から,FFT 法とKaratsuba 法の両ハードウェア実装おいて,パラメータに応じた性能コスト比の変化と適用範囲が明らかになった.本論文は,広い桁範囲における多倍長乗算のハードウェア化に関する詳細な研究結果を述べた唯一のものであり,多倍長乗算を用いたアプリケーションやシステムの実現において有益な指標となる.また,多倍長演算に関する実装技術の研究や開発,およびアプリケーションシステムの利用促進に大きく寄与すると考えられる.