Parallel Selection Algorithms for CGM and BSP Models with Application to Sorting (特集並列処理) -- (並列・分散アルゴリズム)

概要

論文の詳細を見る
In this paper, we present two deterministic selection algorithms with application to sorting for the CGM and BSP models. The first is a parallel algorithm whose computation time is cost optimal, which runs with O(n/p)computation time and O(min(log p, log log n))communication rounds for n/p≥p^ε and ε>0. The second is a parallel algorithm whose number of communication rounds is optimal, which runs with O(n/p log p)computation time and a constant number of communication rounds for n/p≥p^ε and ε>0. In addition, we apply the second selection algorithm to sorting. The sorting algorithm runs with O(n/p log n)computation time and a constant number of communication rounds, when n/p≥p^ε and ε≥2.
一般社団法人情報処理学会の論文
2000-05-15