省メモリでスケーラブルなマージソートアルゴリズム
書誌事項
- タイトル別名
-
- Memory efficient and scalable merge sort argolithm
この論文をさがす
抄録
昨今,並列性能の重要性が高まっているが,代表的なソートアルゴリズムであるクイックソートは逐次実行のクリティカルパスの長さのため,並列性能が高いとは言えない.一方で並列性能の高いソートアルゴリズムである Cilk sort や sampling sort は一時メモリがソート対象の大きさ分必要となり,大規模なデータのソートにおいてはその範囲に制約がかかってしまう.本研究では並列性能が高く省メモリである bitonic sort を基盤として,その利点を維持しながら,実用においての欠点である逐次計算量とほぼソートされた列に対しての無駄な処理の削減を目指す鋸ソートを提案する.実験の結果,鋸ソートは対象となるデータがキャッシュから大きくはみ出さない範囲においてはその全てを達成した.
収録刊行物
-
- 情報処理学会研究報告. [ハイパフォーマンスコンピューティング]
-
情報処理学会研究報告. [ハイパフォーマンスコンピューティング] 2013 (2), 1-8, 2013-07-24
一般社団法人情報処理学会
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1570291227951636096
-
- NII論文ID
- 110009588122
-
- NII書誌ID
- AN10463942
-
- 本文言語コード
- ja
-
- データソース種別
-
- CiNii Articles