Efficient Graph Techniques for Partial Scan Pattern Debug and Bounded Model Checkers

Continuous advances in VLSI technology have led to more complex digital designs and shrinking transistor sizes. Due to these developments, design verification and manufacturing test have gained more importance and 70 % of the design expenditure in on validation processes. Electronic Design Automation (EDA) tools play a huge role in the validation process with various verification and test tools. Their efficiency have a high impact in saving time and money in this competitive market. Direct Acyclic Graphs (DAGs) are the backbone for most of the EDA tools. DAG is the most efficient data structure to store circuit information and also have efficient backt traversing structure which help in developing reasoning/ debugging tools. In this thesis, we focus on two such EDA tools using graphs as their underlying structure for circuit information storage • Scan pattern Debugger for Partial Scan Designs • Circuit SAT Bounded Model Checkers We developed a complete Interactive Scan Pattern Debugger Suite currently being used in the industry for next generation microprocessor design. The back end is an implication graph based sequential logic simulator which creates a Debug Implication Graph during the logic simulation of the failing patterns. An efficient node traversal mechanism across time frames, in the DIG, is used to perform the root-cause analysis for the failing scan-cells. In addition, the debugger provides visibility into the circuit internals to understand and fix the root-cause. We integrated the proposed technique into the scan ATPG flow for industrial microprocessor designs. We were able to resolve the First Silicon logical pattern failures within hours, which would have otherwise taken a few days of manual effort for root-causing the failure, understanding the root-cause and fixing it. For our circuit SAT implementation, we replace the internal implication graph used by the SAT solver with our debug implication graph (DIG). There is a high amount of circuit unrolling in circuit SAT/ BMC (Bounded Model Checking) problems which creates copies of the same combinational blocks in multiple time frames. This allows us to use the repetitive circuit structure and club it with the CNF database in the SAT solver. We propose a new data structure to store data in a circuit SAT solver which results up to 90% reduction in number of nodes.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Electrical and Computer Engineering

Department dc:contributor.department

Electrical and Computer Engineering

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2012

Author dc:creator

• Misra, Supratik Kumar

Chair dc:contributor.committeechair

• Hsiao, Michael S.

Committee members dc:contributor.committeemember

• Shukla, Sandeep K.
• Abbott, A. Lynn

• Directed Acyclic Graph
• Partial Scan Design
• Pattern Debugger
• Implication Graphs

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Dc Identifier Other

etd-02062012-153606

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/31153