Microsoft PowerPoint mod.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint mod.ppt"

かずひろたかにし
5 years ago
Views:

1 並列アルゴリズム 2005 年後期火曜 2 限高見利也 ( 青柳睦 ) Aoygi@cc.kysh-.c.jp 月日 ( 火 ) 9. LU 分解法とその並列化 ( 講義 ) PC クラスタによる並列プログラミング ( 演習 ) 1

2 もくじ 1. 序並列計算機の現状 2. 計算方式およびアーキテクチュアの分類 3. 並列計算の目的と課題 4. 数値計算における各種の並列化 5. MPI の基礎 6. 並列処理の性能評価 7. 集団通信 (Coective Commictio) 8. 領域分割 (Domi Decompositio) 9. LU 分解法とその並列化 ( 講義 ) PC クラスタによる並列プログラミング ( 演習 ) 2

3 3 LU 分解について b b b b b x x x x x Ax b x 行列 (give) A x ベクトル (kow) b ベクトル (give) 最も基本的な線形方程式 : 未知ベクトルを求める方程式元 1 次連立方程式数値計算のさまざまな場所で現れるどうやって未知ベクトルを求めるか Gss 消去法 ( 直感的な方法手計算のやり方 ) LU 分解法 ( 同じ行列に対して繰り返すときに効率的 ) 繰り返し法 ( 行列にゼロ要素が多い場合など ) etc.

