論文の概要: Pipelining Kruskal's: A Neuromorphic Approach for Minimum Spanning Tree

• arxiv url: http://arxiv.org/abs/2505.10771v2
• Date: Mon, 19 May 2025 05:05:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-20 12:45:56.179082
• Title: Pipelining Kruskal's: A Neuromorphic Approach for Minimum Spanning Tree
• Title（参考訳）: パイプライニング Kruskal's:ミニマルスパンニングツリーに対するニューロモルフィックアプローチ
• Authors: Yee Hin Chong, Peng Qu, Yuchen Li, Youhui Zhang,
• Abstract要約: 我々は,SNNに基づくユニオンソートルーチンと,KruskalのMSTアルゴリズムのパイプラインバージョンを提案する。 提案手法は,大規模グラフ上での最先端プリム法よりも優れた性能を示す。
• 参考スコア（独自算出の注目度）: 8.12111159815123
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Neuromorphic computing, characterized by its event-driven computation and massive parallelism, is particularly effective for handling data-intensive tasks in low-power environments, such as computing the minimum spanning tree (MST) for large-scale graphs. The introduction of dynamic synaptic modifications provides new design opportunities for neuromorphic algorithms. Building on this foundation, we propose an SNN-based union-sort routine and a pipelined version of Kruskal's algorithm for MST computation. The event-driven nature of our method allows for the concurrent execution of two completely decoupled stages: neuromorphic sorting and union-find. Our approach demonstrates superior performance compared to state-of-the-art Prim 's-based methods on large-scale graphs from the DIMACS10 dataset, achieving speedups by 269.67x to 1283.80x, with a median speedup of 540.76x. We further evaluate the pipelined implementation against two serial variants of Kruskal's algorithm, which rely on neuromorphic sorting and neuromorphic radix sort, showing significant performance advantages in most scenarios.
• Abstract（参考訳）: イベント駆動計算と大規模並列処理を特徴とするニューロモルフィックコンピューティングは、大規模グラフに対する最小スパンニングツリー(MST)の計算など、低消費電力環境におけるデータ集約的なタスクの処理に特に有効である。 動的シナプス修飾の導入は、ニューロモルフィックアルゴリズムの新しい設計機会を提供する。 本稿では,SNNに基づくユニオンソートルーチンと,MST計算のためのKruskalアルゴリズムのパイプラインバージョンを提案する。 本手法の事象駆動特性は,神経型分類とユニオンフィンという,完全に分離された2つの段階の同時実行を可能にする。 提案手法は,DIMACS10データセットから得られた大規模グラフ上でのPrim's-based法と比較して,269.67xから1283.80xの高速化を実現し,中央値の540.76xである。 我々はさらに、ニューロモルフィックソートとニューロモルフィックラディクスソートに頼って、Kruskalアルゴリズムの2つのシリアル変種に対するパイプライン化実装を評価し、ほとんどのシナリオにおいて顕著な性能上の利点を示した。

関連論文リスト

• SymbolNet: Neural Symbolic Regression with Adaptive Dynamic Pruning for Compression [1.0356366043809717]
  モデル圧縮技術として特別に設計された記号回帰に対するニューラルネットワークアプローチである$ttSymbolNet$を提案する。 このフレームワークは、単一のトレーニングプロセスにおいてモデルウェイト、入力特徴、数学的演算子の動的プルーニングを可能にする。
  論文  参考訳（メタデータ） (2024-01-18T12:51:38Z)
• Dynamic Sparse Training with Structured Sparsity [11.778353786208765]
  ダイナミックスパーストレーニング(DST)法は、スパースニューラルネットワークトレーニングにおいて最先端の結果を達成する。 本研究では, 微細構造N:M空間の変形を学習するために, スパース・ツー・スパースDST法, Structured RigL (SRigL)を提案する。 オンライン推論用CPUでは3.4x/2.5x、GPUでは1.7x/13.0x、バッチサイズは256である。
  論文  参考訳（メタデータ） (2023-05-03T17:48:55Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。 我々の手法は古典的DPベースの推論に広く適用できる。 また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
  論文  参考訳（メタデータ） (2021-12-07T11:26:41Z)
• Random Features for the Neural Tangent Kernel [57.132634274795066]
  完全接続型ReLUネットワークのニューラルタンジェントカーネル(NTK)の効率的な特徴マップ構築を提案する。 得られた特徴の次元は、理論と実践の両方で比較誤差境界を達成するために、他のベースライン特徴マップ構造よりもはるかに小さいことを示しています。
  論文  参考訳（メタデータ） (2021-04-03T09:08:12Z)
• Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach [144.21892195917758]
  一般化構造方程式モデル(SEM)のクラスにおける推定について検討する。 線形作用素方程式をmin-maxゲームとして定式化し、ニューラルネットワーク(NN)でパラメータ化し、勾配勾配を用いてニューラルネットワークのパラメータを学習する。 提案手法は,サンプル分割を必要とせず,確固とした収束性を持つNNをベースとしたSEMの抽出可能な推定手順を初めて提供する。
  論文  参考訳（メタデータ） (2020-07-02T17:55:47Z)
• Run-time Mapping of Spiking Neural Networks to Neuromorphic Hardware [0.44446524844395807]
  本研究では、オンライン学習SNNベースのアプリケーションのニューロンとシナプスを、実行時にニューロモルフィックアーキテクチャに分割し、マッピングする設計手法を提案する。 提案アルゴリズムは, 設計時間に基づくSNN分割手法と比較して, ソリューション品質が6.25%低いSNNマッピング時間を平均780倍に削減する。
  論文  参考訳（メタデータ） (2020-06-11T19:56:55Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)
• A Study of Performance of Optimal Transport [16.847501106437534]
  本稿では,ネットワークの単純化と拡張パスに基づくアルゴリズムが,数値行列スケーリング法より一貫して優れていることを示す。 古典的なKuhn-Munkresアルゴリズムを改良した新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-03T20:37:05Z)

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

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