プログラムの並列化
2004年5月7日
吉田仁
目次
並列アプリケーションの例
並列化するには
並列プログラムの例
並列アプリケーションの例
海洋シミュレーション
多体問題シミュレーション
レイ・トレーシング
データ探索
多体問題シミュレーション(1)
空間上にあるn体の星について
の微分方程式を数値シミュレーションすることで
星の動きを予想する
レイ・トレーシング
光が通る道を追跡して3Dオブジェクトを2Dディス
プレイ上に表現する。
多体問題シミュレーション(2)
充分に遠い星団は纏めて考えることが
できる
並列化するには
Sequential
Decomposition
Assignment
computation
Tasks
Processors
Processes
Mapping
Parallel program
Orchestration
並列プログラムの例
 海洋シミュレーション型の具体例を考える
 問題設定
(n+2)2の正方形に集まった点の集合を考える
内側にあるn2の点について、以下の式に基づいてデータを
更新する
更新によるデータの差が指定値以下になるまで繰り返す
Decomposition(1)
プログラム1
 単純に記述してみた
 逐次プログラムなので、処理が遅い
 これを並列化して早くする
Decomposition(2)
解決案その1
 処理が矢印のように影響
を与えることを考えると、
同一点線上のタスクは並
列化できる。
 O(n2)→O(n)
Decomposition(3)
解決案その2
 順番を無視すると、影響を与
えるのは回りの4点だけ
 市松模様で考えると、同じ色
の点の影響を受けない
 1回のSweepを赤黒の2つ
のSweepに分ける
 それぞれの色については
全てを並列化可能
 O(n2)→O(1)
Decomposition(4)
順番を無視するならプログラム2が最適?
 それだけの数を全て同時に並列処理させることは現実的に
は不可能
 プロセッサごとに偏りができるかもしれない
Assignment
プロセスにどれだけのタスクを
割り当てるかもプログラムに
記述する
以下、n/p行ごとに分け、各プ
ロセスに割り当てるようにする
P0
P1
P2
Orchestration(1)
プログラム3
DECOMPはnprocsのプロセスにタスクを振り分け
るよう指示を出す
REDUCEはmydiffの総和をdiffに代入する
この2つで具体的にどの様なことをしている
か分かりづらい
もう少し低級で書き換える
Orchestration(2)
プログラム4
CREATEではnprocs-1個のプロセスを作り、それぞれ
Solveを呼び出させている
WAIT_FOR_ENDは全プロセスの終了を待つ
BARRIERで同期を取っている
LOCK,UNLOCKは排他処理を行っている
排他処理
 ほぼ同時にdiffへアクセスがあった場合、以下のよ
うなエラーが起こることがある
P2
P1
r1 ← diff
{P1 gets 0 in its r1}
r1 ← diff
r1 ← r1 + r2 {P1 sets its r1 to 1}
diff ← r1
{P2 gets 0 in its r1}
r1 ← r1 + r2 {P2 sets its r1 to 1}
{P1 stores 1 into diff}
diff ← r1
{P2 stores 1 into diff}
 変数にロックをかけることでこのようなエラーを防ぐ
ことができる
Orchestration(3)
メモリがプロセッサごとにバラバラにあった
ら?
インターネットやLANで繋がれたコンピュータのよう
に、現実的。
プログラム5
Orchestration(4)
 myAはプロセッサごとのメモリ確保なのでmallocを
使っている
 16a~16dでは、隣のプロセッサと境界データの交
換をしている
 SENDは指定IDのプロセスへデータを送信する
 RECEIVEはデータを受け取るまで待機する
データ交換
SEND
RECEIVE
RECEIVE
SEND
Orchestration(5)
理論上はこれで上手く行くはず
通信路のエラーがあり得る
SENDが送信後、確認通知が来るまで待つ/待たない
が問題になる(確実にするか、速くするか)
プロセスが途中で死ぬことがあり得る
対故障処理
オーバーヘッドがある
分けすぎると逆に遅くなることもある
現実には、このようなことも考える必要がある
ダウンロード

PPT