Path delay fault testing for digital VLSI circuits using specialized binary decision diagrams

Abstract

Η αυξημένη πολυπλοκότητα στο σχεδιασμό, καθώς επίσης και οι υψηλές ταχύτητες λειτουργίας των σύγχρονων κυκλωμάτων, τα οποία περιέχουν δισεκατομμύρια ημιαγωγούς (transistors) σε ένα ενιαίο ολοκληρωμένο κύκλωμα, έχουν οδηγήσει στην παραγωγή κυκλωμάτων με απίστευτες ικανότητες. Η ραγδαία αυτή πρόοδος των κυκλωμάτων, μέσα σε ένα αυστηρώς εξελισσόμενο περιβάλλον, έχει οδηγήσει τη διαδικασία ελέγχου μετά την παραγωγή τους σε νέες προκλήσεις. Το αντικείμενο αυτής της διατριβής έχει ως στόχο τη μελέτη του ελέγχου της ορθής λειτουργίας χρονισμού κυκλωμάτων, συγκεκριμένα την ανίχνευση χρονικών παραβάσεων σε κυκλώματα μετά την παραγωγή τους, έτσι ώστε να διασφαλίζεται η χρονική τους ακρίβεια. Συγκεκριμένα, αυτή η διατριβή διερευνά τον εντοπισμό (αναγνώριση) και την παραγωγή διανυσμάτων ελέγχου, τόσο για μονά, όσο και για πολλαπλά σφάλματα χρονικών καθυστερήσεων σε μονοπάτια (Path Delay Faults - PDFs), για κυκλώματα πλήρης σάρωσης αλλά και για κυκλώματα χωρίς δυνατότητα σάρωσης. Ένα πρόβλημα ζωτικής σημασίας για το PDF μοντέλο, που μελετάται στη διατριβή αυτή, είναι η παραγωγή συμπαγών διανυσμάτων ελέγχου σε ψηφιακά κυκλώματα πολύ μεγάλης κλίμακας ολοκλήρωσης (VLSI). Η αναγνώριση μονοπατιών και η παραγωγή διανυσμάτων ελέγχου για αυτά, διερευνάται για διάφορες ταξινομήσεις του PDF μοντέλου. Οι αλγόριθμοι για την παραγωγή διανυσμάτων ελέγχου που προτείνονται σε αυτήν την διατριβή, χρησιμοποιούν παραλλαγές εξειδικευμένων δομών δεδομένων, γνωστές ως δυαδικά διαγράμματα αποφάσεων (Binary Decision Diagrams - BDDs), με τέτοιο τρόπο κατά τον οποίο η απευθείας απαρίθμηση (explicit enumeration) των διαφόρων PDFs να αποφεύγεται. Τα υπό εξέταση μονοπάτια, και PDFs, διερευνήθηκαν με άμεσο τρόπο, χωρίς απαριθμήσεις, κάτι που διευκολύνει τη χρήση τους όσον αφορά την αντιμετώπιση μεγάλου αριθμού PDFs σε ένα κύκλωμα, μέσα σε λογικά χρονικά πλαίσια. Για την περίπτωση των μονών PDFs, τα πειραματικά αποτελέσματα που πάρθηκαν από κυκλώματα πλήρης σάρωσης, επιδεικνύουν την πρακτικότητα της μεθόδου όσον αφορά την πυκνότητα των διανυσμάτων ελέγχου για το σύνολο των κρίσιμων PDFs. Επιπλέων, για την περίπτωση των πολλαπλών PDFs, τα αποτελέσματα δείχνουν ότι μόνο ένας μικρός αριθμός πολλαπλών κρίσιμων PDFs, σε σύγκριση με τον αριθμό των μονών PDFs, χρειάζεται και επαρκεί να εξεταστεί. Ως εκ τούτου, μόνο ένας μικρός αριθμός επιπρόσθετων διανυσμάτων ελέγχου χρειάζεται για να διασφαλιστούν οι χρονικές ενός κυκλώματος. Για κυκλώματα χωρίς δυνατότητες σάρωσης, όπως οι μικροεπεξεργαστές, τα πειράματα δείχνουν ότι η μεθοδολογία που υιοθετείται επιτρέπει τη μείωση του χρόνου παραγωγής των διανυσμάτων ελέγχου, με την επικέντρωση σε κατάλληλα ταξινομημένες δομικά συνεκτικές λίστες σφαλμάτων και την αποφυγή υπολογισμού εντατικών προσομοιώσεων σε επίπεδο πύλης. Τέλος, προτείνεται ένας αποτελεσματικός τρόπος αναγνώρισης και εύρεσης συσχέτισης μεταξύ των φυσικών μονοπατιών ανά ζεύγος, σε ένα σύνολο μονοπατιών. Πέραν της εφαρμογής του στα προβλήματα αναγνώρισης και ελέγχου για PDFs, αυτό το μέτρο έχει σημαντικές επιπτώσεις σε διάφορα προβλήματα αυτοματοποίησης σχεδιασμού, όπως ο ακριβής καθορισμός της μέγιστης καθυστέρησης, ανίχνευση και διάγνωση σφαλμάτων σε ψηφιακά κυκλώματα. Εξετάζοντας την πολυπλοκότητα και τους στενούς χρονικούς περιορισμούς των σύγχρονων κυκλωμάτων, η συσχέτιση αυτή επηρεάζει τόσο την διαδικασία σχεδιασμού όσο και τις μεθοδολογίες ελέγχου που ακολουθούνται της παραγωγής.

Increasing complexity and speed with billions of transistors on a single integrated circuit has let to circuits with incredible capabilities. Circuit advances in a rigorous evolving environment have let manufacturing testing into new test challenges. This thesis studies delay testing, that is detecting the circuit's timing violations and ensuring it's temporal correctness. Specifically, this dissertation investigates the identification and test generation of single and multiple Path Delay Faults (PDFs) for enhanced fully scanned digital circuits as well as circuits with no scan capabilities. A crucial problem for the PDF model is the derivation of compact test sets. The PDF identification and test generation for various PDF classifications is investigated. The newly proposed test generation algorithms, utilize variants of special data structures known as Binary Decision Diagrams (BDDs) in a way that explicit enumeration of the PDFs is avoided. Paths and PDFs, are processed in an implicit and non-enumerative manner, which facilitates their usage in terms of dealing with a large number of circuit paths in reasonable time. For the single PDF case, experimental results on the enhanced full-scanned benchmarks, demonstrate clearly the practicality of the method in terms of test compactness for the critical PDF set. Furthermore, for the multiple PDF set, experimental results indicate that only a small number of critical multiple faults, compared to the number of single critical faults, needs and suffices to be examined. Therefore, only a small number of additional test patterns is needed to guarantee a circuit's timing specifications. For circuits with no scan capabilities such as microprocessors, experiments show that the methodology adopted allows reducing the test generation time, by concentrating on suitably classified structurally coherent fault lists and avoiding computation intensive gate level simulations. Finally, an efficient way of identifying the pairwise physical paths correlation between the paths in a set is proposed. Beyond PDF testing, this metric has important implications in various design automation problems, such as timing analysis, test generation and diagnosis. When considering the complexity and tight timing constraints of modern circuits, this correlation affects both the design process and the testing approaches followed in manufacturing.