Η συνεχής μείωση των διαστάσεων των ψηφιακών κυκλωμάτων σε συνδυασμό με την ολοένα αυξανόμενη πολυπλοκότητά τους, έχει οδηγήσει στην απαίτηση για αξιοπιστία και συνεπώς στην εφαρμογή τεχνικών ελέγχου για την εξασφάλιση της ορθής λειτουργίας τους. Οι βασικοί τρόποι εφαρμογής του ελέγχου σε ένα κύκλωμα μετά την κατασκευή του και την τοποθέτησή του στη συσκευασία είναι ο εξωτερικός (off-chip – εξολοκλήρου χρήση εξωτερικού ελεγκτή ATE), ο BIST (Built-In Self Test – μηδενική χρήση ATE) και ο ενσωματωμένος (embedded – συνδυασμός χρήσης ATE με ενσωματωμένες δομές ελέγχου). Η συγκεκριμένη διπλωματική εργασία επικεντρώνεται στη χρήση του ενσωματωμένου ελέγχου και συγκεκριμένα σε μια κατηγορία αυτού που ονομάζεται εμφώλευση συνόλου δοκιμής (test set embedding) στην οποία το σύνολο δοκιμής ενσωματώνεται σε μια μεγαλύτερη ακολουθία καταστάσεων ενός κυκλώματος παραγωγής διανυσμάτων δοκιμής. Σε αυτή τη διπλωματική εργασία προτείνεται μια νέα μέθοδος για ενσωματωμένο έλεγχο που κάνει χρήση της ανατροφοδότησης (reseeding) για έλεγχο με χρήση ολισθητή γραμμικής ανάδρασης (LFSR). Η μέθοδος αυτή χρησιμοποιείται είτε σε απλές αρχιτεκτονικές ελέγχου με LFSR, είτε σε πολυφασικές αρχιτεκτονικές, πάντα για κυκλώματα με πολλαπλές αλυσίδες. Στην πολυφασική αρχιτεκτονική εκμεταλλευόμαστε τις ακολουθίες από bits που εξάγονται από διάφορες βαθμίδες ενός LFSR, το οποίο χρησιμοποιείται για την παραγωγή διανυσμάτων δοκιμής, για να κωδικοποιήσουμε το σετ ελέγχου της υπό δοκιμή λειτουργικής μονάδας. Παρουσιάζεται ένας νέος αλγόριθμος, ο οποίος περιλαμβάνει τέσσερα κριτήρια για την αποδοτική επιλογή νέων αρχικών καταστάσεων και των βαθμίδων του LFSR. Τέλος παρουσιάζεται και μια μεθοδολογία μείωσης του μήκους της παραγόμενης ακολουθίας δοκιμής. Στη συνέχεια και για να συγκρίνουμε τα αποτελέσματα που εξάγονται από την παραπάνω μέθοδο υλοποιήθηκε μια νέα τεχνική που έχει προταθεί πρόσφατα στη βιβλιογραφία. Η μέθοδος αυτή καλείται REusing Scan chains for test Pattern decompressIoN (RESPIN) και έχει κύριο χαρακτηριστικό την εμφώλευση του συνόλου δοκιμής. Σύμφωνα με τη μέθοδο αυτή η αποσυμπίεση των διανυσμάτων που ελέγχουν μια λειτουργική μονάδα γίνεται με τη χρήση αλυσίδων ελέγχου μιας δεύτερης λειτουργικής μονάδας που βρίσκεται μέσα στο chip και που τη στιγμή του ελέγχου είναι σε αδρανή κατάσταση. Έπειτα από εκτενή σύγκριση των δυο προαναφερθέντων τεχνικών καθώς και άλλων τεχνικών που αναφέρονται στη βιβλιογραφία καταλήξαμε στο συμπέρασμα ότι ο συνδυασμός του αλγόριθμου επιλογής νέων αρχικών καταστάσεων ενός LFSR με την τεχνική μείωσης των ακολουθιών ελέγχου αποτελεί ελκυστική λύση και παρέχει καλύτερα αποτελέσματα τόσο ως προς το πλήθος των δεδομένων που αποθηκεύονται στο ΑΤΕ, όσο και ως προς το μήκος των ακολουθιών δοκιμής. / The continual reduction of digital systems’ size in combination to the increase of their complexity, leads to the need of reliability. Consequently it is necessary to apply testing techniques in order to ensure the right functionality. The ways to apply the testing in an in package circuit is the external (off-chip – total use of the external ATE), the BIST (Built-In Self Test – no use of ATE) and the embedded (use of external ATE in combination to embedded test structures). This diploma thesis focus in the embedded testing and particular in test set embedding. In this technique the test set is embodied in a larger state sequence of a test pattern generator circuit. In this diploma thesis we suggest a new method of embedded testing which uses the reseeding of a LFSR. This method is used either in simple architectures with LFSR, or in multiphase architectures, always for circuits with multiple scan chains. In the multiphase architecture we take advantage of the sequence of bits that are driven by the various stages of a LFSR, which is used to generate test patterns, in order to embody the test set of the circuit under test. We present a new algorithm, which include four standards for the efficient selection of new seeds and states of the LFSR. Finally, we present a new method for test sequence length reduction. After that and in order to compare the results of the above method we implement a new technique, which has been suggested recently in the bibliography. This method is called REusing Scan chains for test Pattern decompressIoN (RESPIN) and its main characteristic is the test set embedding. According to this method, the decompression of test patterns is accomplished using the scan chains of another on-chip module, which is in idle state during the test. After a thorough comparison of these two techniques we conclude that the combination of the seed selection algorithm with the test sequence length reduction technique comprise an attractive solution and gives better results for the amount of data to be stored in the external ATE and for the test sequence length.

