Efficient Parallelized Simulation of Cyber-Physical Systems
Authors: Bas van der Heijden
Laura Ferranti
Jens Kober
Robert Babuska
Venue: Accepted by TMLR ()

Abstract: Advancements in accelerated physics simulations have greatly reduced training times for reinforcement learning policies, yet the conventional step-by-step agent-simulator interaction undermines simulation accuracy. In the real-world, interactions are asynchronous, with sensing, acting and processing happening simultaneously. Failing to capture this widens the sim2real gap and results in suboptimal real-world performance. In this paper, we address the challenges of simulating realistic asynchronicity and delays within parallelized simulations, crucial to bridging the sim2real gap in complex cyber-physical systems. Our approach efficiently parallelizes cyber-physical system simulations on accelerator hardware, including physics, sensors, actuators, processing components and their asynchronous interactions. We extend existing accelerated physics simulations with latency simulation capabilities by constructing a `supergraph' that encodes all data dependencies across parallelized simulation steps, ensuring accurate simulation. By finding the smallest supergraph, we minimize redundant computation. We validate our approach on two real-world systems and perform an extensive ablation, demonstrating superior performance compared to baseline methods.

Published in Transactions on Machine Learning Research (05/2024)
Efficient Parallelized Simulation of Cyber-Physical Systems
Bas der Heijden
J.hejjdenhhobmune
Cognitive Robotics
Delft University of Technology
Laura Ferranti
Lferronti@tudelf..t
Cognétive Robotics
Delft University of Technology
Jens Kober
j.koberStudelft.tt
Cognitive Robotics
Delft University of Technology
Robert Babuska
r.babukka Studellfkarrddrr......
Cognitive Robotics, Delft University of Technology,
CIRCC, Czech Technical University in Prague
Reviewed on OpenReview: https: // openreview. met/ forum? id= VaKXbCaNoU
Abstract
Advancements in accelerated physics simulations have greatly reduced training times for reinforcement learning policies, yet the conventional step-by-step agent-simulator interac- tion undermines simulation accuracy. In the real world, interactions are asynchronous, with sensing, acting and processing happening simultaneously. Failing to capture this widens the sim2real gap and results suboptimal real-world performance. In this paper, we address the challenges of simulating realistic asynchronicity and delays within parallelized simula- tions, crucial bridging the sim2real gap complex syber-physical systems. Our approach efficiently parallelizes cyber-physical system simulations accelerator hardware, including physics, sensors, actuators, processing components and their asynchronous interactions. We extend existing accelerated physics simulations with latency simulation capabilities by con- structing a 'supergraph" that encodes all data dependencies across parallelized simulation steps, ensuring accurate simulation. By finding the smallest supergraph, we minimize re- dundant computation. We validate our approach on two real-world systems and perform an extensive ablation, demonstrating superior performance compared to baseline methods.
1 Introduction
Physics simulations on accelerator hardware (NVIDIA, 2020; Hu et al., 2020; Freeman et al., 2021; Todorov et al., 2012) have significantly reduced training times for reinforcement learning policies that conform to traditional, scquentially-sttruuuurd agent-simulator intoractions (Rudin et al., 2022). Such interactions lead to clear-cut and predictable execution paths, allowing for efficient parallelization, as shown in Fig. la. However, this sequential approach fails to capture the concurrent and dynamic nature of the real world.
Accounting for latency crucial in the simulation of eyber-physical systems (CPS), which integrate com- putational algorithms with physical processes. In CPS, embedded computers and networks both monitor and control these processes, typically through feedback loops where physical processes impact computations and vice versa via sensors and actuators (Baheti & Gill, 2011). A critical application of CPS is vehicular platooning, involving multiple vehicles that operate in close proximity, coordinating their actions based on shared sensor data in real-time. This coordination is highly sensitive to time delays, making the accurate simulation of these delays critical for developing robust platooning algorithms (Zhao al., 2021).

---

Published in Transactions on Machine Learning Research (05/2024)
Delayed sensor data causes an agent to choose ac- tions based on outdated information. Similarly, slow policy evaluation can unavoidably extend the effect of previous actions beyond their planned du- ration. Moreover, the focus has traditionally been on single agents trained end-to-end (Singh et al., 2019). In practice, however, Al systems deployed in real-world settings often rely on a pipeline of models. Accounting for the latency between these models will become crucial as tasks grow in com- plexity (Nishihara et al., 2017). Finally, physics simulators often bundle physics, sensor, and ac- tuator simulations into a single unit running at single rale. However, in realily, there are vital asynchronous effects within this block that need to be accounted for. Overlooking these asynchronous effects in simulation widens the sim2real gap and can lead to policies that do not perform well in the real world.
Sensor
Actuator Delay
Delay
Agents Action
Agent's state
Sinuiatur's slate
Agent
Observation
Actustor
Agent
Sensoz
Simulator
Physics
.reset()
.stsp()
.ttpp
_5top()
Step()
simulated time (8)
simulated time (s)
(a) Sequential interaction
(b) Asynchronous interaction
Figure Comparative illustration of computation graphs with and without simulated delays. Vertices represent peri- odic computations, and edges represent data dependencies. (a) The absence of delay simulation creates consistent blocks of computation, enabling efficient parallelization across sim- ulation steps yet failing to capture the inherent asynchrony of the real world. (b) While improving simulation fidelity, simulated delays between various components turn every sim- ulation step into a diverse mix of computation, challenging parallelization efficiency.
To represent the asynchronous interactions between components, we advocate the division of the simulator into separate parts. This matches the typical design in robotics, where systems consist of interconnected nodes operating asynchronously at various rates (Quigley et al., 2009). This division enables the creation of computation graphs that accurately represent data flow in real-world siluations, including latency effects. Consequently, each simulation step turns into a diverse mix of computation units from various components that run at different time scales, as illustrated in Fig. 1b. These must be executed in a sequence that respects the data dependencies outlined by the graph's edges. Simulating with these diverse partitions improves accuracy but complicates parallelization (i.e., simulating multiple copies of the simulation parallel), as distinct partitions may need to execute simultaneously across GPU threads, hindering GPU efficiency. Such misalignment can happen with independent episodic resets, often initiated based on variable reset criteria. One parallel simulation might reset because the agent reached its goal, while another continues because the agent is still far away. Diverging execution paths can significantly reduce kernel efficiency (Shibata, 2010). When GPU threads take different paths, they must be serialized, leading to more instructions and reduced performance.
The main contribution of this paper an approach to parallelize cyber-physical system simulations that emulates asynchronicity and delays with minimized computational overhead on accelerator hardware. This allows existing accelerated physics simulations to be extended with efficient latency simulation capabilities. We achieve this by identifying a graph-ideally the smallest one possible-that encodes all the data de- pendencies outlined by every simulation step's edges. This universal graph, referred to as a supergraph, is determined prior to simulation. Sorting the supergraph topologically yields a static execution order for parallel processing of simulation steps without violating data dependencies. By targeting the smallest su- pergraph, we minimize rodundant computation. Finding the smallest supergraph is generally a complex, NP-hard problem (Trimble, 2023); however, our greedy algorithm efficiently approximates this supergraph by leveraging the inherent periodicity in cyber-physical systems.
In sum, we make four key claims: Our approach (i) emulates asynchronicity leading to more accurate simulation, (ii) efficiently handles time-scale differences and asynchronicity, resulting in higher parallelized simulation speeds than baseline approaches, and (iii) scales to complex system topologies. These claims are supported by an experimental evalustion on two real-world robotic systems, followed by a scalability analysis on two sybee-physical system topologies: vehiclo-to-vehicle (V2V) platooning (Zhao et al., 2021) and unmanned aerial vehicle (UAV) swarm control (Asaamoning et al., 2021). An ablation study on the effects of the algorithmic simplifications was also conducted and included an appendix. Finally, motivational video for our approach is included as supplementary material, logether with example source code to efficiently compile parallelized training enviromments with our approach.
2

---

Published in Transactions on Machine Learning Research (05/2024)
2 Preliminaries
Before diving into the details of our approach, we first lay down some basic definitions and notation that will aid in the formalization of our problem and the description of our approach. We consider graphs g = (V, B) consisting of a set of vertices V(g) and a set of directed edges F(g). Edge (u, E F(G) denotes an edge from vertex u to vertex v. The notation [V]) denotes the number of vertices in G. Any subset of vertices V' S (g) induces a unique subgraph g' S G. The difference G2 - 91. where G1 S G2, yields a graph 9 with V(G) = V(G2) \ (((i) and E(G)= F(22) \ F(Gi). The edges that connect 91 and G2 91 are defined as the cut-set C₁2 (91), which is a subset of E(G2). The union of graphs 91 and G2 with respect
set of edges E12 and B(G) E(Gi) U E(G2) U E1s. The addition 91 92, where G1. 92 S 9s, yields a subgraph G12 S G3. by unifying 91 EI S2 where E12 Cg2 (G))nCg, (92). An edge contraction on an edge (u, v) E E(g) yields a new graph g' such that V(g') = V(g) \ {u, u) U {w} and
is denoted as G = Gi UF G2, where V(G)
L
= (E(g) \ {(u, v), ())
U ((w,x) (u, E E(g) or (v,x) E B(G)
U ((r,w)) (z) E E()) or (z,v) B(G))
The ancestors of a vertex Au(u) are all vertices V'(g) S V(g) that can reach u via a directed path in G. The roots of graph 9 are the set of vertices that have incoming edges, formally R(g) {u V(G) Vo V(G), (v, (v, u) & E(g)). Similarly, the leafs of graph 9 are the set of vertices that have no outgoing edges. A Directed Acyclic Gruph (DAG) is directed graph that contains cycles. A lopological sort of a directed acyclic graph G is a linear ordering of its vertices such that for every directed edge (u, v) E E()), vertex u comes before v in the ordering. Multiple topological sorts may exist for a given graph G, and the set of all possible topological sorts is denoted by T(g). labeling function L V + I is a function that assigns a label to each vertex. The set of all vertices with label denoted by Vi(9) and is arranged as a sorted list consistent with a topological sort of G. We denote the set of topological sorts where the final vertex is of label I in G as (G). Formally, this is defined as:
(G) = (T E T(9) [(T, u) 19), u E Vi(9)),
where 1(T, u) gives the position of vertex u in the sorted set T. A matching function fm : V V (True, False) is defined as follows:
True if TT) = M(v),
fulu,
False otherwise.
A mapping between two graphs S. and G2 is a bijective function M ('(Gi) - (G22 where V represent subset of the vertices. Its domain dom(M) (M) is V'GG)) and its range rng(M) is V'(22). Operations like union U, intersection n, and difference ) can be applied to both dom(M) and mg(M)). A mapping M can extend to M' by adding a new vertex pair (u, with M = M U ((u,w)) where u E V(Gi) \ dom(M) and U E VG2) \ rng(MM. A subgraph monomorphism M : V(G) + V'G is a specialized mapping that maps each verlex u to o such that L(u) = L(v) and each edge (u, v) corresponds to an edge (M(,), M()) in G2. If such M exists, G2 is a supergroph of 91 and can be reduced to Gi by removing vertices and edges in G2. The transformed set of edges Exs under the mapping M is defined as follows:
EM(GI) = ((u', v') (u, E E(G1), u' = (u) if dom(M), u' = u otherwise,
J' = M(p) if u E dom(M), e' = e otherwise]
This set includes edges (v/, v/) where w' and o' are either mapped vertices of u and under M if they are in the domain of M, or are u and v themselves otherwise.
3

---

Published in Transactions on Machine Learning Research (05/2024)
3 Our Approach
Physics
Sensor
Agent
Actustor
Asynchronous systems produce non uniform computation graphs due to delays
Consider the set of computation graphs generated by multiple episodes of an asynchronous system, as illustrated in Fig. 2, where vertices of the same color represent the same periodic computation unit, and edges represent data dependencies. These graphs might be partially recorded from real-world exe- cutions or synthetically created to reflect expected computation and communication delays. Variations in these graphs across episodes lead to distinct ex- ecution paths. However, managing these variations with conventional if-clse branching for parallel exc- cution on GPUs is inefficient, as highlighted in (Shi- bata, 2010). Predication (Taylor & Li, 2011) is technique that sidesteps the need for if-else branch- ing by executing all possible paths and masking out the computations that are not needed. This ap- proach, while climinating branching, can be ineffi- cient due to the execution of all vertices in the paths, making it crucial to minimize the number of vertices.
"Supendsor"
Supergraph
Predication Masks
Masked
O
Used
reset()
stap
stepp)
tme
'Wasted compule.
opicode 2
step
sstep()
Sime
opsoble 1
resat
steppC
sttep)
Sme
Figure 2: This figure illustrates our approach to efficiently simulating multi-rale asynchronous systems. Given vari- able delays, computation graphs can differ across episodes (left). We find a supergraph and predication masks, il- lustrated by the grey shaded blocks, for every computa- tion graph that enables parallel execution across partitions (right). This mask, randomized during simulation, allows us to efficiently emulate asynchronicity and time-scale dif- ferences with minimal computational waste.
To achieve this, we introduce an approach to identify a minimum common supergraph (mcs) that is acyclic and encapsulates all potential exccution paths from a collection of computation graphs, optimizing for the fewest vertices (i.e., computational overhead).
Topologically sorting the supergraph yields execution order that, via predication masking, is transformed into a valid order for any given graph, as the supergraph encodes all data dependencies.
In aligning with standard simulator interfaces (Brockman et al., 2016), illustrated in Fig. 1, we first parli- tion these computation graphs into disjoint subgraphs, each corresponding to a simulation step. Crucially, we designate a supervisor node in each partition, a pivotal element that dictates the boundaries of these subgraphs. In the context of reinforcement learning, the supervisor node is akin to the agent, while all other nodes within the partition form the environment, providing observations to and receiving actions from the supervisor node. The supervisor node's operating rate sets the simulation time step, ensuring that each partition accurately reflects a step of the simulation process. We then find a supergraph that accommodates all possible paths in every partition with a minimum number of vertices. This supergraph serves as a tem- plate that can be reduced to match any of the partitions (i.c., simulation steps) by masking (i.c., removing) specific vertices and edges. This setup enables parallel execution of any partilion on accelerated hardware.
3.1 Problem Definition
Consider a set of observed computation graphs denoted by (Go. Gr....>, where each 9, a DAG. For a given supervisor label s, our goal is to partition each Gi into disjoint subgraphs P.,,, Pi...... Each subgraph corresponds to discrete simulation step and contains exactly one leaf vertex labeled as s. The objective is to determine these valid partitions along with the smallest DAG, S, that serves common supergraph for all partitions. Similar to cach partition, a single instance of the designated supervisor vertex in S must be a leaf vertex. Here, 'smallest" is defined by the number of verlices to minimize computational overhead. We aim to find a subgraph monomorphism Mr,- V(P.,) V'(S) for each partition Pt,-- This mapping allows us to reduce S into P., using a predication mask. The predication mask is a binary mask applied to S selectively remove vertices and edges not present in Pt,j Specifically, the mask is false for vertices and edges not in rng(M (M.) and EM,,, (Prs), respectively, and true otherwise.
4

---

Published in Transactions on Machine Learning Research (05/2024)
P.n
Pla
S
pe
U1,
Ag. (M.,2)
a) Process next computation graph starting with current supergraph 5t-1 (lnee 2)
sarilond tre
b) After two partitions, match the next supervisor vertex (lines 5-6)
c) Find the largest match (lines
Pice
PLi
Piaa
So
S
Masked Compuaatin
Sénulaned Fime
Resulting final supergreph after processing
Update s unmatched yellow
6) Backtrack
newlly updated Supergraph
Figure 3: Illustration of the Minimum Common Supergraph Search process (Alg. 1) at a midway point. First, read from left to right, then top to bottom. A partial match is found for u4,, leading to updated & with missing ancestors P and initiating a backtrack to re-evaluate previous partitions.
3.2 Supergraph Search
Our approach, as outlined in Alg, 1 and illustrated in Fig. 3, aims to simultancously achieve three main objectives: identifying the supergraph S, de- termining the partitionings Pt,j. and discovering the associated mappings Mij- For each compu- tation graph Gú, the algorithm iterates until all supervisor vertices are matched, as specified in Line 4. In every iteration, the largest partition p* and its associated mapping M are sought (Line 5- 7), following the method detailed in Alg. and explained later on in Sec. 3.3.
Algorithm 1: Minimum Common Supergraph Search (mes)
Input: Designated supervisor label s
Input: Number steps backtrack 3
Input: set of observed computation graphs (9o. .1.....
Output: A set of partitions (Po.1, P.. Pt.......... ...}
Output: A supergraph S and mapping Mr,, for
partitions P.,j S + Initialize with V(S) = (u[ o) and E(S) 0
2. for G. E (So. (So.9I.....
3 Fu +- Initialize unmatched graph as G.
/+ Until all supervisor vertices natched +/
while (G.G.) * 0 do
We.j Get next supervisor from sorted set (G.)
with index (V.), u))
Depending whether all ancestors are matched, partial
Au Way and its anccstors: Ag, (vx,) (us,]
the algorithm finds either complete match corresponding to the supervisor vertex u. In the case of a complete match, both P and M* are stored (Line 10-13). For partial matches, the algorithm backtracks ilerations to reconsider previously matched partitions (Line 15). In either case, the supergraph & is updated using Eq. (1) to ensure it remains supergraph of its previous version and incorporates all necessary ancestors V(P') for future matches, as follows:
M Get largest map: Alg. with S.
p Partition subgraph: dom(M") V())
P < Missing subgraph: Ag, (14.) V(P*)CCI
10
if V(P) = then
/s All ancestors
matchad */
Mr.j +- Store subgraph monomorphism Af*
P., Store partition p
9. Remove matched partition: G. Pig
14
else
/- Partial natch
Go < Restore 8 partitions Gu Gi with
Gu + P.p-- Pig--41 f... Pa5-1
16
S + Update to S' with missing vertices and edges:
S' = (V= E(S) (P' +P)).
UV()) UN) EM- + +))
(1)
where P C G. More edges in the updated
supergraph S' effectively constrain the number of possible mappings for subsequent partitions by reducing the number of topological sorts available in the supergraph. Conversely, more vertices in S' increase its expressiveness by increasing the number of vertices that can be mapped to vertex in subsequent partitions, but also increase the computational overhcad of the simulation. In the next section, we detail the algorithm for finding the largest malch, Alg. 2, which is a critical component of the supergraph search algorithm. It may only result in mappings M that ensure that collectively contracting all edges (u, v) E E(P*) in Gu will not introduce any cycle in the resulting graph 9/ This constraint critical to ensure that the updatod supergraph S', as governed by equation Eq. (1), remains acyelic. This sets apart from previous work (Bunke et al., 2000; 2003), which do not consider this constraint.
5

---

Published in Transactions on Machine Learning Research (05/2024)
F
Iteration:
P
domi (M)
Unmatched
Matched
Eodidedd hoo search tun
Most matched ancestors
Iteration: ++1 1
For F
P Unmatched
dom()))
Matched
Figure 4: Midway illustration of Line 9-16 in the Largest Match Search (Alg. 2) linked to step (c) in Fig. 3. The / and X symbols indicate whether vertex the candidate front F is matched Line 12. The first iteration yields an empty mapping due to the absence of a yellow vertex in the supergraph. In the second iteration, the vertex is excluded from the front, enabling a large partial match. The search is only displayed for a single topological sort.
3.3 Largest Match Search
Our approach to identifying the largest. valid map- ping M for each supervisor vertex Uz in out- lined in Alg. 2 and illustrated in Fig. Initially, tries match all ancestor vertices in candi- date subgraphs 9 extracted from the unmatched graph Gexel (Line 2). The search is refined by iter- atively excluding ancestors in a breadth-fing -rrrst man- ner from go (Line 8, and 21).
Algorithm 2: Largest Match Search
Input: Designated supervisor label
Input: Supcrgraph S
Input: Unmatched computation graph Gu.
Input: Vertices to be matched A.
Output: Largest mapping M
M <- Initialize an empty mapping
Goxel < Initialize search graph as Gu
while True do
Fexel + Initialize search front as roots R(Gevel)
To this end, a refined search front F is formed for each iteration (Line 4-6, Line 9). The algorithm explores all k-combinations of Foon in descend- ing order of k (Line 6). For cach combination, the largest candidate mapping M is sought by traversing all valid topologies of S, starting from the refined search front fe (Line 7-10). Every time a match is found, the mapping is extended and the search front updated (Line 11-16). Our approach assumes that vertices are stateful, i.e., verticos of similar labels are connected with another, ensuring the uniqueness of the match (Line 12-13). Tf a larger mapping is found, M is updated (Line 17-18). The algorithm halts the search if no larger match can be found (Line 19- 20). To lower computational complexity, we apply crucial greedy approximations in lines and 7, as further motivated in Sec. 3.4.
5
Feon + Determine constrained front: Faxel O Au
6
forall From E k-comb((F (Feen) do // Greedy: one Fes per &
7
forall E (S) do // Gready: only single
8
9 + Remove u E Feon \ Feom from V(Gexe)) Fe Initialize frout: Pexel \\ (Feon') \ Feom)
9
10
M +- Initialize an empty candidate mapping
11
forall E do
if Bu Fc fm(u,v) True then {u E pe fm,(,, = Truc)
M Extend mapping: M ((u, v))
go Remove matched from (())
Update front: F [u] R(7))
17
if [dom{ n Aul > [dom(M") Ayl then /t Store largest napping +/ Smax |uul |Aa V(Goset) (|Feoul |oomll if (|dom{ ( Aul) 2 smax or dommmd = [S] then return M/
18
L M + Mr
21 Gexel + Exclude vertices from search graph:
((Goeet) \ Peon
We may only consider mappings M that ensure that the updated supergraph S' remains acyclic after updating with Eq. (1). To ensure this, we initiate each candidate scarch at the roots of Goxel and S, as specified in Line 4 and 7, adopting a search strategy aligned with the topological sort of S and a breadth-first search of Gexel. This approach guarantees that edges between matched vertices in dom(M"), represented by P", cannot create cycles in S'. For vertices not matched dom(M*) (designated as P*), their positioning is either strictly prior to or following P* in the topological sense, thus also ensuring acyclicity in S'. This strict placement is achieved by initially removing only root vertices from consideration (Line 4) and subsequently

---

Published in Transactions on Machine Learning Research (05/2024)
extending the search frontier solely upon removing a newly found match that subsequently leads to new root vertices (Line 15-16).
3.4 Limitations and Approximations
The efficacy of our approach is contingent on set of assumptions. Firstly, the best performance is achieved when the computation graphs exhibit a recurring topological structure. Secondly, the model assumnes sub- stantial timo-scale differences between what we term the supertisor vertez and other vertices. Finally, approach assumees that vertices are stateful, L.e, vertices of similar labels are connected with one another. These assumptions are particularly well-suited for cyber-physical systems where components are stateful and run at fixed target frequencies, and where the supervisor vertex often takes the form of a slower, learning agent or an outer-loop controller. Morcover, the algorithm assumes that the computation graphs' structure does not depend on the data processed by the vertices. Specifically, we assume delays the system are not function of the internal states, outputs, or incoming inputs.
Identifying the minimal common supergraph is an NP-hard problem (Trimble, 2023). To manage this complexity, we make several approximations to Alg. 2. If all vertices are assumed to be stateful, then the constrained front Feon can contain at most one vertex for each label, i.c. |Fooul = |rng(L)]. Then, the worst-case time complexity for considering all topological sorts of the supergraph S and all combinations of Foon is (())m + [V[!) (Line 6-7 in Alg. 2). We alleviate this by considering only a single topological sort of S and a single combination per combination size k reducing the worst-case time complexity O[Ing(L) + +|++VV)) We have found that these approximations do not significantly impact the resultant supergraph in our evaluations, which computation graphs are processed can affect the resultant supergraph. Similar to Bunke et al. (2003), this has not proven to have a significant impact in our evaluations.
detailed in the ablation study in Appendix B. Tastly, the sequence in
4 Experimental Evaluation
The main focus of this work is an efficient approach to simulate delays parallelized simulation on accelerator hardware. We present our experiments to show the capabilities of our approach and support our key claims that our approach (i) emulates asynchronicity leading more accurate simulation, (ii) efficiently handles time-scale differences and asynchronicity, resulting in higher parallelized simulation speeds than bascline approaches, (iii) scales to complex system topologies. In the remainder of this section, we will use mes to refer to our proposed method.
4.1 Baselines
We outline three baseline methods for our experimental evaluation. The sequential baseline (seq) assumes delays in computation graph processing, illustrating a conventional approach as shown in Fig. 1a. This baseline serves a reference for evaluating the impact of realistic delays in simulations.
We then introduce two baselines that incorporate delays by randomizing predication masks in parallelized simulations, but differ in supergraph construction. Given the absence of existing methods that can handle the DAG constraint and partitioning requirements for our supergraph (as discussed in Sec. 3.3), these baselines represent straightforward strategies for supergraph construction. Both baselines sequentially stack K layers in the supergraph, with each layer containing a vertex for every non-supervisor label and concluding with final layer of a single supervisor vertex. This structure ensures the supergraph is DAG and with its size [S] K x ([rng(L) 1) + 1, thereby ensuring subgraph monomorphisms across partitions with an adequate number of layers. The topological baseline (top) sets K equal to the number of vertices in the largest partition. While this method guarantees a subgraph monomorphism with each partition, it can lead to disproportionately large supergraphs with sparse layer utilization. The generational baseline (gen), on the other hand, sets K as the maximum path distance across partitions. This approach is more space-efficient but also tends to over-include vertices, as it does not account for timo-scale differences between vertices. Consequently, each layer incorporates every vertex label, even those infrequently used.
7

---

Published in Transactions on Machine Learning Research (05/2024)
1e6
Angle sensor 80
seeed (Fps
1000
1000
Dynamics 100 Hz
Only present in simulation
RL agent 20 Hz
cost
cost
500
500
Torque motor
20 Hz
%
20000 40000
steps
environment
5eg mcs
efficiency (%)
(a) Pendulum
(b) Control diagram
(c) Training curve
(d) Sim2real
(e) Speed
Figure Sim2real evaluation an RL policy trained to swing up pendulum with (mes) and without delays (seg). Panels (a) and (b) depict the experimental setup and control diagram, respectively. Panels (c) and (d) show that mes oulperforms seq in the real-world evaluation despite a slower convergence and lower simulated performance. This discrepancy is attributed to seg's inability to develop a robust policy, evidenced by cruss-evaluatioss in panel (d) of mes and seq in each others training environment, where mes proved effective both environments, unlike seg. Panel (e) shows that mos achieves higher mean simulation speed with compacter supergraph (mes: [8] 13) than baseline approaches that also consider delays (gen: |S] = 31 and top: [S] - 43).
To evaluate these methods, we introduce the supergraph efficiency metrie (n))
1 N
Payl S
17 100
Here, N denotes the total number of partitions, with 1j indicating the mean partition size relative to the total supergraph size. This metric effectively quantifies the proportion of vertices actively utilized (unmasked) emulating the computation graphs across episodes. Note that 100% efficiency may not be achievable in practice, it would imply that all partitions have equal number of vertices.
4.2 Performance
In this set of experiments, we aim to validate that randomizing predication masks during training enhances the fidelity of robotic simulations and our approach identifying the supergraph leads to more efficient parallelized simulations. We validate the performance two real-world systems: a pendulum swing-up task and vision- based robotic manipulation task. We use two different control strategies, reinforcement learning (RI) and model predictive control (MPC), to demonstrate the utility of our approach in different real-world settings.
4.2.1 Pendulum swing-un up task
The pendulum swing-up task is well-known RL benchmark with nonlinear, unstable, and underactuated dynamics sensitive to delays (Derner et al., 2020). The choice for this task is deliberate; it highlights the core challenge of delay compensation in reinforcement learning. By demonstrating how neglecting delay simulation can impair policy transfer even in seemingly simple scenarios, we underscore the greater consequences for complex systems where delays are unavoidable and complexity is greater, as discussed in prior work (Liu et al., 2019; Asaamoning et al., 2021; Lou al., 2019; Peters et al., 2014). The simplicity of the task serves clarify the fundamental importance of accounting for delays sim2rcal approaches.
The experimental setup and control diagram are depicted in Figures 5a and 5b, respectively. A failure to emulate the asynchronous real-world interactions between components makes simulation-trained policy ineffective when transferred to real-world setting. Policies were trained using soft actor-critic (SAC) (Haarnoja et al., 2018) in two simulators: one emulating delays (our approach: mcs) and another without delays (sequential approach: seq). Note that the gen and top baselines are not included in the sim2real evaluation. This exclusion is due their replication of the same effective computation graphs as mes, leading to identical policy outcomes. Hence, we only consider these baselines later on in the simulation speed evaluation within this section. We record 10 computation graphs from the real-world system to identify
8

---

Published in Transactions on Machine Learning Research (05/2024)
top
Webcam 20 Hz
Box pose detector 10 Hiz
distance (cm)
distance (cm)
1a3 (Hz)
6
Brax
Joint angles
Planner Fig. Be
20
Joint matarss
Plan extecutor
0
4
8
12
16
90
12
14
16
0
50
100
20 Hz
time (s)
time (s)
efficiency (%)
(a) Box pushing
(b) Control diagram
(c) Peformance
(d) Final accuracy
(e) Planning rate
Figure 6: A comparison of four MPC strategies for a task where a manipulator moves a box to a target: three cousider delays (mes, gen, top) and one does not (seq). Panels (a) and (b) depict the experimental setup and control diagram, respectively. Panels (c) and (d) depict the mean convergence rate and final accuracy over 10 episodes with 95% confidence intervals, respectively, while (e) correlates these with the achieved replanning rate. The seq strategy, although faster initially, leads to less accurate movements due to ignoring delays. The mcs method, while replanning less frequently, achieves approximately 40% higher accuracy. Moreover, mes exhibits the highest replanning rate with smaller supergraph (mes: [G] = 54) compared to gen ( [g] 139) and top (l9) = 223) that also consider delays.
supergraph, partitioning and corresponding predication masks that were randomized during training. Each experiment replicated five times with different random seeds and the results presented in Fig. 5. Though the sequential (seg) approach exhibits quicker convergence and superior simulated performance, it underperforms in real-world tests compared to our approach that includes latency simulation during training. A smaller performance gap between simulation and reality suggests that our approach leads to more accurate simulation, yielding more effective real-world policies. This further supported by cross-evaluations of the trained policies in each other's 's training environment, where mes proved effective both environments, unlike seg.
On average, it took 0,54 seconds to identify the supergraph and predication masks for the 10 recorded computation graphs, which is a one-time startup cost that is small compared to the total training and compilation time of 100 seconds. To establish the link between efficiency and simulation speed, we carried out a parallelized performance evaluation of the swing up-task on an RTX 3070 GPU. We deliberately measure simulation speed during policy evaluation rather than measuring the overall training time to clearly separate simulation speed improvements from any learning algorithm and training-related overhcad. Wo compiled the supergraph with JAX (Frostig al., 2018) and randomized the predication masks across 1000 parallelized episodes. We used the supergraphs produced by our approach with backtracking both baseline methods and recorded the simulation frames per second (fps). As indicated in Fig, 5, our method notably outperforms other baselines that include delays, achieving an approximate simulation speed of 3 million fps. This improvement is largely attributed to a more compact supergraph. We observed a clear linear relationship between r) and simulation fps, which consistent with the inverse proportionality between simulation fps and supergraph size.
5 and
4.2.2 Manipulation task
In the manipulation task, a Viper 300x robotic manipulator moves a box to a target based on streaming webcam images. The goal is to minimize the distance between the box and a goal position. Our experimental setup and control diagram are shown Figures 6a and 6b. Emphasizing the importance of delay simulation, we use consumer-grade Logitech C170 webcam, chosen for its low resolution, modest frame rate, and high latency, to track the box's position and orientation.
We adopt the MPC approach from Yang et al. (2020), planning actions based on the most recent robot observations using the Cross Entropy Method (CEM) (Rubinstein & Kroese, 2004). CEM, known for its efficient, derivative-free optimization, is particularly advantageous due to its parallelizability. Considering the contact-rich nature of box pushing, we opt for Brax (Freeman et al., 2021) as our dynamics model within the MPC framework, instead of learning complex contact dynamics. Brax, a differentiable physics simulator, is optimized for GPU acceleration and effectively handles contact-rich tasks. In a similar approach, Pezzato
9

---

Published in Transactions on Machine Learning Research (05/2024)
100
efficiency (%)
sigma
Followers (F)
Leader (L)
V2V Platoon
0.0
16
60
0.1
32
0.2
64
0.3
topology
nodes
uav
2
x
v2v
UAV Swarn
10
10
10a
UAVs (U)
Control (C)
Control
elapsed time (s)
(a) Schematic
(b) Topology
(c) Complexity analysis
Figure 7: Panel (a) shows the V2V platooning and UAV swarm control systems, with the former comprising leader and followers, and the latter a central controller and UAVs. Panel (b) depicts their respective topologies, where every component communicates at 20 Hz with each other, while the simulator are chosen as the supervisor nodes, respectively. Panel (c) shows the computational complexily versus elficiency for different topologies, asynchronicity levels, and node counts, highlighting their impact on performance.
at 200 Hz. The leader and controller
et al. (2023) recently used PhysX (NVIDIA, 2020) to solve box-pushing task. Our implementation employs CEM for three iterations, involving 75 samples per iteration and planning horizon of two control steps, each lasting 0.15 seconds. We implement our approach using JAX (Frostig et al., 2018) and execute it on an RTX 3070 GPU.
We evaluate four MPC strategics: three accounting for delays (mes, gen, top) and one ignoring them (seq). Delay-inclusive strategies, following Yang el al. (2020), use past plans to predict future box positions and orientations at action time. This prediction is based on the 10 recorded computation graphs of the system that are used to identify supergraph, partitioning, and corresponding prodication masks. On average, it took 1.53 seconds to identify the supergraph and predication masks for the 10 recorded computation graphs, which is one-time startup cost that is small compared to the total evaluation time of 160 seconds. Due to their computational load, these strategies have a lower replanning rate compared to the delay-agnostic seg. The slower the replanning rate, the further into the future the planner must predict, increasing the likelihood of inaccurate predictions. As Fig. 6d shows, mes achieves 40% higher accuracy than seg, despite less frequent replanning. Morcover, the mes method also results in smoother operations than seg, as can be observed in the supplementary material's video. The larger supergraphs in gen and top result in excessively slow replanning, significantly reducing convergence rates, and final accuracy. This illustrates the trade-off between accuracy and efficiency, where the improved accuracy must justify the additional computational load.
4.3 Scalability
The next set of experiments support the claim that our approach scales to complex system topologies. In Sec. 4.2, we showed that employing supergraph with randomized predication masks can effectively emulate direct delay simulation. We also identified an approximate linear correlation between graph efficiency 1) and simulation speed. Next, we assess our method's scalability, analyzing various system topologies and modifying node counts and asynchronicity degrees to ascertain their effects on identifying efficient supergraphs. In this section, we consider two cyber-physical systems for which delay simulation is crucial: vchicle-to-vchicle (V2V) platooning (Zhao et al., 2021; Jia et al., 2015; Peters et al., 2014) and unmanned aerial vehicle (UAV) swarm control (Asaamoning et al., 2021). Furthermore, detailed analysis of the impact of different abstract topological characteristics on supergraph efficiency is provided in Appendix A.
Fig. 7a illustrates the V2V platooning and UAV swarm control systems. In V2V platooning, vehicles maintain a set distance and speed, following a leader. This requires each vehicle to respond to the leader, highlighting the necessity for delay-aware simulation. Vehicles communicate with the leader and the vehicle ahead. For UAV swarm control, central entity directs the UAVs to prevent collisions and achieve formation, with UAVs communicating solely with this controller. Additionally, each component connects to the simulator to
10

---

Published in Transactions on Machine Learning Research (05/2024)
0.0
0.1
0.2
0.3
mS
gen
top
mcs
gen
top
elapsed time (9)
elapsed time (s)
100
100
100
100
efficiency (%)
efficiency (%)
efficiency (%)
80
efficiency
60
60
60
60
2
40
40
40
40
20
20
20
20
100
36
64
8 16 16.3266 64
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
matched (%)
matched (%)
nodes
nodes
sigma
sigma
(a) V2V
(b) UAV
(c) V2V
(d) UAV
(c) V2V
(1) UAV
Figure 8: Panels (a) and (b) show the elapsed time for completion with N 32 nodes across various asynchronicity, Initial episodes are time-intensive due to numerous preliminary partial matches, followed by consistent linear time scaling in processing time. Panels (c-f) compare the elficiency of mes (our approach), top, and gen. panels (c) and (d) the number of nodes is varied with asynchronicity (a (a=00) 0), while in panels (e) and (f) the asynchronicity levels are varied with a fixed size of nodes.
enable physics simulation. Accurate simulations require delays simulation in both systems, discussed in Zhao et al. (2021) and Asaamoning et al. (2021). Within systems encompassing N nodes, there is a single simulator and one leader or controller designated as the supervisor, alongside N - 2 Followers and UAVs, respectively, as illustrated in Fig. 7b. The simulator runs at 200Hz, while all other nodes communicate with each other at a target rate of 20Hz. The effective sampling time of every node i is computed as At,, = At, + max(0, 2t,),,, where 2 is the delay of node i, experience during sequence number k scaled with the node's nominal sampling time. An Ornstein-Ublenbeed (OU) process (Bibbona et al., 2008) is used to model every node's delay to reflect the temporal correlation of delays, defined as follows:
Fh Or + av,
(2)
where is correlation coefficient, a is the standard deviation, and v is a Gaussian random variable with zero mean and unit variance. The standard deviation of an OU process is related to the standard deviation of a Gaussian distribution with o, = 20 We artificially generate computation graphs for the 0.3) and the number of
topologies depicted in Fig. 7b, varying the asynchronicity level a E nodes N E 4,, 4, 8, 16, 32,64) 64). We replicate each experiment 5 times using different random seeds. For each configuration,
generate 10 computation graphs, each running for duration of 10 seconds. Example compulation graphs are presented in Appendix C. We employ Alg. I to identify supergraph on a single core of an Intel Core 19-109K and compare its performance with two baseline approaches.
Fig. 7c presents an analysis of our method's computational complexity in constructing the supergraph, con- sidering both the computation graph's characteristics (N, and lopology (v2v, wav). We observe that efficiency is inversely related the asynchronicity level and, a lesser extent, the number of nodes. Moreover, decrcase in efficiency correlates with increase in computation time, primarily because fewer complete matches are found. Nevertheless, the one-time upfront cost of identifying the supergraph is usually minor when compared to the overall simulation time, substantiating our claim that our approach scales effec- tively to complex system topologies. Figures Sa and 8b detail the required computation time under varying levels of asynchronicity, as it processes all recorded computation graphs. The initial episodes incur higher computational costs due to the increased computational overhead of handling numerous partial matches (Line 6-7 in Alg. 2), while subscquent episodes demonstrate lincar scaling in time.
Figures 8c and 8d compare the performance of our algorithm with baseline approaches for different numbers of nodes when there is asynchronicity (a 0). Our approach achieves 100% efficiency, whereas the efficiency of bascline approaches declines rapidly as the number of nodes increases. Figures 8e and 8f demonstrate the performance of our algorithu compared with baseline approaches for different levels of asynchronicity when the topologies comprise = nodes. As asynchronicity increases, partitions become more dissimilar, and the efficiency of our approach does docline, yet it remains multiples higher than that of the baseline approaches. The supergraphs generated by our method, along with those from the bascline approaches, depicted in Appendix C.
11

---

Published in Transactions on Machine Learning Research (05/2024)
In summary, evaluation suggests that our method successfully emulates asynchronicity, offering more accurate and faster parallelized simulations compared to baseline approaches. At the same time, our method scales well to larger system topologies by finding more efficient supergraphs than baseline methods. Thus, we have substantiated all our key claims through this experimental evaluation.
5 Related Work
Accelerated Physics Simulation Accelerated physics simulators like Brax (Freeman et al., 2021), MJX (Todorov et al., 2012), and PhysX (NVIDIA, 2020) are designed for GPU exccution. However, they lack fea- tures for simulating delays belween their physics engine and other components, such as sensors and actuators. Moreover, to mimic complete systems, these simulators must be extended with controllers and perception modules. Yct, these extensions typically interact with simulators soquentially, ignoring the concurrent and asynchronous nature of real-world systems. Our approach builds on this by dividing these simulators into separate components, facilitating the simulation of asynchronous interactions between them.
Adressing Asynchronicity and Delays The ORBIT framework (Mittal et al., 2023) and research by Bouteiller et al. (2021) have explored integrating delays into robotic simulations. While ORBIT introduces actuator delays PhysX, it overlooks the asynchronicity between other system components. Bouteiller et al. (2021)'s 's work centers on compensating for system delays in the learning algorithm, not addressing the dynamic interactions among delayed components. In contrast, our method extends beyond actuator delays, encompassing asynchrony across all components.
Minimum Common Supergraph Our approach addresses a variant of the minimal universal supergraph (MUG) problem, which seeks the smallest supergraph, i.e., the mes, containing all graphs in given set a subgraph (Trimble, 2021). Unlike the brute-force exact algorithm presented in Trimble (2021), which is suitable only for small graph sets, our approximate greedy algorithm is capable of handling graphs with more than 2000 vertices. In Bunke et al. (2003), an iterative update strategy, based on Bunke et al. (2000), is utilized to approximate the mos. Our method shares similarities but satisfies an additional constraint: the resulting mes must remain acyclic post-merge. Furthermore, our extended objective is to efficiently partition a provided set of larger graphs into smaller subgraphs before finding the mes for these partitioned subgraphs. In contrast, Trimble (2021) and Bunke et al. (2003) start from given and static collection of graphs and focus strictly on the identification of the mes, meaning the partitioning we perform together with the supergraph identification is already given in their scenario. Both Trimble (2021) and Bunke et al. (2003), and our method, (approximately) solve the marimum common subgraph problem as a subroutine to find the minimum common supergraph (mcs) (McCreesh et al., 2017; McGregor, 1982). However, our focus is on subgraph monomorphisms, which allow for additional edges in the subgraph, rather than inducod subgraph isomorphisms, which require a one-to-one correspondence between every node and edge in the subgraph and target graph. To efficiently identify the largest mapping, leverages the acyclic nature of our mes that accelerates the scarch for a large approximate mapping. Note that our algorithm restricts the largest mapping to connected subgraphs, potentially overlooking larger disconnected mapping candidates.
introduce an algorithm that
6 Conclusion
In this paper, we introduced method for efficiently simulating inherently asynchronous systems on accelera- tor hardware. Our approach leverages recorded computation graphs from real-world operations to accurately model asynchronicity and time-scale differences. The experiments suggest that our approach provides a scal- able, efficient, and accurate means for simulating cyber-physical systems. We evaluated our method in two real-world scenarios against baselines and confirmed its elficacy in emulating asynchronicity and handling time-scale differences efficiently. Our work opens avenues for developing fast and accurate cyber-physee system simulations. Finally, our approach holds promisc for enhancing the intogration of other machine learning algorithms that generate dynamic graphs into frameworks like Jax (Frostig al., 2018), by aligning dynamic computation graphs with static ones.
12

---

Published in Transactions on Machine Learning Research (05/2024)
7
Acknowledgments
This work is funded by the EU's H2020 OpenDR project (grant No 871449) and the Dutch Science Foundation NWO-TTW's Veni project HARMONIA (18165).
References
Godwin Asaamoning, Paulo Mendes, Denis Rosário, and Eduardo Cerqueira. Drone swarms as networked control systems by integration of networking and computing. Sensors, 21 (8):22642, 2021.
Radhakisan Baheti and Helen Gill. Cyber-physical systems. The Impuct of Control Technology, 12(1): 161 166, 2011.
Enrico Bibbona, Gianna Panfilo, and Patrizia Tavella. The Ornstein-Uhlenbeck process model of low pass filtered white noise. Metrologia, 45(6):S117, 2008.
Yann Bouteiller, Simon Ramstedt, Giovanni Beltrame, Christopher Pal, and Jonathan Binas. Reinforcement learning with random delays. In Proc. of the Int. Conf. on Learning Representations (ICLR), 2021.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl Gym. arXiv preprint, 2016.
Horst Bunke, Xiaoyi Jiang, and Abraham Kandel. On the minimum common supergraph of two graphs. Computing, 65:13-25, 2000.
Horst Bunke, Pasquale Foggia, Corrado Guidobaldi, and Mario Vento. Graph clustering using the weighted minimum common supergraph. Gruph Based Representations in Pattern Recognition, pp. 235 246, 2003.
Erik Derner, Jiri Kubalik, Nicola Ancona, and Robert Babuska. Constructing parsimonious analytic models for dynamic systems via symbolic regression. Applied Soft Compuling, 94:106432, 2020.
C. Daniel Freeman, Erik Frey, Anton Raichuk, Sertan Girgin, Igor Mordatch, and Olivier Bachem. Brax-A Differentiable Physics Engine for Large Scale Rigid Body Simulation. In Proc. of the Advances in Neural Information Processing Systems (NeurIPS), 2021.
Roy Frostig, Matthew James Johnson, and Chris Leary. Compiling machine learning programs via high-level tracing. Systems for Machine Learning, 4(9), 2018.
Tuomas Haarnoja, Aurick Zhou, Picter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proc. of the lnl. Conf. on Machine Learning (ICML), pp. 1861-1870. PMLR, 2018
Yuanming Hu, Luke Anderson, Tzu-Mao Li, Qi Sun, Nathan Carr, Jonathan Ragan-Kelley, and Frédo Durand. DiffTaichi: Differentiable Programming for Physical Simulation. In Proc. of the Int. Conf. Learning Representations (ICLR), 2020.
Dongyao Jia, Kejie Lu, Jianping Wang, Xiang Zhang, and Xuemin Shen. A survey on platoon-based vehicular cyber-physical systems. IEEE Communications Surveys & Iulorials, 18(1):263 284, 2015.
Xing Liu, Hansong Xu, Weixian Liao, and Wei Yu. Reinforcement learning for ey cyber-physical systems. In 2019 IEFE International Conference on Industrial Internet (ICIT), pp. 318 327. IEFF, 2019.
Xin Lou, Cuong Tran, David KY Yau, Rui Tan, Hongwei Ng, Tom Zhengjia Fu, and Marianne Winslett. time delay attack characterization for cyber-physical systems. In 2019 IEEE Interna- tional Conference on Communications, Control, and Computing Technologies for Smart Grids (Smart- GridComm), pp. 1 6-6. IEEE, 2019.
Ciaran McCreesh, Patrick Prosser, and James Trimble. A partitioning algorithm for maximum common subgraph problems. Proc. of the Inil. Conf. Artificial Intelligence (IJCAT), pp. 712 719, 2017.
13

---

Published in Transactions on Machine Learning Research (05/2024)
James J. McGregor. Backtrack search algorithms and the maximal common subgraph problem. Software: Practice and Experience, 12, 1982.
Mayank Mittal, Calvin Yu, Qinxi Yu, Jingzhou Liu, Nikita Rudin, David Hoeller, Jia Lin Yuan, Ritvik Singh, Yunrong Guo, Hammad Mazhar, Ajay Mandlekar, Buck Babich, Gavriel State, Marco Hutter, and Animesh Garg. Orbit: A Unified Simulation Framework for Interactive Robot Learning Environments. IEEE Robolics and Aulomation Lellers (RA-L), pp- 8, 2023. doi: 111109/LRA.2233333
Robert Nishihara, Philipp Moritz, Stephanic Wang, Alexey Tumanov, William Paul, Johann Schleier-Smith, Richard Liaw, Mehrdad Niknami, Michael Jordan, and Ion Stoica. Real-time machine learning: The missing pieces. In Proc. of the Workshop Hot Topics Operating Systems (HTOS), pp. 106-110, 2017.
NVIDIA. NVIDIA PhysX, 2020. URL hwrllattpp::/deeellorr..../// www.diia.p..iiiiii.............. www.:ccwwopppeceeeeeee sck).
Andrés A Peters, Richard H Middleton, and Oliver Mason. Leader tracking in homogeneous vehicle platoons with broadcast delays. Automatica, 50(1):64 74, 2014.
Corrado Pezzato, Chadi Salmi, Max Spahn, Elia Trevisan, Javier Alonso-Mora, and Carlos Hernandez Corbato. Sampling-base based model prodictive control leveraging parallelizable physics simulations. arXiv preprinl, 2023.
Morgan Quigley, Ken Conley, Brian Gerkey, Josh Faust, Tully Foote, Jeremy Leibs, Rob Wheeler, Andrew Y Ng, al. ROS: an open-source Robot Operating System. Proc. of the IEEE Intl. Conf. on Robotics & Automation (ICRA), 3:5, 2009.
Reuven Y Rubinstein and Dirk P Kroese. The cross-entropy method: a unified approach to combinatorial optimization, Monte-Carlo simulation, and machine learning. Springer, 133, 2004.
Nikita Rudin, David Hoeller, Philipp Reist, and Marco Hutter. Learning to Walk in Minutes Using Massively Parallel Deep Reinforcement Learning. Proc. of the Conf. Robot Learning (CoRL), 164:91 100, 2022.
Naoki Shibata. Efficient Evaluation Methods of Elementary Functions Suitable for SIMD Computation.
Computer
and development, 25:25-32 32, 2010.
Avi Singh, Larry Yang, Kristian Hartikainen, Chelsea Finn, and Sergey Levine. End-to-end robotic rein- forcement learning without reward engineering. arXiv preprint, 2019.
Ryan Taylor and Xiaoming Li. Seftware-Based Branch Predication for AMD GPUs. SIGARCH Comput. Archit. News, 38(4):66- 72, 2011.
Emanuel Todorov, Tom Erez, and Yuval Tassa. MuJoCo: A physics engine for model-based control. Proc. of the TEEE/RS. Tnil. Conf. on Intelligent Robots and Systems (IROS), pp. 5026-5033, 2012.
James Trimble. Induced universal graphs for families of small graphs. XrXiv preprint, 2021.
James Trimble. Partitioning algorithms for induced subgraph problems. PhD thesis, University of Glasgow, 2023.
Yuxiang Yang, Ken Caluwaerss, Atil Iscen, Tingnan Zhang, Jie Tan, and Vikas Sindhwani. Data efficient reinforcement learning for legged robots. Proc. of the Conf. Robot Learning (CoRL), pp. 1 10, 2020.
Fei Zhao, Yu Liu, Jian Wang, and Li Wang. Distributed model predictive longitudinal control for connected autonomous vehicle platoon with dynamic information flow topology. In Actuators, volume 10, pp. 204. MDPI, 2021.
14

---

Published in Transactions on Machine Learning Research (05/2024)
Supervisor vertex
Asynchronous interaction
Randomly connected
Bidirectional
IHz
2Hz
N-1Hz
200Hz
1H2
N-182
283H2
142
N-1Hz
288Hz
(a) Unidirectional
(b) Bidirectional
(c) Unirandom
Figure 9: Three abstract topologies to evaluate the scalability of our approach. (a) Unidirectional: each node has a single outgoing connection. (b) Bidirectional: each node has two outgoing connections. (c) Unirondom: akin to Unidirectional, but with extra random outgoing connection per node.
mcS
gen
top
100
100
100
100
100
100
efficlency (%)
efficiency (%)
efficiency (%)
efficiency (%)
efficiency (%)
80
80
80
80
efficiency
40
40
40
40
20
20
20
20
20
20
2 4 8 12
8 16
2
16.32 64
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
0.0
0.2 sigma
0.1
0.3
nodes
nodes
nodes
sigma
sigma
(a) Unidiroctional
(b) Bidirectional
(c) Unirandom
(d) Unidirectional
Bidirectional
(1) Unirandom
Figure 10: Efficiency comparison of mes (our approach), top, and gen. In panels (a-c) the number of nodes is varied with asynchronicity (a 0), while in panels (d-f) the asynchronicity levels are varied with fixed size of N 8 nodes.
A Scalability Analysis with Abstract Topologies
In this scalability study, we focus on artificially generated computation graphs, as they allow us to system- atically vary the number of nodes, the level of asynchronicity, and the topology of the graph. We consider three different topologies: unidirectional, bidirectional, and unirandom, depicted in Fig. 9.
The nominal sampling time of each node is set according to the node's index i At, 1 except for the last node's sampling time which is set to AIN 200 s. These topologies resemble cascaded control schemes that are common in robotic systems, with slower learning-based nodes and faster simulator nodes with intermediate controllers, estimators, sensors and actuators. The effective sampling time is computed with Eq. (2) as further detailed in Sec. 4.3.
As in Sec. 4.3, we consider different number of nodes N E (2,4,8, 16, and varying levels of asynchronicity
00,0.1, 0.2, 0.3), and replicate every experiment 5 times using different random seeds. For cach configuration, we generate 20 computation graphs, each running for duration of 100 seconds.
Figures 10a, 10b, and 10c illustrate the performance of our algorithm for different numbers of nodes when there is no asynchronicity (a= 0). Our approach achieves a 100% efficiency for the unidirectional topology, whereas the efficiency of bascline approaches declines rapidly as the number nodes increases. The superior efficiency of our approach in the unidirectional topology is attributed to its fewer connections. Figures 10d, 10c, and 10f demonstrate the performance of our algorithm for different levels of asynchronicity when the network comprises N nodes. As asynchronicity increases, partitions become more dissimilar, and the efficiency of our approach does decline, yet it remains multiples higher than that of the baseline approaches.
Figure 11 presents an analysis of our method's computational complexity in constructing the supergraph, considering both the computation graph's characteristics and topology, and the scaling of supergraph search complexity over all recorded computation graphs. Figures 1la, 11b, and 11c detail our algorithm's complexity under varying asynchronicity levels through time as processes all recorded computation graphs. The initial episodes incur higher computational costs due the increasod computational overhead of handling numerous partial matches (Line 6-7 in Alg. 2), while subsequent episodes demonstrate linear scaling in time.
15

---

Published in Transactions on Machine Learning Research (05/2024)
0.1
0.2
0.3
elapsed time (s)
elapsed time (s)
elapsed time (s)
100
100
100
80
0.0
sigma
16
effidency
60
0.1
12
0:3
topology
20
rodes
50 100
10'
10' elapsed time (=)
10
matched (%)
matched (%)
matched (%)
(a) Unidirectional
(b) Bidirectional
Unirandom
(d) Complexity analysis
Figure 11: Performance analysis of computational complexity and elficiency. Panels (a-c) show the elapsed time for completion with N = 32 nodes across various asynchronicity levels and topologies. Initial episodes are time-intensive due numerous preliminary partial matches, followed by consistent linear time scaling in processing time. Panel (d) shows the computational complexity versus efficiency for different topologies, asynchronicity levels, and node counts, highlighting their impact on performance.
elapsed time (s)
elapsed time (s)
40
10 15 20
elapsed time
linear
10
arbitrary
topology
topology
topology
100
100
100
efficiency (%)
10
15
efficlency (%)
power
efficlency (%)
max-edge arbitrary
80
80
linear
60
rand
topology
topology
topology
(a) Backtrack
(b) Combination
(c) Sort
Figure 12: Ablation study topologies with N 32 and 0.1, examining computational complexity and efficiency. Sub-figures show: (a) Effects varying B; (b) Efficiency-impactt considering one (linear) vs. all combinations per size l (power); (c) Comparison of arbitrary and mar-edge topological sorts.
In Fig. 11d, we again observe that efficiency is inversely related both the asynchronicity level and the number of connections per node within topology. Specifically, the unidirectional topology outperforms the bidirectional and unirandom topologies due its fewer edges. A decrease in efficiency correlates with an increase in computation time, primarily because fewer complete matches found, which is consistent with the results in Sec. 4.3. While the most substantial contributor to computation lime is the number of nodes in the topology, it does not affect efficiency as similar efficiency is achieved with different numbers of nodes.
B Ablation Study
In this study, our goal to substantiate that our approach employs simplifications discussed in Sec. 3.4 that reduce computational complexity without significantly affecting performance. For this ablation study, we focus the topologies in Fig. 9 with N 32 and 0.1, ablating the proposed simplifications.
Fig. 12 illustrates that the benefits of backtracking are limited. However, it neither increases the computa- tional complexity of our approach nor adversely affects efficiency.
We also analyzed the effect of considering only a single combination for each size k as opposed to exploring all combinations. Fig. 12 demonstrates that this simplification has negligible impact on efficiency but consid- erably reduces the computational complexity (note the log-scale). It worth noting that only considering a single combination seems perform slightly better in cases. This outcome, while not statistically
16

---

Published in Transactions on Machine Learning Research (05/2024)
implausible, may also be caused by other factors, such as the order in which the graphs processed. Our hypothesis centers the specific nature of the computation graphs generated by cyber-physical systems. These graphs tend to exhibit relatively fixed structure, meaning the variety of topological orderings is con- sidcrably constrained compared to more generic graphs. Consequently, this structural rigidity could diminish the advantages we might expect from checking all combinations.
Lastly, we explored the implications of using a single topological sort. Rather than exhaustively considering all topological sorts-an approach that would be computationally prohibitive-wi we compared the effects of using arbitrary sort versus max-edge sort. The max-edge sort of the supergraph is defined accommodates the maximum number of potential edges (i.c., constraints) and therefore increases the chance of finding a match in Alg. 2. Due to the inherent unidirectionality of the unidirectional topology, the max- edge sort arranges vertices of lower indices before those of higher indices. Since we lack max-edge sorting criteria for bidirectional and unirandom topologies, we limited this part of the study the unidirectional topology. Fig. 12 shows that this simplification has negligible impact on efficiency.
that
C Graphs
SIM 000000O
SIM
0.00
0.05
0.10
0.15
0.20
0.25
$
10
15
20
25
time (s)
topological generation
(a) Computation graph of V2V platooning
(b) Our approach (mcs)
F1
F2
F2
SIM
SIM
10 topological generation
10 15
20
25
topological generation
(c) Topological (top)
(d) Cenerational (gen)
Figure 13: Panel (a) presents a segment of computational graph corresponding to the platooning scemario in Fig. 7b with N and 0.2. Vertices of identical color correspond the periodic computation unit. and edges represent data dependencies. Panels (b-d) illustrate the supergraphs generated by our method (mes), as well as the topological (top) and generational (gen) methods. Our approach yields supergraph with reduced number of vertices, indicating enhanced elficiency in identifying commonalities across the computation graphs.
17

---

Published in Transactions on Machine Learning Research (05/2024)
UAV,
UAV1
UAV
UAV>
SIM
0.00
0.05
0.10
0.15
0.20
0.25
5
10
15
20
25
time (s)
topological generation
(a) Computation graph of UAV control
(b) Our approach (mcs)
C
UAV.
UAV1
UAV
UAV
SIM
SIM
20
10
20
25
topological generation
topological generation
(c) 'oooloogccll (top)
(d) Generational (gen)
Figure 14: Panel (a) presents segment of computational graph corresponding the nav swarm scenario in Fig. 7b with N = 4 and = 0.2. Vertices of identical color correspond to the same periodic computation unit, and edges represent data dependencies. Panels (b-d) illustrate the supergraphs generated by our method (mes), as well the topological (top) and generational (gen) methods. Our approach yields supergraph with reduced number of vertices, indicating enhanced efficiency identifying commonalities across the computation graphs.
18


Reviews:
[{"review_id": "zhuPBF4rzr", "reviewer": "Reviewer_DfLD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* Highlighting an interesting and overlooked problem in sim2real transfer.\n  * The paper highlights the challenges involved in dealing with real systems, which are often far from their idealized counterparts in simulation. The kinds of asynchronous timings that the paper discusses are common, and existing commonly used simulators often do not account for them. The experiments run in the paper highlight that this is a problem for sim2real transfer, and show that the presented asynchronous simulator supports better transfer of RL policies to the real world.\n* Novel greedy algorithm for discovering Minimum Common Supergraphs\n  * As this is not my area of expertise, I cannot directly comment on the novelty of this contribution, but the paper claims that their greedy approach to finding a minimum common supergraph is novel, and it appears to work better than two reasonable sounding baselines. This is not a machine learning contribution, however.\n\nWeaknesses\n* Relevance to machine learning audience\n  * By the paper's own statement: \"The main contribution of this paper is an approach to parallelize cyber-physical system simulations that\nemulates asynchronicity and delays with minimized computational overhead on accelerator hardware.\" This is very interesting, but is not really about machine learning. The main contribution instead relates to software optimization. The main innovations relating to finding super graphs do not involve any machine learning. \n\n  * Instead, the way in which this is connected to machine learning is the fact that the sim2real performance is tested with a reinforcement learning agent. However, this is a somewhat tenuous connection to machine learning. Without source code for the GPU optimization being released with the paper (instead only Algorithms 1 and 2 are provided), it is hard to imagine that TMLR's audience members would use these algorithms for GPU optimization, meaning that it would likely not be adopted.\n\n* Presentation and clarity of writing\n  * The paper is similarly written with a software optimization audience in mind. As a result, it will be difficult for readers of TMLR to understand. There are many undefined terms throughout the paper (for example, what is a predication mask? monomorphism? What is control flow vs. data flow?) which might be obvious to people with a software optimization background, but which are less likely to be familiar to readers coming from a machine learning background.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a technique for efficiently simulating asynchronous physical systems. When simulations are asynchronous, there is a nontrivial computation graph that arises where individual environment steps can no longer be parallelized on a GPU. This paper presents a novel method for finding a partitioning strategy of the multi-step asynchronous computation graph that allows for more effective parallelization on a GPU. The paper then shows that this asynchronicity matters for sim2real transfer when training an RL agent. By matching the asynchronicity of a real system in simulation, the RL agent trained in simulation better transfers to the real world. Similarly, the paper shows that the presented method for finding static computation graphs leads to more efficient simulation than baseline approaches.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Presentation clarity needs to be improved for a machine learning audience \n* Examples\n  * Figure 2 could use work in a few ways\n    * what is the difference between the red and black arrows?\n    * what do the different node colors mean? Do they correspond to Figure 1? Could these be labelled here again?\n    * why is the supervisor node always the top green one? does it need to be?\n  * Predication mask is not clearly defined in the text -- what is it? Control flow to data flow dependencies was not super clear.\n  * Can the authors give some examples of computation graphs that would come up for a given agent interacting with a given environment? This would help ground several of the algorithms into meaningful examples that might be easier to parse for a machine learning audience\n  * In general, it would be helpful to refer to the different types of nodes with names that indicate their physical system counterparts, as done in Figure 1\n  * In the experimental section on computation graph topologies, it would similarly be useful to give grounded physical simulation examples of when each of those topologies would come up, and why they would matter.\n  * Many terms in the related work section on minimum common supergraphs are undefined, and will be unknown to a machine learning audience. It might make more sense to move this section later in the paper, after preliminaries and the details of the algorithm. (e.g. what a monomorphism is, what \"post-merge\" means, etc.)\n \n* Questions about experiments\n  * Is the time for algorithm 1 / 2 to be run included in the overall timing comparisons between MCS and seq? Could this be clarified in the paper?\n\nSmaller changes\n* be consistent with capitalization, use MCS always or mcs always, but do not mix between the two\n* in the related work section: “Furthermore, we discover the set of graphs alongside the mcs, whereas Trimble (2021) and Bunke et al. (2003) presume a given graph set.”\n  * Earlier it was stated that the minimal universal supergraph problem … “ seeks the smallest supergraph, i.e., the minimum common supergraph (mcs), containing all graphs in a given set as a subgraph (Trimble, 2021)”\n  * This seems contradictory to the statement above then, as the graph set has to be initially given according to the problem statement. Could this be explained?\n* Notation could be improved\n  * |G| denotes the number of vertices in G, but does not include edges. Consider changing to |V| which is more direct.\n  * \"The edges that connect G1 and G2 − G1 are defined as the embedding embG2 (G1), which is a subset of E(G2)\"\n    * this will be confusing for a machine learning audience, as embeddings typically mean the outputs of a neural network.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "zbOAvlxw2B", "reviewer": "Reviewer_Arj5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper's approach addresses the key issue of accurately simulating the asynchronous interactions between computational elements, sensors, and actuators in cyber-physical systems. This makes the simulator more reflective of actual conditions.\n\n- The construction of supergraph that encodes all data dependencies across parallelized simulation steps, ensuring that simulation steps are processed in a sequence that respects these dependencies without violating them, is very interesting.\n\n- The goal of finding the smallest supergraph possible and sorting it topologically, minimizes redundant computation. This efficiency is critical in maintaining high simulation speeds and reducing the needed computational resources.\n\nWeaknesses/Questions\n\n- Identifying the smallest supergraph is a complex, NP-hard problem, which could potentially limit the approach's applicability in scenarios where computational resources are constrained or when simulating exceedingly complex systems. It would be useful to relate the assumptions used in the greedy approximation to real-world constraints on a CPS. For example, isn't it normal for different nodes to be stateful?\n\n- The evaluation is over two very simple systems - pendulum and box pushing manipulator. Given the focus on large scale CPS system simulation, these examples are not sufficient to demonstrate practical utility.\n\n- The relevance to machine learning is tenuous. Demonstrating how this efficient simulation can be helpful for some learning task would be useful.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focuses on the challenge of accurately simulating the asynchronous and delay-filled interactions that occur in cyber-physical systems. While the advancements in accelerated physics simulations have significantly reduced the training times for reinforcement learning policies, these traditional simulations fail to capture the real-time, asynchronous nature of real-world interactions, leading to a notable gap between simulated and real-world performance (the \"sim2real gap\"). The paper attempts to develop an efficient parallel approach for cyber-physical system simulations on accelerator hardware, including physics, sensors, actuators, processing components and their asynchronous interactions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall, the paper presents a promising approach to bridging the sim2real gap in cyber-physical systems by accurately simulating asynchronicity and delays. But the evaluation of the approach is very limited and the paper is not yet ready for publication. Addressing the weaknesses above would make the paper stronger.\n\nScaling to CPS systems such as an autonomous car, an UAV, a robot, etc will require addressing a lot of challenges left unaddressed in the paper. For e.g., different observed variables in CPS evolve at different time-scales. At the very least, one can consider a parametric system (e.g, traffic collision avoidance TCAS system with increasing number of aircrafts) and study how the scalability changes with the parameter. The reviewer would request authors to look at academic (and small to moderate) sized CPS benchmarks at https://github.com/lyudeyun/AI-CPS-Benchmark and https://github.com/natchi92/BASBenchmarks\n\nThe new experiments address the primary concern of this reviewer.", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fiSzC08Jbu", "reviewer": "Reviewer_AtP5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: the paper is pretty clear about the goal of enabling parallel simulation of physical environments, with an extended capability for handling delays in different components of the system. The authors make arguments for why this is worthwhile, and why the proposed method is reasonable, with some experimental justification.\n\n\nWeaknesses: the motivation seems to better sim-to-real performance, resting on one fairly simple environment and a fairly small difference in absolute terms within a more complicated environment, and it's not compared to any real alternatives. Can this be strengthened? ORBIT has limited asynchronicity, but does have some delay -- how does sim-to-real performance compare if those delays are introduce in the sample environment?  Or are there are other ways to strengthen the claim that there is a significant benefit in the sim-with-delay, beyond two environments where the agent does do better (rather than lucky regularisation/bias?): how does sim-to-delay-sim compare to sim-to-real?\n\nNote to be clear -- I do not think the current set of experiments are definitely inadequate, but I do think this might be the biggest weakness.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an approximate method for generating efficient accelerator computation graphs for repeated not-quite-identical simulation steps. The target domain is physics simulation, where the differences come from asynchronously operating parts with varying delays: computation, multiple sensors, actuators, physics model updates.\n\nThe paper introduces an approximate algorithm for finding the minimum size, directed acyclic supergraph that contains all model steps, from some large set of previously observed steps or synthetic data. This single supergraph can then be used to do a fast parallel (multi-environment) simulation step, with different environments delays being represented through data dependencies.\n\nThe authors provide sim-to-real experiments on two physical systems. In one of these domains, simulation speed was mostly irrelevant to real performance, but the other experiment did planning and had a real performance cost for increased simulation time. Despite the authors' delay-aware simulation steps being slower than ignoring the delays (producing simple, identical model steps that are easily and efficiently parallelisable), the proposed algorithm had better sim-to-real performance for both environments. The sequential and proposed models are compared to mock algorithms for delay-aware compuation graphs.\n\nThe authors also provide synthetic data experiments on supergraph construction time, and on the efficiency of the supergraph -- how many nodes are not masked out through data dependencies when computing steps.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "How is algorithm 2 guaranteed to only considering acyclic mappings? Is this just because S is already acyclic? How is S being guaranteed to avoid adding a cycle as it adds the different edges from different partitions?\n\nI suspect and hope there's a fairly simple, obvious answer I'm just missing. The remaining points are all non-critical.\n\n\n\"Our approach addresses the minimal universal supergraph problem\" -- given the acyclic constraint, would it be more accurate to say it addresses a variant of the MUG problem?\n\n\"Unlike the brute-force algorithm presented .. our greedy algorithm is\" -- suggest something like \"Unlike the brute-force exact algorithm presented ... our approximate greedy algorithm\"\n\nFigure 3.  Are all the lines/nodes correct?\nFor example, in b), how has the second magenta sensor node ended in Pi,0 when it's not an ancestor of S0?  Because i>0 and there's an existing S matching it from the first purple physics node? If so, it would be nice to have that current S at the start is this iteration i.\nWhy is there no edge from the third magenta (first in Pi,1) to the green node in Pi,1?  Edges from green to orange in e)?\n\nAlgorithm 1.  I'm not sure what indexing a vertex u_i means. Is that just relabeling it? Why do do this at all, rather than saying j <- index of  u: I(...) and use u_i and Pi,j Mi,j?\nLater text also states \"We alleviate this by considering only a single ...\". This should be in the algorithm: as is, it seems to be considering all combinations and all sortings.\n\nSection 5.1: should note here that there is a non-trivial startup cost to generate the supergraph, but this cost is only paid at startup, and is not being included in the evaluation of run-time performance.  I was glad to eventually discover that this was already noted at the end of the section on scalability, but I think it should be included at the front where it is describing how the algorithm is evaluated, either in addition to the section 5.3 comment or instead of. While I broadly agree that the startup cost can be reasonably amortised across a larger run, the slowest point in FIgure 9 is around 10^3 seconds, which makes the startup / run-time split be worth mentioning.\n\nFigure 5: given the non-trivial difference in speed, it would be good to have the training curve with time as the x-axis -- either instead of steps, or in addition to steps if the authors would like to preserve the existing figure.\n\n\"Moreover, mcs method also results in smoother operations than seq.\"  Is there anything viewable to the readers to see that? If not, should soften this to something like \"Moreover, in the author's subjective evaluation, the mcs method ...\"\n\n\"The effective sampling time of each node is computed as delta t_i,ik  ... scaled with the nominal sampling time.\"  There appears to be something not quite right with this sentence. Should there be a delta t_i-1,k?  Was there previously an x_i,k that was removed? If there is a delta i_,k = delta i-1,k, it seems to be non-decreasing given the current location of max(0,...)\n\nAblation: the choice of \"linear\" (a single combination) seems to actually be better than \"power\" for both uni and bi. The algorithm is a greedy approximation so this is not impossible, but it's surprising.  Do the authors have an explanation?\n\n\"optimal sort\": does this actually cause the algorithm to produce the optimally efficient supergraph? If not, I would suggest a different name (\"max-edge sort\"? something else?) that doesn't imply algorithm optimality. If it *does* imply optimal efficiency -- great! -- then fine as is.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: As noted all three reviewers voted to accept and are happy with the paper. 

The AE has two requests:
1. There are whitespace formatting issues to address
2. The intro should include a clear definition of CPSs and a description of one application. Both are implicitly included in the paper (the definition is a sub-clause of a sentence), but making these more direct and intentional would improve the accessibility and potential impact of the paper.
Decision: Accept (poster)