Accession Number:

ADA619756

Title:

Model Checking with Multi-Threaded IC3 Portfolios

Descriptive Note:

Technical paper

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SOFTWARE ENGINEERING INST

Personal Author(s):

• Chaki, Sagar
• Karimi, Derrick

Report Date:

2015-01-15

Pagination or Media Count:

22.0

Abstract:

Three variants of multi-threaded ic3 are presented. Each variant has a fixed number of ic3s running in parallel, and communicating by sharing lemmas. They differ in the degree of synchronization between threads, and the aggressiveness with which proofs are checked. The correctness of all three variants is shown. The variants have unpredictable runtime. On the same input, the time to find the solution over different runs varies randomly depending on the thread interleaving. The use of a portfolio of solvers to maximize the likelihood of a quick solution is investigated. Using the Extreme Value theorem, the runtime of each variant, as well as their portfolios is analysed statistically. A formula for the portfolio size needed to achieve a verification time with high probability is derived, and validated empirically. Using a portfolio of 20 parallel ic3s, speedups over 300 are observed compared to the sequential ic3 when on hardware model checking competition examples.

Descriptors:

• *ALGORITHMS
• COMPUTER PROGRAM VERIFICATION
• MATHEMATICAL MODELS
• PARALLEL PROCESSING

Subject Categories:

• Operations Research
• Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE