Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

CLEVER: Divide and Conquer Combinational Logic Equivalence VERification with False Negative Elimination

John MoondanosContact Information, Carl H. SegerContact Information, Ziyad HannaContact Information and Daher KaissContact Information

(6)  Logic Validation Technologies, Intel Corporation, USA
(7)  Strategic CAD Labs, Intel Corporation, USA
Abstract
Formal equivalence verifiers for combinational circuits rely heavily on BDD algorithms. However, building monolithic BDDs is often not feasible for today's complex circuits. Thus, to increase the effectiveness of BDD-based comparisons, divide-and-conquer strategies based on cut-points are applied. Unfortunately, these algorithms may produce false negatives. Significant effort must then be spent for determining whether the failures are indeed real. In particular, if the design is actually incorrect, many cut-point based algorithms perform very poorly. In this paper we present a new algorithm that completely removes the problem of false negatives by introducing normalized functions instead of free variables at cut points. In addition, this approach handles the propagation of input assumptions to cut-points, is significantly more accurate in finding cut-points, and leads to more efficient counter-example generation for incorrect circuits. Although, naively, our algorithm 1 would appear to be more expensive than traditional cut-point techniques, the empirical data on more than 900 complex signals from a recent microprocessor design, shows rather the opposite.

Contact Information John Moondanos
Email: john.moondanos@intel.com

Contact Information Carl H. Seger
Email: carl.seger@intel.com

Contact Information Ziyad Hanna
Email: ziyad.hanna@intel.com

Contact Information Daher Kaiss
Email: daher.kaiss@intel.com
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.106 • Server: MPWEB25
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)