論文の概要: Giga-scale Kernel Matrix Vector Multiplication on GPU
- arxiv url: http://arxiv.org/abs/2202.01085v1
- Date: Wed, 2 Feb 2022 15:28:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-03 17:23:58.336434
- Title: Giga-scale Kernel Matrix Vector Multiplication on GPU
- Title(参考訳): GPU上のギガスケールカーネル行列ベクトル乗算
- Authors: Robert Hu, Dino Sejdinovic, Joan Alexis Glaun\`es
- Abstract要約: Kernel matrix vector multiplication (KMVM) は、カーネル文学から信号処理まで、機械学習と科学計算におけるユビキタスな演算である。
KMVMのスケーリング問題に対処するために,Faster-Fast and Free Memory Method(textF3$M)という新しい近似手法を提案する。
我々は、$textF3$Mで10億ポイントのKMVMを1分以内のハイエンドGPUで計算できることを示し、既存のCPU手法と比較して大幅に高速化された。
- 参考スコア(独自算出の注目度): 9.106412307976067
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Kernel matrix vector multiplication (KMVM) is a ubiquitous operation in
machine learning and scientific computing, spanning from the kernel literature
to signal processing. As kernel matrix vector multiplication tends to scale
quadratically in both memory and time, applications are often limited by these
computational scaling constraints. We propose a novel approximation procedure
coined Faster-Fast and Free Memory Method ($\text{F}^3$M) to address these
scaling issues for KMVM. Extensive experiments demonstrate that $\text{F}^3$M
has empirical \emph{linear time and memory} complexity with a relative error of
order $10^{-3}$ and can compute a full KMVM for a billion points \emph{in under
one minute} on a high-end GPU, leading to a significant speed-up in comparison
to existing CPU methods. We further demonstrate the utility of our procedure by
applying it as a drop-in for the state-of-the-art GPU-based linear solver
FALKON, \emph{improving speed 3-5 times} at the cost of $<$1\% drop in
accuracy.
- Abstract(参考訳): kernel matrix vector multiplication (kmvm) は、カーネルの文献から信号処理まで、機械学習と科学計算におけるユビキタスな操作である。
カーネル行列ベクトル乗算はメモリと時間の両方で二次的にスケールする傾向があるため、これらの計算スケーリングの制約によってアプリケーションは制限されることが多い。
KMVMのスケーリング問題に対処するために,Fast-Fast and Free Memory Method ("\text{F}^3$M") という新しい近似手法を提案する。
大規模な実験により、$\text{F}^3$Mは10-3$の相対誤差を持つ経験的な \emph{linear time and memory} 複雑性を持ち、ハイエンドGPU上で10億ポイントの KMVM を計算できることが示され、既存のCPU手法と比較して大幅に高速化された。
さらに,最先端のGPUベース線形解法 FALKON, \emph{improving speed 3-5 times} のドロップインとして, 精度$<$1\%のコストで適用することで, 提案手法の有用性を実証する。
関連論文リスト
- vTensor: Flexible Virtual Tensor Management for Efficient LLM Serving [53.972175896814505]
大規模言語モデル(LLM)は様々なドメインで広く使われ、数百万の日次要求を処理する。
大規模言語モデル(LLM)は様々なドメインで広く使われ、数百万の日次要求を処理する。
論文 参考訳(メタデータ) (2024-07-22T14:37:58Z) - Fast Evaluation of Additive Kernels: Feature Arrangement, Fourier Methods, and Kernel Derivatives [0.5735035463793009]
厳密な誤り解析を伴う非等間隔高速フーリエ変換(NFFT)に基づく手法を提案する。
また,本手法は,カーネルの分化に伴う行列の近似に適していることを示す。
複数のデータセット上で高速な行列ベクトル積を持つ付加的カーネルスキームの性能について述べる。
論文 参考訳(メタデータ) (2024-04-26T11:50:16Z) - Snacks: a fast large-scale kernel SVM solver [0.8602553195689513]
SnacksはKernel Support Vector Machines用の新しい大規模ソルバである。
スナックは、カーネル行列の「Nystr」近似と、下次法の加速変種に依存している。
論文 参考訳(メタデータ) (2023-04-17T04:19:20Z) - Sub-quadratic Algorithms for Kernel Matrices via Kernel Density
Estimation [24.166833799353476]
カーネルグラフ上では$textitweighted edge sample$、カーネルグラフ上では$textitweighted walk$、行列で$textitweighted sample$からKernel Density Estimationへ効率よく還元する。
当社の削減は、それぞれのアプリケーションにおいて中心的な要素であり、それらが独立した関心事である可能性があると信じています。
論文 参考訳(メタデータ) (2022-12-01T16:42:56Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳(メタデータ) (2022-07-09T09:14:12Z) - PLSSVM: A (multi-)GPGPU-accelerated Least Squares Support Vector Machine [68.8204255655161]
Support Vector Machines (SVM) は機械学習で広く使われている。
しかし、現代的で最適化された実装でさえ、最先端ハードウェア上の大きな非自明な高密度データセットにはうまくスケールしない。
PLSSVMはLVMのドロップイン代替として使用できる。
論文 参考訳(メタデータ) (2022-02-25T13:24:23Z) - Fast Sketching of Polynomial Kernels of Polynomial Degree [61.83993156683605]
他のカーネルはしばしばテイラー級数展開を通じてカーネルによって近似されるので、カーネルは特に重要である。
スケッチの最近の技術は、カーネルの$q$という難解な程度に実行時間に依存することを減らしている。
我々は、この実行時間を大幅に改善する新しいスケッチを、先頭の注文項で$q$への依存を取り除くことで提供します。
論文 参考訳(メタデータ) (2021-08-21T02:14:55Z) - VersaGNN: a Versatile accelerator for Graph neural networks [81.1667080640009]
我々は,超効率的なサイストリックアレイベースの多用途ハードウェアアクセラレータである textitVersaGNN を提案する。
textitVersaGNNは平均3712$times$ speedup with 1301.25$times$ energy reduction on CPU、35.4$times$ speedup with 17.66$times$ energy reduction on GPUを達成している。
論文 参考訳(メタデータ) (2021-05-04T04:10:48Z) - GPU-Accelerated Primal Learning for Extremely Fast Large-Scale
Classification [10.66048003460524]
ロジスティック回帰や線形サポートベクターマシン(SVM)分類などのL2正規化原始問題を解く最も効率的な方法の1つは、広く使われている信頼領域ニュートンアルゴリズムであるTRONである。
我々は、GPU最適化の法則を用いて、異なる損失と特徴表現に対するTRONトレーニング時間を劇的に短縮できることを示した。
論文 参考訳(メタデータ) (2020-08-08T03:40:27Z) - Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。
最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。
ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
論文 参考訳(メタデータ) (2020-06-18T08:16:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。