کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431532 688570 2012 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Designing fast LTL model checking algorithms for many-core GPUs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Designing fast LTL model checking algorithms for many-core GPUs
چکیده انگلیسی

Recent technological developments made various many-core hardware platforms widely accessible. These massively parallel architectures have been used to significantly accelerate many computation demanding tasks. In this paper, we show how the algorithms for LTL model checking can be redesigned in order to accelerate LTL model checking on many-core GPU platforms. Our detailed experimental evaluation demonstrates that using the NVIDIA CUDA technology results in a significant speedup of the verification process. Together with state space generation based on shared hash-table and DFS exploration, our CUDA accelerated model checker is the fastest among state-of-the-art shared memory model checking tools.The effective utilization of the CUDA technology, however, is quite often reduced by the costly preparation of suitable data structures and limited to small or middle-sized instances due to space limitations, which is also the case of our CUDA-aware LTL model checking solutions. Hence, we further suggest how to overcome these limitations by multi-core construction of the compact data structures and by employing multiple CUDA devices for acceleration of fine-grained communication-intensive parallel algorithms for LTL model checking.


► Acceleration of the LTL model checking process by means of massively parallel GPUs.
► Redesign of accepting cycle detection algorithms for efficient GPU utilization.
► Multi-core construction of compact data structures allowing for parallel processing.
► Overcoming of GPU memory limitations by employing multiple CUDA devices.
► Design of fine-grained communication-intensive parallel LTL model checking algorithms.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 72, Issue 9, September 2012, Pages 1083–1097
نویسندگان
, , , ,