省メモリでスケーラブルなマージソートアルゴリズム

書誌事項

タイトル別名
  • Memory efficient and scalable merge sort argolithm

この論文をさがす

抄録

昨今,並列性能の重要性が高まっているが,代表的なソートアルゴリズムであるクイックソートは逐次実行のクリティカルパスの長さのため,並列性能が高いとは言えない.一方で並列性能の高いソートアルゴリズムである Cilk sort や sampling sort は一時メモリがソート対象の大きさ分必要となり,大規模なデータのソートにおいてはその範囲に制約がかかってしまう.本研究では並列性能が高く省メモリである bitonic sort を基盤として,その利点を維持しながら,実用においての欠点である逐次計算量とほぼソートされた列に対しての無駄な処理の削減を目指す鋸ソートを提案する.実験の結果,鋸ソートは対象となるデータがキャッシュから大きくはみ出さない範囲においてはその全てを達成した.

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1570291227951636096
  • NII論文ID
    110009588122
  • NII書誌ID
    AN10463942
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