1
Maximizing Parallel Execution of Series-Parallel Task Graphs for Safety-Critical Embedded Control
arXiv:2606.31481v1 [cs.SE] 30 Jun 2026
Jinghao Sun
, Zhenchu Hu
, Ye Ma
, Bo Tang, Qingxu Deng
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 mixedgraph-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 exactreference 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. Index Terms—Embedded control, FPGA acceleration, Lagrangian relaxation, maximum parallel execution, series-parallel graphs, task scheduling.
I. I NTRODUCTION A series-parallel (SP) task graph is a structured special case of a directed acyclic graph (DAG). It models a computation as subtasks composed by two fundamental operations: series composition, which chains subtasks that must execute sequentially due to data dependencies, and parallel composition, which groups independent subtasks that may execute concurrently. This recursive structure arises naturally in a broad class of safety-critical embedded control programs—PID regulation Jinghao Sun and Xiuzhen Cheng are with the School of Computer Science and Technology, Shandong University, Qingdao 266237, China (e-mail: [email protected]; [email protected]). Zhenchu Hu and Ye Ma are with the School of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China (e-mail: [email protected]; [email protected]). Bo Tang is with Weichai Power Co., Ltd., Weifang 261061, China. (e-mail: [email protected]) Qingxu Deng is with the School of Computer Science and Engineering, Northeastern University, Shenyang 110004, China (e-mail: [email protected]). Corresponding author: Ye Ma (e-mail: [email protected]).
, and Xiuzhen Cheng
loops, sensor fusion pipelines, and fault-detection logic— where certain operations depend on the output of others while the remaining operations are mutually independent [1], [2]. Given such a task graph, a central question is: how should its subtasks be dispatched to maximize parallel execution and thereby minimize the overall completion time (makespan)? We refer to this as the Maximum Parallel Execution (MPE) problem on SP task graphs, and it is the subject of this paper. The MPE problem is motivated by timing constraints in realtime embedded control. Safety-critical control systems—found in industrial automation, robotics, autonomous vehicles, and high-precision instrumentation, must complete their control algorithms within a bounded control period to guarantee stability and responsiveness [3], [4]. Traditionally, these control tasks are executed sequentially on microcontrollers or digital signal processors, and decades of effort have been devoted to optimizing serial performance through instruction-level pipelining, compiler optimizations, and clock-frequency scaling [5]–[7]. These serial techniques are increasingly constrained by power, frequency, and memory latency limits. At the same time, modern applications often demand shorter control periods, for example when faster physical dynamics or finer-grained actuation require a loop to run at millisecond or sub-millisecond scale. Exposing task-level parallelism is therefore an important way to reduce the time spent in one control cycle. Field-Programmable Gate Arrays (FPGAs) are a natural platform for this form of parallelization. Prior implementations of industrial control, predictive current control, model predictive control, and IEC 61131-3 timer logic show that typical embedded control functions can be mapped to FPGA hardware with moderate resource usage and deterministic timing behavior [8]–[11]. Beyond their familiar role in neural-network acceleration [12], [13], FPGAs are attractive for embedded control because they combine hardware-level determinism, reconfigurability, low power consumption, and robustness in harsh operating environments [8], [14]. Under this resourceabundant setting, the main question is no longer processor allocation, but structure: which tasks can be batched together without violating dependencies, and in what staged order should those batches be executed? Compared with scheduling on arbitrary DAGs, a wellstudied but NP-hard problem in general [15], the SP restriction admits significantly more efficient solutions. SP graphs possess a recursive decomposition tree that mirrors their series-parallel construction, and this structure can be exploited algorithmically [1], [2], [16]. Yet, existing work on SP graph scheduling has largely focused on resource-constrained settings, such as limited processors, or general-purpose parallel platforms, and
2
does not directly address the FPGA-oriented scenario where computation units are abundant but the goal is to maximize the parallelism exposed from an originally sequential program [2], [16]. Moreover, prior studies on FPGA-based control acceleration typically treat the task graph as a flat pipeline or rely on ad hoc manual partitioning, without systematically exploiting the SP structure inherent in control programs [5]. This paper formalizes the MPE problem on SP task graphs for FPGA platforms under the assumption of sufficient computation units, and proposes an efficient L AGRANGIAN - BASED I TERATIVE H EURISTIC (LIH) for generating static staged batching plans. Given a control program with an SP-like dependency structure, LIH exposes within-stage parallelism while preserving precedence consistency between stages. The main contributions are as follows: • We formulate MPE on an augmented series-parallel task graph that combines precedence arcs, compatibility edges, weighted task costs, and staged batching semantics for FPGA-oriented execution. • We express MPE as a weighted clique-partitioning problem with contracted-graph acyclicity, giving both an exact column model and a direct interpretation in which each selected clique is one parallel hardware stage. • We propose LIH, which uses pricing-filtered candidate generation, Lagrangian reduced-cost pricing, feasibility repair, and local refinement to avoid enumerating the exponential space of feasible batches. • We evaluate LIH against an exact weighted mixed-graphcoloring baseline and a randomized greedy baseline, and further demonstrate the complete PLC ladder-to-HDL workflow through parsing, MPE optimization, Verilog generation, simulation, and scan-cycle comparison. The remainder of this paper is organized as follows. Section II presents the system model and problem formulation. Section III describes the proposed Lagrangian-based iterative heuristic. Section IV reports experimental results. Section V shows how a PLC ladder program is mapped to the MPE graph and how a batching plan can be realized on FPGA-oriented hardware. Related work is discussed in Section VI. Section VII concludes the paper. II. S YSTEM M ODEL AND P ROBLEM F ORMULATION This section formulates Maximum Parallel Execution (MPE) as a clique-partitioning problem on an augmented series-parallel task graph (SPG). We first define the graph model and staged batching semantics, and then give the exact integer formulation used as the reference problem.
Let the input SPG be represented as a mixed graph1 G = (V, E, A), where V is the set of computational tasks, E is the set of undirected compatibility edges, and A is the set of directed precedence arcs. Each vertex v ∈ V represents an atomic operation, a function block, or a higher-level control action, and has a positive execution time wv > 0. The directed graph (V, A) is acyclic and follows the series-parallel precedence structure. A directed arc (u, v) ∈ A means that task u must finish before task v can start. An undirected edge {u, v} ∈ E means that u and v are mutually compatible and may be placed in the same parallel execution batch. The compatibility relation collects implementation conditions that cannot be represented by precedence alone, such as conflicting state updates, exclusive I/O access, or hardware resources that cannot be duplicated. Resource attributes such as LUT, DSP, BRAM, memory-port, or safety-partition usage can also be encoded in E. In this paper we assume sufficient FPGA computation units for any selected batch, so the limiting factor is the dependency and compatibility structure of G. Under this concurrent execution semantics, the duration of a selected batch is determined by its slowest task. B. Clique Partitioning and Parallelization Semantics Partitioning turns graph-level parallelism into an executable sequence of parallel batches. Write u ⇝A v if there is a directed path from u to v in (V, A). A subset S ⊆ V is a feasible batch if its vertices are pairwise compatible and have no direct or transitive precedence relation: {u, v} ∈ E,
u ̸⇝A v,
v ̸⇝A u,
∀u, v ∈ S, u ̸= v.
Equivalently, S is a clique in the compatibility graph that does not collapse any precedence path. The execution cost of S is c(S) = max wv . v∈S
In the FPGA deployment, one batch corresponds to one execution stage: all tasks in S are enabled together, and interstage registers hold values required by later stages. Compared with P serial execution, the local saving of a non-singleton batch is v∈S wv −maxv∈S wv . Singleton batches remain available for tasks that cannot be legally or profitably merged. A clique partition C = {C1 , . . . , Cm } assigns every vertex to exactly one feasible batch: Ci ∩ Cj = ∅ (i ̸= j),
m [
Ci = V.
i=1
A. Series-Parallel Task Graph An SPG describes a computation built from series and parallel composition. Series composition imposes an execution order, whereas parallel composition places subgraphs in the same logical region without an internal ordering relation. This structure appears naturally in embedded control programs, where serial data dependencies coexist with independent sensing, filtering, diagnosis, and actuation branches that can be mapped to parallel FPGA logic.
We use staged sequential batching semantics. Tasks in the same batch execute concurrently, while batches are issued one at a time by a controller according to a topological order of the contracted graph. This preserves the sequential effects of 1 Strictly speaking, the model used in this paper is an augmented SPG rather than a conventional SP graph. The series-parallel restriction is imposed on the directed precedence component (V, A); the model additionally includes undirected compatibility edges E, vertex execution times wv , and the stagedbatching semantics with contracted-graph acyclicity used for MPE.
3
the original program while exploiting spatial parallelism inside each stage. After each Ci is contracted into a super-vertex, every original arc (u, v) ∈ A with u ∈ Ci , v ∈ Cj , and i ̸= j induces an arc Ci → Cj . This contraction replaces several fine-grained tasks by one coarse-grained parallel stage. The partition is legal only if the contracted graph G/C is acyclic, which ensures that the selected batches admit at least one staged execution order. Fig. 1 shows an infeasible partition whose contraction creates a directed cycle.
Fig. 2. An example SPG and a feasible clique partition. Fig. 1. An infeasible clique partition whose contracted graph contains a directed cycle.
For a legal partition C, the makespan under the staged batching semantics is the sum of the selected batch costs: X X T (C) = c(C) = max wv . (1) C∈C
C∈C
v∈C
Thus, maximizing parallel execution is equivalent to minimizing the additive cost of legal batches. In Fig. 2, for example, the partition C1 = {v1 , v5 } and C2 = {v2 , v3 , v4 } has costs 15 and 25, giving T (C) = 40. C. Maximum Parallel Execution Formulation Let P ⋆ be the unrestricted set of all feasible batches in G. It contains every feasible clique satisfying compatibility and no-internal-path conditions. Fig. 3 illustrates P ⋆ for the same SPG. Each candidate batch is represented as a column p ∈ P ⋆ with vertex set Sp ⊆ V , cost cp = max wv , v∈Sp
and incidence coefficient ( avp =
1, 0,
if v ∈ Sp , otherwise.
The binary variable zp indicates whether column p is selected: ( 1, if Sp is selected as a batch, zp = 0, otherwise. The Maximum Parallel Execution (MPE) problem is then formulated as X T ⋆ (G) = min cp zp (2) z
s.t.
p∈P ⋆
X
avp zp = 1,
∀v ∈ V, (3)
p∈P ⋆
G/{Sp : zp = 1} is acyclic, zp ∈ {0, 1},
(4) ⋆
∀p ∈ P .
Singletons {v1 }
{v2 }
{v3 }
{v4 }
{v5 }
Pairs {v1 , v3 }
{v1 , v4 }
{v1 , v5 }
{v2 , v3 }
{v2 , v4 }
{v2 , v5 }
{v3 , v4 }
{v4 , v5 }
Triples {v1 , v3 , v4 }
{v1 , v4 , v5 }
{v2 , v3 , v4 }
{v2 , v4 , v5 } Sets containing both v1 and v2 are excluded by precedence.
Fig. 3. Example of the unrestricted feasible batch set P ⋆ for the SPG in Fig. 2.
Constraint (3) is the exact coverage constraint: every task must be assigned to one and only one selected batch. Constraint (4) preserves global precedence consistency after batch contraction. The objective (2) minimizes the total execution time of the selected parallel batches. D. Challenges for Parallelization Although exact, the formulation is difficult to solve directly. It contains set-partitioning and clique-partitioning structure, which is NP-hard in general [15], and the column set P ⋆ can be exponentially large. The selected columns must also cover every vertex exactly once and yield an acyclic contracted graph, so local clique feasibility alone is insufficient. The next section therefore introduces a Lagrangian-based iterative heuristic. Instead of enumerating all of P ⋆ , it works with a restricted candidate set P ⊆ P ⋆ while retaining the same column notation Sp , cp , avp , and zp . The exact coverage equality (3) then becomes the source of the Lagrangian multipliers.
4
III. L AGRANGIAN - BASED I TERATIVE H EURISTIC The exact model in Section II uses the unrestricted candidate set P ⋆ , which can be exponentially large. The Lagrangianbased Iterative Heuristic (LIH) instead works over a restricted pool P ⊆ P ⋆ . Each column in P is still a locally feasible clique; the restriction only limits which feasible cliques are considered. LIH first builds a preliminary pool from singleton and random-greedy cliques. Because the useful cliques are unknown a priori, a warm-up Lagrangian pricing pass ranks the generated non-singleton columns. LIH keeps all singleton columns and only the top-ranked non-singleton columns for the main iterations, reducing the influence of low-value cliques while preserving a trivial feasible partition. The retained pool is then priced, repaired, and refined; repair is needed because the relaxed selection may overlap, miss vertices, or create a cycle after contraction. For clarity, Table I lists the notation used in this section. Lagrangian relaxation moves coupling constraints into the objective with multipliers [17], [18]. In LIH, the multipliers act as vertex prices: over-covered vertices become more expensive, whereas uncovered vertices become cheaper. The pricing step therefore provides both a dual search signal and a ranking rule for candidate cliques.
of P ⋆ , the restricted optimum may be worse than the unrestricted optimum; LIH accepts this trade-off to avoid the full exponential column space. Relaxation Strategy The local feasibility of each column is guaranteed during candidate generation: LIH checks pairwise compatibility and rejects cliques containing a directed precedence path. Coverage, however, is global. The equality X avp zp = 1 p∈P
couples all columns that contain vertex v. LIH therefore relaxes the exact coverage constraints and assigns one multiplier λv to each vertex. If the relaxed solution covers v more than once, λv is increased, making columns containing v more expensive. If the relaxed solution does not cover v, λv is decreased, making columns containing v more attractive. Thus, the multipliers are adaptive vertex prices derived directly from (3). The pricing step is therefore a search guide rather than a complete feasibility mechanism: coverage and contracted acyclicity are restored later by repair, while the relaxed subproblem remains separable by columns.
A. Restricted Column Model and Relaxation
B. Lagrangian Pricing and Multiplier Update
We reuse the notation introduced in Section II. The only change from the exact formulation is the candidate set:
Let λv ∈ R be the Lagrange multiplier associated with the coverage equality of vertex v. For a fixed multiplier vector
P ⊆ P ⋆,
λ = (λv )v∈V ,
{{v} : v ∈ V } ⊆ P.
For each p ∈ P, the vertex set Sp , cost cp , incidence coefficient avp , and binary selection variable zp have the same meaning as in Section II. The preliminary pool can be written as P0 = Psg ∪ Prg , where Psg contains singleton columns and Prg contains random greedy cliques. LIH then applies a warm-up pricing screen to obtain the working pool P = Psg ∪ Topη P0 \ Psg , where Topη (·) denotes the top η fraction of non-singleton columns under the warm-up reduced-cost ranking. The singleton columns ensure that the restricted model always has at least the serial feasible partition. Using these columns, the restricted column-selection model is formulated as X min cp zp z
s.t.
p∈P
X
avp zp = 1,
∀v ∈ V,
=
p∈P
v∈V
p∈P
X
XX
λv avp zp −
(6) ∀p ∈ P.
Constraint (5) enforces exact coverage, and constraint (6) enforces acyclicity after contraction. Since P is only a subset
v∈V p∈P
X
λv .
(7)
v∈V
Exchanging the summation order gives XX XX λv avp zp = λv avp zp . v∈V p∈P
p∈P v∈V
Since avp = 1 only when v ∈ Sp , X X λv avp zp = λv zp . v∈V
(8)
v∈Sp
Substituting (8) into (7) gives L(z, λ) = −
G/{Sp : zp = 1} is acyclic,
cp zp +
p∈P
(5)
p∈P
zp ∈ {0, 1},
the Lagrangian objective is obtained by adding the weighted coverage violation to the original objective: X X X L(z, λ) = cp zp + λv avp zp − 1
X
cp +
X
λv zp .
(9)
Equation (9) defines the reduced cost of column p: X c̄p (λ) = cp + λv .
(10)
v∈V
λv +
X p∈P
v∈Sp
v∈Sp
5
TABLE I LIH NOTATION . Symbol
Meaning
Symbol
Meaning
L(z, λ) c̄p (λ), c̄(λ) ϕ(λ), ϕt P − (λ), P − hv (λ), hv
Vertex multiplier, vector, iteration-t value, and warm-up vector. Lagrangian objective. Column reduced cost and vector. Dual function and current dual value. Negative-reduced-cost columns. Relaxed coverage count.
gv (λ), gv , g t
Coverage violation/subgradient.
αt , ρ, ϵ
Step size, scale, and minimum step.
max [x]w ,x ϵ
Scalar clipping to [ϵ, wmax ].
M , Π[−M,M ]
Multiplier bound and projection.
C, C b C best C 0 , C,
SPG: tasks, compatibility edges, and precedence arcs. Task vertices. Vertex subset; subset of column p. Vertex time, weight vector, maximum weight. All feasible columns; restricted pool. Preliminary, singleton, and random-greedy pools. Fraction of non-singleton columns retained after warm-up pricing. Column index, preliminary columns, retained columns, vertices, and maximum column size. Pool cap, random-greedy rounds, seed, and optional deadline. Random-greedy round, ordered list, and shuffled list. Clique/batch and clique partition. Initial, repaired, and best partitions.
λv , λ, λtv , λw
c(S), c(C), cp avp zp , zp (λ) G/{Sp : zp = 1}, G/C
Batch or column cost. 1 if v ∈ Sp , 0 otherwise. Column selection and relaxed selection. Contracted graph.
U Bt , U B saving(p), τ (p), score(p) t, T , h ∥ · ∥2 , | · |, O(·) ∅, R, {0, 1}
Best feasible objective value. Repair saving, insertion order, and ranking key. Iteration index, limit, and repair interval. Norm, cardinality, complexity. Empty, real, and binary sets.
G = (V, E, A) u, v S, Sp wv , w, wmax P ⋆, P P0 , Psg , Prg η p, m0 , m, n, q mmax , Rrg , ξ, ∆ ℓ, V ↓ , Vπ
For a fixed multiplier vector λ, the relaxed pricing problem is min
z∈{0,1}|P|
L(z, λ).
Because coverage and contracted acyclicity are relaxed during pricing, each zp can be optimized independently: ( 1, if c̄p (λ) < 0, zp (λ) = (11) 0, if c̄p (λ) ≥ 0. Thus, only negative-reduced-cost columns are selected in the relaxed solution. Substituting the best independent decisions from (11) into (9) yields the Lagrangian dual function X X ϕ(λ) = − λv + min{0, c̄p (λ)}. (12) v∈V
p∈P
LIH does not solve the dual problem to optimality. It uses ϕ(λ) and the reduced costs as search signals: a small reduced cost indicates either a low clique cost, under-covered vertices, or both. Subgradient Multiplier Update The dual function (12) is piecewise linear and may be nondifferentiable. Therefore, LIH updates the multipliers by a subgradient method. Let P − (λ) = {p ∈ P : c̄p (λ) < 0}
The corresponding coverage violation is gv (λ) = hv (λ) − 1. This expression is inherited directly from the relaxed coverage P equality p∈P avp zp − 1 = 0, so gv (λ) is a valid subgradient component for multiplier λv . The multiplier update is λt+1 = Π[−M,M ] λtv + αt gvt , ∀v ∈ V, v where Π[−M,M ] denotes projection onto the interval [−M, M ]. In the implementation, M = 2wmax ,
wmax = max wv . v∈V
The projection prevents excessively large multipliers from dominating the original clique costs and stabilizes the search. The update follows the price interpretation: over-covered vertices (hv > 1) become more expensive, uncovered vertices (hv = 0) become cheaper, and exactly covered vertices keep the same price. Let U Bt be the best feasible objective value found so far, and let ϕt = ϕ(λt ). When ϕt < U Bt , LIH uses a Polyak-style step size: w U Bt − ϕt max αt = ρ , if ϕt < U Bt , ∥g t ∥22 ϵ
(13)
where ρ > 0 is a step-scale parameter and be the set of columns selected by the relaxed pricing rule. The coverage count of vertex v in this relaxed solution is X hv (λ) = avp . p∈P − (λ)
max [x]w = min{wmax , max{ϵ, x}}. ϵ
Here, ϵ > 0 is a small minimum step-size parameter. It provides the lower clipping bound, so an active multiplier
6
update is not reduced to an exactly zero step by the step-size rule. The numerator U Bt − ϕt measures the current primaldual gap, while ∥g t ∥22 normalizes the update by the coverage violation. When ϕt ≥ U Bt , LIH switches to a damped fallback step: wmax wmax √ . (14) αt = ρ t max{1, ∥g t ∥22 } ϵ This fallback keeps the multiplier update active, while the √ factor 1/ t gradually reduces oscillation in later iterations. C. Candidate Pool, Repair, and Local Refinement The candidate pool is constructed once before the main Lagrangian iterations. Singleton columns guarantee coverage and define the serial initial partition C 0 = {{v} : v ∈ V }. Algorithm 1 adds locally feasible multi-vertex cliques by checking compatibility, precedence paths, size, duplicates, and the pool cap. The resulting preliminary pool P0 may still contain many low-value cliques. LIH therefore performs one warm-up pricing iteration and ranks non-singleton columns by c̄p (λw )/|Sp |, where λw is the warm-up multiplier vector. It then keeps all singletons and the top η fraction of non-singleton columns. In our experiments, η = 5% is sufficient to retain nearly all columns used by optimal partitions on exact-reference instances. The remaining task is to select disjoint retained columns whose contraction is acyclic. Algorithm 1: RandomGreedyColumns candidate-pool generation.
for
Input: SPG G = (V, E, A), vertex weights w, initial pool P, size bound q, pool cap mmax , rounds Rrg , seed ξ, optional deadline ∆; 2 Output: Updated candidate pool P; 3 initialize the random generator with seed ξ; ↓ 4 V ← vertices sorted by nonincreasing wv ; 5 for ℓ = 1, . . . , Rrg do 6 if |P| ≥ mmax or deadline ∆ is reached then 7 break; 1
8 9 10 11 12 13
14 15 16
17
Vπ ← RandomShuffle(V ↓ ); S ← ∅; for each v ∈ Vπ do if |S| ≥ q then break; if {u, v} ∈ E, u ̸⇝A v, and v ̸⇝A u for every u ∈ S then S ← S ∪ {v}; if S ∈ / P and S is a feasible clique then insert S into P and record c(S) and avp ; return P;
Repairing the Relaxed Solution
The relaxed solution from (11) may overlap, miss vertices, or create a cycle after contraction. LIH therefore uses reduced costs only as guidance and repairs the selection into a legal partition. Each candidate column p is assigned a repair score. Let X saving(p) = wv − cp . v∈Sp
This value measures the local time saved by executing the vertices of Sp together instead of executing them as singleton batches. Let τ (p) denote the insertion order of column p in the generated pool. The columns are sorted lexicographically by c̄p (λ) , −saving(p), −|Sp |, cp , τ (p) . score(p) = |Sp | The repair first prefers low reduced cost per vertex, then larger singleton savings, larger columns, lower execution cost, and earlier generated columns. The repair scans this ranked list and accepts a column only if two conditions hold. First, all vertices in the column must still be uncovered. Second, adding the column to the already accepted columns, while leaving all remaining uncovered vertices as singleton columns, must keep the contracted directed graph acyclic. The second condition is a look-ahead feasibility test: it prevents the repair from accepting a locally attractive clique that would make the final partition impossible to schedule. If no multi-vertex column can be accepted, LIH inserts the heaviest remaining vertex as a singleton, guaranteeing progress and feasibility. After exact coverage is obtained, LocalRefine tries non-increasing legal vertex migrations among cliques while preserving clique feasibility and contracted acyclicity; repeated partition signatures are rejected to prevent cycling. Algorithm 2 summarizes the routine. D. Complete Procedure, Complexity, and Limitations Algorithm 3 summarizes LIH. The algorithm initializes the singleton partition, builds the pricing-filtered restricted pool, and then sets all main-loop multipliers to zero. Each iteration prices columns, periodically repairs and refines a feasible partition, and updates the multipliers from the coverage violation. The repair interval h, step parameters ρ, ϵ, column-size bound q, pool-generation parameters mmax , Rrg , ξ, ∆, and screening fraction η control the search. Complexity and Limitations We state the time bound in Lemma 1. Let n = |V |, m0 = |P0 | be the preliminary-pool size, m = |P| be the retained working-pool size, md = |A|, and let q be the maximum candidate-column size. The pricing screen gives m ≤ n + ⌈η(m0 − n)⌉. Let T be the number of Lagrangian iterations, h the repair interval, rrep = O(T /h) the number of repair calls, b the repair scan width, c ≤ n the number of cliques in the current partition, and L the number of localrefinement passes after one repair.
7
Algorithm 3: Lagrangian-based Iterative Heuristic (LIH) for SPG clique partitioning.
Algorithm 2: LocalRefine(G, w, C). Input: SPG G = (V, E, A), vertex weights w, current clique partition C; 2 Output: A refined legal clique partition; 3 record the current partition signature as visited; 4 while a legal non-increasing migration is found do 5 process source cliques in ascending order of c(C); 6 process target cliques in descending order of c(C); 7 process vertices inside each source clique in descending order of wv ; 8 for each candidate move x : Cs → Ct do 9 Cs′ ← Cs \ {x}, Ct′ ← Ct ∪ {x}; 10 let C ′ be the partition after replacing Cs , Ct by Cs′ , Ct′ and removing empty cliques; 11 if Ct′ is a feasible clique, G/C ′ is acyclic, c(Cs′ ) + c(Ct′ ) ≤ c(Cs ) + c(Ct ), and C ′ has not been visited then 12 accept the move and record the new signature; 13 restart the search from the updated partition; 1
Input: SPG G = (V, E, A), vertex weights w, iteration limit T , repair interval h, step parameters ρ, ϵ, column-size bound q, pool cap mmax , random-greedy rounds Rrg , seed ξ, screening fraction η, optional deadline ∆; best 2 Output: A legal clique partition C ; 0 3 C ← {{v} : v ∈ V }; P 4 UB ← C∈C 0 c(C); best 5 C ← C0; 6 Psg ← {{v} : v ∈ V }; 7 P0 ← RandomGreedyColumns(G, w, Psg , q, mmax , Rrg , ξ, ∆); 8 run one warm-up pricing iteration on P0 and rank P0 \ Psg by c̄p (λw )/|Sp |; 9 P ← Psg ∪ Topη (P0 \ Psg ); 10 λv ← 0, for all v ∈ V ; 11 for t = 1, . . . , T do 12 Compute c̄p (λ) for all p ∈ P by Eq. (10); 13 P − ← {p ∈ P : c̄p (λ) < 0}; 14 Compute ϕ(λ) by Eq. (12); 15 if t = 1, or t = T , or t mod h = 0, or P − = ∅ 14 return C; then 16 Cb ← Repair(P, c̄(λ)); b 17 Cb ← LocalRefine(G, w, C); Lemma 1. Under the above notation, Algorithm 3 runs in P 18 if Cb is legal and C∈Cb c(C) < U B then O Rrg nq + m0 (q 2 + q + log m0 ) + T (mq + n) b 19 C best ←P C; + rrep mq log m + nb(q + n + md ) 20 U B ← C∈Cb c(C); P + Lc2 q(q + n + md ) . 21 hv ← p∈P − avp , for all v ∈ V ; gv ← hv − 1, for all v ∈ V ; Since c ≤ n, the refinement term is O(Ln2 q(q + n + md )) in 22 23 if ∥g∥22 = 0 then the worst case. 24 break; Proof. Candidate generation scans Rrg randomized vertex Compute αt by Eq. (13) or Eq. (14); orders while growing cliques of size at most q, and checking, 25 26 λv ← Π[−M,M ] (λv + αt gv ), for all v ∈ V ; recording, pricing, and ranking at most m0 columns gives 2 O(Rrg nq + m0 (q + q + log m0 )). Each Lagrangian iteration 27 return C best ; evaluates reduced costs and relaxed coverage counts over the retained pool, which costs O(mq + n). A repair call ranks retained columns, performs at most n insertions, and scans up Empirically, retaining all singleton columns and the top 5% to b candidates per insertion, giving O(mq log m + nb(q + n + of non-singleton columns provides a compact pool that is md )). Local refinement checks source–target clique pairs and sufficient for near-optimal solutions in the tested instances. legal vertex moves for L passes, giving O(Lc2 q(q + n + md )). Multiplying the repair and refinement costs by rrep yields the IV. E VALUATION stated bound. This section evaluates MPE on randomly generated seriesThe lemma shows the intended design trade-off: pricing over parallel task graphs. We compare solution quality and runtime the bounded retained pool is polynomial and relatively cheap, under varying graph sizes, compatibility densities, precedence while repair and refinement dominate because they repeatedly ratios, and task-weight distributions using three methods. check contracted-graph feasibility. • Weighted BB-MGC. An exact branch-and-bound baseline The quality of LIH depends on the restricted candidate adapted from the mixed graph coloring framework in [19]. pool. If a useful clique is never generated or is removed Because mixed graph coloring is equivalent to our cliqueby screening, the Lagrangian selection step cannot choose partitioning formulation after complementing the compatiit. This is the central trade-off of the method: restricting P bility edge set, this method provides the optimal weighted greatly reduces the search complexity, while random greedy makespan when it finishes within the time limit. construction and the warm-up pricing screen aim to preserve • Randomized Greedy (RG). A randomized constructive the columns that are most valuable for parallel execution. baseline that repeatedly scans a randomized topological 1
8
order and inserts each vertex into one feasible existing batch chosen from a small ranked candidate list. • LIH. The proposed Lagrangian-based Iterative Heuristic in Section III and Algorithm 3. LIH builds a preliminary candidate pool, retains all singleton columns and the top 5% of non-singleton columns after warm-up pricing, and then repairs the priced relaxed solution into a legal clique partition. All methods are implemented in C++ and compiled with G++ 11.2 using the -O3 option. The experiments are run on a computer equipped with an AMD Ryzen 7 8745HS processor at 3.80 GHz and 32 GB RAM. Each run is terminated if it does not finish within 1800 seconds. A. Baselines and Experimental Setup The weighted BB-MGC baseline uses the mixed graph coloring view. In MPE, E denotes compatibility, whereas in mixed graph coloring undirected edges denote conflicts. We therefore construct Gc = (V, E, A), V
where E = 2 \ E. A color class in Gc then corresponds to a compatible batch in the original MPE instance. The branch-and-bound framework in [19] is unit-time; we keep its exact coloring search but replace the unit colorclass cost by c(C) = maxv∈C wv . The feasible coloring space is unchanged, so the adapted baseline remains exact for the weighted makespan in (1); pruning and incumbent comparisons are also evaluated with the weighted batch cost. Randomized Greedy Baseline Algorithm 4 gives the randomized greedy baseline. Each round processes vertices in a randomized topological order and inserts the current vertex into a feasible existing batch when possible. Candidate batches are ranked by incremental partition cost, new batch cost, and batch size; RG then samples uniformly from the best K candidates. The method remains purely constructive but can escape some unlucky early insertions. RG and LIH use the same feasibility checks and objective. RG relies on local insertions, whereas LIH uses Lagrangian prices to guide a repaired column selection. Instance Generation Synthetic SPG instances are generated in the mixed-graph form G = (V, E, A). • Vertices and weights. Each instance contains Nv vertices. By default, Nv = 25. Each vertex weight wv is sampled from [5, 95]. We test Uniform, Normal, and Bimodal distributions. The default setting is Normal with µ = 50 and σ = 15. The Bimodal setting uses two modes with µ1 = 20, µ2 = 80, and σ = 5. • Compatibility and precedence. We first sample Na = ⌊DNv (Nv − 1)/2⌋ unordered vertex pairs, where D is the graph density and defaults to 30%. A fraction R of these pairs is converted into directed precedence arcs. The default value is R = 5%. Directed arcs are oriented according to a
Algorithm 4: Randomized Greedy Clique Partitioning (RG). 1 Input: SPG G = (V, E, A), vertex weights w, round limit R, candidate width K; best 2 Output: A legal clique partition C ; best 3 C ← {{v} : v ∈ V }; 4 for r = 1, . . . , R do 5 draw a randomized topological order π of (V, A); 6 C ← ∅; 7 for each v ∈ π do 8 F ← existing batches in C that can accept v without violating feasibility or contracted-graph acyclicity; 9 if F = ∅ then 10 append the singleton batch {v} to C; else rank C ∈ F by the increase in T (C), by c(C ∪ {v}), and then by |C|; choose one batch uniformly from the first min{K, |F|} ranked candidates; insert v into the chosen batch;
11 12
13
14
if C is legal and T (C) < T (C best ) then C best ← C;
15 16
return C best ;
17
TABLE II D EFAULT PARAMETERS FOR RANDOM INSTANCE GENERATION . Parameter
Default value
Number of vertices Nv Graph density D Directed-edge ratio R Weight range Weight distribution Instances per setting Time limit
25 30% 5% [5, 95] Normal, µ = 50, σ = 15 200 1800 seconds
TABLE III E XPERIMENT GROUPS . Group
Varied parameter
Candidate values
G1 G2 G3 G4
Number of vertices Nv Graph density D Directed-edge ratio R Weight distribution
5, 10, 15, 20, 25, 30, 35 5%, 10%, . . . , 50% 0%, 5%, 10%, 15%, 20% Uniform, Normal, Bimodal
random topological order to avoid directed cycles. The remaining unordered pairs are inserted into E as compatibility edges. Instances that violate the required acyclicity or SPG structure are regenerated. Table II lists the defaults; each experiment group varies one parameter at a time. Evaluation Metrics For each instance, we record the makespan T (C) in (1). When BB-MGC finishes within the time limit, we report the
9
TABLE IV OVERALL COMPARISON ACROSS ALL COMPARABLE INSTANCES . Method
Opt. prob.
Avg. gap
Median gap
Avg. time
RG BB-MGC LIH
41.16% 100.00% 91.25%
2.16% 0.00% 0.073%
0.87% 0.00% 0.00%
13.75 ms 22.83 s 18.19 ms
TABLE V S OLUTION QUALITY AS THE NUMBER OF VERTICES VARIES . Nv
Comp.
RG opt.
LIH opt.
RG gap
LIH gap
5 10 15 20 25 30 35
200 200 200 200 200 200 183
100.0% 100.0% 93.0% 58.0% 27.0% 11.0% 1.1%
100.0% 100.0% 99.0% 98.0% 91.5% 84.0% 74.3%
0.00% 0.00% 0.28% 1.21% 2.41% 3.51% 5.96%
0.00% 0.00% 0.026% 0.019% 0.056% 0.160% 0.198%
comparisons. The average RG-to-LIH gap increases from 9.70% at Nv = 50 to 15.91% at Nv = 100, and LIH’s average compression exceeds RG by 3.39–4.98 percentage points. This supports the exact-reference trend: Lagrangian pricing becomes more valuable as the clique-combination space grows. C. Sensitivity to Graph and Weight Parameters Effect of Graph Density Figure 6 reports the effect of compatibility density. As D increases from 5% to 50%, the exact baseline’s average compression rises from 25.91% to 66.95%, but the grouping decision also becomes harder. RG’s optimal probability drops from 96.0% to 12.0%, and its average gap grows from 0.04% to 4.15%. LIH is less sensitive: its optimal probability stays between 79.0% and 100.0%, and its average gap never exceeds 0.21%.
relative gap of RG and LIH: TM (G) − TBB (G) Gap(M ) = , TBB (G)
Effect of Directed-Edge Ratio M ∈ {RG, LIH},
where TBB (G) is the optimal weighted BB-MGC makespan. We also report optimal probability and the compression ratio P wv − T (C) P Comp. = v∈V . v∈V wv Runtime is measured as wall-clock time. Instances where BBMGC times out are excluded from gap and optimal-probability statistics. B. Overall Comparison and Node Scaling Table IV summarizes all instances with an exact reference. BB-MGC certifies the optimum but requires 22.83 s on average. RG is much faster at 13.75 ms, but matches the optimum in only 41.16% of the instances and has an average gap of 2.16%. LIH remains close to RG in runtime (18.19 ms) while reaching 91.25% optimal probability and an average gap of only 0.073%. When LIH is not optimal, its median positive gap is 0.56% and its 95th percentile positive gap is 2.32%. Effect of the Number of Vertices Table V and Fig. 4 show the node-scaling trend. The “Comp.” column gives the number of instances with a certified BB-MGC reference; at Nv = 35, 17 of 200 BB-MGC runs time out. RG’s optimal probability falls from 100.0% at Nv = 10 to 1.1% at Nv = 35, while LIH still reaches 74.3% with an average gap below 0.2%. BB-MGC runtime grows to 638.21 s at Nv = 35; RG and LIH remain in the millisecond range, with averages of 27.39 ms and 46.65 ms. Large-Node Comparison with Randomized Greedy For larger instances, where BB-MGC is impractical, we compare LIH directly with RG for Nv = 50, 60, . . . , 100, using 200 instances per setting under the default D = 30%, R = 5%, and Normal-weight configuration. Figure 5 shows that LIH obtains a smaller makespan in all 1200 pairwise
Figure 7 isolates precedence constraints. As R increases from 0% to 20%, average exact compression decreases from 58.29% to 52.12%, while BB-MGC runtime falls from 4.44 s to 0.20 s because ordering constraints reduce the coloring search space. RG’s optimal probability decreases from 37.0% to 11.5%, with its average gap rising from 2.03% to 3.50%. LIH maintains 81.0%–92.0% optimal probability and keeps the average gap below 0.17%. Effect of Weight Distribution Figure 8 compares Uniform, Normal, and Bimodal weights. RG stays fast but its quality varies: the average gap is 1.06%, 2.41%, and 1.53%, respectively. LIH is more stable, with optimal probabilities of 94.5%, 91.5%, and 91.5%, and an average gap no larger than 0.056%. Reduced-cost pricing therefore captures weighted savings more reliably than local insertion alone. D. Discussion Overall, BB-MGC is useful for certification but becomes expensive as the coloring search space expands. RG is lightweight, yet its local insertion decisions degrade with graph size, density, and precedence complexity. LIH adds Lagrangian pricing before feasibility repair, giving high optimal probability, very small gaps, and millisecond-level runtime in the exact-reference settings. On 50–100-node instances, LIH also consistently improves over RG in makespan and compression, supporting its use for static MPE batching when solution quality matters. V. C ASE S TUDY: F ROM PLC L ADDER L OGIC TO MPE This section reports an end-to-end case study that maps PLC ladder programs to the proposed MPE model, generates staged Verilog, and simulates the resulting HDL to measure controlcycle latency.
10
BB-MGC
60 40 20 0
LIH
7
10
6
6
10
5
10
4
10
3
10
2
10
1
10
0
Average runtime (ms)
80
Average gap (%)
Optimal probability (%)
100
RG
5 4 3 2 1
5
10
15
20
25
30
35
0
5
10
15
Nv
20
25
30
35
10
−1
10
−2
5
10
15
Nv
20
25
30
35
Nv
Fig. 4. Evaluation results for different numbers of vertices with configuration: D = 30%, R = 5%, and Normal weights (µ = 50, σ = 15).
RG-vs-LIH makespan gap (%)
Pairwise Makespan Gap Between RG and LIH Mean gap 20 15 10 5 0 50
60
70
Nv
80
90
100
Fig. 5. Pairwise makespan gap between RG and LIH on larger random instances. The gap is computed as 100(TRG − TLIH )/TLIH , so positive values indicate that LIH obtains a smaller makespan.
A. PLC Ladder Programs and Dependencies Programmable Logic Controllers (PLCs) are widely used in industrial automation and embedded control, where deterministic scan behavior is essential. In each scan, the controller samples inputs, evaluates the ladder program, and updates outputs. Ladder Diagram (LD) represents this logic as rungs composed of contacts and coils: normally open contacts read a signal directly, normally closed contacts read its complement, and coils update memory variables or physical outputs. During rung-by-rung execution, later rungs may observe values produced by earlier rungs in the same scan. For rung Ri , let Read(Ri ) and Write(Ri ) denote the variables it reads and writes. If Write(Ri )∩Read(Rj ) ̸= ∅, then Rj depends on Ri . Multiple writes to the same coil also preserve scan order. Interlocking-signal conflicts, such as complementary NO/NC reads of the same input or mutually exclusive control actions, are treated as compatibility constraints even when they do not form direct data dependencies. Thus, ladder programs contain both local serial chains and independent branches. MPE exposes the legal withinscan parallelism without changing the observable PLC scan semantics. B. SPG Modeling of PLC Ladder Logic We model a ladder program by constructing the mixed graph G = (V, E, A) and the weight vector w used in Section II.
The construction has four steps. 1) Task extraction. Each rung, or each basic logic block inside a large rung, becomes a task vertex v ∈ V . The vertex weight wv is the estimated execution delay of that rung or logic block. 2) Precedence extraction. If a value written by Ri is read by Rj , or if two writes must preserve scan order, we add a directed arc (Ri , Rj ) ∈ A. The reachability relation in (V, A) is later used to forbid batching two rungs that are connected by a direct or transitive dependence. 3) Compatibility extraction. Two vertices are connected by an undirected edge in E only when they have no precedence-path conflict, no interlocking-signal conflict, and no platform-specific conflict such as exclusive I/O access or a shared hardware resource that cannot be duplicated. 4) Batch optimization. The resulting graph is solved as an MPE instance. A selected clique represents one legal parallel execution batch, and the contracted graph gives the order in which batches are issued. The implemented front end supports compact ladder descriptions and PLCOpen-style XML programs [20]. For XML input, each program POU is converted into one SPG: coils or outVariable elements become vertices, upstream contacts provide read sets, scan-order write/read relations become directed arcs, and function blocks become weighted computation dependencies or HDL module instances. Table VI gives a representative fragment. R1 writes C1 , which is read by R2 and R3 , so arcs (R1 , R2 ) and (R1 , R3 ) are added. R4 and R5 read I2 through complementary contacts, so their compatibility edge is omitted. The mapping is shown in Fig. 9. Assume the rung weights are (wR1 , wR2 , wR3 , wR4 , wR5 ) = (4, 6, 5, 3, 4). Serial execution has makespan 4+6+5+3+4 = 22. Applying LIH to this graph returns the following legal staged batching plan: C = {R1 , R4 }, {R2 , R3 , R5 } .
11
BB-MGC
60 40
5
10
4
4
10
3
10
2
10
1
10
0
3 2 1
20 0
LIH
Average runtime (ms)
80
Average gap (%)
Optimal probability (%)
100
RG
5
0
10 15 20 25 30 35 40 45 50
5
Graph density D (%)
10 15 20 25 30 35 40 45 50
10
−1
10
−2
5
10 15 20 25 30 35 40 45 50
Graph density D (%)
Graph density D (%)
Fig. 6. Evaluation results for different graph densities with configuration: Nv = 25, R = 5%, and Normal weights (µ = 50, σ = 15). BB-MGC
60 40
Average runtime (ms)
80
3
2
1
20 0
LIH
4
Average gap (%)
Optimal probability (%)
100
RG
0
5
10
15
0
20
0
Directed-edge ratio R (%)
5
10
15
20
10
3
10
2
10
1
10
0
10
−1
10
−2
0
Directed-edge ratio R (%)
5
10
15
20
Directed-edge ratio R (%)
Fig. 7. Evaluation results for different directed-edge ratios with configuration: Nv = 25, D = 30%, and Normal weights (µ = 50, σ = 15). BB-MGC
60 40
Average runtime (ms)
2.0
80
Average gap (%)
Optimal probability (%)
LIH
2.5
100
1.5 1.0 0.5
20 0
RG
Uniform
Normal
Bimodal
0.0
Weight distribution
Uniform
Normal
Bimodal
10
3
10
2
10
1
10
0
10
−1
10
−2
Uniform
Weight distribution
Normal
Bimodal
Weight distribution
Fig. 8. Evaluation results for different weight distributions with configuration: Nv = 25, D = 30%, and R = 5%.
The two stages preserve the dependencies from R1 to R2 and R3 and separate the interlocking pair R4 , R5 . Under the staged batching semantics in Section II, the makespan is
T (C) = max{4, 3} + max{6, 5, 4} = 10.
The example illustrates the weighted clique-partitioning objective: each batch is a feasible clique, and total time sums the slowest task in each batch.
C. FPGA-Oriented Parallel Realization After LIH produces a legal batching plan, each batch is emitted as one FPGA execution stage. Contacts become signal reads or negations, LD operations become combinational logic or function-block instances, and coils are mapped to intermediate or output registers according to scan semantics. The generated Verilog module uses a clocked start/done interface. At the start of a scan, physical inputs are sampled into input-image registers; a finite-state controller then issues the MPE stages in a topological order of the contracted graph.
12
TABLE VI E XAMPLE MAPPING FROM LADDER RUNGS TO MPE CONSTRAINTS . Rung
Read variables
Write variables
Graph constraint
R1 R2 R3 R4 R5
I1 (NO) C1 , I4 (NO) C1 , I3 (NO) I2 (NC) I2 (NO)
C1 M1 M2 C2 M3
Source rung Arc (R1 , R2 ) Arc (R1 , R3 ) Incompatible with R5 Incompatible with R4
All rungs in the current clique are evaluated in parallel, and their results are registered before the next stage. This preserves the PLC input/output boundary while extracting parallelism inside the execution phase.
(a) Ladder-program fragment.
D. Benchmark and Simulation Results The evaluation uses six compact ladder kernels and 30 legitimate PLCOpen XML programs from the PLC-LD benchmark collection [20]2 . The compact kernels cover representative dependency patterns; the XML programs test the full parsing, scheduling, HDL generation, and simulation pipeline. Table VII gives the per-program comparison. Across the six compact ladder kernels, MPE reduces weighted makespan by 42.12% on average; PID-bank and interlock gain most from compatible branches, while sequence control is limited by longer scan-order chains. For the PLCOpen XML benchmarks, the pipeline generated one SPG, one LIH schedule, and one Verilog module per program. All 30 generated modules compiled with the common HDL library and completed ModelSim simulation. The measured controller latency falls from 4.27 PLC scan cycles to 2.57 HDL cycles on average, giving a 1.642× cycle speedup and a 38.54% cycle reduction. In the weighted MPE metric, the same benchmarks achieve 2.399× average speedup, or a 58.10% staged-makespan reduction. Thus, the selected cliques are not only scheduling abstractions; they translate into executable HDL stages that preserve PLC scan semantics. VI. R ELATED W ORK This section follows the same progression as the paper. We first review task-graph and series-parallel scheduling models related to the MPE formulation, then discuss mixed graph coloring and clique partitioning, followed by column models and Lagrangian relaxation. We finally relate the resulting batching model to FPGA-based embedded control.
(b) Corresponding SPG. Fig. 9. Case-study mapping from a ladder fragment to the corresponding SPG. In Fig. 9b, gray edges are compatibility edges, blue arrows are precedence arcs, and the dashed red segment marks the omitted compatibility edge caused by an interlocking-signal conflict.
heterogeneous platforms [24], typed DAG tasks on heterogeneous multicores [25], and energy-efficient scheduling on heterogeneous embedded platforms [26]. These studies emphasize resource assignment and schedule construction on specified heterogeneous resources, whereas MPE abstracts a sufficiently provisioned FPGA stage and asks which compatible tasks can be batched without violating precedence-induced acyclicity. Series-parallel graphs provide additional structure. Their recognition and decomposition are well studied [27], and scheduling methods have exploited this structure for processorconstrained approximation and static scheduling [2], [28]. In contrast, MPE forms parallel batches under abundant hardware parallelism, with feasibility defined by both precedence and compatibility plus acyclicity after contraction.
A. Task-Graph and Series-Parallel Scheduling Precedence-constrained task-graph scheduling is NP-hard in general [15]. Classical heterogeneous DAG schedulers such as HEFT [21] and PEFT [22] map and order tasks on a fixed processor set while respecting precedence and communication costs. Recent work has extended this line to FPGA-based heterogeneous real-time systems [23], preloaded shared-bus 2 https://github.com/UniboSecurityResearch/PLC-LD-dataset
B. Mixed Graph Coloring and Clique Partitioning The MPE formulation is closely related to mixed graph coloring and clique partitioning. A mixed graph contains both undirected edges and directed arcs, and mixed graph coloring uses undirected edges to encode conflicts and directed arcs to encode ordering constraints [29]. This viewpoint is widely used in scheduling models based on disjunctive or
13
TABLE VII P ER - PROGRAM COMPARISON OF ORIGINAL PLC SCAN AND PARALLELIZED HDL. C- SPD . AND W- SPD . DENOTE CYCLE SPEEDUP AND WEIGHTED - MAKESPAN SPEEDUP, RESPECTIVELY. XML HDL CYCLES ARE MEASURED IN M ODEL S IM , AND COMPACT- KERNEL HDL CYCLES ARE DERIVED FROM THE SAME GENERATED STAGE CONTROLLER . Benchmark
Graph
Cycles
Makespan
|V |
|A|
|E|
PLC
HDL
C-spd.
Ts
Tp
W-spd.
alarm/fault interlock motor chain sensor vote pid bank sequence
10 5 6 7 7 8
10 2 4 6 6 7
11 7 9 4 12 9
10 5 6 7 7 8
6 3 4 5 4 6
1.67 1.67 1.50 1.40 1.75 1.33
31 22 20 24 38 24
18 10 12 16 16 18
1.72 2.20 1.67 1.50 2.38 1.33
lassignment lassignment1 lexit lstart cycle lstart cycle1 lstart eq lstart le lstart le1 lstart lt lstart lt1 lstop eq lstop eq1 lstop ge lstop ge1 lstop gt lstop gt1 lsub function lsub function1 lsub function2 lsub function3 lsubstitution coil lsubstitution coil1 lsubstitution start lsubstitution start1 lsubstitution stop lsubstitution stop1 lvalue filtering lvalue filtering1 lvalves handler lvalves handler1
5 3 7 5 3 5 5 3 3 3 5 3 5 3 5 3 6 6 6 4 5 3 5 3 5 3 5 3 5 3
2 0 6 2 0 2 2 0 0 0 2 0 2 0 2 0 2 2 2 0 2 0 2 0 2 0 2 0 2 0
8 3 15 8 3 8 8 3 3 3 8 3 8 3 8 3 13 13 13 6 8 3 8 3 8 3 8 3 8 3
5 3 7 5 3 5 5 3 3 3 5 3 5 3 5 3 6 6 6 4 5 3 5 3 5 3 5 3 5 3
3 2 4 3 2 3 3 2 2 2 3 2 3 2 3 2 3 3 3 2 3 2 3 2 3 2 3 2 3 2
1.67 1.50 1.75 1.67 1.50 1.67 1.67 1.50 1.50 1.50 1.67 1.50 1.67 1.50 1.67 1.50 2.00 2.00 2.00 2.00 1.67 1.50 1.67 1.50 1.67 1.50 1.67 1.50 1.67 1.50
46 32 62 58 44 49 49 35 35 25 49 35 49 35 49 35 51 51 51 37 52 38 51 37 51 37 62 48 46 32
21 14 29 27 20 21 21 14 14 9 21 14 21 14 21 14 21 21 21 14 21 14 21 14 21 14 29 22 21 14
2.19 2.29 2.14 2.15 2.20 2.33 2.33 2.50 2.50 2.78 2.33 2.50 2.33 2.50 2.33 2.50 2.43 2.43 2.43 2.64 2.48 2.71 2.43 2.64 2.43 2.64 2.14 2.18 2.19 2.29
mixed graphs. Kouider and Ait Haddadene [19] proposed a biobjective branch-and-bound algorithm for unit-time job shop scheduling through mixed graph coloring. We use a weighted adaptation of this exact mixed-coloring framework as the BBMGC baseline in the experiments. Our formulation is related but not identical. In MPE, undirected edges denote compatibility, so the mixed-coloring instance is obtained by complementing the edge set. The objective is also weighted: a batch costs the maximum execution time of its tasks, matching FPGA-style concurrent execution. This gives an exact BB-MGC baseline for small instances, but its branch-and-bound search becomes expensive as feasible color classes grow. C. Column Models and Lagrangian Relaxation The exact MPE formulation can be viewed as a setpartitioning model over all feasible cliques. Such columnbased formulations are common in large-scale combinatorial optimization, but the number of columns can be exponential. Branch-and-price methods address this difficulty by solving a restricted master problem and generating useful columns through reduced costs [30]. Lagrangian relaxation provides another classical way to handle hard coupling constraints by moving them into the objective with multipliers [17], [18].
LIH follows this philosophy but targets MPE. It constructs a pricing-filtered pool of SPG-aware cliques, uses Lagrangian multipliers as vertex prices, and repairs the relaxed selection into an acyclic clique partition. This retains a global pricing signal without the cost of full branch-and-price. D. FPGA-Based Embedded Control FPGAs are widely used in industrial and safety-critical control because they provide deterministic timing, fine-grained parallelism, and isolation. Prior work surveys FPGA design for industrial control [8] and fault-tolerant SRAM-based FPGA systems [14]. Recent studies also accelerate PLC and embedded-control workloads, such as multi-PID FPGA implementations for reducing PLC scan time [5], deterministic parallelization of legacy control code [6], and shared-resource effects on real-time microcontrollers [7]. These works motivate hardware acceleration, while our focus is the graph-level batching problem that decides which compatible tasks can share an FPGA execution stage. Work on heterogeneous real-time FPGA systems, such as MESSI [23], and accelerator-scheduling surveys [31] mainly emphasize resource allocation and deadline analysis. We instead study a sufficiently provisioned setting where dependency and compatibility determine the available parallelism.
14
VII. C ONCLUSION This paper studied Maximum Parallel Execution (MPE) for series-parallel task graphs motivated by FPGA acceleration of embedded control programs. We modeled MPE as a weighted clique-partitioning problem: compatible tasks share a parallel batch, and selected batches are issued in a topological order of the contracted precedence graph. The proposed LIH algorithm combines SPG-aware candidate generation, warm-up pricing screening, Lagrangian pricing, feasibility repair, and local refinement. The experiments show that LIH keeps the solution quality close to the exact BB-MGC reference while remaining in the millisecond range. Across comparable instances, LIH matches the optimum in 91.25% of cases with an average gap of 0.073%, whereas the exact baseline becomes costly as the coloring search space grows. On 50–100-node instances, LIH consistently improves over the randomized greedy baseline, indicating that the pricing signal becomes more useful as the grouping space expands. The PLC ladder case study further connects the graph model to HDL generation and cycle-level simulation, showing that selected cliques can be realized as deterministic FPGA stages. Future work will incorporate explicit hardware resources, communication overheads, and more detailed FPGA placement or safety-partitioning requirements. R EFERENCES [1] J. Valdes, R. E. Tarjan, and E. L. Lawler, “The recognition of series parallel digraphs,” in Proceedings of the eleventh annual ACM symposium on Theory of computing, 1979, pp. 1–12. [2] J. Keller and R. Gerhards, “Peelsched: A simple and parallel scheduling algorithm for static taskgraphs,” PARS: parallel-algorithmen,rechnerstrukturen und-systemsoftware, vol. 28, no. 1, pp. 100–109, 2011. [3] J. Nilsson, “Real-time control systems with delays,” PhD Thesis TFRT1049, 1998. [4] D. Henriksson and A. Cervin, “Optimal on-line sampling period assignment for real-time control tasks based on plant state information,” in Proceedings of the 44th IEEE Conference on Decision and Control. IEEE, 2005, pp. 4469–4474. [5] G. Dhanabalan, S. Tamil Selvi, and M. Mahdal, “Scan time reduction of plcs by dedicated parallel-execution multiple pid controllers using an fpga,” Sensors, vol. 22, no. 12, p. 4584, 2022. [6] J. Hennig, H. von Hasseln, H. Mohammad, S. Resmerita, S. Lukesch, and A. Naderlinger, “Towards parallelizing legacy embedded control software using the let programming paradigm,” in 2016 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). IEEE Computer Soc., 2016, pp. 1–1. [7] D. Oliveira, W. Chen, S. Pinto, and R. Mancuso, “Shared resource contention in mcus: A reality check and the quest for timeliness,” in 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2024, pp. 5–1. [8] E. Monmasson and M. N. Cirstea, “Fpga design methodology for industrial control systems—a review,” IEEE transactions on industrial electronics, vol. 54, no. 4, pp. 1824–1842, 2007. [9] D. Sankar, L. Syamala, B. Chembathu Ayyappan, and M. Kallarackal, “Fpga-based cost-effective and resource optimized solution of predictive direct current control for power converters,” Energies, vol. 14, no. 22, p. 7669, 2021. [10] S. Lucia, D. Navarro, O. Lucia, P. Zometa, and R. Findeisen, “Optimized fpga implementation of model predictive control for embedded systems using high-level synthesis tool,” IEEE transactions on industrial informatics, vol. 14, no. 1, pp. 137–145, 2017. [11] M. Chmiel, R. Czerwinski, and A. Malcher, “Fpga implementation of iec 61131-3-based hardware-aided timers for programmable logic controllers,” Electronics, vol. 12, no. 20, p. 4255, 2023.
[12] S. Mittal, “A survey of fpga-based accelerators for convolutional neural networks,” Neural computing and applications, vol. 32, no. 4, pp. 1109– 1139, 2020. [13] E. Nurvitadhi, G. Venkatesh, J. Sim, D. Marr, R. Huang, J. Ong Gee Hock, Y. T. Liew, K. Srivatsan, D. Moss, S. Subhaschandra et al., “Can fpgas beat gpus in accelerating next-generation deep neural networks?” in Proceedings of the 2017 ACM/SIGDA international symposium on field-programmable gate arrays, 2017, pp. 5–14. [14] C. Bernardeschi, L. Cassano, and A. Domenici, “Sram-based fpga systems for safety-critical applications: A survey on design standards and proposed methodologies,” Journal of Computer Science and Technology, vol. 30, no. 2, pp. 373–390, 2015. [15] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. [16] M. Fryer et al., “Messi: Task mapping and scheduling strategy for fpga-based heterogeneous real-time systems,” IEEE Access, vol. 11, pp. 128 632–128 649, 2023. [17] A. M. Geoffrion, “Lagrangean relaxation for integer programming,” Mathematical Programming Study, vol. 2, pp. 82–114, 1974. [18] M. L. Fisher, “The lagrangian relaxation method for solving integer programming problems,” Management science, vol. 27, no. 1, pp. 1–18, 1981. [19] A. Kouider and H. Ait Haddadène, “A bi-objective branch-and-bound algorithm for the unit-time job shop scheduling: A mixed graph coloring approach,” Computers & operations research, vol. 132, p. 105319, 2021. [20] A. Iacobelli, L. Rinieri, A. Melis, A. Al Sadi, M. Prandini, and F. Callegati, “Detection of ladder logic bombs in plc control programs: an architecture based on formal verification,” in 2024 IEEE 7th International Conference on Industrial Cyber-Physical Systems (ICPS). IEEE, 2024, pp. 1–7. [21] H. Topcuoglu, S. Hariri, and M.-Y. Wu, “Performance-effective and low-complexity task scheduling for heterogeneous computing,” IEEE transactions on parallel and distributed systems, vol. 13, no. 3, pp. 260– 274, 2002. [22] H. Arabnejad and J. G. Barbosa, “List scheduling algorithm for heterogeneous systems by an optimistic cost table,” IEEE transactions on parallel and distributed systems, vol. 25, no. 3, pp. 682–694, 2013. [23] S. Ahmadi-Pour, S. Saha, K. McDonald-Maier, and R. Drechsler, “Messi: Task mapping and scheduling strategy for fpga-based heterogeneous real-time systems,” ACM Transactions on Design Automation of Electronic Systems, vol. 30, no. 3, pp. 1–29, 2025. [24] C. Chaudhary, R. Devaraj, and A. Sarkar, “Scheduling task graph applications on preloaded shared-bus based heterogeneous platforms,” ACM Transactions on Design Automation of Electronic Systems, vol. 31, no. 2, pp. 1–29, 2025. [25] Y. Wu, Y. Ma, M. Xie, and W. Zhang, “Partitioned scheduling and analysis for a typed dag task on heterogeneous multi-cores,” ACM Transactions on Architecture and Code Optimization, vol. 22, no. 3, pp. 1–24, 2025. [26] B. Hu, X. Yang, and M. Zhao, “Online energy-efficient scheduling of dag tasks on heterogeneous embedded platforms,” Journal of Systems Architecture, vol. 140, p. 102894, 2023. [27] J. Valdes, R. E. Tarjan, and E. L. Lawler, “The recognition of series parallel digraphs,” SIAM Journal on Computing, vol. 11, no. 2, pp. 298– 313, 1982. [28] K. Elbassioni, D. Regnault, and A. Srivastav, “Approximation algorithms for scheduling on series-parallel graphs,” in Proceedings of the International Symposium on Algorithms and Computation (ISAAC), 2009, pp. 97–106. [29] P. Hansen, J. Kuplinsky, and D. de Werra, “Mixed graph colorings,” Mathematical Methods of Operations Research, vol. 45, no. 1, pp. 145– 160, 1997. [30] C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W. Savelsbergh, and P. H. Vance, “Branch-and-price: Column generation for solving huge integer programs,” Operations research, vol. 46, no. 3, pp. 316–329, 1998. [31] A. Zou, Y. Xu, Y. Ni, J. Chen, Y. Ma, J. Li, C. Gill, X. Zhang, and Y. Jin, “A survey of real-time scheduling on accelerator-based heterogeneous architecture for time critical applications,” 2025, arXiv:2505.11970.