2014 年 2 月 6 日

平成 25 年度 情報・通信工学科 コンピュータサイエンスコース 卒研発表会

FPGA クセラレータを用いた FMM アルゴリズムの高速化
情報・通信工学科 学籍番号:1011027 成見研究室 宇川斉志

1

はじめに近年, 大規模計算の需要は急激に増加している。これらの需要は気象の予測から分子レベルのシミュレーションまで多岐にわたる。これに伴い計算機も発達し, 京をはじめとするスーパーコンピューターや, 汎用 PC を大量につなげたクラスター,GPU を用いて科学技術計算を行う GPGPU など,
図 1: FMM の計算概念

様々な高速計算システムが出現した。こうしたハードウェ
アの進化のおかげで様々な問題を数値計算で解くことができるようになったが, 科学技術などの分野では高速な計算機を使用しても膨大な時間がかかってしまうような問題が存在する。そうした問題の中に粒子の N 体問題というものがある。

目的4

FMM は非常に高速なアルゴリズムで, 今後広い分野での応用が予測される。そこで本研究では,FMM アルゴリズムを, FPGA(Field Programmable Gate Array) というハー2粒子の N 体問題
粒子の N 体問題とは, その名の通り N 個の粒子が存在する系において相互作用を計算する問題である。これらの相互ドウェアデバイス上で実装することによってその回路規模,計算速度を評価し, 高速なアルゴリズムと専用ハードウェアを組み合わせより高速な重力多体計算システムの作成を目指す。

作用は解析的に解くことができないとされ, 数値的なシミュレーションを行うことになる。以下に N 体問題の例としての重力を計算する際の式を示す。

f⃗i =N∑Gi̸=jmj (⃗ri − r⃗j )|⃗ri − r⃗j |3

この式は i 番目の粒子にかかる力を表していて, i 番目以外の N − 1 個の粒子からの力の合計を計算している。この計算を N 個の粒子すべてに対して行うので, 実際の計算量はO(N 2 ) となる。したがってこのまま総当たりで系全体の相5

既存研究5.1

Exa-FMM

ソフトウェアでの FMM の実装に関しては様々な研究が行われてきた。Exa-FMM [2] はそういった研究の一つで横田らによって開発されたオープンソースで提供される多機能な FMM のライブラリ群である。dual tree traversal[3] と呼ばれる特殊な探索法を用いて計算を実行する。

互作用を求めようとすると, 粒子数が増えるにつれ計算量は爆発的に増え, 膨大な時間がかかってしまい計算機がいく

5.2

hwModule

ら高速でも現実的ではなくなってしまう。そこで,1985 年にV.Rokhlin によって FMM[1] (Fast Multipole Method) という粒子の N 体問題の計算量を大幅に削減できるアルゴリズムが提案された。

FPGA を用いて高速計算を行う既存システムとして
hwModule[4] というものが存在する。これは東京農工大学の関根らによって提唱された hw/sw 複合体 [5] を実現させるために開発された FPGA を用いたボードである。hw/sw複合体とは, 大規模計算においてハードウェアとソフトウェ

3FMM についてFMM は N 体問題の計算量を O(N ) まで減らすことができるアルゴリズムである。通常粒子間の相互作用を直接計算法で計算する場合は 1 粒子対 1 粒子間の相互作用を N 2個の組合せ分計算する。一方 FMM では図 1 のように複数の粒子をまとめて粒子群とみなし, 粒子群と粒子群の間の相互作用を計算し, それを粒子群内の各粒子点において再評価する, という計算方法をとる。

アの各々に適した処理を割り当て分散協調動作させるシステムである。音声処理や画像処理, 数値計算などが実装例が報告されているが,FMM の実装例はないため本研究とは異なる。

実行環境

61e+07CPU
GRAPE-9directO(N)

1e+06

6.1

GRAPE-9

FPGA デバイスには GRAPE-9[6] を用いる。GRAPE-9
は K&F Computing Research によって開発された FPGAを用いた専用計算機である。図 2 に GRAPE-9 のブロック図を示す。

