Microsoft PowerPoint - SWoPP06HayashiSlides.ppt

Transcription

1 Cell プロセッサへの分子軌道法 プログラムの実装と評価 林徹生 九州大学大学院システム情報科学府九州大学情報基盤センター 本田宏明稲富雄一井上弘士村上和彰九州大学大学院システム情報科学研究院

2 背景と目的 Cell アーキテクチャ 構成と特徴 分子軌道法プログラム アルゴリズムと特徴 タスク分配法 ( 実装方法 ) 粒度と割り当て 同期方法 評価 評価対象モデル 評価結果 おわりに 発表手順

3 背景と目的 Cell アーキテクチャ 構成と特徴 分子軌道法プログラム アルゴリズムと特徴 タスク分配法 ( 実装方法 ) 粒度と割り当て 同期方法 評価 評価対象モデル 評価結果 おわりに 発表手順

4 背景 ( プロセッサ アーキテクチャ ) チップマルチプロセッサ (CMP) の登場 並列処理で性能向上を図る 従来の汎用プロセッサに比べ高い処理能力 プロセステクノロジ (nm) トランジスタ数 ( 個 ) 面積 (mm²) 動作周波数 (Hz) ピーク性能 (GFLOPS) 単精度倍精度 Cell 90 2 億 3400 万 221 4G( 最大 4.6G) 256(SPE 8) 26 (SPE 8) Pentium 億 2500 万 G 日経マイクロデバイス <No.237,PP44> より ( 一部改 )

5 背景 ( アプリケーションプログラム ) 科学技術計算を低コスト かつ 高速に解く要求 現在は大規模並列計算機システムで処理 汎用プロセッサでは計算時間が膨大 非経験的分子軌道法計算 創薬や素材開発に利用 タンパク質の計算時間年単位! ( 生体 ) 高分子をもっと高速に解きたい

6 目的 科学技術計算を高速に解きたい! メディア処理を意識した高性能 CMP が登場 メディア処理向け CMP をベースとした高速な科学技術計算の可能性 CMP 構成は多岐に渡る 科学技術計算との親和性は? Cell プロセッサへ分子軌道法プログラムを実装して性能を評価 高性能 CMP を活用 効率的に計算可能かを評価 Cell アーキテクチャの特徴がプロセッサ性能に与える影響を解析

7 背景と目的 Cell アーキテクチャ 構成と特徴 分子軌道法プログラム アルゴリズムと特徴 タスク分配法 ( 実装方法 ) 粒度と割り当て 同期方法 評価 評価対象モデル 評価結果 おわりに 発表手順

8 Cell の構成 ヘテロジニアス CMP (Power Processor Element): 制御プロセッサ SPE(Synergistic Processor Element): 演算プロセッサ 1 SPE 8 を時計回り 2 本 反時計回り 2 本のリング型バスで接続 L2 キャッシュ SPE1 SPE2 SPE3 SPE4 256G バイト / 秒 SPE8 SPE7 SPE6 SPE5 ローカル ストア 25.6G バイト / 秒 主記憶 オフチップ

9 Cell の特徴 8 個の演算プロセッサによるスレッドレベル並列性の向上 ハードウェアの簡素化による消費電力の削減 4GHz での動作可能 トランジスタ資源を出来るだけ演算器に使用 ハードウェア制御からソフトウェア制御へ移行 (SPE) ソフトウェア分岐予測の採用 ソフトウェア制御オンチップメモリ アラインメントをとらない LS (Local Store)

10 SPE の特徴 (1/3) ソフトウェア分岐予測の採用 アセンブリ言語 ヒント命令 + ヒント バッファ C ソースレベル _builtin_expect 関数 コンパイラによる最適化

11 SPE の特徴 (1/3) ソフトウェア分岐予測の採用 長所 : 低消費電力化と回路面積の削減 ハードウェア分岐予測機における命令フェッチ毎の消費電力削減 分岐予測制御用の回路面積を削減可能 短所 : 分岐予測ヒット率低下による性能悪化の可能性 ハードウェア ( 動的 ) 分岐予測機においては 分岐予測ヒット率は 90% を超える

