並列分散ソフトウェア
電子・情報工学系
新城 靖
<yas@is.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2003-12-04
あるいは、次のページから手繰っていくこともできます。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/
http://www.is.tsukuba.ac.jp/~yas/index-j.html
http://www.hlla.is.tsukuba.ac.jp/~yas/index-j.html
次の3つを合算する。
- クイズ
- 並列プログラムのレポート
- 分散プログラムのレポート
並列プログラムの作り方
- パラダイム
- 例: 家の建築
- 手法
- メッセージ・パッシング
- ライブ・データ構造体
- 分散データ構造体
- 例: N-体問題
- Linda
- rd(), in(), out(), eval()
- パタン: Task Bag, 配列、ストリーム
資料
- Nicholas Carriero (著), David Gelernter (著), 村岡 洋一 (翻訳), "
並列プログラムの作り方", 共立出版 (1993). ISBN: 4320023625
- Nicholas Carriero , David Gelernter: "How to write parallel
programs: a guide to the perplexed", ACM Computing Surveys, Vol.21,
No.3, pp.323-357 (September 1989).
- 並列
- 速く解きたい
- 分散
- 離れていても心は1つ
逐次処理は非常に特殊。
- 歴史的な都合。ハードウェアが高かった。
- 逐次プログラムの書きやすさ。制限をつけた方がわかりやすい。
共通の話
- プロセッサが複数
- プロセスか複数
- プロセス間の協調(coordination)が必要。同期、通信。
- 資源割り当ての最適化、スケジューリングが重要
分類
- 共有メモリがある
- アクセスが均質: UMA (Uniform Memory Access), SMP (Symmetric Multiprocessor)
- アクセスが不均質(100倍くらい): NUMA (Non-uniform Memory Access)
- 共有メモリがない: NORMA (No-Remote Memory Access)
態度
- 人間が書きやすいもので書く。
- ハードウェアの性能を引出すように書く。
- 変換する。
2つの言語が必要
- 計算言語
- 個々の活動を記述
- 協調言語
- 統一されたプログラムに組み立てるための「糊」
-- 並列/分散プログラムのパタン。
- パラダイムを選ぶ
- パラダイムに合った手法(Methods)で書く
- メッセージ・パッシング
- ライブ・データ構造体
- 分散データ構造体
- プログラム変換する
性能が十分でない場合には、他のパラダイムを使って書き直す
並列処理の最終結果に焦点を当る。
例: 家の建築:
- 壁(前、後ろ、両脇、内部)、土台、屋根に大工を割り当てる
- 全大工が並列に仕事をする
並列処理を行う作業者に焦点を当る。
例: 家の建築:
- 計測士、基礎工、大工、鉛管工、電気屋などの専門家が流れ作業的(pipeline)におこなう
並列処理の手順に焦点をあてる
例: 家の建築:
- 何でもやる作業者がいる
- 壁、土台、屋根の作業手順がある(動的に生成されることもある)
- 各作業者は、前の仕事が終わったら、次の手順を見ながら仕事をする
問題にあったものを使う。
実際の家の建築では、全部の方法が使われている。
簡単。
結果のデータ構造を得るための依存関係が予めわかっている時に便利。
うまく行く例:ベクトルの足し算: S[i] = A[i] + B[i]
- n 要素のベクトルを作る
- S[i] は、A[i] と B[i] を加えればわかる。
出力データが不明なもの、結果が1つのもには適していない。
- テキスト処理、コンパイラ、
- 結果が可変
- LU分解(繰り返しがある)
- OS、実時間
- 結果というよりは作用が大事
マスタ・ワーカ
- マスターが計算を始める
- 同一のワーカ・プロセスの集合を作る
- ワーカ、どの仕事でもやる。
- 仕事がなくなれば終わり
うまく行く例: データベースの項目から、ある関数の値が最小のものを探す
- マスターは、袋(task bag)の中にデータ・レコードを全部入れる
- 各ワーカは、袋から取り出して(複雑な)関数の計算を行い、
結果をマスターに返す
- マスターは、ワーカから送られてきたものの最小のものを記録する。
- 全部が終われば終わり。
プロセスのネットワークが作られる
例:輸送時間見積もり
- プロセス
- 道路(都市)
- データ
- トラック
道路が並列。複数のデータが流れる。
- データ並列
- 各要素について同じ変換(transformation)を適用する
- 変換=手順で、プロセスが次々とデータを取っては処理するならば、手順並列法
- 推論並列(OR 並列)
- ヒューリスティック検索、木検索の各枝について要・不要を選択する
- 選択=手順で、プロセスが次々と枝を調べるならば、手順並列法
- メッセージパッシング(Message Passing)
- ライブデータ構造体(Live Data Structure)
- 分散データ構造体(Distributed Data Structure)
視点
- プロセスの中にデータが含まれる。
- 対応パラダイムは、専門家並列法
- プロセス生成は明示的
- 通信も明示的
TSD (Thread Specific Data)
図
- データの中にプロセスが含まれている。プロセスはデータを1つ作って死ぬ。
- 対応パラダイムは、結果並列法
- プロセス生成は暗黙的
- 通信も暗黙的
関数型言語
図
- データとプロセスは独立
- 対応パラダイムは、手順並列法
共有メモリのマルチスレッドは、TSD をのぞいてだいたいこれ。
N個の物体の位置をq時間単位分計算する。
位置の配列: M[i][j]、i=0..N-1, j=0..q
M[][0] に最初の位置。
position(i,j), 繰り返し j での 物体 i の位置を計算する。
図
手順(ワーカの仕事):集合に含まれている全ての物体について、次の位置を
計算する。
マスタで、N 個の物体を作る。
ワーカを作る。ワーカの数は、N 個ではなくて、もっと少ない(CPU数と同じに
する)。
物体の位置を分散データ構造体(共有メモリ)に置く。
図
物体に対応したプロセスを作る。
図
- 問題に適したパラダイムわ選ぶ
- パラダイムに適した手法でプログラムを書く
- 必要なら効率のよい手法で書き直す
(粒度の調整)
図
- アブストラクション
- データとプロセスの結び付きを切る
- スペシャリゼーション
- データとプロセスから分離して分散データ構造体におく
- クランピング
- 通信を明示的に行うようにする
- デクランピング
- 通信を暗黙的にに行うようにする
問題1: ライブデータ構造体でプログラムを書いたらプロセス生成が多くて
性能が出ない。
解決1:ライブデータ構造体を、受動的な構造体に書き換える。プロセスを複数
の構造体に対応させる。
問題2:分散データ構造体で書いたプログラム(共有空間が必要)が、NORMA で
うまく動かない。
解決:メッセージ・パッシングに変換する。
Carriero と Gelernter の主張:分散データ構造体がいい。
Java では、スレッド、RMI、Javaspaces の順に導入された。
- 1. ライブデータ構造体
- データフロー: Id Nouveau
- 関数型言語: Multilisp, Sisal
- 2. 分散データ構造体
- 言語:HPF
- 共有メモリとロック/セマフォ
- DSM: Orca, Munin, Midway, Linda
- 3. メッセージパッシング
- 特殊言語:CSP/Occam
- RPC:Ada
- ライブラリ:PVM, MPI
モニタ:Concurrent Pascal, Modula
モニタは、メッセージパッシングの仲間か分散データ構造体か。
協調言語(<−>計算言語)。
タプルペースモデル(tupple space model)で分散データ構造体を支援。(メッ
セージ・パッシングやライブデータ構造体的なプログラムも書ける。)
タプルの集合である。
タプルは、型付きの値の並び。
タプルの例:
("a string", 10.01, 17, 10)
(0,1)
2種類のタプル
- データタプル
- 受動的
- ライブタプル(プロセスタプル)
- 全部が同時に実行している。
データタプルを読み書きする。
終了するとデータタプルに変化する。
タプルスペースを操作する基本4命令
- out()
- タプルをタプル空間内に生成する。(受動的なタプル)
- in()
- タプルを取り去る
- rd() -- (read)
- in と似ているが、タプルがタプルスペースに残る。
- eval()
- out() と似ているが、新たにプロセスが作られて、そのプロセスによりタ
プルが評価される。(ライブタプル)
predicate つき(デットロック対策で使う)
- inp()
- in() と同じだが、見つからなければ 0 を返す
- rdp()
- rd() と同じだが、見つからなければ 0 を返す
out("a string", 10.01, 17, x)
in("a string", ?f, ?i, y)
「?」付のものは、formal。型が同じものとマッチする。
ついていないものは、actual。型と値が同じものとマッチする。
eval("e", 7, exp(7))
in(), out() で同期がとられる。
- 要素が全て同じか区別できないような構造体。逐次ではあまり使われない。
- 要素が名前で区別できる。C言語の構造体。オブジェクト。
- 要素が位置て区別される。
- ランダムアクセスされる。配列。連想配列。
- 逐次アクセスされる。リスト、木、グラフなど。
スクリプト言語(Perl、awk)の連想配列と同じ。
タプルの形式: (name,val)
読込み:
rd(name,?val)
変更:
in(name,?val)
val = ... val ... ;
out(name,val)
P命令: in("sem")
V命令: out("sem");
同じタプルを out したら溜る。
仕事を入れる: out("task",TaskDescription)
仕事を取り出す: in("task",?NewTask)
逐次:
for( i=0 ; i<N; i++ )
{
func(i,args);
}
並列:
for( i=0 ; i<N; i++ )
{
eval ("loop-33", func(i,args) ); // プロセス生成
}
for( i=0 ; i<N; i++ )
{
in("loop-33", 1 ); // 待ち
}
func(i,args)
{
...
return( 1 );
}
全部のプロセスが到着してから次に進む。
図
n プロセスのバリア
初期化: out("barrier-37",n)
各プロセス:
in("barrier-37",?val)
out("barrier-37",val-1)
rd("barrier-37",0)
A[10][10];
("A",0,0,val00)
("A",0,1,val01)
("A",0,2,val02)
...
("A",9,9,val99)
ローカルのメモリと遅い大域的な共有メモリ
1人が読むとデータが消える。
("stream",0,val0)
("stream",1,val1)
("stream",2,val2)
...
ポインタ
("stream","head",0)
("stream","tail",0)
ストリームに要素を追加:
int index;
in("stream","tail",?index);
out("stream","tail",index+1);
out("stream",index,new_element);
ストリームから要素を取り出す:
int index;
in("stream","head",?index);
out("stream","head",index+1);
in("stream",index,?element);
これは、複数source、複数sink。
source、sinkが1つなら、head, tail をタプルスペースに置かなくてもよい。
1つのストリームを、複数の読み手でアクセスできる(マルチキャスト)。
head の代わりに、局所変数でアクセスする。
ストリームから要素を取り出す:
int index=0 ;
while( ... )
{
rd("stream",index++,?element);
}
- eval を使ってプロセスを作る。
- ストリームでプロセスを結合する。
問題: ランデブは、どうするか。
RPC はどうするか。
- 受動タプル(out)ではなくライブタプル(eval)を使う。
- 結果は配列かもしれない。
並列プログラムの作り方
- パラダイム
- 例: 家の建築
- 手法
- メッセージ・パッシング
- ライブ・データ構造体
- 分散データ構造体
- 例: N-体問題
- Linda
- rd(), in(), out(), eval()
- パタン: Task Bag, 配列、ストリーム
↑[もどる]
・[12月04日]
・[12月11日]
Last updated: 2003/12/18 03:35:17
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>