マルチ集合演算モジュール multi_set 並列版版説明書 ◎各述語の仕様 モジュール multi_set の以下の述語により、マルチ集合演算を行います。 1. encode(L, M) 入力：L : 整数の線形リスト 出力：M : マルチ集合の内部表現形式 マルチ集合を表す L を、内部表現形式 M に変換します。 M は、実行時のノード数を n として、 M = multiset(M1,...,Mn) Mi = [e(Int, Num), ...] という形式になっており、マルチ集合の要素が、値 Int とその個数 Num で 表されます。また、各エントリ e(Int, Num) は i = Int mod n としたとき Miに属し、それぞれのMi中で、Int の値で昇順にソートされています。 2. decode(M, L) 入力：M : マルチ集合の内部表現形式 出力：L : 整数の線形リスト マルチ集合の内部表現形式を、整数の線形リストに変換します。 3. union(M0, M1, M) 入力：M0: マルチ集合の内部表現形式 M1: マルチ集合の内部表現形式 出力：M : マルチ集合の内部表現形式 内部表現形式のマルチ集合 M0, M1 の和集合を計算し、それを M に返します。 4. intersection(M0, M1, M) 入力：M0: マルチ集合の内部表現形式 M1: マルチ集合の内部表現形式 出力：M : マルチ集合の内部表現形式 内部表現形式のマルチ集合 M0, M1 の積集合を計算し、それを M に返します。 5. difference(M0, M1, M) 入力：M0: マルチ集合の内部表現形式 M1: マルチ集合の内部表現形式 出力：M : マルチ集合の内部表現形式 内部表現形式のマルチ集合 M0, M1 の差集合を計算し、それを M に返します。 6. contraction(M0, M) 入力：M0: マルチ集合の内部表現形式 出力：M : マルチ集合の内部表現形式 内部表現形式のマルチ集合 M0 中の同一要素の重複を取り除き、その結果を M に返します。 7. choose(M, E, S) 入力：M : マルチ集合の内部表現形式 出力：E : 取り出した要素を表す整数 S : マルチ集合の内部表現形式 内部表現形式のマルチ集合 M0 より、要素を一つ取り出し、E に返します。 また、残りのマルチ集合を内部表現形式で S に返します。 Eは、内部表現形式で先頭にある要素が選択されます。また、M はかならず 1 個以上の要素を含んでいなければなりません。 ◎設計の方針 プログラムは、基本的に動作速度を優先して作成しました。 このため、 ・リダクションオーバヘッドを減らすため、まとめられる部分は一つの 節内に押し込んでしまいました。そのため、エンコードまわりなどは 可読性が犠牲になっています。 ・仕様で求められていない限り、エラーチェックなどはすべて省いてい ます。 また、並列版では、ノード間の通信を減らすことを重視して設計しました。 データの内部表現形式は、集合演算述語が呼び出された際にデータ分割を容 易にするため、あらかじめノード個数分の線形リストの形で表されています。 各リストは、逐次版で採用した、同じ要素をまとめて要素数と個数の組で表 すという形をとり、集合の各要素がどのリストに属するか(つまり、どのノ ードが処理を担当するか)は、(要素値 mod ノード数)で決定します。 この方式では、データ内容に偏りがあった場合、各ノードの処理量が一定に ならず、並列性が落ちる可能性があります。たとえば、偶数値のみを要素に 持つマルチ集合だった場合には、ノードの半数は仕事をしなくなります。 しかし、集合演算において、同じ値の要素がかならず同じノード上にあるこ とが保証されるので、データ分割後は各ノードが通信なしで並列計算を行え るというメリットがあります。また、仮に仕事量の少ないノードが生じたと しても、負荷分散処理が軽いため、最悪でも逐次版と同程度の速度は保証さ れます。 データの偏りに対応するため、バランス木を等分して各ノードが担当するな どの方法も検討しましたが、演算のたびにデータの再分散が必要になるため、 並列化の最大性能があまり高くならず、負荷分散の粒度などによっては、逐 次版より性能が低下する可能性も考えられます。今回は、データにあまり偏 りがないことを仮定して、前述の方式を採用しました。評価用のデータによ っては並列性が低くなる可能性はありますが、実際の応用を考えると、ほと んど偶数値を取るマルチ集合のような極端な場合は、そういう性質が事前に 判っていると予想されるので、処理ノードの計算式を単なるモジュロから適 当な式に修正すれば対応できます。 逐次処理される単位については、逐次版とほぼ同等の処理を行っています。 1 ノード上の処理単位は、昇順にソートされた(要素値, 個数)の組のリスト になっており、この形式では、エンコード処理がある程度重くなるものの、 演算については union, intersection など、すべてリストを一回パースす るだけで終了します。また、contraction は各エントリの個数を 1 にする だけで済みます。このため、一度エンコードを行った後、内部表現形式によ る演算がある程度繰り返される限りは、かなり効率よく動作するはずです。 プログラムについては、基本的に逐次版の上に、データ分散用の述語を被せ た形になっています。 エンコードを並列に行うため、まずエンコード形式の外殻となるファンクタ をつくり、各引数を未具体化変数としておきます(init_unbound_functor/3)。 つぎに、gen_encoder/3 により、逐次版のエンコード部と同等のプロセス (sort/3)を各ノード上に生成し、それぞれが入力リストをエンコードし、 その結果を先の各未具体化変数の値とするようにします。 次に、split_data/3 により、元の入力リストをモジュロにより分割し、各 整数をそれが属するノードに割り振ります。ここで、split_data/3 と、各ノ ード上の sort/3 の間で 1 対 n のストリーム通信を行うため、divlist/n というファンクタを用いています。これは最初各引数が未具体化変数であり、 i 番目の引数をノード(i-1)上の sort/3 と split_data/3 が共有しています。 sort/3 はこれを一般の(入力)ストリーム変数と同様に扱い、split_data/3は 元リストの入力要素 Int 毎に、Intが属するノード (i-1) を判定し、 divlist/n の i 番目の引数変数を [Int | NewVar]で具体化します。また、 その引数を NewVar で置き換えたものを新たな divlist/n として再帰ループ することにより、sort/3 の入力ストリームに対して、次々と値を出力するこ とができます。 union などの演算述語については、すでにデータ分割は終わっているので、フ ァンクタ multiset/n の各引数を各ノードに送信し、並列に処理を行います。 ここで、以前にエンコードや演算が行われた集合については、同じ要素は再び 同じノードが担当するので、物理通信によるデータ転送が生じないことが期待 できます。ただし、共有メモリ環境ではこの利点は生かせないので、あまり性 能はでないかもしれません。