Title page for ETD etd-02062012-153606


Type of Document Master's Thesis
Author Misra, Supratik Kumar
URN etd-02062012-153606
Title Efficient Graph Techniques for Partial Scan Pattern Debug and Bounded Model Checkers
Degree Master of Science
Department Electrical and Computer Engineering
Advisory Committee
Advisor Name Title
Hsiao, Michael S. Committee Chair
Abbott, A. Lynn Committee Member
Shukla, Sandeep K. Committee Member
Keywords
  • Directed Acyclic Graph
  • Partial Scan Design
  • Pattern Debugger
  • Implication Graphs
Date of Defense 2012-02-03
Availability unrestricted
Abstract
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.

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Misra_SK_T_2012.pdf 772.64 Kb 00:03:34 00:01:50 00:01:36 00:00:48 00:00:04

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

If you have questions or technical problems, please Contact DLA.