＜ プログラムの説明 ＞


【 概要 】

  並列環境でのマルチ集合の高速な演算モジュールである.

  N をある定数( 素数 )として, 内部表現は

	[ Ｌ0, Ｌ1, ... , Ｌ(N-1) ]
	Ｌk = [ 要素１の値, 要素１の個数, 要素２の値, 要素２の個数, ...]

という N 個のリストのリストで, その要素 Ｌk は個数つきのソートされたリスト
である. ノード数 P のとき, 第 k リスト Ｌk は ノード

	Node = k mod P

において演算が行なわれる.  マルチ集合の演算において, Ｌi と Ｌj (i≠j) は
独立しているのでノード間に跨った演算は起こらない. また, N を適切な値に選ぶ
と, 負荷は P 個のノードへ均等に分配される.

  リスト長を Len としたときの, (逐次処理での) encode のコストは,

	平均: O( Len log(Len / N) )
	最悪: O( Len log(Len) )

である. ただし, 最悪の場合が起こる可能性は非常に低い.

  また, decode, union,intersection など一連の演算は O(Len), choose は定数
時間で処理される.


【 内部表現と負荷分散 】

  並列環境では負荷分散方式の決定が最も重要である. 特に, 共有メモリへのアク
セスを可能な限り少なくするのがよい. 以下, 内部表現と負荷分散方式を検討して
いく.

  ここでは, 処理するデータは整数の集合であるから, 入力リスト L の各要素 X 
を定数 N の剰余 X mod N によって N 個のリストに分配し, 内部表現は

	[ Ｌ0, Ｌ1, ... , Ｌ(N-1) ]   (N は定数)

という, N 個のリスト Ｌ0 .. Ｌ(N-1) を並べたリストとする. 各リストＬk は

	Ｌk = [ 要素１の値, 要素１の個数, 要素２の値, 要素２の個数, ...]

のように, 値と個数の組を, 要素の値の昇順に並べたリストである. リストＬkの
任意の要素 X は

	X mod N = k

を満たす ( N による剰余が k ). また, リストＬk は空リストでもよい.

  例えば, N=3 のとき, 次のマルチ集合

	L = [0,0,1,1,1,2,2,2,2,3,3,3,3,3,4]

の内部表現は,

	M = [[0,2,3,5],[1,3,4,1],[2,4]]
	    ( [ 0 が 2 個, 3 が 5 個 ], [ 1 が 3 個, ...], ... )

となる.

  定数 N の剰余によって N 個のリストに振り分けたため, マルチ集合の演算に関
しては, Ｌi と Ｌj ( i ≠ j ) は独立している. 従って, union, intersection 
といった２つの集合 M と M' の演算を行なう際にはそれぞれ k ( 0 ≦ k ≦ N-1 ) 
番目のリスト Ｌk と Ｌ'k を比較していくだけで良い. そのため, ノード数を P 
としたときに, 各リスト Ｌk の処理をノード

	Node = k mod P

で行なうようにすると, 複数ノードにまたがった演算は起こらない. さらに, 要素 
X を常にノード

	Node = ( X mod N ) mod P

に割り振ることが保証できるので, ノードのキャッシュを有効に活用でき, 共有メ
モリへのアクセスを削減できる.

  上の式 ( X mod N ) mod P において, N を素数にとると, 入力が「すべて偶数」
のように偏っていても, N の剰余は良い具合にランダムになる. N を十分大きい値
にとれば, 入力が「すべて N の倍数」や「N による剰余が等しい」といった極端
に偏ったものになる確率を十分低くできる. さらに, マルチ集合の要素数を Len 
としたとき,

	P << N << Len , ( N は素数 )

であるように N を選ぶと, 実質的にどんな入力に対しても P 個のノードへ均等に
負荷を分散できる. ここでは, P ≦ 16 を考慮して,

	N = 307

とした.


【 エンコード 】

  入力リストを N 個に分配することはエンコードにとっても有利である.

  内部表現は

	[ Ｌ0, Ｌ1, ... , Ｌ(N-1) ]
	Ｌk = [ 要素１の値, 要素１の個数, 要素２の値, 要素２の個数, ...]

という形式で, Ｌk は個数つきのソートされたリストであった. 各リスト Ｌk の
ソートには高速で安定したマージソートを用いる. 入力リスト長を Len としたと
き, ＬK の平均のサイズは Len / N であるから, ソートのオーダを下げることが
でき, コストは,

	平均: O( Len log(Len / N) )
	最悪: O( Len log(Len) )

である. ただし, 最悪の場合は, 要素の N による剰余がすべて等しいときであり, 
起こる可能性は非常に低い. 各リスト Ｌk のソートはノード k mod P で行なわれ
る.


【 マージソートについて 】

  マージソートは入力に最初の並び方に左右されず, 安定して NlogN 回の比較で
整列する. まず, encode モジュール中の mergesort_init で整数のリストを

	[ [ 値, 個数, 値, 個数 ], [ 値, 個数, 値, 個数 ], ... ]

のように初期化する. mergesort(L,M) の入力 L は上のような, リストのリストで
ある. merge_pairs(L,R) はリスト L の要素(リスト)を先頭から順に２個ずつマー
ジしていく. すなわち, mergesort が merge_pairs を呼ぶたびに, ボトムアップ
に整列が進行していく.


--------------------------------------------------------------------------
    宇佐治彦    東京大学工学系研究科
                E-Mail: usa@logos.t.u-tokyo.ac.jp