Using Constraint Satisfaction for Test Generation
Machine Organization Accomplishment | 1995 - 2006
IBM researchers: Allon Adir, Merav Aharoni, Sigal Asaf, Yael Ben-Haim, Eyal Bin, Odellia Boni, Shadi Copty, Laurent Fournier, Wesam Ibraheem, Yoav Katz, Yehuda Naveh, Gil Shurek
Where the work was done: IBM Haifa Research Laboratory
What we accomplished: Verification of modern hardware designs consumes more than 70 percent of overall efforts put into design. Indeed, the cost of releasing hardware containing serious bugs is tremendous, both from a financial and image perspective. At the same time, the process of creating all possible tests to check the design before it is released (or even cast in silicon) is prohibitively large and complex. IBM has developed and pioneered the application of constraint satisfaction technology, a sub-field of artificial intelligence, to help in automating the design process. In this regard, relevant aspects of the design architecture, as well as expert knowledge about prone-to-bugs areas and tests likely to exorcise them, are modeled as constraints. Sophisticated mathematical algorithms are used as well to solve this set of constraints in order to create a multitude of valid and interesting tests. The science and resulting technology have not only proved primal for the verification of all of IBM's high-end hardware designs; it has since been adopted and applied in virtually all test-benches coming from top vendors and manufacturers in the entire electronics design industry. As a return-on-investment to the scientific community, this technology has also pushed the state of the art in the constraint satisfaction field, as we were challenged by, and provided basic solutions to, such major issues as solution sampling, efficient representation and operations on variables of large domains, soft constraint hierarchy and conditional sub-problems. The work has also given IBM two state-of-the-art generic constraint solvers -- deterministic and stochastic -- which have since been used in business cases far removed from hardware verification.
Related links: Constraint-Based Random Stimuli Generation for Hardware Verification, AI magazine Vol 28 Number 3.
IBM Systems Journal, 2002.
Generating random solutions for constraint satisfaction problems, AAAI 2002.
Constraint Satisfaction for Test Program Generation, International Phoenix Conference on Computers and Communications, March 1995.
Image credit: IBM
BACK TO IBM RESEARCH ACCOMPLISHMENTS