CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム(<特集>並列・分散)

スポンサーリンク

概要

論文の詳細を見る
本稿では, 近年注目されている並列計算モデルであるCGMモデル及びBSPモデル上で, 要素数nの選択及びソートを行う決定性の並列アルゴリズムを提案する.まず最初に, 内部計算時間がO(n/p)時間, 通信ラウンド数がO(min(log p, loglog n)のコスト最適な選択を行う並列アルゴリズムを提案する.次に内部計算時間がO(n/p log p)時間, 定数通信ラウンド数の通信ラウンド数が最適な並列アルゴリズムを提案する.上記の2つのアルゴリズムは, n/p≥P^εかつε>0を満たすプロセッサ数pに対して動作する.最後に, 2つ目の選択アルゴリズムの拡張として, n/p≥P^2を満たすpに対して, O(n/p log n)時間, 定数通信ラウンド数でソートを行うアルゴリズムを提案する.
一般社団法人情報処理学会の論文
1998-03-23

著者

関連論文

もっと見る

スポンサーリンク