高速剰余算アルゴリズムとそのハードウェア実装についての研究 数理情報科学専攻　福永研究室 山本　聡

目次 研究背景 ハードウェアでの回路設計 HDLを用いた剰余算回路の設計 研究結果について まとめと今後の課題 開発環境 Verilog HDL（Hardware Description Language） FPGA（Field Programmable Gate Array） HDLを用いた剰余算回路の設計 研究結果について まとめと今後の課題

研究背景(1) コンピュータ上でのデータは二進数で処理され、基本的な演算を繰り返すことで様々な動作を可能にしている。 演算の処理速度は、汎用コンピュータ上のソフトウェアでの実行よりも、専用のハードウェアによる計算のほうが高速に計算できることが知られている。

研究背景(2) CPU内で用いられている、四則演算などの基本的な演算を行う回路についても高速化など性能向上のための研究がなされており、その中でも特に除算（剰余算）回路の設計アルゴリズムの研究は現在でも頻繁に行われている。 参考文献：高木直史 「算術演算のVLSIアルゴリズム（コロナ社　2001）」

研究背景(3) 高速な除算回路を設計することで、 という可能性を見込むことができる。 CPUの演算速度のさらなる高速化 計算する数を大きなビット幅に対応させることでの暗号解読分野への応用 　という可能性を見込むことができる。

ハードウェアでの回路設計(1) ハードウェア上では、全ての数が二進数（0と1のみ）で表現されている。 回路は、全て以下の図で示す「組み合わせ回路」と呼ばれる論理回路で構成されている。 組み合わせ回路と真理値

ハードウェアでの回路設計(2) 組み合わせ回路を複数個用いることで、求める数値を出すように回路を設計する。 FA真理値表 FA（全加算器） hAとFAを組み合わせた4ビット加算器 hA真理値表 hA（半加算器）

開発環境(1) Verilog HDL ソフトウェア上で回路を記述することができるハードウェア記述言語（HDL : Hardware Description Language）の一つ。 配線などを直接記述するゲートレベルでの記述の他に、先の組み合わせ回路であるAnd、Or、Notがそれぞれ　 、+ 、~ という数式で表すことができることから、C言語に似たビヘイビアルレベルという記述法でも回路を設計することができる。

開発環境(2) FPGA（Field Programmable Gate Array） 利用者が独自に回路を設計し、ハードウェアの動作として評価をすることができる書き換え可能なIC。 Verilogで記述した論理回路をダウンロードケーブルを用いて書き込むことでICを作成できる。 FPGA評価ボード（VirtexⅣ　xc4vfx12）

開発環境(3) FPGA内には書き換え可能な論理ブロックと配線が用意されており、HDLで記述した論理回路と接続配線の情報をそれぞれにプログラミングすることで、回路情報をハードウェア化し評価することができる。 FPGAの構造

開発環境(4)

HDLを用いた剰余算回路の設計(1) FPGAには書き込める素子数が決められている。一般に回路の高速化を図ろうとすると回路が複雑になるため使用する素子数が増える。 そのため使用するFPGAの素子数に応じた高速化を行うことが必要になる。

HDLを用いた剰余算回路の設計(2) 剰余算のアルゴリズムは現在でも発展途上の段階であり、特に縮小化・高速化という観点で研究がなされている。 乗算した値の剰余を取る乗算剰余算 において縮小化・高速化を実現したアルゴリズムとして、インターリーブ法とモンゴメリ法が考案されている。

インターリーブ法 インターリーブ法とは、上位ビットから剰余の計算を行うアルゴリズムである。

インターリーブ法の略回路図 単純な動作で剰余を実現しているため、 少ない素子数で回路を設計することができる。

モンゴメリ法 モンゴメリ法とは下位のビットから剰余を計算を行うアルゴリズムである。

モンゴメリ法の略回路図 大きなビットを扱う乗算器を使用しなければならないため使用する素子数は多くなるが、複数ビットをまとめて計算を行うため、高速に演算を終えることができる。

研究と結果について(1) 今回の研究では高木直史（名古屋大学）の提案した二分乗算剰余算アルゴリズムの、素子数の省略化を施した状態での実装を行い、計算時間と素子使用率についての詳細な評価を行った。 二分乗算剰余算とは、先に解説したインターリーブ法とモンゴメリ法を並列に処理させることで、計算時間を短縮しようというアルゴリズムである。

研究と結果について(2) 各アルゴリズムの計算速度に応じて計算するビットを変化させることで最適化できる。 例えばモンゴメリ法がインターリーブ法より2倍の計算速度だとすると、モンゴメリ法の計算ビットをインターリーブ法の2倍にすることで最適化を図ることができる。 二分乗算剰余算の回路図

研究と結果について(3) 回路内の共通の演算部を再利用することで素子数の使用率を抑える工夫をした。 結果として素子数を抑えることができ、より大きな計算ビットを処理できる回路を作成することができた。 共通の回路を一つにまとめた回路図 通常の回路

研究と結果について(4) インターリーブ法とモンゴメリ法の計算速度を評価し、回路が入力値を最適に計算するビット幅に分割して回路を作成した。

まとめ 今回の実装では、二分乗算剰余算を回路化することで、352ビット同士の積を352ビットで剰余を行うという計算を、高速に剰余演算を行うとされているモンゴメリ法の79%の計算時間で行うことができた。

今後の課題 今後の課題として、今回よりも素子数の大きなFPGAを用いてより大きな数の剰余計算を行うことができる回路を設計することがあげられる。 また実現した回路を用いることで、高速な剰余算の計算が多数回必要とされる暗号解読分野への応用が見込めると考えている。