4 LU 分解アルゴリズム ( 基礎知識 ) A LU , i ij ikkj ( i < k 1 j ij k 1 ik kj ( i j) j) i < i i > j j j i 1 < j) ij k 1 ( i + ik kj ii ij 1 ij ij i k 1 ( ) / 1 ik kj ii j 1 j) ij k 1 ( i + ik kj ij jj 2 ij ij j k 1 ( ) / 1 ik kj jj 4

5 LU 分解アルゴリズム L,U の対角値 Dooitte 型 L ii 1 クラウト (Crot) 型 U ii 1 3 通りのアルゴリズム right-ookig 法 ( ガウス法 ) メモリアクセスが広範囲, バンド幅を要求 eft-ookig 法 ( ガウス法その2) Crot 法 right-ookig 法よりもメモリアクセス範囲は狭い 5

6 分解アルゴリズムの内容 (Right-ookig 法 ) /* Right-ookig method Crot type (_ii 1) Ipt : mtrix, : mtrix size Otpt : mtrix */ for(k0;k<-1;k++) { for(jk+1;j<;j++) [k][j] / [k][k]; for(ik+1;i<;i++) for(jk+1;j<;j++) [i][j] - [i][k] * [k][j]; } k0 k1 k

7 例えば 4 for(k0;k<-1;k++) { for(jk+1;j<;j++) [k][j] / [k][k]; for(ik+1;i<;i++) for(jk+1;j<;j++) [i][j] - [i][k] * [k][j]; } / 10 / / k k k / / /

8 例えば 4 i 1 ( 1i < jの場合 ) ( )/ ij ij ik kj ii k (0 < 1,2,3) ( ) / / k k k / / ( 1 kk 2) / ( 1002) / k ( 1 kk 3) / ( 1003) / k 0 ( 1 < 2) ( 1 < 3) (k のループでどの位置にある配列要素が参照されているかに注目 ) ( 23 2kk 3) / 22 ( ) / k 0 ( 2 < 3) 22 8

9 ( 2i jの場合 1 ) ( jj に注意 )/ 0 1 j 1 ij ij ik kj jj k 0 (3, 2,1,0 0) ( ) / / k k k / / / 00 (3, 2,1 1) ( ) / ( ) / 1k k k 0 21 ( )/ 31 ( )/ 2 1 (3, 2 2) ( ) / ( ) / k k k 0 ( )/ (3 3) ( ) / ( ) / 3k k k 0 9

10 アルゴリズムの違い ( 参考まで ) /* Crot method /* Left-ookig method Crot type (_ii 1) (Up-ookig method) Ipt : mtrix, : mtrix size Crot type (_ii 1) Otpt : mtrix */ Ipt : mtrix, : mtrix size Otpt : mtrix */ for(k0;k<;k++) { for(i0;i<;i++) for(ik;i<;i++) { for(j0;j<k;j++) for(k0;k<i;k++) [i][k] - [i][j] * [j][k]; for(jk+1;j<;j++) for(jk+1;j<;j++) [i][j] - [i][k] * [k][j]; for(i0;i<k;i++) for(ji+1;j<;j++) [k][j] - [i][j] * [k][i]; [i][j] / [i][i]; for(jk+1;j<;j++) } [k][j] / [k][k]; } 10

11 LU 分解の逐次プログラムを並列化する void _s(it, mt_t ) { it i,j,k; } for(k0;k<-1;k++) { for(jk+1;j<;j++) [k][j] / [k][k]; } for(ik+1;i<;i++) for(jk+1;j<;j++) [i][j] - [i][k] * [k][j]; : /* Strt p MPI */ MPI_Iit(&rgc, &rgv); /* Fid ot process rk */ MPI_Comm_rk(MPI_COMM_WORLD,&my_rk); /* Fid ot mber of processes */ MPI_Comm_size(MPI_COMM_WORLD, &mprocs); : gemt(, ); : _p(, ); : 並列化行について cycic または bock 分割を試みる自 Rk が持っていない要素の位置に注意処理が終わったら Rk0 に集約する

12 LU 分解アルゴリズムの並列化例 (R-L 法 ) void _p(it, mt_t ) { it i,j,k; it MAP[SIZE]; it bk; /* cycic decompositio */ for(i0;i<;i++) MAP[i] i % mprocs; /* bock decompositio bk/mprocs; for(i0;i<mprocs;i++) for(j0;j<bk;j++) MAP[i*bk + j] i; */ for(k0;k<-1;k++) { if( MAP[k] my_rk ) for(jk+1;j<;j++) [k][j] / [k][k]; MPI_Bcst(&[k][k+1],-k-1,MPI_DOUBLE, MAP[k],MPI_COMM_WORLD); ( 以下右上に続く ) for(ik+1;i<;i++) { if( MAP[i] my_rk ) for(jk+1;j<;j++) [i][j] - [i][k] * [k][j]; } /* ed of i-oop */ } /* ed of k-oop */ /* copy [i][*] of my_rk -> [i][*] of Rk0 */ for(i0;i<;i++) { if(map[i] > 0) MPI_Sed(&[i][0],, MPI_DOUBLE,0,i,MPI_COMM_WORLD); } if(my_rk0) for(i0;i<;i++) { if(map[i] > 0 ) MPI_Recv(&[i][0],, MPI_DOUBLE,MAP[i],i, MPI_COMM_WORLD,&stts); } } /* Ed of _p */

13 実行時間の計測について所要時間 (Tr Arod Time) 最初に実行を開始したプロセスの開始時刻から最後に実行を終了したプロセスの終了時刻までを計測し, 所要時間とする. MPI_Brrier(MPI_COMM_WORLD); t_strt MPI_Wtime(); /* この間に所要時間を測定する処理を記述 */ MPI_Brrier(MPI_COMM_WORLD); t_stop MPI_Wtime(); pritf( Tr rod time %.16f ", t_stop - t_strt ); MPI_Brrier バリア同期と呼ばれすべてのプロセスがこれを呼び出すまで各プロセスが待ち合わせる機能を持つ,MPI 標準の関数.

14 PC クラスタを利用した演習 ( 月日 ) 利用計算機 : Xeo 3.06GHz d processor 16 台から成る PC クラスター Memory:4GB/ode, Disk: 1.2TB(tot) Logi UID: 講義中に配布端末からの Logi 方法 : Widows XP teet or ssh で omeg.cc.kysh-.c.jp へ接続 Fie 転送 : Loc PC Cster IE( ブラウザ ) から ftp://uid:pwd@omeg.cc.kysh-.c.jp/ Fie 編集 : Loc の Widows 上メモ帳, ワードパッド等, エディター Fie 編集 : PC Cster 上 vi エディター 14

15 PC クラスタを利用した演習 (cot.) Logi 後の設定 : PC クラスタには Score という並列環境が入っており, これを ctivte するためにコマンドプロンプトから scot g と入力すること. Mpi progrm のコンパイル & リンク : mpicc test.c Mpi progrm の実行 : mpir p [1-16 のノード数 ].ot [progrm の引数 ] はじめの一歩 : 講義で指定した LU 分解の並列計算プログラムを翻訳 & 実行する実行時間の計測 : MPI_Brrier(COMM), MPI_Wtime() 関数を使って, 時間を計測できるようにprogrmを変更し,p 数を変えて経過時間を計る. MPI_Wtime() 関数の型は dobe. 15

16 課題演習レポート ( 月日出題 ) 講義で使用した行で cycic 分割した LU 分解プログラムを基に, 以下について並列化効率の観点から考察しレポートにして, 下記の要領でメールで提出してください. (1) LU 分解部分の経過時間を計測できるように書き換え, 使用ノード数を変えて計測結果を表またはグラフにまとめる. (2) 行で Bock 分割するように LU 分解プログラムを変更し, 上と同様に経過時間を計測し結果を (1) と比較する. (3) 行で Bock-Cycic 分割するように LU 分解プログラムを変更し, (1)(2) と同様に経過時間を計測し結果を (1)(2) と比較する. 提出先 :oygi@cc.kysh-.c.jp Sbject: 並列アルゴリズム課題締め切り : 平成 17 年月 27 日 ( 火 ) 形式 :text, pdf, ps, Word, Exce ファイルの添付可 16

Microsoft PowerPoint ppt

Microsoft PowerPoint ppt 並列アルゴリズム 2005 年後期火曜 2 限高見利也 ( 青柳睦 ) Aoyagi@cc.kyushu-u.ac.jp http://server-500.cc.kyushu-u.ac.jp/ 12 月 20 日 ( 火 ) 9. PC クラスタによる並列プログラミング ( 演習 ) つづき 1 もくじ 1. 序並列計算機の現状 2. 計算方式およびアーキテクチュアの分類 3. 並列計算の目的と課題