- 著者
-
枝廣 正人
山下 慶子
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. DC, ディペンダブルコンピューティング (ISSN:09135685)
- 巻号頁・発行日
- vol.106, no.603, pp.19-24, 2007-03-08
マルチコア向けの並列ソートアルゴリズムMap Sortを提案する.今後単体CPUの性能向上が鈍化し、プロセッサがマルチコアによって性能向上する時代では、並列対応されていないソフトウェアは計算機が進歩しても性能は向上しない。従って単体CPUでは従来と同等処理時間で、かつ並列CPUではスケーラブルに性能向上するようなアルゴリズムが必須となるが、我々はそれをスケーラブルアルゴリズムとよんでいる。本論文ではソート問題を取り上げ、新しいスケーラブルアルゴリズムMap Sortを提案する。Map Sortの時間に関する計算複雑度はN個のデータ、P台のCPUで0((N/P) log N)であり、単体CPU上での下界値0(N log N)の(1/P)である。また計算機実験の結果、単体CPU上のクイックソートと比較し、単体CPUでは同等性能、4CPUでは3倍の性能向上であることが示された。