GPU accelerated on-the-fly reachability checking

• Main Authors: WU, Zhimin, LIU, Yang, SUN, Jun, SHI, Jianqi, QIN, Shengchao
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2015
• Subjects: Computer and Systems Architecture; Software Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/4951; https://ink.library.smu.edu.sg/context/sis_research/article/5954/viewcontent/ICECCS2015b.pdf
• Institution: Singapore Management University

Model checking suffers from the infamous state space explosion problem. In this paper, we propose an approach, named GPURC, to utilize the Graphics Processing Units (GPUs) to speed up the reachability verification. The key idea is to achieve a dynamic load balancing so that the many cores in GPUs are fully utilized during the state space exploration.To this end, we firstly construct a compact data encoding of the input transition systems to reduce the memory cost and fit the calculation in GPUs. To support a large number of concurrent components, we propose a multi-integer encoding with conflict-release accessing approach. We then develop a BFS-based state space generation algorithm in GPUs, which makes full use of the GPU memory hierarchy and the latest dynamic parallelism feature in CUDA to achieve a high parallelism. GPURC also supports a parallel collaborative event synchronization approach and integrates a GPU hashing method to reduce the cost of data accessing. The experiments show that GPURC can give significant performance speedup (average 50X and up to 100X) compared with the traditional sequential algorithms.