Parallel Combinational Equivalence Checking

Combinational equivalence checking (CEC) has been widely applied to ensure design correctness after logic synthesis and technology-dependent optimization in digital integrated circuit design. CEC runtime is often critical for large designs, even when advanced techniques are employed. Three complementary ways for enabling parallelism in CEC are proposed, addressing different design and verification scenarios. The experimental results have demonstrated the speedups up to 63x when comparing the proposed approach to a single-threaded implementation of a similar CEC engine. A practical impact of such a speedup, for instance, is the runtime reduction from 19 h to only 18 min when checking equivalence of AND-inverter graphs comprising more than 20 million nodes. Therefore, the proposed solution presents great potential for improving current electronic design automation environments.