論文の概要: Efficient algorithms to solve atom reconfiguration problems. III. The bird and batching algorithms and other parallel implementations on GPUs

• arxiv url: http://arxiv.org/abs/2504.06182v1
• Date: Tue, 08 Apr 2025 16:22:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-09 13:28:38.373639
• Title: Efficient algorithms to solve atom reconfiguration problems. III. The bird and batching algorithms and other parallel implementations on GPUs
• Title（参考訳）: 原子再構成問題の効率的な解法 III. 鳥とバッチ化アルゴリズムとGPU上の並列実装
• Authors: Fouad Afiouni, Remy El Sabeh, Naomi Nishimura, Izzat El Hajj, Amer E. Mouawad, Alexandre Cooper,
• Abstract要約: 本稿では,CPUとGPUの両方を対象とした原子再構成アルゴリズムの効率的な実装について述べる。 提案手法は,時間的複雑性を低減し,実行時間を高速化するアルゴリズムを改良した。 これらのアルゴリズムは、光学トラップの配列における中性原子の欠陥のない構成を作成するために使用できる。
• 参考スコア（独自算出の注目度）: 38.2058847337805
• License:
• Abstract: We present efficient implementations of atom reconfiguration algorithms for both CPUs and GPUs, along with a batching routine to merge displacement operations for parallel execution. Leveraging graph-theoretic methods, our approach derives improved algorithms that achieve reduced time complexity and faster operational running times. First, we introduce an enhanced version of the redistribution-reconfiguration (red-rec) algorithm, which offers superior operational and runtime performance. We detail its efficient implementation on a GPU using a parallel approach. Next, we present an optimized version of the assignment-reconfiguration-ordering (aro) algorithm, specifically tailored for unweighted grid graphs. Finally, we introduce the bird algorithm to solve reconfiguration problems on grids, achieving performance gains over both red-rec and aro. These algorithms can be used to prepare defect-free configurations of neutral atoms in arrays of optical traps, serve as subroutines in more complex algorithms, or cross-benchmark the operational and runtime performance of new algorithms. They are suitable for realizing quantum circuits incorporating displacement operations and are optimized for real-time operation on increasingly large system sizes.
• Abstract（参考訳）: 並列実行のための変位演算をマージするバッチ処理ルーチンとともに,CPUとGPUの両方の原子再構成アルゴリズムの効率的な実装を提案する。 グラフ理論の手法を活用することで,計算時間を短縮し,実行時間を高速化するアルゴリズムを改良する。 まず,再配布-再設定(red-rec)アルゴリズムの強化版を導入する。 並列手法を用いてGPU上での効率的な実装について詳述する。 次に、非重み付きグリッドグラフに特化して、割り当て再構成順序付けアルゴリズム(aro)の最適化版を提案する。 最後に,リコンフィグレーション問題の解法として,リコンフィグレーションアルゴリズムを導入し,レッドレックとアロの両方の性能向上を実現した。 これらのアルゴリズムは、光学トラップの配列中の中性原子の欠陥のない構成を作成したり、より複雑なアルゴリズムのサブルーチンとして機能したり、新しいアルゴリズムの運用および実行時の性能を横断的に評価するために使用することができる。 これらは、変位演算を取り入れた量子回路の実現に適しており、ますます大きなシステムサイズでのリアルタイム演算に最適化されている。

関連論文リスト

• Performance Evaluation of Evolutionary Algorithms for Analog Integrated Circuit Design Optimisation [0.0]
  本稿では,アナログ回路の自動サイズ化手法について述べる。 探索空間を対象とする探索は粒子生成関数と補修バウンド関数を用いて実装されている。 アルゴリズムは、より良い最適解に収束するように調整され、修正される。
  論文  参考訳（メタデータ） (2023-10-19T03:26:36Z)
• VAPI: Vectorization of Algorithm for Performance Improvement [5.835939416417458]
  ベクトル化(Vectorization)は、一度に1つの値で動作するアルゴリズムを、一度に1つの値のコレクションで動作して高速に実行するアルゴリズムに変換するテクニックである。 ベクトル化手法はまた、複数の繰り返しを1つの演算に置き換えることで、アルゴリズムの性能を高速化する。 本研究では,メタヒューリスティックアルゴリズムの1つにベクトル化手法を適用し,ベクトル化アルゴリズムと非ベクトル化アルゴリズムを比較した。
  論文  参考訳（メタデータ） (2023-07-19T11:23:03Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Improving the Efficiency of Gradient Descent Algorithms Applied to Optimization Problems with Dynamical Constraints [3.3722008527102894]
  通常の微分方程式を用いて最適化問題を解くための2つのブロック座標降下アルゴリズムを提案する。 このアルゴリズムは損失関数勾配を評価するために直接または随伴感度解析法を実装する必要はない。
  論文  参考訳（メタデータ） (2022-08-26T18:26:50Z)
• Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer Vision [6.574107319036238]
  Hochbaum pseudoflowアルゴリズムは最速のシリアルアルゴリズムであり、Boykov-Kolmogorovアルゴリズムは最もメモリ効率が高い。 既存の min-cut/max-flow アルゴリズムは、大きな問題ではシリアルアルゴリズムを著しく上回るが、中小問題ではオーバーヘッドが増大する。
  論文  参考訳（メタデータ） (2022-02-01T14:06:27Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。 我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
  論文  参考訳（メタデータ） (2021-12-09T02:27:52Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)

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

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