文献

J-GLOBAL ID：202202275763931694   整理番号：22A0984749

現場(共有メモリ)ソーティングアルゴリズムのエンジニアリング【JST・京大機械翻訳】

Engineering In-place (Shared-memory) Sorting Algorithms

著者 (4件)： Axtmann Michael (Karlsruhe Institute of Technology, Karlsruhe, Germany) ,  Witt Sascha (Karlsruhe Institute of Technology, Karlsruhe, Germany) ,  Ferizovic Daniel (Karlsruhe Institute of Technology, Karlsruhe, Germany) ,  Sanders Peter (Karlsruhe Institute of Technology, Karlsruhe, Germany)
資料名： ACM Transactions on Parallel Computing  (ACM Transactions on Parallel Computing)
巻： 9  号： 1  ページ： 1-62  発行年： 2022年 
JST資料番号： W5703A  ISSN： 2329-4949  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： ここでは,広範囲の入力サイズ,入力分布,データタイプ,およびマシンのための最速の既知技術を表す新しい逐次および並列ソーティングアルゴリズムを提案した。驚いたことに,速度利点の一部は,入力アレイを超える空間のかなりの量を必要としない,現場で動作するアルゴリズムの追加特徴のためである。以前に,現場特徴は,しばしば性能ペナルティを意味した。著者らの主なアルゴリズム的貢献は,おそらくキャッシュ効率が高い,現場データ分布に対するブロックワイズアプローチである。また,動的負荷分散とメモリ局所性を考慮したこの手法を並列化する。著者らの新しい比較ベースのアルゴリズムIn-situ並列スーパースカラーサンプル(IPS4o)は,この技術を枝なし決定木と組み合わせる。多くの等しい要素を考慮して,分布度を動的に順応することによって,著者らは,ほとんど3の因子によって,最良の以前の現場並列比較ベースのソーティングアルゴリズムより性能が優れている高ロバストアルゴリズムを得た。また,このアルゴリズムは,現場,並列あるいは逐次設定で考慮しないかどうかにかかわらず,最良の比較ベース競争者より優れている。もう一つの驚くべき結果は,IPS4oが,広範囲の状況において,最良(in situまたはin situ)整数ソーティングアルゴリズムよりも性能が優れていることである。残りの事例(しばしば,ほぼ均一な入力分布,小さな鍵,あるいは逐次設定を含む)の多くにおいて,著者らの新しいIn-pace並列Super Scalar Radix Sort(IPS2Ra)は最良のアルゴリズムである。若干の意味で「最良」ソーティングアルゴリズムを持つためのClaimsは,すべて真実でない多くの論文で見つけることができる。したがって,著者らは,21の最先端のソーティング符号,6つのデータタイプ,10の入力分布,4つの機械,4つのメモリ割り当て戦略,および7桁以上の入力サイズを含む,大規模な実験研究に関する著者らの結論を基礎づけた。これは,関連する出版物で報告された測定のコンクリートセット外の多くの競争者における主要な性能問題を明らかにしながら,著者らのアルゴリズムのロバスト性能に関する主張を確認した。これは,ロバスト汎用ソーティングのための比較ベースアルゴリズムを好む一つの理由を与える整数ソーティングアルゴリズムに対して特に真実である。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  *記憶装置 ,  刊行物 ,  データ ,  記憶割当 ,  キャッシュメモリ ,  *ソーティング ,  ディシジョンツリー ,  局所性 ,  データ型 ,  ペナルティ ,  ロバスト性 ,  *共有メモリ ,  並列化
準シソーラス用語： 動的負荷分散 , 【Automatic Indexing@JST】

著者キーワード (2件)： 現場アルゴリズム ,  分岐予測

分類 (3件)： 人工知能  (JE08000Z) ,  ディジタル計算機方式一般  (JC02010O) ,  その他のシステムプログラミング  (JD03070M)

タイトルに関連する用語 (3件)： 現場 ,  共有メモリ ,  エンジニアリング