Hitching a Ride to a Lasso: Massively Parallel On-The-Fly LTL Model Checking
Open Access
- 5 April 2024
- book chapter
- Published by Springer Nature
- p. 23-43
Abstract
The need for massively parallel algorithms, suitable to exploit the computational power of hardware such as graphics processing units, is ever increasing. In this paper, we propose a new algorithm for the on-the-fly verification of Linear-Time Temporal Logic (LTL) formulae [45] that is aimed at running on such devices. We prove its correctness and termination guarantee, and experimentally compare a GPU implementation with state-of-the-art LTL model checkers. Our new GPU LTL-checking algorithm is up to 150 $$\times $$ faster on proving the correctness of a system than LTSmin running on a 32-core high-end CPU, and is more economic in using the available memory.
Keywords
This publication has 57 references indexed in Scilit:
- From Spot 2.0 to Spot 2.10: What’s New?2022
- GPU Acceleration of Bounded Model Checking with ParaFROST2021
- SAT Solving with GPU Accelerated Inprocessing2021
- ParaMoC: A Parallel Model Checker for Pushdown Systems2020
- SIGmA: GPU Accelerated Simplification of SAT Formulas2019
- Parallel SAT Simplification on GPU Architectures2019
- The SLCO Framework for Verified, Model-Driven Construction of Component Software2018
- Improving Spin’s Partial-Order Reduction for Breadth-First Search2005
- Distributed Explicit Fair Cycle Detection (Set Based Approach)2003
- On a Decision Method in Restricted Second Order Arithmetic1990