2017

 back to the year overview

• Jan Burchard, Dominik Erb, Sudhakar M. Reddy, Adit D. Singh, Bernd Becker
  TSO Tests
  2017 IEEE VLSI Test Symposium (VTS'17)
• Jan Burchard, Felix Neubauer, Pascal Raiola, Dominik Erb, Bernd Becker
  Evaluating the Effectiveness of D-Chains in SAT based ATPG
  2017 IEEE Latin American Test Symposium (LATS'17)
  » show abstract« hide abstract
  Abstract

  With the ever increasing size of today’s Very-Large-Scale-Integration (VLSI) designs new approaches for test pattern generation become more and more popular. One of the best known methods is SAT-based automatic test pattern generation (ATPG) which, in contrast to classical structural ATPG, first generates a mathematical representation of the problem in form of a Boolean formula. A specialized solver evaluates this representation to determine the testability of faults and extracts a test pattern in case a satisfying assignment was found. In order to increase the solving speed introduced the concept of D-chains which add additional information to the mathematical model. In return, this forces the solver to only consider assignments that might lead to a valid test pattern and thus reduce the search space. With the advent of incremental solving new concepts like the backward D-chain or even more recently an indirect D-chain were introduced. However, none of the previous publications tried to analyze and evaluate which of these methods is the most beneficial. In this paper we present a thorough investigation of the different D-chain concepts to evaluate which is the best method for different problems. In addition, we propose a new indirect D-chain algorithm with two extensions. Our experimental results show that depending on the incorporated D-chain the runtime can be reduced tremendously.
• Pascal Raiola, Dominik Erb, Sudhakar Reddy, Bernd Becker
  Accurate Diagnosis of Interconnect Open Defects based on the Robust Enhanced Aggressor Victim Model
  2017 30th International Conference on VLSI Design
  » show abstract« hide abstract
  Abstract

  In addition, it allows to distinguish faults at the same interconnect and thus reducing the area that has to be considered for physical failure analysis. Experimental results show the high efficiency of the new method handling circuits with up to 500,000 non-equivalent faults and considerably increasing the diagnostic resolution.
• Pascal Raiola, Jan Burchard, Felix Neubauer, Dominik Erb, Bernd Becker
  Evaluating the Effectiveness of D-chains in SAT-based ATPG and Diagnostic TPG
  2017 J Electron Test, volume: 33, issue: 6, pages: 751 - 767
  » show abstract« hide abstract
  Abstract

  The ever increasing size and complexity of today’s Very-Large-Scale-Integration (VLSI) designs requires a thorough investigation of new approaches for the generation of test patterns for both test and diagnosis of faults. SAT-based automatic test pattern generation (ATPG) is one of the most popular methods, where, in contrast to classical structural ATPG methods, first a mathematical representation of the problem in form of a Boolean formula is generated, which is then evaluated by a specialized solver. If the considered fault is testable, the solver will return a satisfying assignment, from which a test pattern can be extracted; otherwise no such assignment can exist. In order to speed up test pattern generation, the concept of D-chains was introduced by several researchers. Thereby supplementary clauses are added to the Boolean formula, reducing the search space and guiding the solver toward the solution. In the past, different variants of D-chains have been developed, such as the backward D-chain or the indirect D-chain. In this work we perform a thorough analysis and evaluation of the D-chain variants for test pattern generation and also analyze the impact of different D-chain encodings on diagnostic test pattern generation. Our experimental results show that depending on the incorporated D-chain the runtime can be reduced tremendously.
• Jan Burchard, Dominik Erb, Adit D. Singh, Sudhakar M. Reddy, Bernd Becker
  Fast and Waveform-Accurate Hazard-Aware SAT-Based TSOF ATPG
  2017 Conference on Design, Automation and Test in Europe
  » show abstract« hide abstract
  Abstract

  unaware tests will fail to detect the targeted opens because of test invalidation – these are reliably detected by our new test generation methodology. Importantly, our approach can also be applied to improve the effectiveness of commercial cell aware tests.

2016

 back to the year overview

• Matthias Sauer, Sven Reimer, Daniel Tille, Karsten Scheibler, Dominik Erb, Ulrike Pfannkuchen, Bernd Becker
  Clock Cycle Aware Encoding for SAT-based Circuit Initialization
  2016 GI/ITG Workshop “Testmethoden und Zuverlässigkeit von Schaltungen und Systemen”
• Karsten Scheibler, Dominik Erb, Bernd Becker
  Applying Tailored Formal Methods to X-ATPG
  2016 GI/ITG/GMM Workshop “Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen”
  » show abstract« hide abstract
  Abstract

  However, usually, one can not assume full control of all sequential elements and primary inputs. Therefore, uninitialized flip-flops may occur in the design -- leading to binary but unknown values (X-values). Classically, these X-values are handled by three-valued logic (01X). But this introduces pessimism when X-values reconverge in the circuit. On the other hand, the expressiveness of QBF allows to encode the unknown values accurately -- but comes at the cost of much higher runtimes. Therefore, we presented in [1] an accurate SAT-based CEGAR approach for automatic test pattern generation (ATPG) in presence of X-values. This approach is tailored to and optimized for this specific problem class and could also be used for closely related topics such as equivalence checking in presence of X-values. Although the approach is similar to an existing CEGAR-based 2-QBF solving algorithm, we show that our method has up to 50x lower runtimes. This underlines that an efficient CNF-encoding of a problem together with the fastest available standard solver does not guarantee optimal performance. Tailoring the underlying formal methods to the target problem class may give remarkable speedups on top.
• Dominik Erb, Karsten Scheibler, Michael A. Kochte, Matthias Sauer, Hans-Joachim Wunderlich, Bernd Becker
  Mixed 01X-RSL-Encoding for Fast and Accurate ATPG with Unknowns
  2016 21st Asia and South Pacific Design Automation Conference
  » show abstract« hide abstract
  Abstract

  In this paper, we propose new ATPG techniques to overcome such limitations. An efficient hybrid encoding combines the accuracy of RSL-based modeling with the compactness of conventional three-valued encoding. A low-cost two-valued SAT-based untestability check is able to classify most untestable faults with low runtime. An incremental and event-based accurate fault simulator is introduced to reduce fault simulation effort. The experiments demonstrate the effectiveness of the proposed techniques. On average, over 99.3% of the faults are accurately classified. Both the number of aborts and the total runtime are significantly reduced compared to the state-of-the-art pure RSL-based algorithm. For circuits up to a million gates, the fault coverage could be increased considerably compared to a state-of-the-art commercial tool with very competitive runtimes.
• Der Andere Verlag
  On the Handling of Uncertainty in Test Pattern Generation
  ISBN: 978-3-86247-571-1
  Dominik Erb
• Karsten Scheibler, Dominik Erb, Bernd Becker
  signs
  2016 Conf. on Design, Automation and Test in Europe
  » show abstract« hide abstract
  Abstract

  Therefore, this paper focuses on a new highly incremental CEGAR-based algorithm that overcomes these limitations and hence is completely accurate in presence of unknown values. It relies on a modified SAT-solver tailored to this specific problem. The experimental results for circuits with up to 2.400.000 gates show that this combination allows high accuracy and high scalability at the same time. Compared to a state-of-the-art commercial tool, the fault coverage could be increased significantly. Furthermore, the runtime is reduced remarkably compared to a QBF-based encoding of the problem.

2015

 back to the year overview

• Dominik Erb, Michael A. Kochte, Sven Reimer, Matthias Sauer, Hans-Joachim Wunderlich, Bernd Becker
  Accurate QBF-based Test Pattern Generation in Presence of Unknown Values
  2015 Computer-Aided Design of Integrated Circuits and Systems (TCAD)
  » show abstract« hide abstract
  Abstract

  circuits investigate the increase in fault coverage for conventional deterministic and potential detection requirements for both randomized and clustered X-sources.
• Karsten Scheibler, Dominik Erb, Bernd Becker
  Improving Test Pattern Generation in Presence of Unknown Values beyond Restricted Symbolic Logic
  2015 to be published at European Test Symposium (ETS)
  » show abstract« hide abstract
  Abstract

  In this paper, we improve test generation based on RSL in two directions in order to reduce the gap to QBF further. First, we present techniques to go beyond the accuracy of RSL when generating test patterns. Second, we include a check which is able to accurately identify untestable faults. Experimental results show the high efficiency of the proposed method classifying almost all faults as testable or proving untestability.
• Dominik Erb, Karsten Scheibler, Matthias Sauer, Sudhakar M. Reddy, Bernd Becker
  Multi-Cycle Circuit Parameter Independent ATPG for Interconnect Open Defects
  2015 33rd VLSI Test Symposium (VTS)
  » show abstract« hide abstract
  Abstract

  In this work we extend the validity of CPI tests by introducing so-called multi-cycle CPI tests and single-value CPI tests. By doing so, we significantly improve the coverage of open defects and ensure their detection whilst including the additional effect of leakage currents on opens. Experimental results for circuits with over 500k non-equivalent faults and several thousand aggressors %deriving the new classes of CPI tests show the effectiveness of the newly proposed CPI tests as well as the high efficiency of a new ATPG algorithm to generate these new classes of CPI tests.

2014

 back to the year overview

• Dominik Erb, Karsten Scheibler, Matthias Sauer, Sudhakar M. Reddy, Bernd Becker
  for Interconnect Open Defects
  2014 23nd IEEE Asian Test Symposium (ATS)
  » show abstract« hide abstract
  Abstract

  faults and several thousand aggressors.
• Dominik Erb, Karsten Scheibler, Michael Kochte, Matthias Sauer, Hans-Joachim Wunderlich, Bernd Becker
  Based on Restricted Symbolic Logic
  2014 Int'l Test Conf.
  » show abstract« hide abstract
  Abstract

  more scalable and more robust.
• Dominik Erb, Karsten Scheibler, Matthias Sauer, Bernd Becker
  Efficient SMT-based ATPG for Interconnect Open Defects
  2014 Conf. on Design, Automation and Test in Europe
  » show abstract« hide abstract
  Abstract

  magnitude.
• Dominik Erb, Michael Koche, Matthias Sauer, Stefan Hillebrecht, Tobias Schubert, Hans-Joachim Wunderlich, Bernd Becker
  Exact Logic and Fault Simulation in Presence of Unknowns
  2014 ACM Transactions on Design Automation of Electronic Systems (TODAES), volume: 19, pages: 28:1 - 28:17
  » show abstract« hide abstract
  Abstract

  significantly increased without increasing the test set size.

2013

 back to the year overview

• Dominik Erb, Michael A Kochte, Matthias Sauer, Hans-Joachim Wunderlich, Bernd Becker
  Accurate Multi-Cycle ATPG in Presence of X-Values
  2013 22nd IEEE Asian Test Symposium (ATS)
  » show abstract« hide abstract
  Abstract

  Unknown (X) values in a circuit impair test quality and increase test costs. Classical n-valued algorithms for fault simulation and ATPG, which typically use a three- or four-valued logic for the good and faulty circuit, are in principle pessimistic in presence of X-values and cannot accurately compute the achievable fault coverage. In partial scan or pipelined circuits, X-values originate in non-scan flip-flops. These circuits are tested using multi-cycle tests. Here we present multi-cycle test generation techniques for circuits with X-values due to partial scan or other X-sources. The proposed techniques have been integrated into a multi-cycle ATPG framework which employs formal Boolean and quantified Boolean (QBF) satisfiability techniques to compute the possible signal states in the circuit accurately. Efficient encoding of the problem instance ensures reasonable runtimes. We show that in presence of X-values, the detection of stuck-at faults requires not only exact formal reasoning in a single cycle, but especially the consideration of multiple cycles for excitation of the fault site as well as propagation and controlled reconvergence of fault effects. For the first time, accurate deterministic ATPG for multi-cycle test application is supported for stuck-at faults. Experiments on ISCAS'89 and industrial circuits with X-sources show that this new approach increases the fault coverage considerably.
• Stefan Hillebrecht, Michael A. Kochte, Dominik Erb, Hans-Joachim Wunderlich, Bernd Becker
  Accurate QBF-based test pattern generation in presence of unknown values
  2013 Conf. on Design, Automation and Test in Europe
  » show abstract« hide abstract
  Abstract

  circuits.