論文の概要: e-boost: Boosted E-Graph Extraction with Adaptive Heuristics and Exact Solving

• arxiv url: http://arxiv.org/abs/2508.13020v1
• Date: Mon, 18 Aug 2025 15:38:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-19 14:49:11.458091
• Title: e-boost: Boosted E-Graph Extraction with Adaptive Heuristics and Exact Solving
• Title（参考訳）: e-boost:適応的ヒューリスティックスと厳密解を用いた強化E-グラフ抽出
• Authors: Jiaqi Yin, Zhan Song, Chen Chen, Yaohui Cai, Zhiru Zhang, Cunxi Yu,
• Abstract要約: Eグラフは多くの分野、特に論理合成と形式的検証に興味を寄せている。 このギャップを3つの重要なイノベーションで埋める新しいフレームワークであるe-boostを紹介します。 e-boostは、従来の正確なアプローチ(ILP)よりも58倍のランタイムスピードアップを示し、最先端の抽出フレームワーク(SmoothE)よりも19.04%パフォーマンスが改善された。
• 参考スコア（独自算出の注目度）: 12.1096064802958
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: E-graphs have attracted growing interest in many fields, particularly in logic synthesis and formal verification. E-graph extraction is a challenging NP-hard combinatorial optimization problem. It requires identifying optimal terms from exponentially many equivalent expressions, serving as the primary performance bottleneck in e-graph based optimization tasks. However, traditional extraction methods face a critical trade-off: heuristic approaches offer speed but sacrifice optimality, while exact methods provide optimal solutions but face prohibitive computational costs on practical problems. We present e-boost, a novel framework that bridges this gap through three key innovations: (1) parallelized heuristic extraction that leverages weak data dependence to compute DAG costs concurrently, enabling efficient multi-threaded performance without sacrificing extraction quality; (2) adaptive search space pruning that employs a parameterized threshold mechanism to retain only promising candidates, dramatically reducing the solution space while preserving near-optimal solutions; and (3) initialized exact solving that formulates the reduced problem as an Integer Linear Program with warm-start capabilities, guiding solvers toward high-quality solutions faster. Across the diverse benchmarks in formal verification and logic synthesis fields, e-boost demonstrates 558x runtime speedup over traditional exact approaches (ILP) and 19.04% performance improvement over the state-of-the-art extraction framework (SmoothE). In realistic logic synthesis tasks, e-boost produces 7.6% and 8.1% area improvements compared to conventional synthesis tools with two different technology mapping libraries. e-boost is available at https://github.com/Yu-Maryland/e-boost.
• Abstract（参考訳）: 電子グラフは多くの分野、特に論理合成と形式的検証において関心を集めている。 Eグラフ抽出はNPハードな組合せ最適化問題である。 指数関数的に多くの等価表現から最適項を識別し、電子グラフベースの最適化タスクにおいて主要なパフォーマンスボトルネックとなる。 ヒューリスティックなアプローチはスピードを提供するが、最適性を犠牲にする一方、正確な手法は最適解を提供するが、実用的な問題では計算コストが禁じられている。 このギャップを埋める新しいフレームワークであるe-boostは,(1)弱いデータ依存を利用してDAGコストを並列に処理し,抽出品質を犠牲にすることなく効率的なマルチスレッド性能を実現する並列化ヒューリスティック抽出,(2)有望な候補のみを保持するためのパラメータ化しきい値機構を用いた適応探索空間のプルーニング,(3)最適に近い解を保存しながら解空間を劇的に縮小する,(3)温暖化開始能力を備えたInteger Linear Programとして問題を解き、高品質な解を高速に導く,という3つの重要なイノベーションを通じて,このギャップを橋渡しする。 e-boostは、形式的検証と論理合成の分野における様々なベンチマークの中で、従来の正確なアプローチ(ILP)よりも558倍の高速化と、最先端抽出フレームワーク(SmoothE)よりも19.04%の性能向上を示している。 現実的な論理合成タスクでは、e-boostは2つの異なる技術マッピングライブラリを持つ従来の合成ツールと比較して7.6%と8.1%の面積改善を実現している。 e-boostはhttps://github.com/Yu-Maryland/e-boost.comで入手できる。

関連論文リスト

• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  本稿では,反復的BONDと自己プレイアライメントの統一的なゲーム理論接続を明らかにする。 WINレート支配(WIN rate Dominance, WIND)という新しいフレームワークを構築し, 正規化利率支配最適化のためのアルゴリズムを多数提案する。
  論文  参考訳（メタデータ） (2024-10-28T04:47:39Z)
• ALPS: Improved Optimization for Highly Sparse One-Shot Pruning for Large Language Models [14.310720048047136]
  ALPSは,演算子分割法と事前条件付き勾配共役型後処理法を用いて,プルーニング問題に対処する最適化ベースのフレームワークである。 提案手法はベクトル化とGPU並列性を有効利用しながら収束を加速し理論的に保証する新しい手法を取り入れている。 OPT-30Bモデルでは70%の間隔で、ALPSはWikiTextデータセットにおけるテストの難易度を13%削減し、既存の手法と比較してゼロショットベンチマークのパフォーマンスを19%改善した。
  論文  参考訳（メタデータ） (2024-06-12T02:57:41Z)
• OptEx: Expediting First-Order Optimization with Approximately Parallelized Iterations [12.696136981847438]
  ほぼ並列化されたイテレーション (OptEx) で高速化された一階最適化を導入する。 OptExは、並列コンピューティングを活用して、その反復的ボトルネックを軽減することで、FOOの効率を高める最初のフレームワークである。 我々は、カーネル化された勾配推定の信頼性とSGDベースのOpsExの複雑さを理論的に保証する。
  論文  参考訳（メタデータ） (2024-02-18T02:19:02Z)
• A Deep Unrolling Model with Hybrid Optimization Structure for Hyperspectral Image Deconvolution [50.13564338607482]
  本稿では,DeepMixと呼ばれるハイパースペクトルデコンボリューション問題に対する新しい最適化フレームワークを提案する。 これは3つの異なるモジュール、すなわちデータ一貫性モジュール、手作りの正規化器の効果を強制するモジュール、および装飾モジュールで構成されている。 本研究は,他のモジュールの協調作業によって達成される進歩を維持するために設計された,文脈を考慮した認知型モジュールを提案する。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Transferable Graph Optimizers for ML Compilers [18.353830282858834]
  計算グラフ最適化(GO)のためのエンドツーエンドで転送可能な深層強化学習法を提案する。 GOは個々のノードに対して自動回帰ではなく,グラフ全体の決定を生成する。 GOは、人間の専門家よりも21%改善し、先行技術よりも18%改善し、15倍早く収束する。
  論文  参考訳（メタデータ） (2020-10-21T20:28:33Z)

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

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