論文の概要: Common Subexpression-based Compression and Multiplication of Sparse Constant Matrices

• arxiv url: http://arxiv.org/abs/2303.16106v1
• Date: Sun, 26 Mar 2023 22:14:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-29 14:21:44.371377
• Title: Common Subexpression-based Compression and Multiplication of Sparse Constant Matrices
• Title（参考訳）: スパース定数行列の共通部分表現に基づく圧縮と乗法
• Authors: Emre Bilgili, Arda Yurdakul
• Abstract要約: 本稿では,圧縮スパースロウ(CSR)をCSEに拡張した圧縮形式を提案する。 加算木を1分で1千倍の1000ドルのマトリックスで作る。 シングルコア組込みシステムのシミュレーションでは、行列乗算の実行時間を20%削減できることが示されている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In deep learning inference, model parameters are pruned and quantized to reduce the model size. Compression methods and common subexpression (CSE) elimination algorithms are applied on sparse constant matrices to deploy the models on low-cost embedded devices. However, the state-of-the-art CSE elimination methods do not scale well for handling large matrices. They reach hours for extracting CSEs in a $200 \times 200$ matrix while their matrix multiplication algorithms execute longer than the conventional matrix multiplication methods. Besides, there exist no compression methods for matrices utilizing CSEs. As a remedy to this problem, a random search-based algorithm is proposed in this paper to extract CSEs in the column pairs of a constant matrix. It produces an adder tree for a $1000 \times 1000$ matrix in a minute. To compress the adder tree, this paper presents a compression format by extending the Compressed Sparse Row (CSR) to include CSEs. While compression rates of more than $50\%$ can be achieved compared to the original CSR format, simulations for a single-core embedded system show that the matrix multiplication execution time can be reduced by $20\%$.
• Abstract（参考訳）: ディープラーニング推論では、モデルパラメータをプルーニングして量子化し、モデルサイズを小さくする。 圧縮法と共通部分表現(cse)除去アルゴリズムはスパース定数行列に適用され、低コストの組み込みデバイスにモデルをデプロイする。 しかし、最先端のcse除去法は大きな行列を扱うのにうまくスケールしない。 行列乗算アルゴリズムは従来の行列乗算法よりも長い時間で実行されるのに対し、CSEを200 \times 200$行列で抽出するのに数時間かかる。 さらに、CSEを利用した行列の圧縮方法も存在しない。 この問題に対する対策として,定数行列の列対におけるCSEを抽出するランダム探索に基づくアルゴリズムを提案する。 1分で1000ドル/1000ドルの行列用の加算木を生成する。 加算木を圧縮するために,圧縮スパースロウ(CSR)をCSEを含むように拡張して圧縮形式を示す。 従来のCSRフォーマットと比較して50\%以上の圧縮率を達成することができるが、シングルコア組み込みシステムのシミュレーションでは、行列乗算の実行時間を20\%$に削減できることを示している。

関連論文リスト

• Optimal Quantization for Matrix Multiplication [35.007966885532724]
  我々は、ネスト格子に基づく普遍量化器を、任意の(非ランダムな)行列対に対する近似誤差の明示的な保証付きで、フロベニウスノルム$|A|_F, |B|_F$, $|Atop B|_F$のみの観点から、$A$, $B$とする。
  論文  参考訳（メタデータ） (2024-10-17T17:19:48Z)
• Matrix Compression via Randomized Low Rank and Low Precision Factorization [47.902465710511485]
  現代の行列は数十億の要素を巻き込み、そのストレージと処理は計算資源とメモリ使用量の観点から非常に要求される。 この構造を利用して任意の行列 $mathbfA$ as $mathbfLmathbfR$ の低階分解を求めるアルゴリズムを提案する。 LlaMa-7$bの層を圧縮し,画像圧縮におけるアルゴリズムの有効性を実証的に実証した。
  論文  参考訳（メタデータ） (2023-10-17T06:56:57Z)
• Multiresolution kernel matrix algebra [0.0]
  本研究では, あるS形式において, 最適スパース行列を生成するサンプルレットを用いて, カーネル行列の圧縮を示す。 カーネル行列の逆数(もし存在するなら)は S-形式でも圧縮可能である。 行列代数は擬微分計算によって数学的に正当化される。
  論文  参考訳（メタデータ） (2022-11-21T17:50:22Z)
• Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
  EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。 本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
  論文  参考訳（メタデータ） (2022-07-09T09:14:12Z)
• Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
  一般的なNystr"om法を不確定な設定に一般化する。 我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。 本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
  論文  参考訳（メタデータ） (2021-12-17T17:04:34Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  我々は,ロバストな1ビット圧縮センシングのための相関に基づく最適化アルゴリズムのリカバリ保証を提供する。 我々は,実用的な反復アルゴリズムを用いて,画像データセットの数値実験を行い,結果の相関付けを行う。
  論文  参考訳（メタデータ） (2021-08-08T05:28:06Z)
• Multiplying Matrices Without Multiplying [0.0]
  行列の乗算は機械学習における最も基本的で計算集約的な操作の1つである。 本稿では,既存の手法を大幅に上回る学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-21T05:08:54Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Doping: A technique for efficient compression of LSTM models using sparse structured additive matrices [14.321761305835972]
  私たちはドーピングの概念を提案します -- 構造化マトリックスに非常にスパースなマトリックスを追加します。 ドーピングは、少数のパラメータに対する追加の自由度を促進し、固定構造から独立して分離することを可能にする。 同一精度で1.3倍から2.4倍の圧縮係数を達成することにより,dip kp圧縮技術は従来の技術圧縮結果を上回ることを示した。
  論文  参考訳（メタデータ） (2021-02-14T05:14:09Z)
• Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
  本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。 提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
  論文  参考訳（メタデータ） (2020-02-23T03:07:31Z)

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

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