対称線形代数カーネルのためのI/O最適アルゴリズム【JST・京大機械翻訳】

Beaumont Olivier; Eyraud-Dubois Lionel; Verite Mathieu; Langou Julien

プレプリント

J-GLOBAL ID：202202218560833598 整理番号：22P0292829

対称線形代数カーネルのためのI/O最適アルゴリズム【JST・京大機械翻訳】

I/O-Optimal Algorithms for Symmetric Linear Algebra Kernels

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (4件)： , , ,
資料名：
発行年： 2022年02月21日プレプリントサーバーでの情報更新日： 2022年02月21日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

本論文では,線形代数における2つの基本的対称カーネル,すなわち,Cholesky因数分解と対称ランクk更新(SYRK)を,これらのカーネルに対する古典的3つのネストループアルゴリズムと共に考察した。さらに,サイズSの高速メモリと非有界低速メモリを持つマシンモデルを考察した。このモデルでは,すべての計算を高速メモリのオペランドで実行しなければならない,そして,目標は遅いメモリと速いメモリの間の通信量を最小にすることである。計算のセットがアルゴリズムの選択によって固定されるので,計算の規則化(スケジュール)だけが通信の体積に直接影響する。著者らは,N×N対称正定行列のCholesky因数分解の通信体積に対するfrac13√2fracN ̄3√Sの下限と,AがN×M行列であるmatAのSYRK計算のためのfrac1√2fracN ̄2M√Sを証明した。両限界は,因子√2による文献から,最良の既知の下限を改善する。さらに,frac13√2fracN ̄3√S+o{N ̄{5/2}の容積で,Coleskyに対するfrac1√2fracN ̄2M√S+oNMlogNとLBCのボリュームを持つSYRKのためのTBSと整合通信容量を持つ2つのコアの逐次アルゴリズムを示した。両アルゴリズムは,因子√2による文献から最良の既知アルゴリズムを改善し,著者らの下限における主導項は,さらに改善できないことを証明した。本研究は,SYRKまたはCholeskyのような対称カーネルの操作強度が,対応する非対称カーネル(GEMMおよびLU因数分解)よりも本質的に高い(因子√2)ことを示した。【JST・京大機械翻訳】

, , , , , , , , ,
, , , , , 【Automatic Indexing@JST】

数値計算 , 人工知能

, , ,

前のページに戻る