Zur Webseite der Uni Stuttgart

Bachelor/Masterarbeit: Effiziente Erzeugung von SAT-Instanzen für Testmustererzeugung

 

Defekte in Chips, die z.B. während der Herstellung eingebracht werden, können zu Fehlfunktionen führen. Deshalb ist ein gründlicher Test jedes gefertigten Chips nötig. Das Ziel der Testmustererzeugung (Automatic Test Pattern Generation, ATPG) ist eine Menge von Eingangsstimuli (Testmuster) zu berechnen, sodass Fehler im Chip entdeckt werden können.

ATPG für einen Zielfehler kann auf eine Instanz des Booleschen Erfüllbarkeitsproblems (SAT) abgebildet werden. SAT-ATPG analysiert jede Fehlerstelle in der Schaltung und findet ein Testmuster, das den Fehler aktiviert und an Schaltungsausgängen beobachtbar macht. Unter Ausnutzung von effizienten SAT-Solvern kann SAT-ATPG die Lösung in akzeptabler Zeit finden oder die Instanz als unerfüllbar klassifizieren (dann ist der Fehler untestbar).

Für große Schaltungen wird jedoch Aufbau der SAT-Instanz selbst ein Engpass. Weil die Instanz für jede untersuchte Fehlerstelle wieder aufgebaut werden muss, trägt der Aufwand zur Konstruktion maßgeblich zur Laufzeit von SAT-ATPG bei.

Das Ziel dieser Arbeit ist es, ein Verfahren zum Aufbau der SAT-Instanz zu entwickeln, das erlaubt die SAT-Instanz für mehrere Zielfehler wiederzuverwenden. Dieses Verfahren kann beispielsweise strukturelle Vorverarbeitung und Analyse der Netzliste der Schaltung verwenden. Die Auswirkungen dieser Optimierung auf die ATPG-Laufzeit soll für größere Benchmark-Schaltungen ausgewertet werden.

Referenzen:

[1] T. Larrabee, "Test pattern generation using Boolean satisfiability," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992, pp. 4-15.

[2] D. Tille, R. Drechsler, “Incremental SAT instance generation for SAT-based ATPG,” In 11th IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems, pp. 1-6, 2008.

[3] S. Eggersgluss, D. Tille, R. Drechsler, “Speeding up SAT-based ATPG using dynamic clause activation,” In Asian Test Symposium, pp. 177-182, 2009.

 

Voraussetzungen:

  • Grundkenntnisse in C++

  • Grundkenntnisse in Hardwarebeschreibungssprachen (Verilog oder VHDL)

 

 

Kontakt:

Dominik Ull (Email: ulldk@iti.uni-stuttgart.de)

Hans-Joachim Wunderlich (Email: wu@informatik.uni-stuttgart.de)