Effiziente Erfüllbarkeitsalgorithmen für die Generierung von Testmustern

• Antragsteller: Professor Dr. Rolf Drechsler
• Fachliche Zuordnung: Sicherheit und Verlässlichkeit, Betriebs-, Kommunikations- und verteilte Systeme
• Förderung: Förderung von 2006 bis 2010
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 15765440

• Erstellungsjahr: 2010

Zusammenfassung der Projektergebnisse

Der Produktionstest ist ein wesentlicher Bestandteil des Entwurfsablaufs von integrierten Schaltungen (Chips). Aufgabe ist es, Produktionsfehler zu erkennen und somit sicherzustellen, dass kein defekter Chip dem Kunden ausgeliefert wird. Mit einer Menge an Eingangsstimuli (sog. Testmuster) wird die Korrektheit jeder einzelnen Schaltung überprüft. Die Testmuster werden zuvor bezüglich eines Fehlermodells berechnet. Verfahren zur Automatischen Testmustergenerierung (ATPG) basierend auf dem Booleschen Erfüllbarkeitsproblem wurden in den frühen 90er Jahren vorgestellt. Praktische Anwendung fanden sie jedoch erst mit dem Aufkommen moderner SAT Beweiser vor wenigen Jahren. Es zeigte sich, dass diese Verfahren im industriellen Umfeld sehr robuste Ergebnisse liefern, die mangelnde Performanz jedoch einen Einsatz erschweren. SAT-basierte Testmustergenerierung effektiv und effizient für praktische Problemstellungen einzusetzen war Ziel des Projekts. Das Hauptaugenmerk lag in der • Verbesserung des Laufzeitverhaltens und der Robustheit • Verbesserung der Qualität durch die Erweiterung auf neue Fehlermodelle Hierfür wurden nach der Integration aktueller SAT Techniken zahlreiche Optimierungsansätze vorgeschlagen. Mittels Logikoptimierungen konnten beispielsweise komplexe SAT Instanzen vereinfacht werden. Dies führte zu einer Beschleunigung der Lösungszeit. Eine wichtige Erkenntnis lieferte eine detaillierte Laufzeitanalyse der angewandten Algorithmen. Es zeigte sich, dass die Generierung der SAT Instanzen oft mehr Zeit in Anspruch nimmt, als das Finden einer Lösung. Durch Optimierung der Instanzgenerierung konnte der gesamte Klassi?zierungsprozess weiter beschleunigt werden. Da die Bedeutung von dynamischen Fehlermodellen durch das Fortschreiten der Technologie wächst, wurde speziell auf die SAT-basierte Testmustergenerierung dieser Fehlermodelle eingegangen. Es wurden effiziente SAT Formulierungen entwickelt welche speziell auf die Generierung qualitativ hochwertiger Testmuster fokussieren. Da die Generierung für dynamische Fehlermodelle typischerweise komplexer und daher laufzeitintensiver ist, wurden neue SAT Techniken vorgestellt, welche strukturelles Wissen über das Problem ausnutzen. Dies resultiert in stark reduzierter Laufzeit und gestiegener Robustheit SAT-basierter ATPG Verfahren. Die Erkenntnisse des Projekts haben zur Publikation von bisher zwei Büchern, vier Zeitschriftenartikeln und zahlreichen Konferenzbeiträgen beigetragen. Weiterhin wurden sechs Diplomarbeiten in diesem Themengebiet erfolgreich bearbeitet. Ferner sind Arbeiten im Rahmen des Projekts Gegenstand zweier abgeschlossener Dissertationen sowie zweier Dissertationen, welche kurz vor der Fertigstellung stehen.

Projektbezogene Publikationen (Auswahl)

• Increasing Robustness and Usability of Circuit Design Tools by Using Formal Techniques. Dissertation, 2006
  G. Fey
  
• Boolean Techniques in Testing of Digital Circuits. Dissertation, 2007
  J. Shi
  
• Combining multi-valued logics in SAT-based ATPG for path delay faults. In Proceedings of the ACM & IEEE International Conference on Formal Methods and Models for Codesign, pages 181–187, 2007
  S. Eggersglüß, G. Fey, R. Drechsler, A. Glowatz, F. Hapke, and J. Schloeffel
  
• Experimental studies on SAT-based ATPG for gate delay faults. In Proceedings of the International Symposium on Multiple-Valued Logic, 2007
  S. Eggersglüß, D. Tille, G. Fey, R. Drechsler, A. Glowatz, F. Hapke, and J. Schloeffel
  
• Improving test pattern compactness in SAT-based ATPG. In Proceedings of the IEEE Asian Test Symposium, pages 445–450, 2007
  S. Eggersglüß and R. Drechsler
  