Στην παρούσα μεταπτυχιακή εργασία περιγράφεται η διαδικασία συνδυασμού προβλημάτων Επιχειρησιακής Έρευνας με την μεθοδολογία εύρεσης συγκριτικής αποδοτικότητας (DEA). Αρχικά, παρουσιάζεται μια γενική περιγραφή της μεθόδου DEA και μια συνοπτική επισκόπηση της σχετικής βιβλιογραφίας. Παρουσιάζεται ο τρόπος συνδυασμού της μεθόδου DEA και δύο κλασσικών μοντέλων χωροθέτησης εγκαταστάσεων, του μοντέλου με περιορισμό και του αντίστοιχου μοντέλου χωρίς περιορισμό στην χωρητικότητα. Για την επίτευξη αυτού του στόχου γίνονται οι απαραίτητοι χειρισμοί στην μέθοδο DEA ούτως ώστε να μπορεί να υπολογίζεται η αποδοτικότητα για όλες τις μονάδες λήψης απόφασης ταυτόχρονα – μέθοδος ταυτόχρονης DEA (Simultaneous DEA), εφόσον το κλασσικό μοντέλο βρίσκει την αποδοτικότητα μιας μονάδας λύνοντας μια φορά το γραμμικό πρόβλημα με τους συντελεστές βαρύτητας αυτής της μονάδας. Η λύση του πολυκριτήριου προβλήματος αναδεικνύει την αλληλεπίδραση μεταξύ κόστους και αποδοτικότητας, για τη λήψη απόφασης ανάλογα με τις ανάγκες που μπορεί ενυπάρχουν σε ένα αντίστοιχο πραγματικό πρόβλημα. Στην συνέχεια αναπτύσσεται για πρώτη φορά στη διεθνή βιβλιογραφία μια μεθοδολογία για το συνδυασμό δύο άλλων βασικών προβλημάτων, της κάλυψης και της σύμπτυξης συνόλου, αντίστοιχα, με την μεθοδολογία DEA. Στόχος είναι να μορφοποιηθεί ένα μοντέλο γραμμικού προγραμματισμού έτσι ώστε εκτός από το μέτρο απόφασης του κόστους για την κάλυψη ή σύμπτυξη ενός συνόλου-στόχου, από διαθέσιμα υποσύνολα να ληφθεί υπόψη και η αποδοτικότητα του εκάστοτε υποσυνόλου, η οποία εν τέλει θα επηρεάσει και την συνολική αποδοτικότητα του συνόλου-στόχου. Γίνεται ο συνδυασμός των μεθοδολογιών και αναπτύσσονται μεθοδολογίες πολυκριτήριας ανάλυσης που μπορούν να χρησιμοποιηθούν για την λήψη αποφάσεων που αφορούν την αποδοτική και οικονομική κάλυψη ή σύμπτυξη ενός συνόλου. Για την πιστοποίηση και τη διαπίστωση της λειτουργικότητας των προτεινόμενων μεθοδολογιών αναπτύσσονται παραδείγματα προβλημάτων, τα οποία και επιλύονται επιτυχώς. / In the present thesis, the combination of Operation Research Problems with the Data Envelopment Analysis (DEA) is performed in order to make optimal and efficient decisions. Firstly, a general description of DEA and a breath literature review is presented. Then, we show and test location modeling formulations that utilize data envelopment analysis (DEA) efficiency measures to find optimal and efficient facility location/allocation patterns. In addition, to the authors’ best knowledge, the combinations of DEA with the Set Covering Problem as well as Set Packing Problem are formulated as multiobjective problems, for first time in the literature. The main aim of the proposed models is to make cost-effective and efficient decisions regarding the Set Covering and Packing Problem, respectively. Numerical examples are developed in order to validate and test the novel models. The numerical results of multiobjective analysis demonstrate that the proposed methods are able to successfully find optimal and efficient solutions for real set covering, packing and partitioning problems.

