Microsoft PowerPoint - sales2.ppt

Transcription

1 並列化の基礎 ( 言葉の意味 ) 並列実行には 複数のタスク実行主体が必要 共有メモリ型システム (SMP) での並列 プロセスを使用した並列化 スレッドとは? スレッドを使用した並列化 分散メモリ型システムでの並列 メッセージパッシングによる並列化 並列アーキテクチャ関連の言葉を押さえよう 21

2 プロセスを使用した並列処理 並列処理を行うためには複数のプロセスの生成必要プロセスとは プログラム実行のための能動実態メモリ空間親プロセス子プロセス Process Process しかし プロセスレベルの Table Table 並列処理はオーバヘッド多し Program Text Data Area Stack Area コピー コピー Process FORK 共有 Data Area Stack Area スレッドの活用 アドレス空間のコピーは時間がかかる 22

3 スレッドの生成と並列処理 軽量プロセス = 生成時のコストが小さい ( オーバヘッド ) メモリ空間 マスタ Process Table Program Text スレッド 共有 複数のスレッドを生成し並列処理を行う Data Area Stack Area プロセス 共有 Stack Area Thread 生成 システムコール 23 Stack area は 並列時独自に使用 Dynamic な allocation

4 スレッドとは プロセスから実行主体 ( スレッド ) を抽出しテキスト データ等は共有する プロセス =( メモリ空間 + 資源情報 )+ プログラム実行主体 人間 = 肉体 ( 物理的な体 ) + 意志 ( 思考形態 ) ピアノ 人 左手 右手 スレッド 1 スレッド 2 24

5 スレッドの実行形態と並列実行 Single process Applications Multi thread 並列実行ライブラリスレッド対応 Operating System 渡り歩く 物理 CPU 数以上のスレッドの存在 OK P P P P Hardware (SMP) P Processor Process Thread 25

6 メッセージパッシングとは Single process 独立のハードウェア Applications P OS P Hardware Processor 同じ並列プログラム メッセージの交換 OS P Hardware Process 26 OS P Hardware データの送受 同期処理はプログラム明示 通信路 MPI

7 スレッド並列 +MPI (Hybrid) Applications Single process Multi thread SMP Cluster P P OS Hardware Processor 同じ並列プログラム メッセージの交換 OS P P P P Hardware Process 27 OS P Hardware Thread 通信路 MPI 実装 スレッド並列 message Passing

8 並列化についての話 並列プログラムはどのように動くのか? 並列プログラミングのモデル (SPMD) どのように並列化するのか? 並列化のための言語と性能 OpenMP HPF MPI 並列の効果 Scalabilityの考え方 どんなものが並列化可能なのか? 並列プログラミング環境 28

9 並列動作の形態 単体処理型 共有メモリ型 分散メモリ型 P P P P P P P Memory Memory Memory Process Process Process Process Process 逐次処理 Thread 生成 時間 並列可能 逐次処理 P 同期処理 スレッド Processor 冗長実行処理 Message Passing 同期 割当てたデータ部のみ処理必要であればデータ交換 29

10 並列プログラミングモデル SPMD =Single Program Multi Data 同一プログラムモジュール プログラムの条件文で扱うデータを制御 Load Load if Node0 if Node1 if Node2 I=1,2 I=3,4 I=5,6 の計算 node0 の計算 node1 の計算 node2 共有メモリ型 & 分散メモリ型 Load 30

11 SPMD による並列モジュール構築 スレッド並列でもメッセージパッシングでも基本は SPMD 共有メモリ型システム スレッドを使用した並列化モジュール コンパイラシステムが自動的に SPMD 型並列モジュールを作成可能 分散メモリ型システム MPI (Message Passing Interface) ライブラリを用いた SPMD 型プログラミング必要 31

