スライド 1

Size: px

Start display at page:

Download "スライド 1"

いおりほうねん
5 years ago
Views:

1 シンプルハードウェアがもたらす計算機システム研究 / 教育の新展開 RECONF システムの魅力と研究の実践同志社大学理工学部吉見真聡 myoshimi@mail.doshisha.ac.jp

発表者について吉見真聡 :Masato YOSHIMI(1981~) 同志社大学理工学部助教 (2009~) 京都府京田辺市

(Windows-HPC, Supernova) 2000~2004 慶應義塾大学理工学部情報工学科天野研究室 FPGA

A Study on Monte-Carlo Biochemical Simulation on Field-Programmable

2 発表者について吉見真聡 :Masato YOSHIMI(1981~) 同志社大学理工学部助教 (2009~) 京都府京田辺市インテリジェント情報工学科知的システムデザイン (ISDL) 研究室進化計算, 知的環境など PC クラスタなど (Windows-HPC, Supernova) 2000~2004 慶應義塾大学理工学部情報工学科天野研究室 FPGA を用いた高性能科学計算の実現に関する研究 2004~2006 同大学院理工学研究科修士課程 2006~2009 同博士課程博士論文題目 A Study on Monte-Carlo Biochemical Simulation on Field-Programmable Gate Arrays 2009 年 2 月 ~3 月英国インペリアルカレッジ Supernova(2003) 1Tflops~ 22th Top500:93 位知的オフィス空間 (2008~)

3 FPGA の用途プロトタイピング : お手軽 (?) ハードウェア実装アクセラレータ : 小さな運用コスト (?) で大きな性能組み込み : 所望の処理ができれば十分. 無駄を省く LED が光ると気持ちイイスターターキットなどで遊ぶところから. Canopus HDTV recorder Black Magic Design Intensity Digital Capture Board Xilinx spartan3(fpga)

.. Yasunori OSANA, Tomonori FUKUSHIMA, Masato YOSHIMI, Hideharu AMANO, An FPGABased

4 ReCSiP ボード ReCSiP board (2003) Xilinx Virtex-2 XC2V6000-4BF957C 比較的大きめのFPGA(Virtex2) 並列アクセス可能な4つのSSRAM, 大容量 DRAM PCI-X 接続による高速なホストメモリ-FPGA 通信全然シンプルハードウェアじゃなかった... Yasunori OSANA, Tomonori FUKUSHIMA, Masato YOSHIMI, Hideharu AMANO, An FPGABased Acceleration Method for Metabolic Simulation, In IEICE Trans. on Information and Systems, Vol. E87-D, No. 8, pp , Aug.2004.

5 FPGA でわかったこと ( 当たり前?) パイプライン, スレッド並列, メモリの有効活用は μp との速度勝負においては極めて有効複雑なデータフロー制御を含むアルゴリズムには弱い専用ハードウェアの利点は,μPのデータの取り回しのオーバヘッドを無くせること PROGRAPE-3 多体問題 ( 天体の粒子系シミュレーション ) Virtex-IIPRO x 4 236GFlops Opteron 2.40GHz と比べて 8 倍程度

6 インペリアルカレッジロンドン Wayne Luk, Peter Cheng, Oskar Mencer など, リコンフィギャラブル研究の総本山 Pilchard( 香港中文大学 ) の関連など博士課程最後だし, せっかくだから. GCOE の仕事を手伝って旅費を出してもらったいろいろ間に合わなかったので,1 ヶ月だけ

7 CUBE : 512 FPGA Cluster 2008 年から開発中 512 個のFPGAが一次元接続された計算システム 8x8にFPGAが並べられたボードを8 枚重ねて運用ストリームアプリケーション向け暗号処理や気象解析に関する評価 ( 電力, 性能 ) 7

8 CUBE のアーキテクチャ FPGA 間が, 単方向データバス (64 ビット ) で接続 100MHz で動作ミドルレンジの FPGA(XC3S4000) を使用とても単純な構造安い, 作るのが難しくない導入運用コストに優れるアプリケーションを限定すれば, 低コストな高性能計算機の可能性の一つデータフローがほぼ固定 8

9 Imperial での研究 (1) わかっていた問題点 : 高い並列性が明白でなければ, 大幅な高速化は難しい 10 倍以上の動作周波数の差を逆転する並列性電力は 1/3 くらいだけど, お値段は 10 倍時間も無いし, どうしよう GHz 200MHz 9

それぞれ良いところがあるはず 80000 70000 60000 50000 40000 30000 20000 10000 0 [ 吉見 IPSJ-ARC172]