Ο όγκος των δεδομένων που απαιτούνται για τον έλεγχο της ορθής λειτουργίας ενός συστήματος που υλοποιείται σε ένα ολοκληρωμένο κύκλωμα είναι πάρα πολύ μεγάλος. Αυτό συνεπάγεται ότι ο χρόνος που απαιτείται για τον έλεγχο της ορθής λειτουργίας του ολοκληρωμένου κυκλώματος μπορεί να είναι απαγορευτικά μεγάλος. Για τη μείωση του απαιτούμενου χρόνου χρησιμοποιούνται διάφορες τεχνικές συμπίεσης των δεδομένων δοκιμής. Κάποιες από αυτές τις τεχνικές βασίζονται στην αποστολή κοινών δεδομένων δοκιμής ταυτόχρονα σε περισσότερες από μία μονάδες του ολοκληρωμένου κυκλώματος. Στην εργασία αυτή υλοποιούμε μια από αυτές τις τεχνικές που βασίζεται στην ύπαρξη μονοπατιών ολίσθησης (scan paths) στις μονάδες του ολοκληρωμένου κυκλώματος. Για την περαιτέρω μείωση του χρόνου που απαιτείται για τον έλεγχο της ορθής λειτουργίας του ολοκληρωμένου κυκλώματος γίνεται χρονοπρογραμματισμός της σειράς με την οποία θα ελεγχθεί η ορθή λειτουργία των διαφόρων μονάδων του ολοκληρωμένου κυκλώματος. / The volume of data that is required to test a SoC is too much big. This means that the time that is required for testing can be prohibitorily big. For the reduction of required time are used various techniques of data compaction.Some of these techniques are based on broadcasting the same value to all of the cores on a SoC.In this work we use one of these techniques that are based on the existence of scan chains in the core (broadcast scan).For further reduction of time that is required for testing a circuit we use a core testing schedule algorithm.