12 どのように並列化するの? DO Loopレベルを分割並列 ( 細粒度並列性 ) コンパイラによる自動並列 on SMP Directive/Pragmaによる並列指示 OpenMP directiveによる並列指示 HPF (High Performance Fortran) による並列化 コンパイラによる自動並列可能 細かな並列指示 =directive 用意 MPI (API) を用いた並列化 全て 人がプログラミング ( 同期処理等も自分で考える ) 32

13 プログラム言語とその対応システム 分散メモリ型システム 細粒度並列性 (DO Loop レベル ) OpenMP HPF MPI 粗粒度並列性 ( 要並列計算量 ) ( 計算領域分割 ) 共有メモリ型システム 33

14 OpenMP = SMP Parallel Fortran/C/C++ Fork/Join Model omp_get_num_threads() omp_set_num_threads() omp_get_thread_num() omp_in_parallel() omp_set_dynamic() Query Functions 1) 自動並列 2) directive を使って細かな並列 F77 C F90 F95 C++ 34!OMP$!OMP$ PARALLEL PARALLEL [clauses] [clauses] < redundant redundant work work >!OMP$!OMP$ DO DO [clauses] [clauses] DO DO I = 1, 1, N < parallel parallel work work >!$OMP!$OMP ATOMIC ATOMIC X(IDX) X(IDX) = X(IDX)+1 X(IDX)+1 ENDDO ENDDO!$OMP!$OMP END END DO DO < redundant redundant work work >!$OMP!$OMP END END PARALLEL PARALLEL Parallel Regions/Constructs

15 自動並列処理による性能向上 -2CPU on SMP - Memory access 軽い Pentium Pro : 2CPUs アプリケーションの計算特性に依存する メモリアクセス量 多重演算の度合い 出展 : Kuck & Associates, Inc. のページより 35

16 自動並列処理による性能向上 - 4CPU on SMP - Pentium Pro : 4CPUs 分割処理量の均衡 Load balancing バランス崩れると性能飽和 出展 : Kuck & Associates, Inc. のページより 36

17 LS-DYNA under OpenMP Speedup Elements Degrees of Freedom 1 CPU Time = 4446 Seconds 2 CPU Time = 2393 Seconds Dual 450Mhz PII Xeon Processors LSDYNA = Over 750,000 lines of Fortran and C source code 1.86X Speedup on 2 processors Parallelized using PGI Fortran and OpenMP 37

18 HPF = Standard Parallel Fortran 配列の陽的並列分割 1) 自動並列 2) directive を使って細かな並列 Data Distribution 配列分割 処理分割!HPF$!HPF$ INDEPENDENT INDEPENDENT DO DO I = 1, 1, N A(IDX(I)) A(IDX(I)) = B(I) B(I) ENDDO ENDDO Parallel Constructs 共有メモリ型分散メモリ型 両方対応 自動生成 38 HPF SMP MPI RPM 各種通信系

19 MPI = Message Passing Fortran/C/C++ SPMD Model mpi_send() mpi_recv() mpi_allgather() mpi_barrier() Point-to-point and collective communications 自分のノード番号に従った部分の計算を行う F90 F77 F95 C C++ 39 call call MPI_INIT(ierr) MPI_INIT(ierr) call call MPI_COMM_RANK( ) call call MPI_COMM_SIZE( ) if if (myid (myid.eq..eq. 0) 0) then then <get <get input> input> endif endif call call MPI_BCAST( ) MPI_BCAST( ) do do I = myid+1, myid+1, n, n, numprocs numprocs x = h * (dble(i) (dble(i) -0.5d0) -0.5d0) sum sum = sum sum +f(x) +f(x) enddo enddo mypi mypi = h * sum sum call call MPI_REDUCE( ) MPI_REDUCE( ) Explicit messaging

20 MPI- 粗粒度計算の例 領域分割法 解析領域 CPU CPU 0 1CPU 2 CPU 3 CPU 0 CPU 1 逐次処理 データの交換 CPU 2 CPU 3 各 CPU に割り当てる計算領域を分割領域境界でのデータの交換必要 並列処理 40

