System and method for parallel model checking utilizing parallel structured duplicate detection

摘要

A technique for parallelizing model checking using breadth-first search in order to detect deadlocks and safety property violations is disclosed. The technique is based on Parallel Structured Duplicate Detection (PSDD) and preserves a model checker's ability to perform partial order reduction with parallel breadth-first search. PSDD also uses much less memory and is able to achieve better parallel speedup and verify models more quickly. Also, PSDD used herein is able to make use of external memory, such as hard disks, to reduce the memory requirements of verification.