論文の概要: Maximizing Parallel Execution of Series-Parallel Task Graphs for Safety-Critical Embedded Control
- arxiv url: http://arxiv.org/abs/2606.31481v1
- Date: Tue, 30 Jun 2026 10:58:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-01 18:27:19.186393
- Title: Maximizing Parallel Execution of Series-Parallel Task Graphs for Safety-Critical Embedded Control
- Title（参考訳）: 安全臨界組込み制御のための連続並列タスクグラフの並列実行の最大化
- Abstract要約: 安全クリティカルな組込み制御プログラムは、境界期間内に各制御サイクルを完了する必要がある。
従来のプロセッサ上でのシーケンス実行は、プログラムの依存関係構造が同時に実行できるサブタスクを含む場合、ボトルネックとなる可能性がある。
本稿では,列並列タスクグラフの最大並列実行問題について検討する。
- 参考スコア（独自算出の注目度）: 18.61597219416426
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Safety-critical embedded control programs must complete each control cycle within a bounded period. Sequential execution on conventional processors can become a bottleneck when the dependency structure of the program contains subtasks that could be executed concurrently. This paper studies the Maximum Parallel Execution (MPE) problem for series-parallel task graphs under a staged batching model: compatible tasks inside one batch execute in parallel, while the selected batches are launched sequentially in a topological order that preserves precedence. We formulate MPE as a weighted clique-partitioning problem that minimizes the sum of batch execution times, with each batch cost determined by its slowest task. To solve this problem efficiently, we propose a Lagrangian-based Iterative Heuristic (LIH). LIH constructs a pricing-filtered restricted pool of feasible candidate batches from singleton columns and random greedy clique generation. It then applies Lagrangian pricing to guide column selection and uses a repair procedure to recover a legal clique partition. Experiments against a weighted mixed-graph-coloring branch-and-bound baseline and a randomized greedy baseline show that LIH matches the exact optimum in 91.25% of comparable instances, with an average gap of 0.073% and an average runtime of 18.19 ms. In the largest exact-reference node setting, the exact baseline requires hundreds of seconds on average, whereas LIH remains below 50 ms. We further present an end-to-end PLC ladder-logic case study in which PLCOpen-style programs are converted to MPE graphs, optimized by LIH, translated into FPGA-oriented HDL, and simulated against the original PLC scan execution.
- Abstract（参考訳）: 安全クリティカルな組込み制御プログラムは、境界期間内に各制御サイクルを完了する必要がある。
プログラムの依存関係構造が同時に実行されるサブタスクを含む場合、従来のプロセッサ上でのシーケンシャルな実行はボトルネックとなる可能性がある。
本稿では, 並列並列タスクグラフの最大並列実行(MPE)問題について, 1つのバッチ内の互換タスクを並列に実行し, 選択したバッチをトポロジ的な順序で順次起動し, 優先順位を保った。
我々は,MPEをバッチ実行時間の総和を最小限に抑える重み付き斜め分割問題として定式化し,各バッチコストを最も遅いタスクによって決定する。
この問題を効率的に解決するために,ラグランジアン系イテレーティブヒューリスティック(LIH)を提案する。
LIHは、シングルトンカラムとランダムなグリーディクリッド生成から実行可能な候補バッチの価格フィルター付き制限プールを構築する。
次に、カラムの選択をガイドするためにLagrangianの価格を適用し、修復手順を使用して法的なcliqueパーティションを復元する。
重み付けされた混合グラフカラーのブランチ・アンド・バウンドベースラインとランダム化されたグレディベースラインに対する実験では、LIHは91.25%で正確な最適値に一致し、平均差は0.073%、平均実行時間は18.19msである。
関連論文リスト
- BASP: Communication-Efficient Batch-Aware Sequence Parallelism for LLM Training [0.48127184936824546]
BASP(Batch-Aware Sequence Parallelism)は、バッチ構造を利用して通信オーバーヘッドを削減するシーケンス並列化手法である。
BASPは、マイクロバッチサイズに応じて分離されたシーケンス並列グループに分割することで、バッチ構造を利用する。
NVIDIA A100クラスタの実験結果によると、BASPはエンドツーエンドのトレーニング時間を最大1.17～1.31倍改善している。
論文 参考訳（メタデータ） (2026-09-02T20:33:23Z) - ELASTIC: Efficiently Learning to Adaptively Scale Test-Time Compute for Generative Control Policies [36.28264388380867]
ジェネレーティブコントロールポリシー(GCP)は、ロボット制御におけるテストタイムスケーリングを可能にする。
テスト時間計算はシーケンシャルスケーリングと並列スケーリングの2つの軸に沿って割り当てることができる。
GCPの状態依存型テスト時間計算スケジュールを学習するアルゴリズムであるELASTICを提案する。
論文 参考訳（メタデータ） (2026-06-30T05:00:32Z) - SonicSampler: Unified Tile-Aware Kernels for LLM Sampling and Speculative Verification [27.358689380362964]
タイルを意識したTritonカーネルの統一スイートであるtextbfSonicSampler$を提示する。
我々のカーネルは文法制約付き復号を含む動的要求ごとのサンプリング動作をサポートしている。
投機的デコーディング全体にわたって、SonicSamplerは最先端のベースラインに対して最大$textbf16xのスピードアップを達成する。
論文 参考訳（メタデータ） (2026-05-24T23:01:50Z) - F-GRPO: Factorized Group-Relative Policy Optimization for Unified Candidate Generation and Ranking [79.49893545611779]
大規模言語モデル(LLM)はサブセットを生成し、それを1つの自己回帰パス内で順序付けることができる。
この柔軟性は、新しい最適化課題をもたらす: モデルが出力空間を検索し、完全なランクリストが生成された後にのみユーティリティフィードバックを受けなければならない。
このクレジット割り当てギャップは、エンドツーエンドの最適化を不安定にし、サンプル非効率にする。
本稿では,単一自己回帰的ロールアウト内の両方を実行する統一フレームワークを提案する。
論文 参考訳（メタデータ） (2026-05-13T04:52:33Z) - Chimera: Latency- and Performance-Aware Multi-agent Serving for Heterogeneous LLMs [62.17306142810532]
ヘテロジニアスLSMクラスタ上で動作するマルチエージェントワークフローの予測スケジューリングシステムであるChimeraを提案する。
Chimeは最高のレイテンシをトレースし、エンドツーエンドのレイテンシを1.2-2.4$times$で削減し、タスクパフォーマンスを平均8.0-9.5ポイント改善する。
論文 参考訳（メタデータ） (2026-03-23T17:01:42Z) - IsoCompute Playbook: Optimally Scaling Sampling Compute for LLM RL [75.28528082188787]
大規模言語モデル(LLM)におけるオンライン強化学習手法におけるサンプリング計算の最適割当について検討する。
並列ロールアウトの計算最適数は,計算予算とともに予測可能で増加し,飽和することがわかった。
本結果は,RLスケーリング法則を規範的割り当て規則として再考し,計算効率の高いLLM RLポストトレーニングのための実践的ガイダンスを提供する。
論文 参考訳（メタデータ） (2026-03-12T16:49:21Z) - Large-scale portfolio optimization on a trapped-ion quantum computer [32.24411362086563]
基数制約付き大規模ポートフォリオ選択のためのエンドツーエンドパイプラインを提案する。
ハードウェア・アウェア分解を用いたトラップイオン量子プロセッサ上での実験実験を行った。
論文 参考訳（メタデータ） (2026-02-27T12:36:14Z) - Para-B&B: Load-Balanced Deterministic Parallelization of Solving MIP [50.917107318582715]
MIP(Mixed-integer Programming)は、連続型と整数型の両方の決定変数を組み込むことで線形プログラミングを拡張する。
本稿では,高性能MIPソルバであるHiGHSに対して,決定論的並列分岐結合の完全なオープンソース実装を初めて提案する。
本手法では,ワーカスレッド間で完全なソルバ状態を複製することにより,厳密な決定性を保証する新しいデータ並列アーキテクチャを提案する。
論文 参考訳（メタデータ） (2026-02-10T14:17:53Z) - Learning Grouped Lattice Vector Quantizers for Low-Bit LLM Compression [57.54335545892155]
本稿では,各重みの群に独自の格子コードブックを割り当てるGLVQ(Grouped Lattice Vector Quantization)フレームワークを紹介する。
提案手法は,既存のトレーニング後の量子化ベースラインと比較して,モデルサイズと精度のトレードオフが良好である。
論文 参考訳（メタデータ） (2025-10-23T20:19:48Z) - dParallel: Learnable Parallel Decoding for dLLMs [77.24184219948337]
拡散大言語モデル(dLLM)は並列トークン予測と低推論遅延を提供する。
既存のオープンソースモデルは、パフォーマンスを確保するためにトークン長のデコードステップをほとんど必要としています。
高速サンプリングのためにdLLMs固有の並列性を解き放つシンプルで効果的な方法であるdParallelを導入する。
論文 参考訳（メタデータ） (2025-09-30T16:32:52Z) - LLM Serving Optimization with Variable Prefill and Decode Lengths [6.937936394246354]
本研究では,各要求が不均一なプレフィルとデコード長を持つLLM要求(Large Language Model)を提供する問題について検討する。
この問題は、配置制約の相互運用、優先関係、メモリ使用量の線形増加などによりNPハードであることが示される。
本稿では,時間とともに効率よくバッチを生成する新しい選択基準に基づく新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-08-08T08:54:21Z) - Multi-Bin Batching for Increasing LLM Inference Throughput [19.652542432683234]
大規模言語モデル(LL)は、システムの効率性を向上させるために人気が高まっている。
リクエストはサーバ上のジョブをスケジューリングする重要なステップです。
リクエストは、しばしば異なる生成長を持ち、リソースの未利用を引き起こす。
我々は、この問題をキューイング理論の観点から形式化し、スループット制御ポリシーを設計することを目的とする。
論文 参考訳（メタデータ） (2024-12-03T03:16:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。