論文の概要: Implementing a GPU-based parallel MAX-MIN Ant System

• arxiv url: http://arxiv.org/abs/2003.11902v1
• Date: Sat, 18 Jan 2020 14:18:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-10 05:11:56.415068
• Title: Implementing a GPU-based parallel MAX-MIN Ant System
• Title（参考訳）: GPUベース並列MAX-MIN Antシステムの実装
• Authors: Rafa{\l} Skinderowicz
• Abstract要約: 我々はGPUベースの並列MMASの実装を改善するための新しいアイデアについて論じる。 MMAS実装は、最先端のGPUベースおよびマルチコアCPUベースの並列ACO実装と競合することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The MAX-MIN Ant System (MMAS) is one of the best-known Ant Colony Optimization (ACO) algorithms proven to be efficient at finding satisfactory solutions to many difficult combinatorial optimization problems. The slow-down in Moore's law, and the availability of graphics processing units (GPUs) capable of conducting general-purpose computations at high speed, has sparked considerable research efforts into the development of GPU-based ACO implementations. In this paper, we discuss a range of novel ideas for improving the GPU-based parallel MMAS implementation, allowing it to better utilize the computing power offered by two subsequent Nvidia GPU architectures. Specifically, based on the weighted reservoir sampling algorithm we propose a novel parallel implementation of the node selection procedure, which is at the heart of the MMAS and other ACO algorithms. We also present a memory-efficient implementation of another key-component -- the tabu list structure -- which is used in the ACO's solution construction stage. The proposed implementations, combined with the existing approaches, lead to a total of six MMAS variants, which are evaluated on a set of Traveling Salesman Problem (TSP) instances ranging from 198 to 3,795 cities. The results show that our MMAS implementation is competitive with state-of-the-art GPU-based and multi-core CPU-based parallel ACO implementations: in fact, the times obtained for the Nvidia V100 Volta GPU were up to 7.18x and 21.79x smaller, respectively. The fastest of the proposed MMAS variants is able to generate over 1 million candidate solutions per second when solving a 1,002-city instance. Moreover, we show that, combined with the 2-opt local search heuristic, the proposed parallel MMAS finds high-quality solutions for the TSP instances with up to 18,512 nodes.
• Abstract（参考訳）: MAX-MIN Ant System (MMAS) は、多くの難しい組合せ最適化問題に対する十分解を見つけるのに効率的であることが証明された、最もよく知られているAnt Colony Optimization (ACO)アルゴリズムの1つである。 ムーアの法則のスローダウンと、汎用計算を高速に実行できるグラフィックス処理ユニット(GPU)の可用性は、GPUベースのACO実装の開発に多大な研究成果をもたらした。 本稿では、GPUベースの並列MMAS実装を改善するための新しいアイデアについて論じ、その後の2つのNvidia GPUアーキテクチャによって提供されるコンピューティングパワーをよりよく活用できるようにする。 具体的には, 重み付き貯留層サンプリングアルゴリズムに基づいて, mmas と他の aco アルゴリズムの核となるノード選択手順を並列に実装する手法を提案する。 また、ACOのソリューション構築段階で使用される別のキーコンポーネントであるタブリスト構造をメモリ効率で実装する。 提案手法は,既存手法と組み合わせて総計6種類のMMASが提案され,198都市から3,795都市を対象とする旅行セールスマン問題(TSP)の事例で評価された。 その結果、mmmsの実装は最先端のgpuベースとマルチコアのcpuベースの並列aco実装に匹敵することがわかった。実際、nvidia v100 volta gpuで得られた時間は、それぞれ7.18xと21.79x小さくなった。 提案されたMMAS変種のうち最速のものは、1,002都市のインスタンスを解く際に毎秒100万以上の候補解を生成することができる。 さらに,2オプト局所探索ヒューリスティックと組み合わせて提案した並列MMASは,最大18,512ノードのTSPインスタンスに対して高品質な解を求める。

関連論文リスト

• EPS-MoE: Expert Pipeline Scheduler for Cost-Efficient MoE Inference [49.94169109038806]
  本稿では,新しいパイプラインスケジューラであるEPS-MoEを紹介する。 その結果,既存の並列推論手法に比べて,プリフィルスループットが平均21%向上していることが判明した。
  論文  参考訳（メタデータ） (2024-10-16T05:17:49Z)
• GPU Based Differential Evolution: New Insights and Comparative Study [7.5961910202572644]
  この研究は、GPUベースの微分進化アルゴリズムの文献における主要なアーキテクチャ選択についてレビューする。 新しいGPUベースの数値最適化ベンチマークを導入し、GPUベースのDEMアルゴリズムを評価し比較する。
  論文  参考訳（メタデータ） (2024-05-26T12:40:39Z)
• New Core-Guided and Hitting Set Algorithms for Multi-Objective Combinatorial Optimization [0.0]
  本稿では,多目的組合せ最適化のための2つの新しい不満足性に基づくアルゴリズムを提案する。 1つはコア誘導MOCOソルバ、もう1つはヒットセットベースのMOCOソルバである。 実験の結果,新しい不満足性に基づくアルゴリズムは,MOCOの最先端SATベースのアルゴリズムより優れていることがわかった。
  論文  参考訳（メタデータ） (2022-04-22T09:46:44Z)
• Distributed Out-of-Memory NMF on CPU/GPU Architectures [1.0051474951635875]
  本稿では,HPCシステムに対する非負行列分解(NMF)アルゴリズムのメモリ外実装を提案する。 ベンチマークの結果、CPUベースのNMFkよりもGPUを使用した新しい実装により、32Xから76倍のスピードアップが大幅に改善された。
  論文  参考訳（メタデータ） (2022-02-19T03:49:21Z)
• A Simple Evolutionary Algorithm for Multi-modal Multi-objective Optimization [0.0]
  マルチモーダル・多目的最適化問題(MMOP)を解くための定常進化アルゴリズムを提案する。 本報告では,1000関数評価の低計算予算を用いて,様々なテストスイートから得られた21個のMMOPの性能について報告する。
  論文  参考訳（メタデータ） (2022-01-18T03:31:11Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  カーネル法は、非パラメトリック学習に対するエレガントで原則化されたアプローチを提供するが、今のところ大規模な問題ではほとんど利用できない。 最近の進歩は、最適化、数値線形代数、ランダム射影など、多くのアルゴリズム的アイデアの利点を示している。 ここでは、これらの取り組みをさらに進めて、GPUハードウェアを最大限に活用する解決器を開発し、テストする。
  論文  参考訳（メタデータ） (2020-06-18T08:16:25Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。 古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。 提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
  論文  参考訳（メタデータ） (2020-06-15T02:57:57Z)
• 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)
• Minimal Filtering Algorithms for Convolutional Neural Networks [82.24592140096622]
  我々は,M=3,5,7,9,11の基本的なフィルタリング操作を実装するための完全並列ハードウェア指向アルゴリズムを開発した。 各ケースにおける提案アルゴリズムの完全な並列ハードウェア実装は、組込み乗算器の数を約30%削減する。
  論文  参考訳（メタデータ） (2020-04-12T13:18:25Z)

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

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