著者

中澤 隆久 田浦 健次朗

雑誌

研究報告ハイパフォーマンスコンピューティング(HPC)

巻号頁・発行日

vol.2012-HPC-135, no.12, pp.1-7, 2012-07-25

---

昨今、並列性能の重要性が高まっているが、代表的なソートアルゴリズムであるクイックソートは逐次実行部分のクリティカルパスの長さのため、並列性能が高いとは言い難い。本研究では並列性能の高いソートの一つである bitonic sort を基盤として、その利点である並列性能の高さを維持しながら、実用においての欠点であるほぼソートされた列に対しての無駄な処理の削減を達成した鋸ソートを提案する。実験の結果、鋸ソートはランダム列に対しては bitonic sort と同等のスケーラビリティを持ち、ほぼソートされた列に対してはごく短い時間でのソートを実現した。