Calculating Time [sec]10000010000

1000100

1010.10.01
100010000

100000
1e+06
Number of Particles

1e+071e+08

図 3: 重力多体計算の実行結果
縦軸が計算時間, 横軸が粒子数で, 青色のグラフが直接計
算, 赤色のグラフが CPU のみで FMM を用いた計算, 緑色のグラフが CPU と GRAPE-9 で FMM を用いた計算, 紫色の直線が O(N ) の計算量での計算時間の伸びである。直接計算
では粒子数が増えるに連れ爆発的に計算時間も伸びている
が,FMM を用いた場合は CPU のみの時,CPU と GRAPE-9を組み合わせた時のどちらでも O(N ) の直線とほぼ平行に
図 2: GRAPE-9 のブロック図なっている。また CPU と GRAPE-9 を組み合わせた場合は CPU に比べてコンスタントに速く,16M 個の粒子で計算

GRAPE-9 は 8 枚のプロセッサチップと呼ばれるカードを内蔵しており, それぞれのプロセッサチップに FPGA 一した場合では約 16 倍の速度が出ていたことを確認した。

つと 2GB の DDR2 が搭載されている。本来は重力多体計算を行うための専用計算機なのでこれらの FPGA には重力8今後の課題計算を行う回路が書き込まれているが, 本研究では FMM を実行する回路を生成し, 書き込むことで FMM に特化した専

現状の回路だと同一のデータを重複して GRAPE-9 側に用計算機を構成する。計算を実行するパイプラインは後述送ってしまっているため, 転送時間がボトルネックとなり計する PGPG2 というソフトウェアで生成する。

算速度が低下してしまっている。また, 実装した GRAPE-9が比較的古く,2013 年の 11 月ごろに最新の FPGA を搭載した新しい GRAPE-9 がリリースされたのでそちらでの実装

6.2

PGPG2

PGPG2(Pipeline Generator for Programmable GRAPE,
generation 2) は GRAPE-9 と同様に,PGPG[7] を元に K&F
Computing Research によって開発された,PG2 という独自言語で書かれた数値演算式からパイプライン化された VHDL
コードやそれらを制御する C 言語のライブラリを自動生成するコードジェネレータである。VHDL とはハードウェア記述言語というもので論理回路を記述するためのプログラミング言語である。PGPG2 を使用すればユーザーが GRAPE-9で実行したい数値演算の VHDL コードを自動生成してくれるので基本的に直接 VHDL コードを編集する必要はない。
本研究でも PGPG2 を用いてパイプライン回路を生成した。などが今後の課題である。

参考文献[1] V.Rokhlin, “Rapid solution of integral equations of classical potential theory”, Journal of Computationl Physics, 60 pp.187-207, 1985
[2] R.Yokota, “An FMM Based on Dual Tree Traversal for Many-coreArchitectures”, arXiv:1209.3516v3, 2012[3] M. S. Warren, J. K. Salmon, “A portable parallel particle program”,
Computer Physics Communications, 87 pp.266―290, 1995
[4] 工藤健慈, 今中晴記, 志賀裕介, 関根優年, “hw/sw 混載システムにおけるhwObject モデルとその制御手法”, 情報科学技術フォーラム一般講演論文集
第 1 分冊 FT2002,C-3,pp.193-194, 2002
[5] 関根優年, 佐藤季花, 工藤健慈, 田向権, “hw/sw 複合体”, 第 21 回 回路とシステムワークショップ講演論文集, pp.207-212, 2008
[6] GRAPE-9, http://www.kfcr.jp/grape9.html

7

評価
重力多体計算を CPU で直接を行った場合,CPU で FMMを用いた場合,GRAPE-9 と CPU を組み合わせた場合の結果をそれぞれ図 3 に示す。

[7] T.Hamada, T.Fukushige, J.Makino, “PGPG:An Automatic Generator of Pipeline Design for Programmable GRAPE systems”, Publications of the Astronomical Society of Japan, Vol.57, No.5, pp.799-813,
2005