論文の概要: Using Sequential Runtime Distributions for the Parallel Speedup Prediction of SAT Local Search

• arxiv url: http://arxiv.org/abs/2403.08790v1
• Date: Tue, 30 Jan 2024 10:29:01 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-25 08:16:13.554342
• Title: Using Sequential Runtime Distributions for the Parallel Speedup Prediction of SAT Local Search
• Title（参考訳）: SAT局所探索の並列高速化予測における逐次実行時分布の利用
• Authors: Alejandro Arbelaez, Charlotte Truchet, Philippe Codognet,
• Abstract要約: 本稿では,その逐次バージョンの実行時挙動を解析することにより,与えられたアルゴリズムの並列性能を推定するフレームワークを提案する。 本研究では,2つのSAT局所探索ソルバ,すなわちSparrowとCCASATの並列処理性能について検討する。 モデルが正確であることを示し、実験データに近い性能を予測する。
• 参考スコア（独自算出の注目度）: 44.99833362998488
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents a detailed analysis of the scalability and parallelization of local search algorithms for the Satisfiability problem. We propose a framework to estimate the parallel performance of a given algorithm by analyzing the runtime behavior of its sequential version. Indeed, by approximating the runtime distribution of the sequential process with statistical methods, the runtime behavior of the parallel process can be predicted by a model based on order statistics. We apply this approach to study the parallel performance of two SAT local search solvers, namely Sparrow and CCASAT, and compare the predicted performances to the results of an actual experimentation on parallel hardware up to 384 cores. We show that the model is accurate and predicts performance close to the empirical data. Moreover, as we study different types of instances (random and crafted), we observe that the local search solvers exhibit different behaviors and that their runtime distributions can be approximated by two types of distributions: exponential (shifted and non-shifted) and lognormal.
• Abstract（参考訳）: 本稿では,Satifiability 問題に対する局所探索アルゴリズムのスケーラビリティと並列化を詳細に解析する。 本稿では,その逐次バージョンの実行時挙動を解析することにより,与えられたアルゴリズムの並列性能を推定するフレームワークを提案する。 実際、シーケンシャルプロセスのランタイム分布を統計的手法で近似することにより、並列プロセスのランタイム挙動を順序統計に基づくモデルで予測することができる。 本研究では,2つのSATローカルサーチソル(Sparrow と CCASAT)の並列性能について検討し,予測性能と384コアまでの並列ハードウェアにおける実実験結果を比較した。 モデルが正確であることを示し、実験データに近い性能を予測する。 さらに,異なる種類のインスタンス(ランダムおよび工芸品)を調査した結果,局所探索解法は異なる挙動を示し,その実行時分布は指数(シフト)と非シフト)と対数正規の2種類の分布で近似できることがわかった。

関連論文リスト

• An Agglomerative Clustering of Simulation Output Distributions Using Regularized Wasserstein Distance [0.0]
  本稿では,正規化ワッサーシュタイン距離をクラスタシミュレーション出力に利用した新しいクラスタリングアルゴリズムを提案する。 このフレームワークには、異常検出、事前最適化、オンライン監視など、いくつかの重要なユースケースがある。
  論文  参考訳（メタデータ） (2024-07-16T18:07:32Z)
• AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
  既存の因果探索法を効率的に並列化することにより,数千次元まで拡張可能であることを示す。 具体的には、DirectLiNGAMの因果順序付けサブプロデューサに着目し、GPUカーネルを実装して高速化する。 これにより、遺伝子介入による大規模遺伝子発現データに対する因果推論にDirectLiNGAMを適用することで、競争結果が得られる。
  論文  参考訳（メタデータ） (2024-03-06T15:06:11Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。 我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。 シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
  論文  参考訳（メタデータ） (2024-01-29T02:08:40Z)
• Sequential and Shared-Memory Parallel Algorithms for Partitioned Local Depths [0.0]
  PaLDは相対距離に基づいて対関係の強さを同定する手法である。 性能最適化戦略を導入し、ベースラインのシーケンシャルな実装に対して、最大29ドル以上のシーケンシャルなスピードアップを実現した。
  論文  参考訳（メタデータ） (2023-07-31T13:32:39Z)
• Exploring Techniques for the Analysis of Spontaneous Asynchronicity in MPI-Parallel Applications [0.8889304968879161]
  マイクロベンチマークと現実的なプロキシアプリケーションを,2つの異なるスーパーコンピュータプラットフォーム上で通常の計算通信構造で実行します。 完全MPIトレースよりもはるかに小さいデータセットから,デシンクロナイゼーションパターンを容易に識別できることを示す。
  論文  参考訳（メタデータ） (2022-05-27T13:19:07Z)
• Conformance Checking Over Stochastically Known Logs [7.882975068446842]
  データログは、例えば、センサ読み取りの不正確さや、処理プログラムによる読み取りの誤った解釈によって不確実になる可能性がある。 この作業では、プロセスモデルとイベントログを比較するコンフォーマンスチェックに重点を置いています。 我々は,ログ内の事象の不確実性を反映したトレースモデル,同期生成物,コスト関数を数学的に定義する。
  論文  参考訳（メタデータ） (2022-03-14T21:33:06Z)
• Cluster-and-Conquer: A Framework For Time-Series Forecasting [94.63501563413725]
  本稿では,高次元時系列データを予測するための3段階フレームワークを提案する。 当社のフレームワークは非常に汎用的で,各ステップで時系列予測やクラスタリングが利用可能です。 単純な線形自己回帰モデルでインスタンス化されると、いくつかのベンチマークデータセットで最先端の結果が得られる。
  論文  参考訳（メタデータ） (2021-10-26T20:41:19Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。 特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
  論文  参考訳（メタデータ） (2020-10-31T18:19:29Z)
• Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
  我々はヘッセン語の形成が計算的に困難であり、通信がボトルネックとなる分散最適化問題を考察する。 我々は、ヘッセンのサンプリングとスケッチを用いたランダム化二階最適化のための非バイアスパラメータ平均化手法を開発した。 また、不均一なコンピューティングシステムのための非バイアス分散最適化フレームワークを導入するために、二階平均化手法のフレームワークを拡張した。
  論文  参考訳（メタデータ） (2020-02-16T09:01:18Z)
• Statistical Outlier Identification in Multi-robot Visual SLAM using Expectation Maximization [18.259478519717426]
  本稿では、同時局所化およびマッピング(SLAM)におけるマップ間ループ閉包外乱検出のための、新しい分散手法を提案する。 提案アルゴリズムは優れた初期化に頼らず、一度に2つ以上のマップを処理できる。
  論文  参考訳（メタデータ） (2020-02-07T06:34:44Z)

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

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