{"ID":5438804,"CreatedAt":"2026-07-01T01:17:58.482524686Z","UpdatedAt":"2026-07-03T10:35:20.036867845Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.31481","arxiv_id":"2606.31481","title":"Maximizing Parallel Execution of Series-Parallel Task Graphs for Safety-Critical Embedded Control","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.","short_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 Executio...","url_abs":"https://arxiv.org/abs/2606.31481","url_pdf":"https://arxiv.org/pdf/2606.31481v1","authors":"[\"Jinghao Sun\",\"Zhenchu Hu\",\"Ye Ma\",\"Bo Tang\",\"Qingxu Deng\",\"Xiuzhen Cheng\"]","published":"2026-06-30T10:58:04Z","proceeding":"cs.SE","tasks":"[\"cs.SE\"]","methods":"[]","has_code":false}