著者

藤原 暁宏 石水 隆 井上 美智子 増澤 利光 藤原 秀雄

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. PRO, [プログラミング]

巻号頁・発行日

vol.98, no.30, pp.129-136, 1998-03-23

---

本稿では, 近年注目されている並列計算モデルである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)時間, 定数通信ラウンド数でソートを行うアルゴリズムを提案する.