論文の概要: A Parallel CPU-GPU Framework for Cost-Bounded DFS with Applications to IDA* and BTS
- arxiv url: http://arxiv.org/abs/2507.11916v1
- Date: Wed, 16 Jul 2025 05:07:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-17 19:00:11.236243
- Title: A Parallel CPU-GPU Framework for Cost-Bounded DFS with Applications to IDA* and BTS
- Title（参考訳）: コストバウンドDFSのための並列CPU-GPUフレームワークとそのIDA*およびBTSへの応用
- Authors: Ehsan Futuhi, Nathan R. Sturtevant,
- Abstract要約: 本稿では,深度第一探索におけるGPU計算手法を提案する。
これは、Iterative Deepening A* (IDA*)アルゴリズムの拡張であるemphsynchronous IDA*のようなアルゴリズムを作成するために使用される。
本研究では, 3x3 の Rubik Cube と 4x4 のスライディングタイルパズル (STP) に対するアプローチを評価し,GPU 操作を DFS で効率的にバッチ化可能であることを示す。
- 参考スコア（独自算出の注目度）: 13.186524200050957
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The rapid advancement of GPU technology has unlocked powerful parallel processing capabilities, creating new opportunities to enhance classic search algorithms. A recent successful application of GPUs is in compressing large pattern database (PDB) heuristics using neural networks while preserving heuristic admissibility. However, very few algorithms have been designed to exploit GPUs during search. Several variants of A* exist that batch GPU computations. In this paper we introduce a method for batching GPU computations in depth first search. In particular, we describe a new cost-bounded depth-first search (CB-DFS) method that leverages the combined parallelism of modern CPUs and GPUs. This is used to create algorithms like \emph{Batch IDA*}, an extension of the Iterative Deepening A* (IDA*) algorithm, or Batch BTS, an extensions of Budgeted Tree Search. Our approach builds on the general approach used by Asynchronous Parallel IDA* (AIDA*), while maintaining optimality guarantees. We evaluate the approach on the 3x3 Rubik's Cube and 4x4 sliding tile puzzle (STP), showing that GPU operations can be efficiently batched in DFS. Additionally, we conduct extensive experiments to analyze the effects of hyperparameters, neural network heuristic size, and hardware resources on performance.
- Abstract（参考訳）: GPU技術の急速な進歩は、強力な並列処理能力を解放し、古典的な検索アルゴリズムを強化する新たな機会を生み出した。
GPUの最近の成功例は、ニューラルネットワークを使用して大パターンデータベース(PDB)ヒューリスティックを圧縮し、ヒューリスティックな許容性を維持することである。
しかし、検索中にGPUを利用するように設計されたアルゴリズムはごくわずかである。
A*のいくつかの変種はGPUのバッチ計算が存在する。
本稿では,GPU計算を深度ファーストサーチでバッチ化する手法を提案する。
特に,最近のCPUとGPUの並列性を利用したコストバウンド・ディープ・ファースト・サーチ(CB-DFS)について述べる。
これは、反復深度 A* (IDA*) アルゴリズムの拡張である \emph{Batch IDA*} や、予算木探索の拡張である Batch BTS などのアルゴリズムを作成するために使用される。
我々のアプローチは、最適化保証を維持しつつ、非同期並列IDA*(AIDA*)の一般的なアプローチに基づいています。
3x3ルービックキューブと4x4スライディングタイルパズル(STP)のアプローチを評価し,DFSでGPU操作を効率的にバッチ化可能であることを示す。
さらに、ハイパーパラメータ、ニューラルネットワークヒューリスティックサイズ、ハードウェアリソースがパフォーマンスに与える影響を分析するための広範な実験を行う。
関連論文リスト
- Minute-Long Videos with Dual Parallelisms [57.22737565366549]
Diffusion Transformer (DiT)ベースのビデオ拡散モデルは、大規模に高品質なビデオを生成するが、長いビデオの処理遅延とメモリコストは禁じられている。
我々はDualParalと呼ばれる新しい分散推論戦略を提案する。
1つのGPUでビデオ全体を生成する代わりに、時間フレームとモデルレイヤの両方をGPU間で並列化します。
論文 参考訳（メタデータ） (2025-05-27T11:55:22Z) - Ramp Up NTT in Record Time using GPU-Accelerated Algorithms and LLM-based Code Generation [11.120838175165986]
ホモモルフィック暗号化(HE)はプライバシ保護機械学習(PPML)のコアビルディングブロックである
HEの性能向上のために、多くのGPU加速暗号方式が提案されている。
大規模言語モデル(LLM)の強力なコード生成能力を考えると、実用的なGPUフレンドリなアルゴリズムコードを自動的に生成する可能性を探究する。
論文 参考訳（メタデータ） (2025-02-16T12:53:23Z) - SIP: Autotuning GPU Native Schedules via Stochastic Instruction Perturbation [0.0]
大型言語モデル(LLM)はその出現以来、重要なワークロードとなっている。
また、数十億のパラメータを持ち、大量のデータで訓練されているため、計算コストも高い。
近年、LLMのトレーニングと推論のための専用カーネルが開発されているため、ハードウェアリソースは可能な限り十分に活用されている。
論文 参考訳（メタデータ） (2024-03-25T15:26:50Z) - CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs [4.55224304015001]
本稿では,並列計算ハードウェアを用いた近接グラフと探索アルゴリズムを提案する。
現代のハードウェアの高性能機能を活用することで,本手法は顕著な効率向上を実現している。
90%から95%のリコール範囲での大規模クエリスループットでは,HNSWよりも3377倍高速で,GPUのSOTA実装よりも3.88.8倍高速である。
論文 参考訳（メタデータ） (2023-08-29T09:10:53Z) - INR-Arch: A Dataflow Architecture and Compiler for Arbitrary-Order
Gradient Computations in Implicit Neural Representation Processing [66.00729477511219]
計算グラフとして表される関数を考えると、従来のアーキテクチャはn階勾配を効率的に計算する上で困難に直面している。
InR-Archは,n階勾配の計算グラフをハードウェア最適化データフローアーキテクチャに変換するフレームワークである。
1.8-4.8x と 1.5-3.6x の高速化を CPU と GPU のベースラインと比較した結果を示す。
論文 参考訳（メタデータ） (2023-08-11T04:24:39Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳（メタデータ） (2022-07-09T09:14:12Z) - Providing Meaningful Data Summarizations Using Examplar-based Clustering
in Industry 4.0 [67.80123919697971]
我々は,従来のCPUアルゴリズムと比較して,一精度で最大72倍,半精度で最大452倍の高速化を実現していることを示す。
提案アルゴリズムは射出成形プロセスから得られた実世界のデータに適用し, 得られたサマリーが, コスト削減と不良部品製造の削減のために, この特定のプロセスのステアリングにどのように役立つかについて議論する。
論文 参考訳（メタデータ） (2021-05-25T15:55:14Z) - RTGPU: Real-Time GPU Scheduling of Hard Deadline Parallel Tasks with
Fine-Grain Utilization [5.02836935036198]
本論文では,複数のGPUアプリケーションの実行をリアルタイムにスケジュール可能なRTGPUを提案する。
提案手法は,従来の作業に比べてスケジューリング性に優れ,複数のGPUアプリケーションに厳しい期限をリアルタイムに保証する。
論文 参考訳（メタデータ） (2021-01-25T22:34:06Z) - Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。
最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。
ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
論文 参考訳（メタデータ） (2020-06-18T08:16:25Z) - Heterogeneous CPU+GPU Stochastic Gradient Descent Algorithms [1.3249453757295084]
ヘテロジニアスCPU+GPUアーキテクチャの深層学習のためのトレーニングアルゴリズムについて検討する。
私たちの2倍の目標 -- 収束率と資源利用を同時に最大化する -- は、この問題を難しくします。
これらのアルゴリズムの実装は,複数の実データセットよりも高速な収束と資源利用の両立を実現していることを示す。
論文 参考訳（メタデータ） (2020-04-19T05:21:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。