21 列ジョブ高々 100/40=2.5 倍並並列の効果 ( どの位?) 並列化不可 並列化可能 単体実行 (1CPU) 並列 1CPU 並列化率 並列 2CPU 並列による性能向上分 並列 3CPU 並列オーバヘッドもあるよ 並列 4CPU ロードバランス良好の時 ( 分 )

22 並列の効果 (Scalability) アムダールの法則 = 並列化率 P% の時の効果は = 100 / (100-P) : 理想値 並列化効率 Number of CPU 並列化率 % % % % % % % % % % % % % % %

23 並列手法による並列効果の違い 並列効果 (Scalability) 並列手法 ( 共有メモリ / 分散メモリ ) による並列効果の違い Coarse Grained Parallel ( 分散メモリ対応 ) MOM-3,PIPE Seismic ベース Fine Grained Parallel ( 共有メモリ対応 ) 現 POM ベース 現 MOM/Seismic ベース MPI SMP 並列 CPU 数 43

24 どんなものが並列化可能か (1) 細粒度並列 (SMP: 自動並列化含む ) 基本的にDO Loopが対象 多重 DO Loopも対象 ループ反復間に変数の依存関係がない I/O 処理 配列の動的割付等を行っていない ループの反復中にループを抜け出さない 依存関係のあるサブルーチンコールを含んでいないこと 間接メモリ参照がない 曖昧なポインタがない 44

25 どんなものが並列化可能か (2) 並列効果の高いアプリケーションソルバー 差分法 : レッド ブラック SOR 法 パイプライン法 : ICCG 法はパイプライン法へ モンテカルロ法 分子動力学等の粒子を扱うもの ニューロンの計算 : 行列 ベクトル計算が主体 境界要素法 : 密行列の連立一次方程式に帰着 並列効果が低いソルバー 有限要素法 ( 陰解法 ): 粗行列 計算量少ない : 領域分割法へ変換 45

26 並列最適化における注意点 並列化を行う前に単体性能の向上重要 並列化率が高くなければ 並列化効果 scalabilityは期待できない 単体性能の最適化では それだけで数倍の性能向上も期待できる アプリケーションの特性で並列化手法が変わる 適切な手法をまず考える 46

27 並列プログラム開発環境での問題 見たいものが見えない 並列デバッグ時の問題箇所の特定が難しい MPI 開発では 演算 通信の状況が見えない 並列プログラミング環境必須 業界標準のデバッガ & ツールマルチプロセスデバッガ : TotalView MPI プログラムの性能解析 : VAMPIR Sun Prism 47

28 並列デバッガ TotalView 業界標準並列デバッガ 操作性に優れた GUI により効率よく使用できる マウスのボタン操作で主要なコマンドを実行可能 多様な分散 並列プログラミングモデルをサポート 巨大で 複雑なプログラムもデバッグ可能 様々な言語 プラットフォーム アーキテクチャで利用可能 (MPI のデバッキング可能 ) 48

29 TotalView の実行状況 Root ウィンドウ Data ウィンドウ 右クリック Process ウィンドウ ダイブによりプロセスの内部を表示可能 49

30 TotalView データの可視化 分散配列の可視化 Visualize array distribution 50

31 VAMPIR の特徴 MPI ( 及びアプリケーションイベント ) のオフライントレース解析 VAMPIRtrace ツールによるトレース生成 扱いやすいユーザインタフェース スケーラブル ( 時間とプロセッサ空間 ) 秀逸なズーミング フィルタリング機能 高性能グラフィックス MPIとアプリケーションイベントの表示 解析 : MPI ルーチン 1 対 1 集団通信 51

32 VAMPIR GUI (1) MPI の動作挙動が見える 52

33 VAMPIR GUI (2) MPICH(p4) による通信状況のスナップショット 53

34 VAMPIR GUI (3) 通信のサマリチャート ( 二つの結果の同定例 ) MPICH MPI/GAMMA 54