並列分散ソフトウェア
電子・情報工学系
新城 靖
<yas@is.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/2001-12-06
あるいは、次のページから手繰っていくこともできます。
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
(1) Linda のタプルには変数は含まれない。
正: ("a string", 10.01, 17, 100)
誤: ("a string", 10.01, 17, x)
(1) read ストリームでは、in() ではなくて rd() を使う
正:rd("stream",index++,?element);
誤:in("stream",index++,?element);
並列処理の最終結果に焦点を当る。
例: 家の建築：
例: 家の建築：
問題にあったものを使う。
実際の家の建築では、全部の方法が使われている。
うまく行く例:ベクトルの足し算: S[i] = A[i] + B[i]
図
図
M[][0] に最初の位置。
position(i,j), 繰り返し j での 物体 i の位置を計算する。
図
マスタで、N 個の物体を作る。
ワーカを作る。ワーカの数は、N 個ではなくて、もっと少ない(CPU数と同じに する)。
物体の位置を分散データ構造体（共有メモリ）に置く。
図
図
解決１：ライブデータ構造体を、受動的な構造体に書き換える。プロセスを複数 の構造体に対応させる。
問題２：分散データ構造体で書いたプログラム（共有空間が必要）が、NORMA で うまく動かない。
解決：メッセージ・パッシングに変換する。
Carriero と Gelernter の主張：分散データ構造体がいい。
Java では、スレッド、RMI、Javaspaces の順に導入された。
モニタは、メッセージパッシングの仲間か分散データ構造体か。
タプルペースモデル(tupple space model)で分散データ構造体を支援。（メッ セージ・パッシングやライブデータ構造体的なプログラムも書ける。）
タプルは、型付きの値の並び。
タプルの例:
("a string", 10.01, 17, 10)
(0,1)
２種類のタプル
out("a string", 10.01, 17, x)
in("a string", ?f, ?i, y)
「?」付のものは、formal。型が同じものとマッチする。 ついていないものは、actual。型と値が同じものとマッチする。
eval("e", 7, exp(7))
in(), out() で同期がとられる。
タプルの形式: (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)
("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が１つなら、head, tail をタプルスペースに置かなくてもよい。
head の代わりに、局所変数でアクセスする。
ストリームから要素を取り出す:
int index=0 ;
while( ... )
{
rd("stream",index++,?element);
}