Fugu-MT 論文翻訳(概要): Predicting the Output Structure of Sparse Matrix Multiplication with Sampled Compression Ratio

論文の概要: Predicting the Output Structure of Sparse Matrix Multiplication with Sampled Compression Ratio

arxiv url: http://arxiv.org/abs/2207.13848v1
Date: Thu, 28 Jul 2022 01:37:57 GMT
ステータス: 処理完了
システム内更新日: 2022-07-29 13:05:43.336340
Title: Predicting the Output Structure of Sparse Matrix Multiplication with Sampled Compression Ratio
Title（参考訳）: サンプル圧縮比を用いたスパース行列乗算の出力構造予測
Authors: Zhaoyang Du, Yijin Guan, Tianchan Guan, Dimin Niu, Nianxiong Tan, Xiaopeng Yu, Hongzhong Zheng, Jianyi Meng, Xiaolang Yan, Yuan Xie
Abstract要約: そこで本研究では,既存のサンプリング方式と比較して,精度と低コストで新しいサンプリング方式を提案する。予測精度を評価するために,種々の行列次元とスパース構造を有する625の試験ケースを構築した。
参考スコア（独自算出の注目度）: 6.54079166923595
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Sparse general matrix multiplication (SpGEMM) is a fundamental building block in numerous scientific applications. One critical task of SpGEMM is to compute or predict the structure of the output matrix (i.e., the number of nonzero elements per output row) for efficient memory allocation and load balance, which impact the overall performance of SpGEMM. Existing work either precisely calculates the output structure or adopts upper-bound or sampling-based methods to predict the output structure. However, these methods either take much execution time or are not accurate enough. In this paper, we propose a novel sampling-based method with better accuracy and low costs compared to the existing sampling-based method. The proposed method first predicts the compression ratio of SpGEMM by leveraging the number of intermediate products (denoted as FLOP) and the number of nonzero elements (denoted as NNZ) of the same sampled result matrix. And then, the predicted output structure is obtained by dividing the FLOP per output row by the predicted compression ratio. We also propose a reference design of the existing sampling-based method with optimized computing overheads to demonstrate the better accuracy of the proposed method. We construct 625 test cases with various matrix dimensions and sparse structures to evaluate the prediction accuracy. Experimental results show that the absolute relative errors of the proposed method and the reference design are 1.56\% and 8.12\%, respectively, on average, and 25\% and 156\%, respectively, in the worst case.
Abstract（参考訳）: スパース一般行列乗法(SpGEMM)は、多くの科学応用において基本的な構成要素である。 SpGEMMの1つの重要なタスクは、効率的なメモリ割り当てと負荷バランスのために出力行列(すなわち出力行当たりのゼロでない要素の数)の構造を計算または予測することであり、これはSpGEMMの全体的な性能に影響を与える。既存の作業では、出力構造を正確に計算するか、上界またはサンプリングベースの方法を採用して出力構造を予測する。しかし、これらのメソッドは実行に多くの時間を要するか、あるいは十分に正確ではない。本稿では,既存のサンプリングベース法と比較して精度と低コストが向上した新しいサンプリングベース法を提案する。提案手法は,同じサンプル結果行列の中間生成物数(フロップ)と非零要素数(nnz)を利用して,まずspgemmの圧縮率を予測する。そして、予測圧縮比で出力行毎にFLOPを分割して予測出力構造を得る。また,提案手法の精度向上を実証するために,計算オーバーヘッドを最適化したサンプリングベース手法の参照設計を提案する。予測精度を評価するために,種々の行列次元とスパース構造を有する625の試験ケースを構築した。実験の結果, 提案手法と基準設計の絶対相対誤差はそれぞれ平均 1.56 % と 8.12 % であり, 最悪の場合には 25 % と 156 % であった。

関連論文リスト

An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-09-30T15:57:14Z)
Algorithme EM r\'egularis\'e [0.0]
本稿では,より少ないサンプルサイズに対応するために,事前知識を効率的に活用するEMアルゴリズムの正規化バージョンを提案する。実データを用いた実験では,クラスタリングのための提案アルゴリズムの性能が向上した。
論文参考訳（メタデータ） (2023-07-04T23:19:25Z)
Plug-and-Play split Gibbs sampler: embedding deep generative priors in Bayesian inference [12.91637880428221]
本稿では, 後方分布から効率的にサンプリングするために, 可変分割を利用したプラグアンドプレイサンプリングアルゴリズムを提案する。後方サンプリングの課題を2つの単純なサンプリング問題に分割する。その性能は最近の最先端の最適化とサンプリング手法と比較される。
論文参考訳（メタデータ） (2023-04-21T17:17:51Z)
Bayesian Sparse Regression for Mixed Multi-Responses with Application to Runtime Metrics Prediction in Fog Manufacturing [6.288767115532775]
フォッグ製造は、分散計算Fogユニットを通じて従来の製造システムを大幅に強化することができる。予測オフロード手法は,実行時のパフォーマンス指標の正確な予測と不確かさの定量化に大きく依存していることが知られている。本稿では,多変量混合応答に対するベイジアンスパース回帰法を提案し,実行時性能指標の予測を強化する。
論文参考訳（メタデータ） (2022-10-10T16:14:08Z)
Sparse high-dimensional linear regression with a partitioned empirical Bayes ECM algorithm [62.997667081978825]
疎高次元線形回帰に対する計算効率が高く強力なベイズ的手法を提案する。パラメータに関する最小の事前仮定は、プラグイン経験的ベイズ推定(英語版)を用いて用いられる。提案手法はRパッケージプローブに実装されている。
論文参考訳（メタデータ） (2022-09-16T19:15:50Z)
Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文参考訳（メタデータ） (2021-05-23T19:21:55Z)
Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文参考訳（メタデータ） (2020-12-29T04:08:38Z)
Instance Based Approximations to Profile Maximum Likelihood [33.51964370430905]
プロファイル最大度(PML)分布を近似計算するアルゴリズムを提案する。 PseudoPMLは、幅広い対称特性のクラスを推定するフレームワークである。
論文参考訳（メタデータ） (2020-11-05T11:17:19Z)
Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。暗黙正則化現象の理論的保証を提供する。
論文参考訳（メタデータ） (2020-07-16T13:27:47Z)
Covariance Estimation for Matrix-valued Data [9.739753590548796]
本研究では,高次元行列データに対する分布自由正規化共分散推定法を提案する。我々は、バンド可能な共分散を推定するための統一的な枠組みを定式化し、ランク1の制約のないクロネッカー積近似に基づく効率的なアルゴリズムを導入する。格子状温度異常データセットとS&P 500ストックデータ解析によるシミュレーションと実応用を用いて,本手法の優れた有限サンプル性能を実証した。
論文参考訳（メタデータ） (2020-04-11T02:15:26Z)
Clustering Binary Data by Application of Combinatorial Optimization Heuristics [52.77024349608834]
本稿では,2値データのクラスタリング手法について検討し,まず,クラスタのコンパクトさを計測するアグリゲーション基準を定義した。近隣地域と人口動態最適化メタヒューリスティックスを用いた5つの新しいオリジナル手法が導入された。準モンテカルロ実験によって生成された16のデータテーブルから、L1の相似性と階層的クラスタリング、k-means(メドイドやPAM)の1つのアグリゲーションの比較を行う。
論文参考訳（メタデータ） (2020-01-06T23:33:31Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。