Η διατριβή ασχολείται με το αντικείμενο του ελέγχου ορθής λειτουργίας κυκλωμάτων κατά τον οποίο λαμβάνεται υπόψη και η συμπεριφορά ως προς την κατανάλωση ισχύος. Οι τεχνικές που προτείνονται αφορούν α) τη συμπίεση ενός συνόλου δοκιμής σε περιβάλλον ενσωματωμένου ελέγχου με χρήση εξωτερικών ελεγκτών, β) την εμφώλευση διανυσμάτων δοκιμής σε περιβάλλον ενσωματωμένου ελέγχου και γ) τη μείωση της κατανάλωση ισχύς και ενέργειας σε περιβάλλον εξωτερικού ελέγχου. Η συμπίεση των δεδομένων βασίζεται στην παρατήρηση ότι ένα διάνυσμα δοκιμής μπορεί να παραχθεί από το προηγούμενό του με την αντικατάσταση κάποιων τμημάτων του. Μεγαλύτερη συμπίεση επιτυγχάνεται όταν γίνει αναδιαταξή διανυσμάτων και αναδιάταξη των φλιπ-φλοπ της αλυσίδας ανίχνευσης. Αν η αναδιάταξη των φλιπ-φλοπ γίνει με βάση τη συχνότητα αλλαγών κατάστασης γειτονικών φλιπ-φλοπ τότε επιτυγχάνεται και μείωση της κατανάλωσης ισχύος. Όσον αφορά τις τεχνικές ενσωματωμένου αυτοελέγχου, μελετήθηκε το πρόβλημα της εμφώλευσης διανυσμάτων δοκιμής. Προτάθηκαν αποδοτικά κυκλώματα παραγωγής διανυσμάτων δοκιμής βασισμένα σε ολισθητές γραμμικής ανάδρασης και δέντρα πυλών XOR και σε ολισθητές συνδυασμένους με δέντρα πυλών OR. Όταν τα κυκλώματα υπό έλεγχο είναι κανονικής μορφής όπως είναι οι αθροιστές του αριθμητικού συστήματος υπολοίπων, προτείνονται κυκλώματα που εκμεταλεύονται την κανονική μορφή του συνόλου δοκιμής. Τέλος, σε περιβάλλον εξωτερικού ελέγχου, προτείνονται μέθοδοι αναδιάταξης διανυσμάτων δοκιμής με επανάληψη διανυσμάτων που μειώνουν την κατανάλωση. Οι μέθοδοι αυτές βασίζονται στην επιλογή των κατάλληλων ελάχιστων γεννητικών δέντρων και στη μετατροπή των κατάλληλων επαναλαμβανόμενων διανυσμάτων επιτυγχάνοντας σημαντική μείωση στην κατανάλωση ενέργειας, στη μέση και στη μέγιστη κατανάλωση ισχύος. / The dissertation is focused on VLSI testing while power dissipation is also taken into account. The techniques proposed are: a) test data compression in an embedded test environment, b) test set embedding in a built-in self test environment and c) reduction in test power dissipation in an external testing environment. Test data compression is based on the observation that a test vector can be produced from the previous one by replacing some parts of the previous vector with new parts of the current vector. The compression is even higher when the test vectors are ordered and scan cell reordering is also performed. If the scan cell reordering is based on a transition frequency approach then reduction in power dissipation is also achieved. In the case of built-in self test the problem of test set embedding was studied and efficient circuits based on linear feedback shift registers combined with XOR trees or shift registers combined with OR trees were proposed. If the circuits have a regular structure, such as the structure of residue number system adders, then a circuit taking advantage of the regular form of the test set can be derived. Finally, when external testing is considered, we proposed test vector ordering with vector repetition methods, which reduce power consumption. The methods are based on the selection of the appropriate minimum spanning trees and through the modification of the repeated vectors they achieve considerable savings in energy, average and peak power dissipation.