12 SPE の特徴 (2/3) ソフトウェア制御オンチップメモリ (LS) レジスタ LS 主記憶 128 ビット単位 Load/Store DMA による制御 ダイレクトアクセス キャッシュではタグ比較に基づくデータ検索 LS と主記憶間で DMA による明示的なデータ通信の必要性 レジスタ -LS 間で 128 ビット単位の Load/Store

13 SPE の特徴 (2/3) ソフトウェア制御オンチップメモリ 長所 : ダイレクトアクセス ( タグ比較に基づくデータ検索が不要 ) による低消費電力化 短所 : プログラマの負担増加 LS と主記憶間で DMA による明示的なデータ通信の必要性

14 SPE の特徴 (3/3) アラインメントをとらない LS 従来の汎用プロセッサ - データタイプ別のメモリアクセス 1 バイト (Byte) Cell プロセッサ -128 ビット単位のメモリアクセス プリファード スロット バイト (Word) Load word 8 バイト (Double Word) 制御命令後

15 SPE の特徴 (3/3) アラインメントをとらない LS 長所 : アクセス時間の低減 ハードウェアによる制御を省略し メモリアクセス時間を削減 短所 : ソフトウェアでのアラインメント処理 アラインメント制御命令が頻発し プロセッサ性能に影響を与える可能性 Cell プロセッサ -128 ビット単位のメモリアクセス プリファード スロット Load word 制御命令後

16 SPE の特徴 (3/3) アラインメントをとらない LS 長所 : アクセス時間の低減 ハードウェアによる制御を省略し メモリアクセス時間を削減 短所 : ソフトウェアでアラインメント処理を行う必要性 アラインメント制御命令が頻発し プロセッサ性能に影響を与える可能性

17 背景と目的 Cell アーキテクチャ 構成と特徴 分子軌道法プログラム アルゴリズムと特徴 タスク分配法 ( 実装方法 ) 粒度と割り当て 同期方法 評価 評価対象モデル 評価結果 おわりに 発表手順

18 分子軌道法プログラム 基底関数の数 N の 4 乗に比例した計算時間 全計算時間の 95% 以上を二電子積分計算とフォック行列の計算が占める 如何にして高速に解くか?

