論文の概要: Fine-Grain GPU Parallelization of the Generalized Partition Crossover for Large-Scale Traveling Salesman Problems
- arxiv url: http://arxiv.org/abs/2608.21233v1
- Date: Fri, 21 Aug 2026 15:42:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-24 14:49:32.628058
- Title: Fine-Grain GPU Parallelization of the Generalized Partition Crossover for Large-Scale Traveling Salesman Problems
- Title（参考訳）: 大規模トラベリングセールスマン問題に対する一般化分割クロスオーバーのファイングラインドGPU並列化
- Abstract要約: トラベリングセールスマン問題(TSP)はNPハード最適化問題の1つである。
提案手法は,結合したメモリレイアウト,ゴーストノード変換,連結ノード解析を用いて,GPXをグラフ並列問題として再構成する。
提案したGPUは、メモリオーバーヘッドを大幅に削減しつつ、48倍から625倍のスピードアップを実現する。
- 参考スコア（独自算出の注目度）: 1.160208922584163
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Traveling Salesman Problem (TSP) is one of the most extensively studied NP-hard optimization problems. Genetic Algorithm (GA)-based solvers, such as the Edge Assembly Crossover (EAX), achieve state-of-the-art performance on many benchmark instances. However, the scalability of these approaches in massively parallel architectures remains limited because crossover operations involve irregular memory access patterns, graph traversals, and sequential dependencies. Existing GPU-based TSP solvers primarily exploit population-level parallelism and are limited to relatively small problem sizes. This work presents a fine-grain GPU implementation of the partition phase of the Generalized Partition Crossover (GPX) operator for large-scale TSP instances. The proposed approach reformulates GPX partitioning as a graph-parallel problem using coalesced memory layouts, ghost-node transformations, and connected-component analysis. The im- plementation parallelizes the union of parent tours, the splitting of degree- four vertices, the deletion of common edges, and the identification of recombining components using CUDA. Experimental results on instances ranging from 10,000 to 2 million cities demonstrate substantial acceleration over a naive sequential CPU imple- mentation. The proposed GPU partitioning achieves speedups between 48x and 625x while significantly reducing memory overhead. The re- sults demonstrate that operator-level parallelism can substantially im- prove the scalability of GA-based TSP solvers on modern many-core architectures.
- Abstract（参考訳）: トラベリングセールスマン問題(TSP)はNPハード最適化問題の1つである。
Edge Assembly Crossover (EAX)のようなGAベースの解法は、多くのベンチマークインスタンスで最先端のパフォーマンスを達成する。
しかし、クロスオーバー操作には不規則なメモリアクセスパターン、グラフトラバーサル、シーケンシャル依存関係が含まれるため、大規模な並列アーキテクチャにおけるこれらのアプローチのスケーラビリティは依然として制限されている。
既存のGPUベースのTSPソルバは、主に人口レベルの並列性を利用しており、比較的小さな問題サイズに限定されている。
本研究は,大規模TSPインスタンスに対するGPX演算子のパーティションフェーズの微粒化GPU実装を提案する。
提案手法は,結合したメモリレイアウト,ゴーストノード変換,連結成分解析を用いて,GPXパーティショニングをグラフ並列問題として再構成する。
im-plementationは、親ツアーの結合、次数4頂点の分割、共通エッジの削除、CUDAを用いた再結合コンポーネントの識別を並列化する。
1万から200万の都市での実験結果から、単純でシーケンシャルなCPUインプレメントよりも大幅に加速された。
提案したGPUパーティショニングは、メモリオーバーヘッドを大幅に削減しつつ、48xから625xのスピードアップを実現する。
再侮辱は、演算子レベルの並列性は、現代のマルチコアアーキテクチャにおけるGAベースのTSPソルバのスケーラビリティを実質的に証明できることを示した。
関連論文リスト
- From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal $k$-Sparse GLMs [6.381561491422844]
分岐およびバウンド(BnB)における異種ノードを処理する汎用的なモジュラーフレームワークを提案する。
このフレームワークはGPU効率の小さなルーチンを中心に構築されており、パディングと軽量のカスタムカーネルを使って不規則なノードデータ構造を処理する。
実験では、挑戦するインスタンスに対して1から2桁のスピードアップと最適性ギャップがゼロであることが示されている。
論文 参考訳（メタデータ） (2026-05-21T08:56:15Z) - cuRegOT: A GPU-Accelerated Solver for Entropic-Regularized Optimal Transport [8.189956090077677]
cuRegOTは、エントロピー正規化OTに適した高性能GPUソルバである。
我々は、CPUボトルネックを軽減するために、アモータイズされたシンボリック分析戦略を含むアルゴリズムとアーキテクチャの最適化スイートを紹介する。
CuRegOTは、さまざまなベンチマークタスクで最先端のGPUベースのソルバよりも大幅にスピードアップする。
論文 参考訳（メタデータ） (2026-05-09T08:27:39Z) - cuNNQS-SCI: A Fully GPU-Accelerated Framework for High-Performance Configuration Interaction Selection with Neural Network Quantum States [12.436495225801863]
cuNNQS-SCIは、これらのボトルネックを克服するために設計された、完全にGPUアクセラレーションされたSCIフレームワークである。
64GPUのNVIDIA A100クラスタでは、cuNNQS-SCIは最大2.32倍のエンドツーエンドのスピードアップを達成する。
優れた分散パフォーマンスを示し、強力なスケーリングテストで90%以上の並列効率を維持する。
論文 参考訳（メタデータ） (2026-04-17T07:15:18Z) - Parallel-in-Time Nonlinear Optimal Control via GPU-native Sequential Convex Programming [2.8852807790754618]
本稿では,連続凸プログラミングと乗算器のコンセンサスに基づく交互方向法を組み合わせた,フルGPUネイティブなトラジェクトリ最適化フレームワークを提案する。
本研究は,有人エッジコンピューティングプラットフォームを用いて,四重項アジャイル飛行タスクと火星搭載降下問題の解法を検証した。
ベンチマークでは、高度に最適化された12コアのCPUベースラインよりも、持続的な4倍のスループットのスピードアップとエネルギー消費の51%削減が明らかにされている。
論文 参考訳（メタデータ） (2026-03-11T12:39:14Z) - Spava: Accelerating Long-Video Understanding via Sequence-Parallelism-aware Approximate Attention [63.69228529380251]
Spavaはシーケンス並列フレームワークで、ロングビデオ推論に最適化されている。
Spavaは、FlashAttn、ZigZagRing、APBで12.72x、1.70x、1.18xのスピードアップを提供する。
論文 参考訳（メタデータ） (2026-01-29T09:23:13Z) - Binary-Gaussian: Compact and Progressive Representation for 3D Gaussian Segmentation [83.90109373769614]
3D Gaussian Splatting (3D-GS)は効率的な3D表現として登場し、セグメンテーションのようなセグメンテーションタスクのための有望な基盤となっている。
本稿では,各特徴を2進数対決定写像によって1つの整数に圧縮する,ガウス単位のカテゴリ表現のための粗大なバイナリ符号化方式を提案する。
さらに,個別のサブタスクに分割し,クラス間の衝突を減らし,きめ細かいセグメンテーション能力を向上させるプログレッシブトレーニング戦略を設計する。
論文 参考訳（メタデータ） (2025-11-30T15:51:30Z) - GSPN-2: Efficient Parallel Sequence Modeling [101.33780567131716]
一般化空間伝搬ネットワーク(GSPN)は2次自己アテンションを直線走査型伝搬方式に置き換えることでこの問題に対処する。
GSPN-2は、視覚アプリケーションにおけるグローバル空間コンテキストをモデル化するための新しい効率フロンティアを確立する。
論文 参考訳（メタデータ） (2025-11-28T07:26:45Z) - Lighter-X: An Efficient and Plug-and-play Strategy for Graph-based Recommendation through Decoupled Propagation [49.865020394064096]
我々は,既存のGNNベースのレコメンデータアーキテクチャとシームレスに統合可能な,効率的かつモジュール化されたフレームワークである textbfLighter-X を提案する。
提案手法は,基本モデルの理論的保証と経験的性能を保ちながら,パラメータサイズと計算複雑性を大幅に低減する。
実験の結果、Lighter-Xはパラメータが大幅に少ないベースラインモデルに匹敵するパフォーマンスを実現している。
論文 参考訳（メタデータ） (2025-10-11T08:33:08Z) - Enabling Population-Level Parallelism in Tree-Based Genetic Programming for GPU Acceleration [9.421242935448722]
木に基づく遺伝的プログラミング(TGP)は、記号回帰、分類、ロボット制御などのタスクに広く用いられている進化的計算アルゴリズムである。
EvoGPは、TGPのGPUアクセラレーションに適した高性能なフレームワークである。
論文 参考訳（メタデータ） (2025-01-21T07:42:54Z) - Breaking the Memory Barrier: Near Infinite Batch Size Scaling for Contrastive Loss [59.835032408496545]
本稿では, コントラスト損失計算を任意の小ブロックに分割するタイルベースの戦略を提案する。
分散システムの階層構造を活用するためのマルチレベルタイリング戦略も導入する。
SOTAメモリ効率のソリューションと比較すると、同等の速度を維持しながら、メモリの2桁の削減を実現している。
論文 参考訳（メタデータ） (2024-10-22T17:59:30Z) - Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [49.41718583061147]
グラフ凝縮(Graph condensation)は、大きなグラフを小さいが情報的な凝縮グラフに置き換えるための、データ中心のソリューションである。
既存のGCメソッドは、複雑な最適化プロセス、過剰なコンピューティングリソースとトレーニング時間を必要とする。
我々は、CGC(Class-partitioned Graph Condensation)と呼ばれるトレーニング不要なGCフレームワークを提案する。
CGCはOgbn-productsグラフを30秒以内に凝縮し、102$Xから104$Xまでのスピードアップを実現し、精度は4.2%まで向上した。
論文 参考訳（メタデータ） (2024-05-22T14:57:09Z) - Learning to Solve Combinatorial Graph Partitioning Problems via
Efficient Exploration [72.15369769265398]
実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。
最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
論文 参考訳（メタデータ） (2022-05-27T17:13:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。