並列プログラミングスタイル(2)

並列分散ソフトウェア

                                       電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2003-12-11
あるいは、次のページから手繰っていくこともできます。
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

■今日の重要な話

並列に素数を求める 資料

■素数を求める

よい例題

◆結果並列法とライブデータ構造体

考え方 次のようなベクトルをタプルスペースに作る。
("primes", 2, 1 ) // primes[2] = 1 ;
("primes", 3, 1 ) // primes[3] = 1 ;
("primes", 4, 0 ) // primes[4] = 0 ;
("primes", 5, 1 ) // primes[5] = 1 ;
("primes", 6, 0 ) // primes[6] = 0 ;
("primes", 7, 1 ) // primes[6] = 1 ;
..

プログラム

利点

問題点

◆手順並列法

結果並列のプログラムをアブストラクションやその他のさまざまな工夫により 手順並列に書き換える。 Linda の表記法:object:count 。配列の最初の count 個の要素。in、または、 rd で ? object:count と書くと、count には要素数が入る。

プログラム

◆専門家並列法

エタトステネスのふるい。 最終的には、次ようなパイプラインを作る。
source | pipe_seg-3 | pipe_seg-5 | pipe_seg-7 | .... | sink
source
整数列を生成する(5以上の奇数だけ)。
sink
見つかった素数 n について、pipe_seg(n,,) を作る(eval)。
pipe_seg(n,next,)
自分宛てのストリーム( ("seg",n,i,?num) )を受け取り、 n で割りきれないものを pipe_seg(next,,) に流す。
各パイプのセグメントは、次のようなストリームが流れる。
("seg", 宛先, ストリームのインデックス, 整数)
たとえば、source の出力(主に pipe_seg-3の入力)は、次のようになる。
("seg", 3, 0, 5 ) // sink が in
("seg", 3, 1, 7 ) // 以下 pipe_seg-3 が in する
("seg", 3, 2, 9 )
("seg", 3, 3, 11 )
("seg", 3, 3, 13 )
...
pipe_seg-3 の出力は、次のようになる。
("seg", 5, 0, 7 )  // sink が in する
("seg", 5, 1, 11 ) // 以下  pipe_seg-5 が in する
("seg", 5, 2, 13 ) 
...
最終的には、次のようなデータがタプルスペースに残される。
("source", 1, 2)
("pipe seg", 2, 3)
("pipe seg", 3, 5)
("pipe seg", 4, 7)
...
("sink", MaxIndex, MaxPrime)
プログラム

この方法は、結果並列や手順並列法よりも、並列性が低い。

◆結論


↑[もどる] ←[12月04日] ・[12月11日] →[12月18日]
Last updated: 2003/12/18 03:49:17
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>