19 for(i=0;i<nshell;i++) リズム新 小原のアルゴリズムと特徴 二電子積分計算を高精度かつ高速に解く for(j=0;j<i;j++) for(k=0;k<j;k++) for(l=0;l<k;l++) for(i=0; i<n i ; i++) for(j=0; j<n j ; j++) for(k=0; k<n k ; k++) for(l=0; l<n l ; l++) <s i,s j,s k,s l > の計算 forend forend forend forend <a I,b J,c K,d L > の計算漸化計算 (RC) 部分フォック行列の計算 (PF) forend forend forend forend 新初期積電分子計積算分計算(IIC) ) ( 2 小原のアルゴ 初期積分計算 (IIC) 並列性低い 複雑な計算がクリティカルパス上に並ぶ 開平逆数演算 指数演算 漸化計算 (RC) 非常に高い並列性 積和演算

20 背景と目的 Cell アーキテクチャ 構成と特徴 分子軌道法プログラム アルゴリズムと特徴 タスク分配法 ( 実装方法 ) 粒度と割り当て 同期方法 評価 評価対象モデル 評価結果 おわりに 発表手順

21 SPE へのタスク分配 タスク分配の粒度 依存関係がない ロードバランスをとる for(i=0;i<nshell;i++) for(j=0;j<i;j++) for(k=0;k<j;k++) for(l=0;l<k;l++) 初期積分計算 (IIC) 漸化計算 (RC) タスク分配 部分フォック行列計算 (PF) forend forend forend forend

22 SPE へのタスク分配法 タスク割り当て SPE でそれぞれ何を計算させるか? IIC RC PF SPE SPE SPE SPE SPE SPE SPE IIC: 初期積分計算 RC: 漸化計算 PF: 部分フォック行列の計算

23 SPE へのタスク分配法 並列性を活用 SPE 8 個の並列性 RC の並列性 RC を SPE で計算 IIC RC PF 備考 SPE SPE SPE RC の並列性を活かせない SPE SPE SPE SPE RC の並列性を活かせない

24 SPE へのタスク分配法 -SPE 間のデータ通信量を削減 初期参照データ以外の通信量を削減 RC に必要なデータを IIC が生成 IIC を SPE で計算 IIC RC PF 備考 SPE SPE SPE RC の並列性を活かせない 中間生成データ通信の必要性 SPE SPE SPE SPE RC の並列性を活かせない

25 SPE へのタスク分配法 SPE の LS サイズ (256K バイト ) に注意 部分フォック行列 ( 最大数百 M バイト ) は で計算 IIC RC PF 備考 SPE SPE SPE RC の並列性を活かせない 中間生成データ通信の必要性 SPE SPE SPE SPE RC の並列性を活かせない PF を で計算 PF を SPE で計算

26 処理の流れ Loop I, J, K, L 初期積分計算 (IIC) 漸化計算 (RC) 部分フォック行列計算 End L2 キャッシュ SPE1 SPE2 SPE3 SPE4 1 から SPE へタスク分配 (ERI) SPE8 SPE7 SPE6 SPE5 2SPE での計算 3SPE から へのデータ転送 4 が部分フォック行列の計算 Fock 主記憶

27 処理の流れ Loop I, J, K, L 初期積分計算 (IIC) 漸化計算 (RC) 部分フォック行列計算 End L2 キャッシュ SPE1 SPE2 SPE3 SPE4 1 から SPE へタスク分配 (ERI) SPE8 SPE7 SPE6 SPE5 2SPE での計算 3SPE から へのデータ転送 4 が部分フォック行列の計算 主記憶 プログラム実行コードと入力データの配布

28 処理の流れ Loop I, J, K, L 初期積分計算 (IIC) 漸化計算 (RC) 各 SPE が I, J, K, L を取得 (DMA) SPE1 SPE2 SPE3 SPE4 L2キャッシュ 部分フォック行列計算 End 1 から SPE へタスク分配 (ERI) SPE8 SPE7 SPE6 SPE5 2SPE での計算 3SPE から へのデータ転送 4 が部分フォック行列の計算 主記憶

29 処理の流れ 計算中 Loop I, J, K, L 初期積分計算 (IIC) 漸化計算 (RC) 部分フォック行列計算 End L2 キャッシュ SPE1 SPE2 SPE3 SPE4 1 から SPE へタスク分配 (ERI) SPE8 SPE7 SPE6 SPE5 2SPE での計算 3SPE から へのデータ転送 4 が部分フォック行列の計算 主記憶 計算中

30 処理の流れ 計算中 Loop I, J, K, L 初期積分計算 (IIC) 漸化計算 (RC) 部分フォック行列計算 End L2 キャッシュ SPE1 SPE2 SPE3 SPE4 1からSPEへタスク分配 (ERI) 2SPEでの計算 3SPEからへのデータ転送 4が部分フォック行列の計算 Fock 主記憶 SPE8 SPE7 計算終了 SPE6 SPE5 計算中

31 処理の流れ 計算中 Loop I, J, K, L 初期積分計算 (IIC) 漸化計算 (RC) 部分フォック行列計算 End L2 キャッシュ SPE1 SPE2 SPE3 SPE4 1 から SPE へタスク分配 (ERI) SPE8 SPE7 SPE6 SPE5 2SPE での計算 3SPE から へのデータ転送 4 が部分フォック行列の計算 Fock 主記憶 計算結果の書き込み 計算中

32 処理の流れ 計算中 Loop I, J, K, L 初期積分計算 (IIC) 部分フォック計算 SPE1 SPE2 SPE3 SPE4 漸化計算 (RC) L2 キャッシュ 部分フォック行列計算 End 1からSPEへタスク分配 (ERI) 2SPEでの計算 3SPEからへのデータ転送 4が部分フォック行列の計算 Fock 主記憶 SPE8 待機中 SPE7 SPE6 SPE5 計算中

33 処理の流れ 計算中 Loop I, J, K, L 初期積分計算 (IIC) 漸化計算 (RC) 部分フォック行列計算 End L2 キャッシュ SPE1 SPE2 SPE3 SPE4 1 から SPE へタスク分配 (ERI) SPE8 SPE7 SPE6 SPE5 2SPE での計算 3SPE から へのデータ転送 4 が部分フォック行列の計算 Fock 主記憶 I, J, K, L を取得 計算中

34 背景と目的 Cell アーキテクチャ 構成と特徴 分子軌道法プログラム アルゴリズムと特徴 タスク分配法 ( 実装方法 ) 粒度と割り当て 同期方法 評価 評価対象モデル 評価結果 おわりに 発表手順

35 評価目的 分子軌道法プログラムを実行したときの性能を評価 ハードウェアの簡素化がプロセッサの実効性能に与える影響を評価 ソフトウェア分岐予測 ソフトウェアでアラインメントをとる LS 倍精度 / 単精度における浮動小数点演算能力の差が プロセッサ性能に与える影響を評価

36 評価対象モデル BASE 従来の Cell PBP(Perfect Branch Prediction) BASE モデルにおいて 分岐予測ヒット率が 100% と仮定したモデル EDP(Extended Double Precision) BASE モデルにおいて倍精度浮動小数点演算性能が単精度並みと仮定したモデル 実装上は倍精度 (double) を単精度 (float) に変換 PBP+EDP PBP と EDP を組み合わせたモデル PentiumD 動作周波数 3.2GHz の PentiumD プロセッサ

37 評価環境 評価 Cell:Cell シミュレータ mambo Pentium: 実機 + 性能評価ライブラリ PAPI コンパイラ Cell:ppu-gcc,spu-gcc PentiumD:gcc オプション : -O2 g 入力データ 評価対象分子 :C 4 ( 仮想上の分子 ) 基底関数 :DZV 基底関数の数 N:20

38 モデル別の実行時間 実効性能 clock cycle (10^6) % 29 % 34 % BASE PBP EDP EDP+PBP PentiumD 評価モデル other stalls dependency stall branch miss stall instruction issue

39 モデル別の実行時間 実効性能 clock cycle (10^6) % 29 % 34 % BASE モデルの実行時間は PentiumD モデルの約 3 倍 SIMD 命令を未実装であることを考慮しても 想定外の実行時間 BASE PBP EDP EDP+PBP PentiumD 評価モデル other stalls dependency stall branch miss stall instruction issue

40 モデル別の実行時間 実効性能 clock cycle (10^6) % 29 % 34 % 分岐予測精度を向上させることで 30% 性能向上の可能性 BASE PBP EDP EDP+PBP PentiumD 評価モデル other stalls dependency stall branch miss stall instruction issue

41 モデル別の実行時間 実効性能 clock cycle (10^6) % 29 % 34 % EDP モデルでは命令実行時間 (instruction issue) を 56.3% 削減 BASE PBP EDP EDP+PBP PentiumD 評価モデル other stalls dependency stall branch miss stall instruction issue

42 モデル別の実行時間 実効性能 clock cycle (10^6) % 29 % 34 % 実行時間はほぼ同等 dependency stall がプロセッサ性能におけるボトルネック BASE PBP EDP EDP+PBP PentiumD 評価モデル other stalls dependency stall branch miss stall instruction issue

43 モデル別の実行時間の評価 BASE モデルの実行時間は PentiumD モデルの約 3 倍 SIMD 命令を未実装であることを考慮しても 想定外の実行時間 分岐予測精度を向上させることで 30% 性能向上の可能性 EDP モデルでは命令実行時間 (instruction issue) を 56.3% 削減 EDP+PBP モデルの実行時間は PentuimD モデルとほぼ同等 データ依存によるパイプライン ストール (dependency stall) がプロセッサ性能におけるボトルネック

44 モデル別の実行時間の評価 BASE モデルの実行時間は PentiumD モデルの約 3 倍 SIMD 命令を未実装であることを考慮しても 想定外の実行時間 分岐予測精度を向上させることで 30% 性能向上の可能性 EDP モデルでは命令実行時間 (instruction issue) を 56.3% 削減 EDP+PBP モデルの実行時間は PentuimD モデルとほぼ同等 データ依存によるパイプライン ストール (dependency stall) がプロセッサ性能におけるボトルネック

45 浮動小数点演算 (FX3) 浮動小数点演算 (FX2) データ並び替え (SHUF) ロード / ストア (LS)

46 EDP+PBP モデルにおける dependency stall のストール箇所 4 実行時間 :clock cycle (10^6) EDP+PBP 0 FX2 SHUF FX3 LS others ストール箇所

47 dependency stall の解析 ストール時間の大半は LS と SHUF で発生 Load / Store 命令とシャッフル命令 (shufb) がペアとなり頻出 新 小原のアルゴリズムにおける Load / Store 命令の多さ Load / Store 命令と shufb 命令は同一グループのパイプライン (Odd pipe) で処理 ソフトウェアによるアラインメント処理が性能に大きく影響

48 背景と目的 Cell アーキテクチャ 構成と特徴 分子軌道法プログラム アルゴリズムと特徴 タスク分配法 ( 実装方法 ) 粒度と割り当て 同期方法 評価 評価対象モデル 評価結果 おわりに 発表手順

49 まとめ ストール頻発による性能低下 ハードウェア制御からソフトウェア制御へ移行した機能の影響 ソフトウェア分岐予測 分岐予測精度向上の重要性 ソフトウェアによるアラインメント処理 アラインメント制御の重要性 倍精度処理能力の向上により 2 倍の性能向上の可能性

50 今後の課題 ソフトウェア制御分岐予測ヒット率の向上 SIMD 命令を含むコード最適化 オンチップ ネットワークを含めた性能評価 実チップを使った正確なデータの採取

51 ご清聴ありがとうございました

52 同期方法 はメモリ上に各 SPE に対応するプログラム通信用の領域を確保 SPE 用のプログラムと引数を格納 SPE の ( 遷移 ) 状態を示す flag を格納 待機 ( 初期状態 ) : flag 1 SPE: flag 2 タスク分配完了 DMAで初期タスク実行 (SPE) データ参照 : flag 0 部分フォック行列の計算 () SPE: flag 3

53 Single issue と Dual issue cycle count (10^6) BASE PBP EDP EDP+PBP PentiumD データモデル others dependency stall branch miss stall dual issu single issue PentiumD:total

54 BASE モデルにおけるロードバランス 実効時間 :clock cycle(10^6) Min=1.7% Max=47.5% BASE SPE 番号 (1~8) と平均 (9)

55 EDP モデルにおけるロードバランス 実効時間 :cycle count(10^6) Max=58.7% Min=10.5% EDP SPE 番号 (1~8) と平均 (9)

56 漸化計算の ILP

57 命令ユニット別のレイテンシ

58 PentiumD における結果 平均 最小 最大 PAPI_L1_DCM L1データキャッシュミス 33,470 30,955 39,890 PAPI_L1_ICA L1 命令キャッシュアクセス 16,669,476 16,658,209 16,689,399 PAPI_L1_ICM L1 命令キャッシュミス 2,428 2,380 2,481 PAPI_L1_LDM L1キャッシュロードミス 31,628 31,089 31,840 PAPI_L2_TCM 全 L2キャッシュミス PAPI_L2_LDM L2キャッシュロードミス PAPI_L2_STM L2キャッシュストアミス PAPI_BR_INS 分岐命令数 1,770,332 1,770,331 1,770,335 PAPI_BR_MSP 分岐予測ミス 18,655 18,466 18,810 PAPI_BR_PRC 分岐予測的中 1,751,607 1,751,261 1,751,993 PAPI_BR_TKN 分岐条件真 1,500,865 1,500,865 1,500,865 PAPI_BR_NTK 分岐条件偽 269, , ,467 PAPI_FP_INS 浮動小数演算数 (x87 命令 ) PAPI_FP_OPS 浮動小数演算数 (x87+sse2 608, , ,965 PAPI_LD_INS ロード命令数 2,645,707 2,645,705 2,645,708 PAPI_SR_INS ストア命令数 1,840,437 1,840,434 1,840,439 PAPI_RES_STL リソース不足によるストール 116, , ,668 PAPI_TLB_IM 命令 TLBミス PAPI_TLB_DM データTLBミス PAPI_TOT_CYC 全クロックサイクル数 12,013,575 12,000,283 12,034,153 PAPI_TOT_IIS 発行命令数 10,410,004 10,387,002 10,448,834 PAPI_TOT_INS 実行命令数 9,742,637 9,742,629 9,742,643 PAPI_VEC_INS SSE 命令数 753, , ,987

59 )BASE( 左 ) とEDP( 右 ) 分 30 布 (25 % FX2 SHUF FX3 LS others ストール箇所