Map Sort : マルチコアプロセッサに向けたスケーラブルなソートアルゴリズム(実時間OS,並列アルゴリズム)

スポンサーリンク

概要

論文の詳細を見る
マルチコア向けの並列ソートアルゴリズム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倍の性能向上であることが示された。
社団法人電子情報通信学会の論文
2007-03-08

著者

関連論文

もっと見る

スポンサーリンク