室橋/6.Synchronous Computations
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[室橋/並列処理輪講2009]]
[[ヤコビ法 - wikipedia:http://ja.wikipedia.org/wiki/%E3%83%A4%E3%82%B3%E3%83%93%E6%B3%95]]~
[[ヤコビ法参考ページ:http://pc-physics.com/jacobi1.html]]
---------------------------------------------------------------------------
-slide25(Prefix Sum Problem)プレフィックス総和問題
--ここからはデータ並列アルゴリズムの例を説明します。
--X0・・・Xn-1の数列の全ての部分和を求めるアルゴリズム。
--(説明はslide27の図で)
-slide26
--16個の数値の部分和のすべてを求めるデータ並列法
-slide27(プレフィックス図)
--図の説明
--(slide25に戻る)
--プレフィックス計算は、加算だけでなく、結合則を満たす他の演算子を使っても定義できる。例えば乗算、最大値、最小値、論理操作(AND,OR,EXORなど) これらは、プロセッサ割り当て、データ圧縮、ソート、多項式評価など、幅広い計算モデルで研究されています。
-slide28(コード)
--Sequential code
---
--Parallel code
---forall
---
-slide29(Synchronous iteration)同期式繰り返し。
--独立した繰り返しが複数ある場合、繰り返し手法(forallとか)で並列化できる。
--ひとつのループ中に複数処理があって、各プロセス(繰り返し)同時に処理がはじまり、全てが終わるまでは次のループにいかない。⇒ 同期式繰り返し。
---(図で説明)
--forall code 使用例
-slide30
--(SPMDプログラムの場合の)バリア使用例
-slide31(Another fully synchronous computation example)
--同期式繰り返しプログラムの例として、ここではヤコビ法について説明します。
---ヤコビ法とはn元の連立一次方程を反復法で解く手法の1つです。
---X0・・・Xn-1(0<=i<=n)が未知数としてn個の未知数とn個の式からなる一般形を仮定します。
---(具体的な配列の図を示す)
-slide32
--式変換。i番目の式。
--この式(Σの式)は、Xiを他の未知数で表しており、各未知数のよりよい近似を得るための繰り返しの式として使用できる。
--ヤコビ法はまず全ての未知数の値を適当に決めます。そして、右辺(Σの式)に代入します。そうすると未知数(Xi)に計算された値が入ります。もし、適当に決めた未知数の値が、真の解であったら新たな解と一致するはずですが、普通そうは上手くいきません。得られた新たな解を再び右辺に代入するとまた新たな解が得られます。これらを繰り返すことで真に解に近似します。そして得られた解と一つ前に求めた解が、ある精度内であればそこで終了し解とみなします。
-slide33(Jacobi Iteration)ヤコビ繰り返し法
--すべてのXの値が一緒に更新される。
--収束条件
---行列aの対角要素の絶対値がその行の対角要素以外のaの要素の絶対値の総和より大きければ(行列aが対角優位であれば)このヤコビ法は収束することが証明できる。
---(行列図で説明)対角要素って?
---Σの式提示。この条件は十分条件であるが必要条件ではない。
-slide34(Termination)終了
--終了は並列化において特に問題。
--簡単でよく用いる手法は、前の繰り返しで得られた値と新しく得られた値とを比較し、すべての未知数(Xi)が[許容誤差の式]に収まれば、t回目の繰り返しで終了する。
--Xt,i = t回目のXiの値。Xt-1,i = t-1回目のXiの値。
--(slide35で説明)
--以下補足
---許容誤差が1%で実際は誤差が0.9999%のときもある。さらに次の計算も0.9998%ということもありえる。
---誤差は複合的なもので、計算値は最終の正しい値とはまだ相当に違っていることもありえる。
-slide35(Convergence)収束曲線
--グラフ説明
---てきとーに書いて比較。
---回数(t)多いほど、Error(誤差)が減っている(収束している)
-slide36(Parallel Code)並列コード
--(Allgatherをslide37で説明)
--Allgatherは新しく計算されたX[i]の値をプロセスiから他のすべてのプロセスにsendし、他のプロセスから送信されたデータを集める。
---Broadcast(送信)とgather(収集)を複合したもの。
-slide37(Allgather)Allgather操作
図の説明
-slide38(Partitioning)分割
--来週の内容の触り。
--すべての並列化がそうであったように、通常、プロセッサ数は計算されるデータ(未知数)の数よりずっと少ない。プロセッサがデータをたくさん処理するためにデータを分割する。
-slide39(block allocation & cyclic allocation)分割手法
--block allocation
---p個のプロセッサ、n個の未知数
---X0からX(n/p)-1をp0に、X(n/p)からX(2n/p)-1をp1に。
---単純に昇順に未知数をプロセッサに割り当てる。
--cyclic allocation
---slideの式参照。
---プロセッサをひとつの未知数に順番に割り当てる。
---未知数を求めるにも動的に複雑な計算が必要。
---未知数をひとつのメッセージに入るようにグループ化するのも手間がかかる。
---時間のロスが大きいのであまり良い割り当てではない。
-slide40(Effects of computation and communication in Jacobi iteration)
--ヤコビ繰り返し法における計算と通信の影響
---解析をすることで並列を更に効率良くする足がかりになる。
---この図は先ほどヤコビ法の全体の実行時間と、計算と通信のそれぞれの時間成分を示している。
---n/pは整数。overall(全体の並列実行時間)は p = 16 で最小。
---Communicationはプロセッサが増えればそれだけ通信も増えるので増加。
---Computationはプロセッサが増えればそれだけ計算量が割り当てられるので減る。~
~
----------------------------------------------------------------------
-slide25(Prefix Sum Problem)プレフィックス総和問題
--X0・・・Xn-1の数列の全ての部分和。
--プレフィックス計算は、加算ではなく、結合則を満たす他の演算子を使っても定義できる。例えば乗算、最大値、最小値、論理操作(AND,OR,EXORなど)これらは、様々な計算モデルと関連して幅広く研究されている。プロセッサ割り当て、データ圧縮、ソート、多項式評価など。
-slide26
--16個の数値の部分和のすべてを求めるデータ並列法
-slide27(プレフィックス図)
--図の説明
-slide28(コード)
--コードの説明
-slide29(Synchronous iteration)
--同期式繰り返し。独立した繰り返しのインスタンスが複数ある場合、繰り返し手法(forall)で並列化できる。
--ひとつのループ中に複数処理があって、各プロセス(繰り返し)同時に処理がはじまり、全てが終わるまでは次のループにいかない。⇒ 同期式繰り返し。
--forall使用例
-slide30
--SPMDプログラムの場合のバリア使用例
-slide31(Another fully synchronous computation example)同期式繰り返しプログラムの例
--繰り返しによる線形連立方程式の解法。n個の未知数とn個の式からなる一般形を仮定する。X0・・・Xn-1(0<=i<=n)が未知数。
--これらの方程式を満たす未知数を求めるひとつの方法が繰り返しである。
-slide32
--式変換。
--この式(Σの式)は、Xiを他の未知数で表しており、各未知数のよりよい近似を得るための繰り返しの式として使用できる。
-slide33(Jacobi Iteration)ヤコビ繰り返し法
--すべてのXの値が一緒に更新される。
--行列aの対角要素の絶対値がその行の対角要素以外のaの要素の絶対値の総和より大きければ(行列aが対角優位であれば)このヤコビ法は収束することが証明できる。
--Σの式提示。この条件は十分条件であるが必要条件ではない。
--Why?
-slide34(Termination)終了
--終了は並列化において特に問題。
--簡単でよく用いる手法は、前の繰り返しで得られた値と新しく得られた値とを比較し、すべての値が[許容誤差の式]に収まれば、t回目の繰り返しで終了する。
--Xt,i = t回目のXiの値。Xt-1,i = t-1回目のXiの値。
--許容誤差が1%で実際は誤差が0.9999%のときもある。さらに次の計算も0.9998%ということもありえる。
--誤差は複合的なもので、計算値は最終の正しい値とはまだ相当に違っていることもありえる。
-slide35(Convergence)収束曲線
--グラフ説明
-slide36(Parallel Code)並列コード
--broadcast=receive?
--Allgatherは新しく計算されたX[i]の値をプロセスiから他のすべてのプロセスにsendし、他のプロセスから送信されたデータを集める。
---MPI_Allgather 各プロセスによって、同じ個数の項目が集められる。個数はパラメータで指定されている。
---MPI_Allgatherv 各プロセスで、異なった個数の項目を集める。
-slide37(Allgather)Allgather操作
図の説明
-slide38(Partitioning)分割
--すべての並列化がそうであったように、通常、プロセッサ数は処理されるデータ(項目→計算される未知数)の数よりずっと少ない。プロセッサがデータをたくさん処理するために問題(データ?)を分割する。
-slide39(block allocation & cyclic allocation)
--block allocation
---p個のプロセッサにn個の未知数があるとすれば、単純に昇順に未知数をプロセッサに割り当てる。
--cyclic allocation
---式参照。
---利点がない。未知数のインデックスを求めるにも複雑な計算が必要で未知数をひとつのメッセージに入るようにグループ化するのも手間がかかる。
-slide40(Effects of computation and communication in Jacobi iteration)
--ヤコビ繰り返し法における計算と通信の影響
---全体の実行時間と、計算と通信のそれぞれの時間成分を示している。
---n/pは整数。実行時間は p = 16 で最小。
終了行:
[[室橋/並列処理輪講2009]]
[[ヤコビ法 - wikipedia:http://ja.wikipedia.org/wiki/%E3%83%A4%E3%82%B3%E3%83%93%E6%B3%95]]~
[[ヤコビ法参考ページ:http://pc-physics.com/jacobi1.html]]
---------------------------------------------------------------------------
-slide25(Prefix Sum Problem)プレフィックス総和問題
--ここからはデータ並列アルゴリズムの例を説明します。
--X0・・・Xn-1の数列の全ての部分和を求めるアルゴリズム。
--(説明はslide27の図で)
-slide26
--16個の数値の部分和のすべてを求めるデータ並列法
-slide27(プレフィックス図)
--図の説明
--(slide25に戻る)
--プレフィックス計算は、加算だけでなく、結合則を満たす他の演算子を使っても定義できる。例えば乗算、最大値、最小値、論理操作(AND,OR,EXORなど) これらは、プロセッサ割り当て、データ圧縮、ソート、多項式評価など、幅広い計算モデルで研究されています。
-slide28(コード)
--Sequential code
---
--Parallel code
---forall
---
-slide29(Synchronous iteration)同期式繰り返し。
--独立した繰り返しが複数ある場合、繰り返し手法(forallとか)で並列化できる。
--ひとつのループ中に複数処理があって、各プロセス(繰り返し)同時に処理がはじまり、全てが終わるまでは次のループにいかない。⇒ 同期式繰り返し。
---(図で説明)
--forall code 使用例
-slide30
--(SPMDプログラムの場合の)バリア使用例
-slide31(Another fully synchronous computation example)
--同期式繰り返しプログラムの例として、ここではヤコビ法について説明します。
---ヤコビ法とはn元の連立一次方程を反復法で解く手法の1つです。
---X0・・・Xn-1(0<=i<=n)が未知数としてn個の未知数とn個の式からなる一般形を仮定します。
---(具体的な配列の図を示す)
-slide32
--式変換。i番目の式。
--この式(Σの式)は、Xiを他の未知数で表しており、各未知数のよりよい近似を得るための繰り返しの式として使用できる。
--ヤコビ法はまず全ての未知数の値を適当に決めます。そして、右辺(Σの式)に代入します。そうすると未知数(Xi)に計算された値が入ります。もし、適当に決めた未知数の値が、真の解であったら新たな解と一致するはずですが、普通そうは上手くいきません。得られた新たな解を再び右辺に代入するとまた新たな解が得られます。これらを繰り返すことで真に解に近似します。そして得られた解と一つ前に求めた解が、ある精度内であればそこで終了し解とみなします。
-slide33(Jacobi Iteration)ヤコビ繰り返し法
--すべてのXの値が一緒に更新される。
--収束条件
---行列aの対角要素の絶対値がその行の対角要素以外のaの要素の絶対値の総和より大きければ(行列aが対角優位であれば)このヤコビ法は収束することが証明できる。
---(行列図で説明)対角要素って?
---Σの式提示。この条件は十分条件であるが必要条件ではない。
-slide34(Termination)終了
--終了は並列化において特に問題。
--簡単でよく用いる手法は、前の繰り返しで得られた値と新しく得られた値とを比較し、すべての未知数(Xi)が[許容誤差の式]に収まれば、t回目の繰り返しで終了する。
--Xt,i = t回目のXiの値。Xt-1,i = t-1回目のXiの値。
--(slide35で説明)
--以下補足
---許容誤差が1%で実際は誤差が0.9999%のときもある。さらに次の計算も0.9998%ということもありえる。
---誤差は複合的なもので、計算値は最終の正しい値とはまだ相当に違っていることもありえる。
-slide35(Convergence)収束曲線
--グラフ説明
---てきとーに書いて比較。
---回数(t)多いほど、Error(誤差)が減っている(収束している)
-slide36(Parallel Code)並列コード
--(Allgatherをslide37で説明)
--Allgatherは新しく計算されたX[i]の値をプロセスiから他のすべてのプロセスにsendし、他のプロセスから送信されたデータを集める。
---Broadcast(送信)とgather(収集)を複合したもの。
-slide37(Allgather)Allgather操作
図の説明
-slide38(Partitioning)分割
--来週の内容の触り。
--すべての並列化がそうであったように、通常、プロセッサ数は計算されるデータ(未知数)の数よりずっと少ない。プロセッサがデータをたくさん処理するためにデータを分割する。
-slide39(block allocation & cyclic allocation)分割手法
--block allocation
---p個のプロセッサ、n個の未知数
---X0からX(n/p)-1をp0に、X(n/p)からX(2n/p)-1をp1に。
---単純に昇順に未知数をプロセッサに割り当てる。
--cyclic allocation
---slideの式参照。
---プロセッサをひとつの未知数に順番に割り当てる。
---未知数を求めるにも動的に複雑な計算が必要。
---未知数をひとつのメッセージに入るようにグループ化するのも手間がかかる。
---時間のロスが大きいのであまり良い割り当てではない。
-slide40(Effects of computation and communication in Jacobi iteration)
--ヤコビ繰り返し法における計算と通信の影響
---解析をすることで並列を更に効率良くする足がかりになる。
---この図は先ほどヤコビ法の全体の実行時間と、計算と通信のそれぞれの時間成分を示している。
---n/pは整数。overall(全体の並列実行時間)は p = 16 で最小。
---Communicationはプロセッサが増えればそれだけ通信も増えるので増加。
---Computationはプロセッサが増えればそれだけ計算量が割り当てられるので減る。~
~
----------------------------------------------------------------------
-slide25(Prefix Sum Problem)プレフィックス総和問題
--X0・・・Xn-1の数列の全ての部分和。
--プレフィックス計算は、加算ではなく、結合則を満たす他の演算子を使っても定義できる。例えば乗算、最大値、最小値、論理操作(AND,OR,EXORなど)これらは、様々な計算モデルと関連して幅広く研究されている。プロセッサ割り当て、データ圧縮、ソート、多項式評価など。
-slide26
--16個の数値の部分和のすべてを求めるデータ並列法
-slide27(プレフィックス図)
--図の説明
-slide28(コード)
--コードの説明
-slide29(Synchronous iteration)
--同期式繰り返し。独立した繰り返しのインスタンスが複数ある場合、繰り返し手法(forall)で並列化できる。
--ひとつのループ中に複数処理があって、各プロセス(繰り返し)同時に処理がはじまり、全てが終わるまでは次のループにいかない。⇒ 同期式繰り返し。
--forall使用例
-slide30
--SPMDプログラムの場合のバリア使用例
-slide31(Another fully synchronous computation example)同期式繰り返しプログラムの例
--繰り返しによる線形連立方程式の解法。n個の未知数とn個の式からなる一般形を仮定する。X0・・・Xn-1(0<=i<=n)が未知数。
--これらの方程式を満たす未知数を求めるひとつの方法が繰り返しである。
-slide32
--式変換。
--この式(Σの式)は、Xiを他の未知数で表しており、各未知数のよりよい近似を得るための繰り返しの式として使用できる。
-slide33(Jacobi Iteration)ヤコビ繰り返し法
--すべてのXの値が一緒に更新される。
--行列aの対角要素の絶対値がその行の対角要素以外のaの要素の絶対値の総和より大きければ(行列aが対角優位であれば)このヤコビ法は収束することが証明できる。
--Σの式提示。この条件は十分条件であるが必要条件ではない。
--Why?
-slide34(Termination)終了
--終了は並列化において特に問題。
--簡単でよく用いる手法は、前の繰り返しで得られた値と新しく得られた値とを比較し、すべての値が[許容誤差の式]に収まれば、t回目の繰り返しで終了する。
--Xt,i = t回目のXiの値。Xt-1,i = t-1回目のXiの値。
--許容誤差が1%で実際は誤差が0.9999%のときもある。さらに次の計算も0.9998%ということもありえる。
--誤差は複合的なもので、計算値は最終の正しい値とはまだ相当に違っていることもありえる。
-slide35(Convergence)収束曲線
--グラフ説明
-slide36(Parallel Code)並列コード
--broadcast=receive?
--Allgatherは新しく計算されたX[i]の値をプロセスiから他のすべてのプロセスにsendし、他のプロセスから送信されたデータを集める。
---MPI_Allgather 各プロセスによって、同じ個数の項目が集められる。個数はパラメータで指定されている。
---MPI_Allgatherv 各プロセスで、異なった個数の項目を集める。
-slide37(Allgather)Allgather操作
図の説明
-slide38(Partitioning)分割
--すべての並列化がそうであったように、通常、プロセッサ数は処理されるデータ(項目→計算される未知数)の数よりずっと少ない。プロセッサがデータをたくさん処理するために問題(データ?)を分割する。
-slide39(block allocation & cyclic allocation)
--block allocation
---p個のプロセッサにn個の未知数があるとすれば、単純に昇順に未知数をプロセッサに割り当てる。
--cyclic allocation
---式参照。
---利点がない。未知数のインデックスを求めるにも複雑な計算が必要で未知数をひとつのメッセージに入るようにグループ化するのも手間がかかる。
-slide40(Effects of computation and communication in Jacobi iteration)
--ヤコビ繰り返し法における計算と通信の影響
---全体の実行時間と、計算と通信のそれぞれの時間成分を示している。
---n/pは整数。実行時間は p = 16 で最小。
ページ名: