Efficient location-based logic diagnosis of digital circuits

Abstract

Logic diagnosis is the task of finding defects within a random logic circuit based on its faulty behavior. Fast and accurate algorithms for logic diagnosis are an integral part of modern chip development. Classic diagnosis algorithms were often based on fault models which contain a priori assumptions on the behavior of defects. In recent technologies, fault model based approaches become ineffective because defect mechanisms get more and more complex. So research has started on location-based diagnosis algorithms, which use more general fault models or no model at all and report defective substructures directly.

The generality however may also have a negative effect on the accuracy of the diagnosis results. With the lack of a fault model, a diagnosis algorithm has less knowledge on possible or likely malfunctions of a circuit. This increases the search space dramatically and may even lead to defect candidates which are physically impossible. Reducing a priori assumptions while retaining sufficient knowledge on likely defect mechanisms is the key to effective logic diagnosis.

This work introduces the Conditional Line Flip (CLF) calculus as a way to describe arbitrary defects in logic circuits. This generalized fault modeling approach is used to investigate the assumptions made by diagnostic fault models and diagnosis algorithms found in the literature.

The second main contribution of this work is a location-based logic diagnosis algorithm called Partially Overlapping Impact couNTER (POINTER). It builds directly upon the CLF calculus, works independently of any specialized fault model and offers powerful heuristics for sorting defect candidates according to their likelihood in physical chips. The POINTER approach is extended and modified to account for the particular challenges of high precision diagnostics in a lab, during production, and in autonomous online diagnosis in the field.

Experimental results on industrial designs confirm that, despite its generality and lack of application specific knowledge, POINTER performs much better than previous diagnosis approaches. In cases where very high response compaction ratios are used, POINTER even enables fault model independent diagnosis for the first time.

Mit Logik-Diagnose bezeichnet man die Aufgabe, Fehler in logischen Schaltungen anhand der beobachteten Syndrome der Gesamtschaltung zu finden. Schnelle und genaue Algorithmen dafür sind essentieller Bestandteil der modernen Chipentwicklung. Klassische Algorithmen basierten oft auf Fehlermodellen, welche a-priori Annahmen über mögliche Defekte treffen. Das Verhalten von Defekten wird mit fortschreitender Technologie jedoch immer vielfältiger, so dass fehlermodell-basierte Algorithmen immer ineffektiver werden. Damit begann die Erforschung von ortsbasierten Diagnosealgorithmen, die unter weitaus schwächeren Fehlerannahmen defekte Unterstrukturen in Schaltungen direkt auffinden können.

Diese Allgemeingültigkeit kann jedoch auch einen negativen Effekt auf die Präzision der Ergebnisse haben. Mit dem Fehlen eines exakten Fehlermodells hat ein Algorithmus auch weniger Wissen über mögliche und wahrscheinliche Fehlfunktionen eines Chips. Dies erweitert den Suchraum dramatisch und kann sogar zu Diagnoseergebnissen führen, die physikalisch unmöglich sind. Der Schlüssel zu einer effektiven Diagnose ist daher die Reduktion von Annahmen unter Beibehaltung von hinreichendem Wissen über mögliche Defektmechanismen.

Die vorliegende Arbeit führt mit dem Conditional Line Flip (CLF) Kalkül eine Methode ein, um beliebige Defekte in Logik-Schaltungen zu beschreiben. Diese verallgemeinerte Fehlermodellierung wird dann dazu genutzt, die Annahmen und Eigenschaften vorgeschlagener diagnostischer Fehlermodelle und Diagnosealgorithmen zu beleuchten.

Der zweite Hauptbeitrag dieser Arbeit ist ein ortsbasierter Logik-Diagnosealgorithmus namens Partially Overlapping Impact couNTER (POINTER). Er basiert direkt auf dem CLF-Kalkül, arbeitet unabhängig von spezialisierten Fehlermodellen und bietet leistungsfähige Heuristiken zur Sortierung von Defekt-Kandidaten anhand ihrer Wahrscheinlichkeit, tatsächlich im Chip vorzukommen. Der POINTER-Ansatz wird daraufhin noch erweitert, um den speziellen Herausforderungen der Präzisionsdiagnose im Labor, der Diagnose während der Produktion, und der autonomen Diagnose im Feld Rechnung zu tragen.

Die experimentellen Ergebnisse bestätigen, dass POINTER trotz seiner Allgemeingültigkeit und ohne tiefes Wissen über die physikalischen Vorgänge bei Defekten, wesentlich bessere Ergebnisse liefert als bisherige Diagnose-Ansätze. Wenn extreme Test-Antwort-Kompaktierung eingesetzt wird, ermöglicht POINTER sogar erstmals die fehlermodell-unabhängige Diagnose der Syndrome.