文献

J-GLOBAL ID：202202272746142607   整理番号：22A0930253

ソートキー値アレイ上の並列マージスタイル操作のための1対オールおよびo(vlog(v))コスト解【JST・京大機械翻訳】

A one-for-all and o(v log(v ))-cost solution for parallel merge style operations on sorted key-value arrays

著者 (7件)： Wang Bangyan (University of California at Santa Barbara, USA) ,  Deng Lei (Tsinghua University, China) ,  Sun Fei (Alibaba DAMO Academy, China) ,  Dai Guohao (Tsinghua University, China) ,  Liu Liu (University of California at Santa Barbara, USA) ,  Wang Yu (Tsinghua University, China) ,  Xie Yuan (University of California at Santa Barbara, USA)
資料名： ACM Proceedings  (ACM Proceedings)
号： ASPLOS 2022  ページ： 669-682  発行年： 2022年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 「マージスタイル操作(MSO)」を用いたソート鍵値アレイの処理は,科学計算,深層学習,データベース,グラフ解析,ソーティング,集合操作などの領域における非常に基本的で重要な問題であり,MSOはSpGEMMやグラフマイニングのような重要なアプリケーションにおける実行時間を支配している。例えば,MSOとしてのスパースベクトル付加は,著者らの実験においてSpGEMMにおいて98%の実行時間を取り入れる。この理由のために,並列実行を用いたCPU,GPU,および加速器上のMSOの加速は広く研究されているが,以前の研究における解決策は3つの主要な限界を持っている。(1)それらは,不和合法を用いて分離問題として異なるMSOを処理し,統一解はまだ不足している。(2)それらは固定ハードウェア設計を与えられた実行時間における可変鍵/値サイズと値計算をサポートする柔軟性を持たない。(3)それらは,ほとんどの場合,与えられた並列Vに対して二次ハードウェアコスト(O(V2))を必要とする。上記の3つの限界に対処するために,次の努力を行った。(1)著者らは,統一抽象化モデル”制限zipマシン(RZM)”に基づいて,すべての関心あるMSOをサポートするための1つの解決策を提示する。(2)可変鍵/値サイズと値計算をサポートするための柔軟性を提供するために,RZMのための一連の計算可能な並列プリミティブを提案した。(3)O(Vlog(V))資源だけを用いて,提案したプリミティブを実装するハードウェア設計を提供した。上記の技術を用いて,MSOの柔軟で効率的な解決策を構築した。本設計は,事前加速器における併合ユニットのドロップイン置換として,O(V2)からO(Vlog(V))へのコスト低減,あるいはCPUとGPUのSIMD ISAへの拡張のいずれかに使用できる。CPUに関する評価において,V=16(512ビットSIMD,32ビット要素)において,セット演算(8.4×),データベース結合(7.3×),スパースベクトル/マトリックス/テンソル加算/乗算を含む代表的カーネルの範囲について,実/複素数(6.5×),併合ソート(スカラー上の8.0×,最先端のSIMD上の3.4×),およびSpGEMM(ベースライン収集における最良のものに対する4.4×)に関する有意な高速化を達成した。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】

著者キーワード (7件)： グラフ ,  結合 ,  キー値アレイ ,  マージソート ,  SIMD ,  SpGEMM ,  スパース線形代数

分類 (4件)： 数値計算  (JE02000J) ,  ディジタル計算機方式一般  (JC02010O) ,  専用演算制御装置  (JC04030Y) ,  その他のシステムプログラミング  (JD03070M)

タイトルに関連する用語 (6件)： ソート ,  キー ,  アレイ ,  マージ ,  スタイル ,  解