論文の概要: Efficient Algorithms for Partial Constraint Satisfaction Problems over Control-flow Graphs
- arxiv url: http://arxiv.org/abs/2602.03588v1
- Date: Tue, 03 Feb 2026 14:38:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-04 18:37:15.516035
- Title: Efficient Algorithms for Partial Constraint Satisfaction Problems over Control-flow Graphs
- Title（参考訳）: 制御フローグラフを用いた部分制約満足度問題の効率的なアルゴリズム
- Authors: Xuran Cai, Amir Goharshady,
- Abstract要約: プログラムの制御フローグラフ(CFG)に対する部分制約満足度問題(PCSP)に焦点を当てる。
PCSPは、よく知られた制約満足度問題(CSP)の一般化として機能する。
我々の主な貢献は、(O(|G| cdot |D|6)の時間複雑性を持つSPLグラフ上のPCSPの一般的なアルゴリズムであり、(|G|)は制御フローグラフのサイズを表す。
- 参考スコア（独自算出の注目度）: 0.21485350418225244
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we focus on the Partial Constraint Satisfaction Problem (PCSP) over control-flow graphs (CFGs) of programs. PCSP serves as a generalization of the well-known Constraint Satisfaction Problem (CSP). In the CSP framework, we define a set of variables, a set of constraints, and a finite domain $D$ that encompasses all possible values for each variable. The objective is to assign a value to each variable in such a way that all constraints are satisfied. In the graph variant of CSP, an underlying graph is considered and we have one variable corresponding to each vertex of the graph and one or several constraints corresponding to each edge. In PCSPs, we allow for certain constraints to be violated at a specified cost, aiming to find a solution that minimizes the total cost. Numerous classical compiler optimization tasks can be framed as PCSPs over control-flow graphs. Examples include Register Allocation, Lifetime-optimal Speculative Partial Redundancy Elimination (LOSPRE), and Optimal Placement of Bank Selection Instructions. On the other hand, it is well-known that control-flow graphs of structured programs are sparse and decomposable in a variety of ways. In this work, we rely on the Series-Parallel-Loop (SPL) decompositions as introduced by~\cite{RegisterAllocation}. Our main contribution is a general algorithm for PCSPs over SPL graphs with a time complexity of \(O(|G| \cdot |D|^6)\), where \(|G|\) represents the size of the control-flow graph. Note that for any fixed domain $D,$ this yields a linear-time solution. Our algorithm can be seen as a generalization and unification of previous SPL-based approaches for register allocation and LOSPRE. In addition, we provide experimental results over another classical PCSP task, i.e. Optimal Bank Selection, achieving runtimes four times better than the previous state of the art.
- Abstract（参考訳）: 本研究では,プログラムの制御フローグラフ(CFG)に対する部分制約満足度問題(PCSP)に焦点を当てる。
PCSPは、よく知られた制約満足度問題(CSP)の一般化として機能する。
CSPフレームワークでは、変数の集合、制約の集合、各変数の可能なすべての値を含む有限ドメイン$D$を定義します。
目的は、すべての制約が満たされるように、各変数に値を割り当てることである。
CSPのグラフ変種では、基礎となるグラフが考慮され、グラフの各頂点に対応する1つの変数と、各エッジに対応する1つまたは複数の制約がある。
PCSPでは,一定の制約が特定のコストで違反されることを許容し,総コストを最小化する解を見つけることを目的としている。
多くの古典的コンパイラ最適化タスクは、制御フローグラフ上のPCSPとしてフレーム化できる。
例えば、レジストレーションアロケーション、生涯最適部分冗長除去(LOSPRE)、銀行選択指導の最適配置などである。
一方、構造化プログラムの制御フローグラフはスパースであり、様々な方法で分解可能であることはよく知られている。
本稿では、~\cite{RegisterAllocation} で導入された直列パラレルループ(SPL)分解に依存する。
我々の主な貢献は、SPLグラフ上のPCSPの一般的なアルゴリズムであり、時間複雑性は \(O(|G| \cdot |D|^6)\) であり、ここで \(|G|\) は制御フローグラフのサイズを表す。
任意の固定領域 $D に対して、$ が線型時間解となることに注意。
我々のアルゴリズムは、レジスタ割り当てとLOSPREに対する従来のSPLベースのアプローチの一般化と統一であると見なすことができる。
さらに,従来のPCSPタスク,すなわち最適銀行選択に対して,従来の最先端の4倍のランタイムを実現する実験結果を提供する。
関連論文リスト
- Inexact Column Generation for Bayesian Network Structure Learning via Difference-of-Submodular Optimization [8.09615396808421]
最先端のBNSLIPの定式化は、指数関数的に多くの変数と制約に悩まされる。
このような課題に対処するためのIPの標準的なアプローチは、行と列の生成テクニックを採用することである。
我々の行と列の生成アプローチは、最先端のスコアベースアプローチよりも高い品質のソリューションが得られることを示す。
論文 参考訳（メタデータ） (2025-05-16T10:23:19Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - A Greedy Strategy for Graph Cut [95.2841574410968]
GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。
これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。
GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
論文 参考訳（メタデータ） (2024-12-28T05:49:42Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。
GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。
本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
論文 参考訳（メタデータ） (2023-05-26T15:13:09Z) - Functional Constrained Optimization for Risk Aversion and Sparsity
Control [7.561780884831967]
リスクとスパーシリティの要件は、ポートフォリオ最適化、アソート計画、放射線計画など、多くのアプリケーションで同時に実施する必要がある。
本稿では,これらの課題に対して凸あるいはスパース軌道を生成するレベル条件勾配(LCG)法を提案する。
提案手法は,極小勾配を解くための内部条件近似(CGO)を最適値のレベル1セット投影することを示す。
論文 参考訳（メタデータ） (2022-10-11T02:51:51Z) - A Deep Reinforcement Learning Framework For Column Generation [13.767526395378638]
カラム生成(CG)は、非常に多数の変数(カラム)を持つ線形プログラムを解くための反復アルゴリズムである。
CGのための最初の強化学習(RL)手法であるRCCGを提案する。
各繰り返しの局所情報に基づいて列をミオプティックに選択する典型的な列選択規則とは異なり、CGを逐次決定問題として扱う。
論文 参考訳（メタデータ） (2022-06-03T03:58:54Z) - Generating Target Graph Couplings for QAOA from Native Quantum Hardware
Couplings [3.2622301272834524]
本稿では,Ising型量子スピン系における限定大域制御を用いた任意の対象結合グラフの構築手法を提案する。
本手法は、量子近似最適化アルゴリズム(QAOA)をトラップされたイオン量子ハードウェア上に実装することによるものである。
Max-Cut QAOAのノイズシミュレーションにより、我々の実装は標準ゲートベースのコンパイルよりもノイズの影響を受けにくいことが示された。
論文 参考訳（メタデータ） (2020-11-16T18:43:09Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。