論文の概要: Karatsuba Matrix Multiplication and its Efficient Custom Hardware Implementations

• arxiv url: http://arxiv.org/abs/2501.08889v1
• Date: Wed, 15 Jan 2025 16:00:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-16 15:51:35.608712
• Title: Karatsuba Matrix Multiplication and its Efficient Custom Hardware Implementations
• Title（参考訳）: カラツバ行列乗算とその効率的なカスタムハードウェア実装
• Authors: Trevor E. Pogue, Nicola Nicolici,
• Abstract要約: 行列乗算に対するスカラーカラツバ乗算アルゴリズムの拡張を提案する。 これにより、元のカラツバアルゴリズムの乗算複雑性の低減と追加加算の複雑さの低減が維持される。 提案するアルゴリズムとハードウェアアーキテクチャは,整数行列の乗算に対して実面積や実行時間を改善することができることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: While the Karatsuba algorithm reduces the complexity of large integer multiplication, the extra additions required minimize its benefits for smaller integers of more commonly-used bitwidths. In this work, we propose the extension of the scalar Karatsuba multiplication algorithm to matrix multiplication, showing how this maintains the reduction in multiplication complexity of the original Karatsuba algorithm while reducing the complexity of the extra additions. Furthermore, we propose new matrix multiplication hardware architectures for efficiently exploiting this extension of the Karatsuba algorithm in custom hardware. We show that the proposed algorithm and hardware architectures can provide real area or execution time improvements for integer matrix multiplication compared to scalar Karatsuba or conventional matrix multiplication algorithms, while also supporting implementation through proven systolic array and conventional multiplier architectures at the core. We provide a complexity analysis of the algorithm and architectures and evaluate the proposed designs both in isolation and in an end-to-end deep learning accelerator system compared to baseline designs and prior state-of-the-art works implemented on the same type of compute platform, demonstrating their ability to increase the performance-per-area of matrix multiplication hardware.
• Abstract（参考訳）: カラツバアルゴリズムは大きな整数乗算の複雑さを減らすが、追加の加算はより一般的に使用されるビット幅の小さい整数に対してその利点を最小化する。 本研究では,スカラーのカラツバ乗算アルゴリズムを行列乗算へ拡張することにより,元のカラツバアルゴリズムの乗算複雑性の低減を抑えつつ,余剰加算の複雑さの低減を図っていることを示す。 さらに,カラツバアルゴリズムのこの拡張を,カスタムハードウェアで効率的に活用するための新しい行列乗算ハードウェアアーキテクチャを提案する。 提案したアルゴリズムとハードウェアアーキテクチャは,スカラーカラツバや従来の行列乗算アルゴリズムと比較して,整数行列乗算の実際の面積や実行時間を改善するとともに,証明されたシストリックアレイやコアにおける従来の乗算器アーキテクチャによる実装もサポートする。 本稿では,アルゴリズムとアーキテクチャの複雑性解析を行い,ベースライン設計や,同じタイプの計算プラットフォーム上で実装された先行技術開発と比較して,一元的かつエンドツーエンドのディープラーニングアクセラレータシステムにおいて,提案した設計を評価し,行列乗算ハードウェアの性能を向上する能力を実証する。

関連論文リスト

• Strassen Multisystolic Array Hardware Architectures [0.0]
  ストラッセンの行列乗算アルゴリズムは、単純行列乗算の複雑さを低減する。 汎用ハードウェアは、アルゴリズムが約束する理論的なスピードアップを達成するには適していない。 本稿では,Strassenのアルゴリズムの理論的複雑性の低減をハードウェアリソースの節約に直接効率的に変換する,新しいシストリックアレイアーキテクチャを提案し,評価する。
  論文  参考訳（メタデータ） (2025-02-14T10:40:32Z)
• SMM-Conv: Scalar Matrix Multiplication with Zero Packing for Accelerated Convolution [4.14360329494344]
  本稿では、CPUアーキテクチャの推論中に畳み込みを加速するための新しいアプローチを提案する。 ネットワークアーキテクチャを用いた実験は,既存の間接手法に比べて大幅に高速化された。
  論文  参考訳（メタデータ） (2024-11-23T21:43:38Z)
• KyberMat: Efficient Accelerator for Matrix-Vector Polynomial Multiplication in CRYSTALS-Kyber Scheme via NTT and Polyphase Decomposition [20.592217626952507]
  CRYSTAL-Kyber (Kyber) は、標準化プロセス中に選択された暗号鍵カプセル化機構 (KEM) の1つである。 本稿では,Kyberアーキテクチャのレイテンシとスループットの制約に対する最適化について述べる。
  論文  参考訳（メタデータ） (2023-10-06T22:57:25Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra [62.37017125812101]
  機械学習における大規模線形代数問題に対して, CoLA という, 単純だが汎用的なフレームワークを提案する。 線形演算子抽象と合成ディスパッチルールを組み合わせることで、CoLAはメモリと実行時の効率的な数値アルゴリズムを自動的に構築する。 偏微分方程式,ガウス過程,同変モデル構築,教師なし学習など,幅広い応用で有効性を示す。
  論文  参考訳（メタデータ） (2023-09-06T14:59:38Z)
• Deep Unrolling for Nonconvex Robust Principal Component Analysis [75.32013242448151]
  我々はロバスト成分分析のためのアルゴリズムを設計する(A) 行列を低主行列とスパース主行列の和に分解する。
  論文  参考訳（メタデータ） (2023-07-12T03:48:26Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• Efficient GPU implementation of randomized SVD and its applications [17.71779625877989]
  行列分解は、次元データの圧縮やディープラーニングアルゴリズムなど、機械学習においてユビキタスである。 行列分解の典型的な解は、計算コストと時間を大幅に増大させる複雑さを持つ。 我々は,計算行列分解の計算負担を軽減するために,現代のグラフィカル処理ユニット(GPU)で並列に動作する効率的な処理操作を利用する。
  論文  参考訳（メタデータ） (2021-10-05T07:42:41Z)
• Coded Distributed Computing with Partial Recovery [56.08535873173518]
  部分回復型符号化計算(CCPR)と呼ばれる新しい符号化行列ベクトル乗法を導入する。 CCPRは計算時間と復号化の複雑さを減らし、精度と計算速度のトレードオフを可能にする。 次に、この手法をより一般的な計算タスクの分散実装に拡張し、部分的回復を伴う符号化通信方式を提案する。
  論文  参考訳（メタデータ） (2020-07-04T21:34:49Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。 古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。 提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
  論文  参考訳（メタデータ） (2020-06-15T02:57:57Z)

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

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