10 Slice Register 動作周波数 [MHz] Imperial での研究 (2) わかっていた問題点 : 博士課程のときの悪夢複雑なアルゴリズムは接続網に割かれるリソースが多い FPGA は HPC に向かないか? GPU や Cell に負けちゃうの? そんなことはないはず! それぞれ良いところがあるはず [ 吉見 IPSJ-ARC172] 算術演算スレッド接続網 Op. Freq. 54.9% % BUS(24) NoC(16)

11 Imperial での研究 (3) 明らかな並列性が認められれば, パイプライン演算の効果が大きく引き出せる条件分岐の無い ( 尐ない ) 単純なアルゴリズム低い動作周波数はロジック資源の量でカバー複数 FPGA による協調動作 Xeon 2.80GHz の約 40 倍のスループット吉見真聡他. `FPGAを用いた確率モデル生化学シミュレータ '. 情報処理学会論文誌 : コンピューティングシステム, 11 Vol. 48, No. SIG 3 (ACS 17), pp , (2007-Feb.).

12 研究の目的 CUBE で実行するアプリケーションを実装し, 性能を評価する文字列編集距離を対象とするちょうど Cell Challenge, GPU Challenge でも使われたアプリツールキットを作ったときにだいたい理解していた他のマルチコアプロセッサと比較 CUBE の実用性を示すロジック資源量と演算量, 通信量の関係を定量的に示し, 対象アプリケーションの性能の予備評価を可能にするロジック資源の使用率と高速化の関係を明らかにする 12

13 文字列編集距離 Edit Distance ( Levenshtein Distance ) 文字列と文字列の距離を求める遺伝子の相同性検索画像認識かな漢字変換プログラム綴り間違いの検出様々なレベルでの並列性を内包スレッドレベル, ループレベル並列性 CUBEの性能評価に適している 13

14 編集距離の操作例 weight と write の編集距離挿入置換削除の手順の繰り返し以下の操作で weight から write になる weight 1. weighte ( 挿入 :e) 2. wrighte ( 置換 :e r) 3. wrihte ( 削除 :g) 4. write ( 削除 :h) 3 回以下の操作では weight を write にできないよって編集距離は 4 削除, 挿入, 置換は文字列の中のどの位置で行ってもよい 14

15 編集距離計算のアルゴリズム ( 概要 ) 動的計画法(Dynamic Programming) が有名操作手順数の表を作って編集距離を求める N w e i g h t 1 w r i t e M 15

16 ブロック化アルゴリズムブロック水色が計算済みであれば赤色は並列に計算できる 16

17 設計 CUBE 向けに編集距離計算のアルゴリズムを実装し, 性能を評価するアルゴリズムのチューニングは行わないシステム全体と各 FPGA の 2 階層に計算を分ける CUBE FPGA0 FPGA1 FPGA511

18 設計 CUBE への実装 CUBE システム全体での処理の流れブロック化アルゴリズムをシストリックアレイで処理 CUBE T=0 FPGA0 FPGA1 FPGA2 FPGA3 Blocked Score Table ホスト PC 一方の文字列を各 FPGA に分割して配布しておく Main memory

19 設計 CUBE への実装システム全体と各 FPGA 内の 2 階層に計算を分ける CUBE システム全体での処理の流れブロック化アルゴリズムをシストリックアレイで処理 T=2 FPGA0 FPGA1 FPGA2 FPGA3 計算中 Blocked Score Table ホスト PC 一方の文字列を各 FPGA に分割して配布しておく Main memory

20 設計 CUBE への実装システム全体と各 FPGA 内の 2 階層に計算を分ける CUBE システム全体での処理の流れブロック化アルゴリズムをシストリックアレイで処理 T=4 FPGA0 計算中 A FPGA1 FPGA2 FPGA3 計算中 B 一方の文字列を各 FPGA に分割して配布しておく Blocked Score Table B A ホスト PC Main memory

21 設計 CUBE への実装システム全体と各 FPGA 内の 2 階層に計算を分ける CUBE システム全体での処理の流れブロック化アルゴリズムをシストリックアレイで処理 T=6 FPGA0 FPGA1 FPGA2 FPGA3 計算中 A 計算中 B 計算中 C 一方の文字列を各 FPGA に分割して配布しておく Blocked Score Table C B A ホスト PC Main memory

22 設計 CUBE への実装システム全体と各 FPGA 内の 2 階層に計算を分ける CUBE システム全体での処理の流れブロック化アルゴリズムをシストリックアレイで処理 T=8 FPGA0 FPGA1 FPGA2 FPGA3 計算中 A 計算中 B 計算中 C 計算中 D 一方の文字列を各 FPGA に分割して配布しておく Blocked Score Table D C B A ホスト PC Main memory

23 設計 CUBE への実装システム全体と各 FPGA 内の 2 階層に計算を分ける CUBE システム全体での処理の流れブロック化アルゴリズムをシストリックアレイで処理 T=10 FPGA0 FPGA1 FPGA2 FPGA3 計算中 A 計算中 B 計算中 C Blocked Score Table ホスト PC 一方の文字列を各 FPGA に分割して配布しておく A B C Main memory

24 設計 CUBE への実装システム全体と各 FPGA 内の 2 階層に計算を分ける CUBE システム全体での処理の流れブロック化アルゴリズムをシストリックアレイで処理 T=12 FPGA0 FPGA1 FPGA2 FPGA3 計算中 A 計算中 B Blocked Score Table ホスト PC 一方の文字列を各 FPGA に分割して配布しておく A B Main memory

25 設計 CUBE への実装システム全体と各 FPGA 内の 2 階層に計算を分ける CUBE システム全体での処理の流れブロック化アルゴリズムをシストリックアレイで処理 T=14 FPGA0 FPGA1 FPGA2 FPGA3 計算中 A Blocked Score Table ホスト PC 一方の文字列を各 FPGA に分割して配布しておく A Main memory

26 各 FPGA の計算 (1/2) LD_thread: 1 ブロックの計算を担う各文字の要素を計算するブロック計算と同様の方法 2 階層のプロセッサで処理処理する文字数を可変に 1 つの FPGA で, 128 文字 128 文字の 1 ブロックを計算する LD_thread 隣接 FPGA から 8 8 文字のブロックの編集距離を計算する LD_core 16 計算するデータやタイミングを指示する制御モジュール隣接 FPGA へ

27 各 FPGA の計算 (2/2) LD_core : 4 段パイプラインでスコアを計算 HW モジュールを Verilog-HDL で実装 Xilinx ISE10.1 で合成, 配置配線 LD_core 部分文字列 1 LD_thread から計算するデータやタイミングを指示する制御モジュール部分文字列のスコアテーブル LD_thread へ

28 ロジック資源の評価 LD_thread : 16 個の LD_core を内蔵する HW モジュール CUBE 内の各 FPGA 上に構成される LD_thread LD_core XC3S4000 Slices FFs LUTs BRAMs Freq 約 81%

29 性能評価 CUBE と比較する計算システム Intel Core2Quad Q9550 物理 4 コア (2 コアで L2 共有 ) C 言語 + pthread ライブラリ 4,8 スレッドで実行 Cell/B.E. C 言語 + libspe2 ライブラリ Sony ZEGO(BCU-100) に搭載のものを使用 (7SPE) IPSJ Cell Challenge 2009 のツールキット ( ブロック化アルゴリズム ) GPU CUDA で実装 Geforce GTX280 で実行 IPSJ GPU Challenge 2009 のツールキット

30 計算性能 (1/2) 問題サイズ ( 文字列長 ) ごとに, 計算に要する時間 [sec] C2Q は 4 スレッド,8 スレッドの 2 種類で評価 CUBE は,FPGA1 個,CUBE ボード 1 枚,CUBE フルシステム (8 枚 ) の 3 種類で評価

31 CUBE が最も高い性能計算性能 (2/2) 問題が大きくなると速度向上が抑制現在のパイプライン効率は0.207 (LD_thread) FPGAの約 20% しか使えていない高性能計算システムにふさわしいスケーラビリティの獲得が課題

32 消費電力比率フルシステム CUBE の消費電力を 1 としたときの相対値他デバイスの消費電力値は各種データシートから取得概ね 10 倍 ~100 倍程度の消費電力の効率化を確認

33 CUBE による編集距離計算まとめ CUBE の回路コンフィギュレーション部分が未完成だったため, 実機動作はできなかったのでシミュレーションパイプライン実行できれば FPGA でかなり良い性能が出せる素晴らしい性能十分なエネルギー効率吉見真聡他,SACSIS2010

34 今後どうする? FPGA の HW 実装は開発コストがとても高い verilog-hdl が使えてもつらいプログラマビリティを向上する方法を考える? チップ内外とのインタフェースだけでもいいから.. PC クラスタと戦うにはアプリ選定がキモでもそれって話がアベコベな気もする従来パソコンで処理していた部分を, 小型の FPGA で代替することができれば, その設計などで論文出せるか..? 開発になってしまわぬように何らかの知見を入れられるかがキモ

31_17.dvi

31_17.dvi Vol. 3 No. 3 209 220 (Sep. 2010) FPGA CUBE 1 2 2 1 1 3 512 FPGA 1 FPGA CUBE CUBE GPU NVIDIA GeForce GTX280 Cell/B.E. Performance Evaluation of One-dimensional FPGA-cluster CUBE for Stream Applications