Spread the Work: Multi-threaded Safety Analysis for Hybrid Systems
Spread the Work: Multi-threaded Safety Analysis for Hybrid Systems
复制标题
分散工作：混合系统的多线程安全分析
DOI：
10.1007/978-3-319-92970-5_6
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Erika Ábrahám
中科院分区：
文献类型：
--
作者：
Stefan Schupp;Erika Ábrahám
我们考虑一种方法的混合系统，其连续的行为是交织在一起的离散执行步骤的有界安全分析。该方法计算一棵树的状态集，其中一起过近似的可达性有限长度的执行。如果没有一个状态集与给定的不安全状态集相交，那么我们已经证明了有界安全性。否则，我们迭代地重复局部细化搜索参数的计算的一部分，以减少过度逼近误差。在本文中，我们提出了上述方法的并行化技术。我们确定独立的计算，可以由不同的线程/进程并发进行，并研究如何实现线程之间的工作平衡，在低通信成本。此外，我们讨论了如何在细化计算期间确保互斥的节点访问，而不会产生高同步成本。我们评估我们提出的解决方案实验上的一些基准。
We consider a method for the bounded safety analysis of hybrid systems, whose continuous behaviour is intertwined with discrete execution steps. The method computes a tree of state sets, which together over-approximate reachability by bounded-length executions. If none of the state sets intersects with a given set of unsafe states then we have proven bounded safety. Otherwise, we iteratively repeat parts of the computations with locally refined search parameters, in order to reduce the over-approximation error.In this paper we present a parallelization technique for the above method. We identify independent computations that can be carried out by different threads/processes concurrently, and examine how to achieve work-balance between the threads at low communication cost. Furthermore, we discuss how to assure mutually exclusive node access during refinement computations, without high synchronization costs. We evaluate our proposed solutions experimentally on some benchmarks.
登录
查看更多内容
ARCH-COMP17 类别报告：具有分段恒定动态的混合系统的有界模型检查
DOI：
--
发表时间：
2017
期刊：
ARCH@CPSWeek
影响因子：
--
作者：
Lei Bu;Rajarshi Ray;Stefan Schupp
通讯作者：
Stefan Schupp
DOI：
10.3182/20090916-3-es-3003.00043
发表时间：
2009
期刊：
--
影响因子：
--
作者：
Goran Frehse;Rajarshi Ray
通讯作者：
Goran Frehse;Rajarshi Ray
DOI：
10.1007/978-3-319-57288-8_20
发表时间：
2017-05
期刊：
--
影响因子：
--
作者：
Stefan Schupp;E. Ábrahám;Ibtissem Ben Makhlouf;S. Kowalewski
通讯作者：
Stefan Schupp;E. Ábrahám;Ibtissem Ben Makhlouf;S. Kowalewski
混合系统可达性分析的高效动态误差减少
DOI：
10.1007/978-3-319-89963-3_17
发表时间：
2018
期刊：
影响因子：
--
作者：
Stefan Schupp;Erika Ábrahám
通讯作者：
Erika Ábrahám