問題適合型高精度計算ライブラリの開発
Development of Adaptive High Accuracy Libraries
長谷川 秀彦 (筑波大学 図書館情報メディア系)
Hidehiko Hasegawa
計算の高度化・高精度化の観点で高性能コンピュータを利用し、
1) 計算誤り検証付きライブラリの開発
2) RSA 暗号(1024ビット)の強度推定
3) 自動チューニング機構付き線形計算ライブラリの開発
4) 精度保証付き線形計算ライブラリの開発
5) 4倍精度線形計算ライブラリの開発
などを行う。
π計算に組み込まれている誤計算チェック(多数桁乗算ルーチン中)を試験的に実際の数値計算ライブラリに組み込む
連立非線形ニュートン法を用いて代数的平方根の計算を行う。ふるい処理、標数２の線形方程式の解法、代数的平方根の計算の３つのステップを合わせて、ES2における RSA暗号の解読時間推定を行う。
地球シミュレータ上で自動チューニングコードを用いてサンプリングを繰り返し、チューニング手法とその効果を検証する。
まずは、精度保証ライブラリを地球シミュレータに移植する。
われわれが持っている既存の行列計算用コードがベクトル並列機上でどのようなふるまいを示すかを観察し、アルゴリズムに改善を加える。
RSA暗号(1024ビット)の強度推定については、若干遅れ気味であるが、予定通り進行中である。その他については、今年度もほとんど進んでいない。
一昨年度のRSA暗号に使われるふるい処理の高速化、昨年度の標数2の線形方程式の高速化に引き続き、最後のステップである代数的平方根の計算を行った。数値は整数で扱い、乗算は整数FMT(高速剰余変換)を利用し、有効桁数を増やすために4回の乗算を中国剰余定理で重ね合わせた。
桁上げの部分を工夫したうえでベクトル化し、RSA-768(10進232桁)、6次の多項式で50億桁の計算が3時間(ES2 １ノード)で実行できた。現在、その他の実測が進行中である。
以前の成果に関して、途中経過を2月に開催された SIAM Parallel Processing for Scientific Computing2012で発表した。今年度の結果の一部(主としてアルゴリズム)を第41回数値解析シンポジウムで発表した。
(年度当初の研究計画を全て達成した場合を100% / 複数の目標があった場合は、それぞれについて達成度を数値で記載)
1) 計算誤り検証付きライブラリの開発 : 0%
2) RSA 暗号(1024ビット)の強度推定 : 80％
3) 自動チューニング機構付き線形計算ライブラリの開発 : 20％
4) 精度保証付き線形計算ライブラリの開発 : 0％
5) 4倍精度線形計算ライブラリの開発 : 20％
現在、「RSA 暗号(1024ビット)の強度推定」が、グループ内でのほとんどの実行時間を占め、アクティブに活動中である。「自動チューニング機構付き線形計算ライブラリの開発」は、予定の大規模計算がストップしている。
(ベクトル化、 並列化チューニング等、 計算機資源を有効利用するために行ったこととその効果を記載)
多数桁の整数演算における桁上げ処理はデータ依存性があるためベクトル計算できない。そこで、桁上げ要素(2進32桁ごと)数が非常に多いため、要素数 n を L ごとに分割し (n= L * M)、 M に1要素加えた (M+1)*L で表現し直して、桁上げ処理を桁上げ方向から分割方向に変更してデータ依存性を取り除いてベクトル化した。
RSA 暗号以外のテーマは、担当者の多忙により進捗がはかばかしくない。特に、進捗が 0% のものは、 CRESTなどの競争的資金にあたったためにまったく時間が割けなくなったことによる。
該当なし。