選択問題を解くBSPモデル及びBSP^*モデル上の並列アルゴリズム

概要

論文の詳細を見る
本論文では, BSP(Bulk-Synchronous Parallel)モデル及びBSP^*モデル上で選択問題を解く並列アルゴリズムを提案する. BSPモデル及びBSP^*モデルは, 近年提案された並列計算モデルであり, 最近の並列計算において重要とされている通信コストを, 同期周期 L, 通信路帯域幅の逆数 g, パケットサイズ Bといったパラメータにより表すことを可能にしたモデルである. 本論文では, データ数 nの選択問題に対し, p個のプロセッサを用いてBSPモデル上で任意の整数d(1≦d≦logn)に対し内部計算時間0(n/p+dlogploglogn+L(logploglogn)/(logd)), 通信時間0(gn/p+(gd+L)(logploglogn)/(logd)), また, BSP^*モデル上で内部計算時間0(n/p+dloglogn+L(logploglogn)/(logd)), 通信時間0(g(n/(pB)+(n/p)^1/7(logp)^6/7)+(gd+L)(logploglogn)/(logd))の並列アルゴリズムを提案する.
社団法人電子情報通信学会の論文
1999-04-25