• Instance generation for SAT-based ATPG. In Proceedings of the IEEE Workshop on Design and Diagnosis of Electronic Circuits and Systems, pages 153–156, 2007
  D. Tille, G. Fey, and R. Drechsler
  
• SAT-based ATPG for path delay faults in industrial circuits. In IEEE European Test Symposium, Informal Digest of Papers, 2007
  S. Eggersglüß, G. Fey, R. Drechsler, A. Glowatz, F. Hapke, and J. Schloeffel
  
• SAT-based ATPG for path delay faults in sequential circuits. In Proceedings of the IEEE International Symposium on Circuits and Systems, pages 3671–3674, 2007
  S. Eggersglüß, G. Fey, and R. Drechsler
  
• Studies on integrating SAT-based ATPG in an industrial environment. In Proceedings GI/GMM/ITG-Workshop Testmethoden und Zuverlässigkeit von Schaltungen und Systemen, 2007
  D. Tille, S. Eggersglüß, G. Fey, R. Drechsler, A. Glowatz, F. Hapke, and J. Schloeffel
  
• Incremental SAT-instance generation for SAT-based ATPG. In Proceedings of the IEEE Workshop on Design and Diagnosis of Electronic Circuits and Systems, pages 68–73, 2008
  D. Tille and R. Drechsler
  
• On acceleration of SAT-based ATPG for industrial designs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27(7):1329–1333, 2008
  R. Drechsler, S. Eggersglüß, G. Fey, A. Glowatz, F. Hapke, J. Schloeffel, and D. Tille
  
• On the influence of Boolean encodings in SAT-based ATPG for path delay faults. In Proceedings of the International Symposium on Multiple-Valued Logic, pages 94–99, 2008
  S. Eggersglüß and R. Drechsler
  
• Robust tests for transition faults with long propagation paths using Boolean satisfiability. In IEEE European Test Symposium, Informal Digest of Papers, 2008
  S. Eggersglüß, D. Tille, and R. Drechsler
  
• Robustness and Usability in Modern Design Flows. Springer, 2008
  G. Fey and R. Drechsler
  
• A fast untestability proof for SAT-based ATPG. In Proceedings of the IEEE Symposium on Design and Diagnosis of Electronic Circuits and Systems, pages 38–43, 2009
  D. Tille and R. Drechsler
  
• A two-stage SAT-based ATPG approach with reduced switching activity. In International Workshop on Impact of Low-Power design on Test and Reliability, 2009
  S. Eggersglüß, D. Tille, and R. Drechsler
  
• Advanced techniques for automatic test pattern generation using boolean satis?ability. In IEEE European Test Symposium, Student’s Forum, 2009
  D. Tille
  
• Effiziente Erfüllbarkeitsalgorithmen für die Generierung von Testmustern. it - information technology, 51(2):102–111, 2009
  R. Drechsler, S. Eggersglüß, G. Fey, J. Schloeffel, and D. Tille
  
• Increasing robustness of SAT-based delay test generation using efficient dynamic learning techniques. In Proceedings of the IEEE European Test Symposium, pages 81–86, 2009
  S. Eggersglüß and R. Drechsler
  
• Robust algorithms for high quality test pattern generation using boolean satisfiability. In IEEE Design, Automation and Test in Europe, PhD Forum, 2009
  S. Eggersglüß
  
• SAT-based automatic test pattern generation. In Dagstuhl Seminar Proceedings, 2009
  R. Drechsler, S. Eggersglüß, G. Fey, and D. Tille
  
• Speeding up SAT-based ATPG using dynamic clause activation. In Proceedings of the IEEE Asian Test Symposium, pages 177–182, 2009
  S. Eggersglüß, D. Tille, and R. Drechsler
  
• Structural heuristics for SAT-based ATPG. In Proceedings of the IFIP/IEEE International Conference on Very Large Scale Integration, 2009
  D. Tille, S. Eggersglüß, H. M. Le, and R. Drechsler
  
• Test Pattern Generation using Boolean Proof Engines. Springer, 2009
  R. Drechsler, S. Eggersglüß, G. Fey, and D. Tille
  
• Using a two-dimensional fault list for compact automatic test pattern generation. In IEEE Latin-American Test Workshop, 2009
  M. Messing, A. Glowatz, J. Schloeffel, and R. Drechsler
  
• Improving CNF representations in SAT-based ATPG for industrial designs using BDDs. In Proceedings of the IEEE European Test Symposium, 2010
  D. Tille, S. Eggersglüß, R. Krenz-Bååth, J. Schloeffel, and R. Drechsler