This thesis presents the development of a fault detection and diagnosis (FDD) procedure capable of capturing, isolating and identifying multiple abrupt parametric faults. The proposed method relies on parameter estimation deployed in a set membership framework. This approach presupposes the utilization of a linearly parametrizable model and the a priori knowledge of bounded noise errors and parameter perturbations. Under these assumptions, a data-hyperspace is generated at every time instant. The goal of set membership identification (SMI) is the determination of the parametric set, formed as an orthotope or ellipsoid, within which the nominal parameter vector resides and intersects with the data-hyperspace. The fault detection mechanism is activated when the normal operation of the SMI procedure is interrupted due to an empty intersection of the data-hyperspace and the estimated parametric set. At the detection instant, a resetting procedure is performed in order to compute the parameter set and the data-hyperspace that contain the varied nominal parameter vector, allowing the SMI algorithm to continue its operation. During the fault isolation, consistency tests are executed, relying on the projections of the worst case parametric sets and the ones arisen from the normal operation of SMI. A faulty component is indicated when these projections do not intersect, while the distance of their centers is used for fault identification. In case of the ellipsoidal SMI-based FDD and under the assumption of a time invariant parameter vector, a new fault detection criterion is defined based on the intersection of support orthotopes of ellipsoids. A more accurate estimation of the time instant of fault occurrence is proposed based on the application of a backward-in-time procedure starting from the fault detection instant, while the conditions under which a fault will never be detected by the orthotopic and ellipsoidal SMI based FDD are provided. This dissertation explores the efficiency of the proposed FDD methodology for capturing failure modes of two microelectromechanical systems; an electrostatic parallel-plate microactuator and a torsionally resonant atomic force microscope. From an engineering point of view, failure modes appeared in the microcomponents of the microactuator and the TR-AFM are encountered as parameter variations and are captured, isolated and identified by the proposed FDD methodology. / Σε αυτή την διατριβή, παρουσιάζεται η ανάπτυξη μιας διαδικασίας Ανίχνευσης και Διάγνωσης Σφαλμάτων, η οποία είναι ικανή να εντοπίζει, απομονώνει και αναγνωρίζει πολλαπλά, απότομα παραμετρικά σφάλματα. H προτεινόμενη μέθοδος βασίζεται στην αναγνώριση του συνόλου συμμετοχής των παραμέτρων. Ο στόχος της Αναγνώρισης Συνόλου Συμμετοχής είναι ο καθορισμός του παραμετρικού συνόλου εντός του οποίου κείται το ονομαστικό διάνυσμα παραμέτρων, δεδομένου ότι το ονομαστικό διάνυσμα παραμέτρων ανήκει επίσης σε έναν υπερχώρο δεδομένων. Το παραμετρικό σύνολο απεικονίζεται ως ένα ορθότοπο ή ένα ελλειψοειδές, λόγω της εύκολης μαθηματικής τους περιγραφής. Έτσι, η διαδικασία Αναγνώρισης Συνόλου Συμμετοχής αντιστοιχεί σε ένα πρόβλημα βελτιστοποίησης, το οποίο αποσκοπεί στον υπολογισμό του ορθοτόπου ή ελλειψοειδούς το οποίο περιέχει το ονομαστικό διάνυσμα παραμέτρων και τέμνεται με τον υπερχώρο δεδομένων. Ο μηχανισμός Ανίχνευσης Σφαλμάτων ενεργοποιείται όταν διακόπτεται η φυσιολογική λειτουργία της Αναγνώρισης Συνόλου Συμμετοχής, λόγω της κενής τομής μεταξύ των εκτιμώμενου παραμετρικού συνόλου και του υπερχώρου δεδομένων. Τη χρονική στιγμή ανίχνευσης ενός σφάλματος, εφαρμόζεται μια διαδικασία επαναρύθμισης που σκοπεύει στον υπολογισμό του νέου παραμετρικού συνόλου, το οποίο περιέχει το μεταβεβλημένο ονομαστικό διάνυσμα παραμέτρων και τέμνεται με το υπερχώρο δεδομένων. Κατά τη διάρκεια της διαδικασίας απομόνωσης του σφάλματος, εκτελούνται τεστ συμβατότητας, τα οποία βασίζονται στις προβολές των νέων παραμετρικών συνόλων και στις προβολές των παραμετρικών συνόλων χείριστης περίπτωσης, ενώ η απόσταση των κέντρων των προβολών χρησιμοποιείται για αναγνώριση σφάλματος. Στην περίπτωση που η Ανίχνευση και Διάγνωση Σφαλμάτων πραγματοποιείται βασιζόμενη στην Αναγνώριση Συνόλου Συμμετοχής με ελλειψοειδή και θεωρώντας το ονομαστικό διάνυσμα παραμέτρων χρονικά αμετάβλητο, ορίζεται ένα νέο κριτήριο ανίχνευσης σφαλμάτων, χρησιμοποιώντας την τομή των περιβαλλόντων ορθοτόπων των ελλειψοειδών. Σε αυτή την περίπτωση, ένα σφάλμα ανιχνεύεται όταν η τομή αυτή είναι κενή. Ακόμη, προτείνεται μια πιο ακριβής εκτίμηση της χρονικής στιγμής εμφάνισης του σφάλματος, ενώ παρατίθενται οι συνθήκες υπό τις οποίες ένα σφάλμα μπορεί να μην ανιχνευθεί ποτέ με την εφαρμογή των προτεινόμενων μεθόδων. Η συγκεκριμένη διατριβή επίσης ερευνά την αποτελεσματικότητα της προτεινόμενης μεθοδολογίας Ανίχνευσης και Διάγνωσης Σφαλμάτων για τον εντοπισμό των τρόπων εκδήλωσης σφαλμάτων σε δύο μικροηλεκτρομηχανικά συστήματα (ΜΗΜΣ), έναν ηλεκτροστατικό μικροεπενεργητή παράλληλων πλακών και ένα ατομικό μικροσκόπιο συντονισμού στρέψης. Από πλευράς μηχανικής, οι τρόποι εκδήλωσης σφαλμάτων στα δομικά στοιχεία του μικροεπενεργητή ή του ατομικού μικροσκοποίου αντιμετωπίζονται ως απότομες παραμετρικές, οι οποίες εντοπίζονται και διαγιγνώσκονται από τις προτεινόμενες μεθόδους.