論文の概要: GPU-Accelerated Loopy Belief Propagation for Program Analysis
- arxiv url: http://arxiv.org/abs/2509.22337v1
- Date: Fri, 26 Sep 2025 13:30:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-29 20:57:54.457525
- Title: GPU-Accelerated Loopy Belief Propagation for Program Analysis
- Title（参考訳）: プログラム解析のためのGPU高速化ループリーブリーフ伝播
- Authors: Haoyu Feng, Xin Zhang,
- Abstract要約: 本稿では,プログラム解析のためのGPU高速化LPPアルゴリズムを提案する。
本稿では,依存関係解析アルゴリズムとともに,任意のユーザ定義更新戦略を指定する統一表現を提案する。
当社のアプローチでは,最先端のシーケンシャルアプローチよりも平均2.14タイム,最先端のGPUベースのアプローチよりも5.56タイムのスピードアップを実現している。
- 参考スコア（独自算出の注目度）: 3.516434517865342
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Loopy Belief Propagation (LBP) is a widely used approximate inference algorithm in probabilistic graphical models, with applications in computer vision, error correction codes, protein folding, program analysis, etc. However, LBP faces significant computational challenges when applied to large-scale program analysis. While GPU (Graphics Processing Unit) parallel computing provides a promising solution, existing approaches lack support for flexible update strategies and have yet to integrate logical constraints with GPU acceleration, leading to suboptimal practical performance. This paper presents a GPU-accelerated LBP algorithm for program analysis. To support the diverse update strategies required by users, we propose a unified representation for specifying arbitrary user-defined update strategies, along with a dependency analysis algorithm. Furthermore, building on previous work that leverages the local structure of Horn clauses to simplify message passing, we group messages to minimize warp divergence and better utilize GPU resources. Experimental results on datarace analysis over eight real-world Java programs show that our approach achieves an average speedup of $2.14\times$ over the state-of-the-art sequential approach and $5.56\times$ over the state-of-the-art GPU-based approach, while maintaining high accuracy.
- Abstract（参考訳）: Loopy Belief Propagation (LBP) は確率的グラフィカルモデルにおいて広く使われている近似推論アルゴリズムであり、コンピュータビジョン、エラー訂正符号、タンパク質の折り畳み、プログラム解析などに応用されている。
しかし、LBPは大規模プログラム解析に適用した場合、重大な計算上の課題に直面している。
GPU(Graphics Processing Unit)並列コンピューティングは有望なソリューションを提供するが、既存のアプローチではフレキシブルな更新戦略をサポートしておらず、GPUアクセラレーションに論理的制約をまだ統合していないため、亜最適の実用的なパフォーマンスをもたらす。
本稿では,プログラム解析のためのGPU高速化LPPアルゴリズムを提案する。
ユーザの要求する多様な更新戦略をサポートするため,依存関係解析アルゴリズムとともに,任意のユーザ定義更新戦略を指定するための統一表現を提案する。
さらに、Hhorn節のローカル構造を利用してメッセージパッシングを単純化する以前の作業に基づいて、ワープのばらつきを最小限に抑えるためにメッセージをグループ化し、GPUリソースをよりよく活用する。
8つの実世界のJavaプログラムに対するデータトレース解析実験の結果、我々の手法は最先端のシーケンシャルなアプローチよりも平均2.14\times$、最先端のGPUベースのアプローチよりも5.56\times$を達成でき、精度は高い。
関連論文リスト
- NGPU-LM: GPU-Accelerated N-Gram Language Model for Context-Biasing in Greedy ASR Decoding [54.88765757043535]
この研究は、統計的なn-gram言語モデルのデータ構造を再考し、GPU最適化推論の高速かつ並列な操作を可能にする。
我々のアプローチは NGPU-LM と呼ばれ、7% 未満の計算オーバーヘッドを持つ全ての主要な ASR モデルに対して、カスタマイズ可能なgreedy decoding を導入している。
提案手法は,ビーム探索による顕著な遅延を回避しつつ,greedy と beam search の精度ギャップの50%以上を排除できる。
論文 参考訳（メタデータ） (2025-05-28T20:43:10Z) - FlashAttention on a Napkin: A Diagrammatic Approach to Deep Learning IO-Awareness [0.0]
FlashAttentionのようなメソッドは、不要なデータ転送を避けることによって、ネイティブのPyTorchよりもx6パフォーマンスの向上を実現している。
本稿では、ディープラーニングモデルのためのニューラルネットワークダイアグラムを拡張し、GPU階層間のリソース使用量とタスクの分散を検討する。
本研究では,中間レベルの擬似コードをダイアグラムで表現する手法を開発し,ハードウェア認識アルゴリズムをステップバイステップで導出できるようにする。
論文 参考訳（メタデータ） (2024-12-04T13:52:04Z) - Implementation and Analysis of GPU Algorithms for Vecchia Approximation [0.8057006406834466]
Vecchia Approximationは計算複雑性を減らすために広く使われており、恥ずかしい並列アルゴリズムで計算することができる。
Vecchia Approximationのためにマルチコアソフトウェアが開発されたが、グラフィックス処理ユニット(GPU)上で動作するように設計されたソフトウェアは不足している。
我々の新しい手法は他の2つより優れており、GpGpU Rパッケージに表示されます。
論文 参考訳（メタデータ） (2024-07-03T01:24:44Z) - GPU Based Differential Evolution: New Insights and Comparative Study [7.5961910202572644]
この研究は、GPUベースの微分進化アルゴリズムの文献における主要なアーキテクチャ選択についてレビューする。
新しいGPUベースの数値最適化ベンチマークを導入し、GPUベースのDEMアルゴリズムを評価し比較する。
論文 参考訳（メタデータ） (2024-05-26T12:40:39Z) - High Performance Computing Applied to Logistic Regression: A CPU and GPU
Implementation Comparison [0.0]
汎用GPUによるロジスティック回帰(LR)の並列バージョンを提案する。
我々の実装は、X. Zouらによって提案された並列なグラディエントDescent Logistic Regressionアルゴリズムの直接変換である。
本手法は,画像認識,スパム検出,不正検出などのリアルタイム予測に特に有用である。
論文 参考訳（メタデータ） (2023-08-19T14:49:37Z) - ParaGraph: Weighted Graph Representation for Performance Optimization of
HPC Kernels [1.304892050913381]
抽象構文木を拡張した並列アプリケーションのためのグラフベースの新しいプログラム表現を提案する。
提案した表現は,OpenMPコード領域のランタイムを予測するために,グラフニューラルネットワーク(GNN)をトレーニングすることで評価する。
その結果,本手法は実効性があり,実行時予測では 0.004 から 0.01 に RMSE を正規化していることがわかった。
論文 参考訳（メタデータ） (2023-04-07T05:52:59Z) - A modular software framework for the design and implementation of
ptychography algorithms [55.41644538483948]
我々は,Pychographyデータセットをシミュレートし,最先端の再構築アルゴリズムをテストすることを目的とした,新しいptychographyソフトウェアフレームワークであるSciComを紹介する。
その単純さにもかかわらず、ソフトウェアはPyTorchインターフェースによる高速化処理を利用する。
結果は合成データと実データの両方で示される。
論文 参考訳（メタデータ） (2022-05-06T16:32:37Z) - Adaptive Elastic Training for Sparse Deep Learning on Heterogeneous
Multi-GPU Servers [65.60007071024629]
本稿では,Adaptive SGDが4つの最先端ソリューションよりも精度が高いことを示す。
本稿では,Adaptive SGDが時間と精度で4つの最先端ソリューションより優れていることを示す。
論文 参考訳（メタデータ） (2021-10-13T20:58:15Z) - Providing Meaningful Data Summarizations Using Examplar-based Clustering
in Industry 4.0 [67.80123919697971]
我々は,従来のCPUアルゴリズムと比較して,一精度で最大72倍,半精度で最大452倍の高速化を実現していることを示す。
提案アルゴリズムは射出成形プロセスから得られた実世界のデータに適用し, 得られたサマリーが, コスト削減と不良部品製造の削減のために, この特定のプロセスのステアリングにどのように役立つかについて議論する。
論文 参考訳（メタデータ） (2021-05-25T15:55:14Z) - Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。
最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。
ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
論文 参考訳（メタデータ） (2020-06-18T08:16:25Z) - MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical
Models [96.1052289276254]
この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。
驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
論文 参考訳（メタデータ） (2020-04-16T16:20:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。