Towards parallelization of simulation-based reachability

Qi, Bolun

Permalink

https://hdl.handle.net/2142/91560 Copy

Description

Title

Towards parallelization of simulation-based reachability

Author(s)

Qi, Bolun

Contributor(s)

Mitra, Sayan

Issue Date

2016-05

Keyword(s)

• reachability analysis
• verification
• hybrid systems
• parallel programming
• OPENMP

Abstract

To check bounded time invariant properties of models with nonlinear dynamics, one promising method is called simulation-based verification. This involves: (a) generating numerical simulations of the ODE from a finite set of representative initial states that cover the whole (uncountably many) initial set, say, (b) bloating each of these simulations by some factor such that the bloated tubes together over-approximate the reachable states from, and (c) checking if this computed over-approximation is adequate for proving invariance; otherwise, add more representative initial states to obtain a more precise over-approximation and repeat from (a). Compare-Execute-Check-Engine (C2E2) is such a tool for verifying bounded time dynamical and hybrid systems models using simulation-based reachability analysis. To make the reachable set computation more accurate, it is preferable to start from smaller initial sets, which requires C2E2 to partition large initial sets into smaller covers at first. However, the number of initial covers will increase exponentially with dimensionality of the system and the fidelity of each cover. Currently, C2E2 does invariant checking for the reachable sets from each cover sequentially, which makes the running time increase proportionally to the initial covers. Simulation-based approaches are naturally parallelizable due to the fact that simulations and reachable set computation for each initial condition considered can be computed independently. In this paper, we introduce the parallelization of C2E2 to utilize the computational power of multi-core CPU and improve the efficiency of tools. The parallel algorithm is implemented using thread library OPENMP. We evaluate the improvement of performance on four different models. Comparison with the sequential counterpart shows a maximum speedup of 7.3x on a four core Intel CPU I7-4790K processor.

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/91560

Owning Collections