著者

矢崎 俊志 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 法の両ハードウェア実装おいて,パラメータに応じた性能コスト比の変化と適用範囲が明らかになった.本論文は,広い桁範囲における多倍長乗算のハードウェア化に関する詳細な研究結果を述べた唯一のものであり,多倍長乗算を用いたアプリケーションやシステムの実現において有益な指標となる.また,多倍長演算に関する実装技術の研究や開発,およびアプリケーションシステムの利用促進に大きく寄与すると考えられる.

著者

塩津 晃明 矢崎 俊志 阿部 公輝

出版者

一般社団法人 電気学会

雑誌

電気学会論文誌. C, 電子・情報・システム部門誌 = The transactions of the Institute of Electrical Engineers of Japan. C, A publication of Electronics, Information and Systems Society (ISSN:03854221)

巻号頁・発行日

vol.133, no.6, pp.1259-1268, 2013-06-01

参考文献数

17

---

TCP, a current de facto standard transport-layer protocol of the Internet, cannot fully utilize the available bandwidth. Fairness between TCP flows is another important measure of TCP performance. We proposed a method for predicting the optimal size of the congestion window to avoid network congestion by using a machine learning approach. In this paper, based on the machine learning approach, we further improve the congestion algorithm with respect to utilization of the available bandwidth and fairness between TCP flows. The improvement includes bringing a size of the congestion windows closer to the optimum value, realizing fairness against congestion algorithms that aggressively use bandwidth, and adapting to the network where the available bandwidth abruptly changes. The proposed method is evaluated with respect to utilization of bandwidth and fairness between TCP flows including flows aggressively using bandwidth by simulation using NS-2.

著者

塩津 晃明 矢崎 俊志 阿部 公輝

出版者

The Institute of Electrical Engineers of Japan

雑誌

電気学会論文誌. C, 電子・情報・システム部門誌 = The transactions of the Institute of Electrical Engineers of Japan. C, A publication of Electronics, Information and Systems Society (ISSN:03854221)

巻号頁・発行日

vol.133, no.6, pp.1259-1268, 2013-06-01

---

TCP, a current de facto standard transport-layer protocol of the Internet, cannot fully utilize the available bandwidth. Fairness between TCP flows is another important measure of TCP performance. We proposed a method for predicting the optimal size of the congestion window to avoid network congestion by using a machine learning approach. In this paper, based on the machine learning approach, we further improve the congestion algorithm with respect to utilization of the available bandwidth and fairness between TCP flows. The improvement includes bringing a size of the congestion windows closer to the optimum value, realizing fairness against congestion algorithms that aggressively use bandwidth, and adapting to the network where the available bandwidth abruptly changes. The proposed method is evaluated with respect to utilization of bandwidth and fairness between TCP flows including flows aggressively using bandwidth by simulation using NS-2.

著者

小川 真 矢崎 俊志 阿部 公輝

雑誌

研究報告音声言語情報処理(SLP)

巻号頁・発行日

vol.2012-SLP-90, no.10, pp.1-7, 2012-01-27

---

VOCALOID 「初音ミク」 の発売以来,ユーザが自由に歌声ライブラリを制作できるフリーの歌声合成器 UTAU が開発されるなど,歌声合成への関心が高まっている.これら歌声合成器は主にアマチュアの音楽制作に使用されるが,ユーザが声色を任意時刻に混ぜて指定する機能がない.また,声色操作を行うことで処理時間やデータ量が大きくなる.本研究では音声合成分析系 WORLD を用い,メルケプストラムと Vorbis による励起信号からなるコーパスを声色別に収録し,各音素間を時間伸縮関数で接続することで,ユーザがモーフィング率を指定し声色を操作できる歌声合成器 v.Connect を開発した.提案手法を用いて歌声コーパス 「波音リツコネクト」 を制作した.このコーパスの容量は波形の 2 倍程度であった.合成速度は 1.7~2.2 倍と改善され,圧縮による劣化は主観的には感じられなかった.

著者

小川 真 矢崎 俊志 阿部 公輝

雑誌

研究報告音楽情報科学(MUS)

巻号頁・発行日

vol.2012-MUS-94, no.10, pp.1-7, 2012-01-27

---

VOCALOID 「初音ミク」 の発売以来,ユーザが自由に歌声ライブラリを制作できるフリーの歌声合成器 UTAU が開発されるなど,歌声合成への関心が高まっている.これら歌声合成器は主にアマチュアの音楽制作に使用されるが,ユーザが声色を任意時刻に混ぜて指定する機能がない.また,声色操作を行うことで処理時間やデータ量が大きくなる.本研究では音声合成分析系 WORLD を用い,メルケプストラムと Vorbis による励起信号からなるコーパスを声色別に収録し,各音素間を時間伸縮関数で接続することで,ユーザがモーフィング率を指定し声色を操作できる歌声合成器 v.Connect を開発した.提案手法を用いて歌声コーパス 「波音リツコネクト」 を制作した.このコーパスの容量は波形の 2 倍程度であった.合成速度は 1.7~2.2 倍と改善され,圧縮による劣化は主観的には感じられなかった.

著者

矢崎 俊志 阿部 公輝

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. VLD, VLSI設計技術 (ISSN:09135685)

巻号頁・発行日

vol.103, no.476, pp.253-258, 2003-11-21

---

円周率計算や暗号などの分野において,数千桁におよぶ多倍長乗算が必要になる場面がある.多倍長乗算を高速に行うためには,FFTを応用した乗算アルゴリズムが用いられる.本論文ではFFT乗算のハードウェア実装について述べる.まず,演算器の構成法に存在する選択肢のいくつかに関して,コストと性能をもとに検討する.さらに,ソフトウェア実装との性能比較を行い,ハードウェア実装の有用性を示す.0.18μmテクノロジを用いて,浮動小数点データ表現形式を16bitにした小型のFFT乗算器を2.8mm角のチップに実装した.2^<16>桁の計算が可能な64bitデータ表現FFT乗算器は,10mm角程度の現実的なチップサイズで実装可能であるが分かった.

著者

矢崎 俊志 阿部 公輝

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. ICD, 集積回路 (ISSN:09135685)

巻号頁・発行日

vol.103, no.478, pp.253-258, 2003-11-21

---

円周率計算や暗号などの分野において,数千桁におよぶ多倍長乗算が必要になる場面がある.多倍長乗算を高速に行うためには,FFTを応用した乗算アルゴリズムが用いられる.本論文ではFFT乗算のハードウェア実装について述べる.まず,演算器の構成法に存在する選択肢のいくつかに関して,コストと性能をもとに検討する.さらに,ソフトウェア実装との性能比較を行い,ハードウェア実装の有用性を示す.0.18μmテクノロジを用いて,浮動小数点データ表現形式を16bitにした小型のFFT乗算器を2.8mm角のチップに実装した.2^<16>桁の計算が可能な64bitデータ表現FFT乗算器は,10mm角程度の現実的なチップサイズで実装可能であるが分かった.