Map Sort：マルチコアプロセッサに向けたスケーラブルなソートアルゴリズム

摘要

マルチコア向けの並列ソートアルゴリズムMap Sortを提案する。 今後単体CPUの性能向上が鈍化し、プロセッサがマルチコアによっで性能向上する時代では、並列対応されていないソフトウェアは計算機が進歩しても性能は向上しない。 従って単体CPUでは従来と同等処理時間で、かつ並列CPUではスケーラブルに性能向上するようなアルゴリズムが必須となるが、我々はそれをスケーラブルアルゴリズムとよんでいる。 本論文ではソート問題を取り上げ、新しいスケーラブルアルゴリズムMap Sortを提案する。 Map Sortの時間に関する計算複雑度はN個のデータ、P台のCPUでO((N/P) log N)であり、単体CPU上での下界値O(N log N)の(1/P)である。 また計算機実験の結果、単体CPU上のクイックソートと比較し、単体CPUでは同等性能、4CPUでは3倍の性能向上であることが示された。