Computer Science – Logic in Computer Science
Scientific paper
2011-11-02
EPTCS 72, 2011, pp. 13-28
Computer Science
Logic in Computer Science
In Proceedings PDMC 2011, arXiv:1111.0064
Scientific paper
10.4204/EPTCS.72.2
Recently, two new parallel algorithms for on-the-fly model checking of LTL properties were presented at the same conference: Automated Technology for Verification and Analysis, 2011. Both approaches extend Swarmed NDFS, which runs several sequential NDFS instances in parallel. While parallel random search already speeds up detection of bugs, the workers must share some global information in order to speed up full verification of correct models. The two algorithms differ considerably in the global information shared between workers, and in the way they synchronize. Here, we provide a thorough experimental comparison between the two algorithms, by measuring the runtime of their implementations on a multi-core machine. Both algorithms were implemented in the same framework of the model checker LTSmin, using similar optimizations, and have been subjected to the full BEEM model database. Because both algorithms have complementary advantages, we constructed an algorithm that combines both ideas. This combination clearly has an improved speedup. We also compare the results with the alternative parallel algorithm for accepting cycle detection OWCTY-MAP. Finally, we study a simple statistical model for input models that do contain accepting cycles. The goal is to distinguish the speedup due to parallel random search from the speedup that can be attributed to clever work sharing schemes.
de Pol Jaco van
Laarman Alfons
No associations
LandOfFree
Variations on Multi-Core Nested Depth-First Search does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Variations on Multi-Core Nested Depth-First Search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Variations on Multi-Core Nested Depth-First Search will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-327441