論文の概要: Slicing Is All You Need: Towards A Universal One-Sided Algorithm for Distributed Matrix Multiplication

• arxiv url: http://arxiv.org/abs/2510.08874v1
• Date: Fri, 10 Oct 2025 00:11:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 00:38:47.899902
• Title: Slicing Is All You Need: Towards A Universal One-Sided Algorithm for Distributed Matrix Multiplication
• Title（参考訳）: スライシングは必要なすべて:分散行列乗算のためのユニバーサルワンシドアルゴリズムを目指して
• Authors: Benjamin Brock, Renato Golin,
• Abstract要約: 本稿では分散行列乗算のための一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺 アルゴリズムはパーティショニングとレプリケーションのすべての組み合わせをサポートする。 我々は高レベルなC++ベースのPGASプログラミングフレームワークを用いてアルゴリズムを実装した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many important applications across science, data analytics, and AI workloads depend on distributed matrix multiplication. Prior work has developed a large array of algorithms suitable for different problem sizes and partitionings including 1D, 2D, 1.5D, and 2.5D algorithms. A limitation of current work is that existing algorithms are limited to a subset of partitionings. Multiple algorithm implementations are required to support the full space of possible partitionings. If no algorithm implementation is available for a particular set of partitionings, one or more operands must be redistributed, increasing communication costs. This paper presents a universal one-sided algorithm for distributed matrix multiplication that supports all combinations of partitionings and replication factors. Our algorithm uses slicing (index arithmetic) to compute the sets of overlapping tiles that must be multiplied together. This list of local matrix multiplies can then either be executed directly, or reordered and lowered to an optimized IR to maximize overlap. We implement our algorithm using a high-level C++-based PGAS programming framework that performs direct GPU-to-GPU communication using intra-node interconnects. We evaluate performance for a wide variety of partitionings and replication factors, finding that our work is competitive with PyTorch DTensor, a highly optimized distributed tensor library targeting AI models.
• Abstract（参考訳）: 科学、データ分析、AIワークロードにまたがる多くの重要なアプリケーションは、分散マトリックス乗法に依存している。 これまでの研究では、1D, 2D, 1.5D, 2.5Dアルゴリズムを含む様々な問題のサイズとパーティショニングに適したアルゴリズムが開発されてきた。 現在の作業の制限は、既存のアルゴリズムがパーティショニングのサブセットに制限されていることである。 複数のアルゴリズムの実装は、パーティショニングの可能な全空間をサポートするために必要である。 特定のパーティショニングに対してアルゴリズムの実装が利用できない場合、1つ以上のオペランドを再配布し、通信コストを増大させる必要がある。 本稿では,分割係数と複製係数の組合せをサポートする分散行列乗算のための一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一辺一 我々のアルゴリズムはスライシング(インデックス演算)を用いて重なり合うタイルの集合を演算する。 このローカル行列乗算のリストは直接実行されるか、最適化されたIRに再順序付けされ、オーバーラップを最大化することができる。 我々はノード間相互接続を用いたGPU間直接通信を行う高レベルなC++ベースのPGASプログラミングフレームワークを用いてアルゴリズムを実装した。 我々は,AIモデルを対象とした高度に最適化された分散テンソルライブラリであるPyTorch DTensorと,さまざまなパーティショニングとレプリケーション係数のパフォーマンスを評価した。

関連論文リスト

• Scalable Private Partition Selection via Adaptive Weighting [66.09199304818928]
  プライベート・セット・ユニオンでは、ユーザーは非有界宇宙からのアイテムのサブセットを保持する。 目標は、ユーザレベルの差分プライバシーを維持しながら、ユーザセットの統一から可能な限り多くのアイテムを出力することである。 この問題に対するアルゴリズムであるMaxDegree (MAD) を提案する。これは、プライバシに必要なしきい値よりもはるかに重いものからより小さいものへ、より適応的に重みを還元するアルゴリズムである。 我々のアルゴリズムは並列アルゴリズムの中で最高の結果を提供し、数十億の項目からなるデータセットにスケールする。
  論文  参考訳（メタデータ） (2025-02-13T01:27:11Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• GreedyML: A Parallel Algorithm for Maximizing Constrained Submodular Functions [2.9998889086656586]
  分散メモリマルチプロセッサ上での単調部分モジュラ関数の最大化のための並列近似アルゴリズムについて述べる。 我々の研究は、大規模データセットにおける部分モジュラー最適化問題を解く必要性によって動機付けられている。
  論文  参考訳（メタデータ） (2024-03-15T14:19:09Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering [6.4805900740861]
  HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。 我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。 48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
  論文  参考訳（メタデータ） (2021-04-02T16:05:00Z)
• A new heuristic algorithm for fast k-segmentation [0.0]
  文献には$k$-segmentationの厳密で近似的な方法が存在する。 本稿では,既存の手法を改善するために,新しいアルゴリズムを提案する。 計算コストのごく一部で正確な手法と競合するアキュラシーを提供することを実証的に見出した。
  論文  参考訳（メタデータ） (2020-09-02T04:50:17Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。 最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。 ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
  論文  参考訳（メタデータ） (2020-06-18T08:16:25Z)

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

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