Au fur et à mesure que la complexité s'accroit, il devient nécessaire de définir de nouvelles méthodes permettant de la gérer. Une des façons de maîtriser cette complexité est d'élever le niveau d'abstraction des spécifications en utilisant des langages de spécification systèmes. D'un autre côté, l'élévation du niveau d'abstraction augmente le fossé entre les concepts utilisés pour la spécification (processus communicants, communication abstraite) et ceux utilisés par les langages de description de matériel. Bien que ces langages soient bien adaptés à la spécification et la validation de systèmes complexes, les concepts qu'ils manipulent ne sont pas aisément transposables sur ceux des langages de description de matériels. Il est donc nécessaire de définir de nouvelles méthodes permettant une synthèse efficace à partir de spécifications systèmes. Le sujet de cette thèse est la présentation d'une approche de génération de code C et VHDL à partir de spécifications systèmes en SDL. Cette approche résout la principale difficulté rencontrée par les autres approches, à savoir la communication inter-processus. La communication SDL peut être traduite en VHDL en vue de la synthèse. Cela est rendu possible par l'utilisation d'une forme intermédiaire qui supporte un modèle de communication générale qui autorise la représentation pour la synthèse de la plupart des schémas de communication. Cette forme intermédiaire permet d'appliquer au système un ensemble d'étapes de raffinement pour obtenir la solution désirée. La principale étape de raffinement, appelée synthèse de la communication, détermine le protocole et les interfaces utilisés par les différents processus pour communiquer. la spécification raffinée peut être traduite en C et VHDL pour être utilisée par des outils du commerce. Nous illustrons la faisabilité de cette approche par une application à un système de télécommunication : le protocole TCP/IP sur ATM.

Thesis (Ph. D.)--Oregon Graduate Institute, 2000.

We present the first dynamic algorithm that maintains a clique tree representation of a chordal graph and supports the following operations: (1) query whether deleting or inserting an arbitrary edge preserves chordality, (2) delete or insert an arbitrary edge, provided it preserves chordality. We give two implementations. In the first, each operation runs in O( n) time, where n is the number of vertices. In the second, an insertion query runs in O(log² n) time, an insertion in O(n) time, a deletion query in O(n) time, and a deletion in O(n log n) time. We also introduce the clique-separator graph representation of a chordal graph, which provides significantly more information about the graph's structure than the well-known clique tree representation. We present fundamental properties of the clique-separator graph and additional properties when the input graph is interval. We then introduce the train tree representation of interval graphs and use it to decide whether there is a certain linear ordering of the graph's maximal cliques. This yields a fully dynamic algorithm to recognize interval graphs in O(n log n) time per edge insertion or deletion. The clique-separator graph may lead to dynamic algorithms for every proper subclass of chordal graphs, and the train tree may lead to fast dynamic algorithms for problems on interval graphs. / Graduate

Call number: LD2668 .T4 1986 B368 / Master of Science / Computing and Information Sciences

Hardware description languages provide digital system designers with a convenient, compact method for describing complex circuits. A Hardware Programming Language (AHPL) is a powerful description language based on the APL programming language. AHPL circuit descriptions can be unambiguously translated into a logic gate network using the HPCOM hardware compiler. The initial discussion section covers the conversion of the VAX version of HPCOM into a version which will run on MS-DOS microcomputers. The major portion of the research focuses on the development, use, and application of a graphics display tool for HPCOM-generated networks. The display package, SUBGRAPH, allows selected subgraphs of a network to be viewed and/or printed. The discussion of this research concludes with an extensive example of the complete circuit generation and graphics display sequence. The printed graphics examples feature cases of particular interest for test generation.

Σκοπός της παρούσας διπλωματικής ήταν η δημιουργία ενός testbench για το ηλεκτρονικό τμήμα της φορητής αντλίας έγχυσης φαρμάκου με χρήση σύριγγας. Η αντλία έγχυσης φαρμάκου με χρήση σύριγγας υπάρχει σε προγραμματιζόμενη και σε μη προγραμματιζόμενη έκδοση. Για την περίπτωση της προγραμματιζόμενης συσκευής χρησιμοποιείται, για τον έλεγχο, ένα TRIPLEX LCD σε συνδυασμό με τρία πλήκτρα (up, down, enter) και ένα Buzzer. Για τη μη προγραμματιζόμενη, που θα έχουμε σταθερό ρυθμό παλμοδότησης - έγχυσης φαρμάκου, δεν θα υπάρχουν τα εξωτερικά πλήκτρα και το display. Αρχικός στόχος ήταν η δημιουργία μιας μονάδας που να ενεργοποιεί τη συσκευή, να είναι ικανή να αλλάζει τις καταστάσεις της, να ενεργοποιεί όλα τα πιθανά σφάλματα και κάποια πιθανά mismatches, ώστε να διαπιστώνεται η σωστή λειτουργία της. Προφανώς για το σκοπό αυτό ήταν απαραίτητη η “αποκωδικοποίηση” όλων των πιθανών καταστάσεων της συσκευής. Απαραίτητη προϋπόθεση, λοιπόν, ήταν η δημιουργία μιας οντότητας που να μπορεί, βάση προεπιλεγμένων εισόδων, να μεταβάλει την τρέχουσα κατάσταση της συσκευής. Η δυνατότητα επιλογής των εισόδων γίνεται με 3 διανύσματα εισόδων (λέξεις), το καθένα από τα οποία θα μεταβάλλει αντίστοιχα τη κατάσταση της συσκευής. Πρωταρχικός στόχος ήταν η δυνατότητα ενεργοποίησης της συσκευής, επιλογής του mode της (προγραμματιζόμενη ή μη) και εναλλαγής των καταστάσεών της. Για τη μη προγραμματιζόμενη συσκευή οι πιθανές καταστάσεις λειτουργίας της είναι η ΟΝ (ενεργοποιημένη) και η OFF (απενεργοποιημένη). Το μοτέρ λειτουργεί με σταθερό ρυθμό παλμοδότησης επομένως δεν υπάρχουν άλλες πιθανές καταστάσεις. Η προγραμματιζόμενη έχει τη δυνατότητα αλλαγής του ρυθμού κίνησης του μοτέρ. Η δυνατότητα αυτή παρέχεται από τα πλήκτρα UP και DOWN. Κάθε αλλαγή στην τιμή του ρυθμού κίνησης του δρομέα γίνεται αποδεκτή αν και μόνον αν πατηθεί το πλήκτρο ENTER. Οι καταστάσεις, λοιπόν, στις οποίες μπορεί να βρεθεί η συσκευή είναι οι: ΟΝ, ΟFF, UP, DOWN, ENTER, NO_ENTER, MODE 0, MODE 1. Οι καταστάσεις MODE 0, MODE 1, έχουν να κάνουν με την επιλογή της συσκευής. Η MODE 0 αφορά την επιλογή της προγραμματιζόμενης ενώ η MODE 1 τη μη προγραμματιζόμενη. Η NO_ENTER επιλέχθηκε για την περίπτωση που κατά τη μετάβαση σε μια UP ή DOWN κατάσταση δεν έχει πατηθεί τo ΕΝΤΕR. Η ενεργοποίηση των παραπάνω καταστάσεων θα γίνεται με επιβολή του αντίστοιχου bit στην τιμή “1”. Κατά την ενεργοποίηση της προγραμματιζόμενης συσκευής, πραγματοποιούνται κάποιοι έλεγχοι. Στην κατάσταση ΟΝ, το κύκλωμα επίβλεψης της μπαταρίας ανιχνεύει την κατάσταση low battery και dead battery, ενώ ταυτόχρονα ελέγχεται αν οι συχνότητες παλμοδότησης του κινητήρα f1και f2 διαφέρουν περισσότερο από 5%. Πραγματοποιούνται , λοιπόν, κάποιοι έλεγχοι που σαν στόχο έχουν την ανίχνευση σφάλματος στη λειτουργία της συσκευής. Σκοπός, λοιπόν, του δεύτερου διανύσματος ελέγχου είναι η ενεργοποίηση αυτών των σφαλμάτων ώστε να διαπιστωθεί η εύρυθμη λειτουργία των διεργασιών ανίχνευσής των από τη συσκευή. Επιλέχθηκε για το σκοπό αυτό ένα διάνυσμα εισόδου, ενεργοποίησης αυτών των σφαλμάτων, 7 bits. Για να γίνει η συσκευή ΟΝ πρέπει, εκτός των άνω επιτυχών ελέγχων, όλες οι διπλές είσοδοι (mode1-mode2, run1-run2, pause1-pause2) να μην έχουν διαφορετική τιμή (mismatch). Aν συμβεί οποιοδήποτε mismatch error στις εισόδους αυτές χτυπά το buzzer. Η πρόκληση αυτού του σφάλματος έγινε με ένα διάνυσμα εισόδου 5 bits. Υλοποιήθηκαν, λοιπόν, τρεις οντότητες καθεμία εκ των οποίων προκαλούσε μεταβολή στην τρέχουσα κατάσταση της συσκευής, είτε σφάλμα είτε απλώς μετάβαση από OFF σε ON κλπ. Η τελική σύνδεση των τριών οντοτήτων σε μία και η επικοινωνία αυτής της οντότητας με τη συσκευή αποτέλεσε το τελικό στάδιο της διπλωματικής. Η καταγραφή των εξομοιώσεων και η όλη συμπεριφορά του υλοποιηθέν μοντέλου απέδειξε τη σωστή επικοινωνία του με τη συσκευή . Ο κώδικας περιγραφής του μοντέλου εκσφαλμάτωσης της συσκευής έγινε σε VHDL ενώ για τις εξομοιώσεις χρησημοποιήθηκε ο εξομοιωτής της Model Technology V-System και Model Sim. / --

Le temps de mise sur le marché et les coûts d’implantation sont les deux critères principaux à prendre en compte dans l'automatisation du processus de conception de systèmes numériques. Les applications de traitement du signal utilisent majoritairement l'arithmétique virgule fixe en raison de leur coût d'implantation plus faible. Ainsi, une conversion en virgule fixe est nécessaire. Cette conversion est composée de deux parties correspondant à la détermination du nombre de bits pour la partie entière et pour la partie fractionnaire. Le raffinement d'un système en virgule fixe nécessite d'optimiser la largeur des données en vue de minimiser le coût d'implantation tout en évitant les débordements et un bruit de quantification excessif. Les applications dans les domaines du traitement d'image et du signal sont tolérantes aux erreurs si leur probabilité ou leur amplitude est suffisamment faible. De nombreux travaux de recherche se concentrent sur l'optimisation de la largeur de la partie fractionnaire sous contrainte de précision. La réduction du nombre de bits pour la partie fractionnaire conduit à une erreur d'amplitude faible par rapport à celle du signal. La théorie de la perturbation peut être utilisée pour propager ces erreurs à l'intérieur des systèmes à l'exception du cas des opérations un- smooth, comme les opérations de décision, pour lesquelles une erreur faible en entrée peut conduire à une erreur importante en sortie. De même, l'optimisation de la largeur de la partie entière peut réduire significativement le coût lorsque l'application est tolérante à une faible probabilité de débordement. Les débordements conduisent à une erreur d'amplitude élevée et leur occurrence doit donc être limitée. Pour l'optimisation des largeurs des données, le défi est d'évaluer efficacement l'effet des erreurs de débordement et de décision sur la métrique de qualité associée à l'application. L'amplitude élevée de l'erreur nécessite l'utilisation d'approches basées sur la simulation pour évaluer leurs effets sur la qualité. Dans cette thèse, nous visons à accélérer le processus d'évaluation de la métrique de qualité. Nous proposons un nouveau environnement logiciel utilisant des simulations sélectives pour accélérer la simulation des effets des débordements et des erreurs de décision. Cette approche peut être appliquée à toutes les applications de traitement du signal développées en langage C. Par rapport aux approches classiques basées sur la simulation en virgule fixe, où tous les échantillons d'entrée sont traités, l'approche proposée simule l'application uniquement en cas d'erreur. En effet, les dépassements et les erreurs de décision doivent être des événements rares pour maintenir la fonctionnalité du système. Par conséquent, la simulation sélective permet de réduire considérablement le temps requis pour évaluer les métriques de qualité des applications. De plus, nous avons travaillé sur l'optimisation de la largeur de la partie entière, qui peut diminuer considérablement le coût d'implantation lorsqu'une légère dégradation de la qualité de l'application est acceptable. Nous exploitons l'environnement logiciel proposé auparavant à travers un nouvel algorithme d'optimisation de la largeur des données. La combinaison de cet algorithme et de la technique de simulation sélective permet de réduire considérablement le temps d'optimisation. / Time-to-market and implementation cost are high-priority considerations in the automation of digital hardware design. Nowadays, digital signal processing applications use fixed-point architectures due to their advantages in terms of implementation cost. Thus, floating-point to fixed-point conversion is mandatory. The conversion process consists of two parts corresponding to the determination of the integer part word-length and the fractional part world-length. The refinement of fixed-point systems requires optimizing data word -length to prevent overflows and excessive quantization noises while minimizing implementation cost. Applications in image and signal processing domains are tolerant to errors if their probability or their amplitude is small enough. Numerous research works focus on optimizing the fractional part word-length under accuracy constraint. Reducing the number of bits for the fractional part word- length leads to a small error compared to the signal amplitude. Perturbation theory can be used to propagate these errors inside the systems except for unsmooth operations, like decision operations, for which a small error at the input can leads to a high error at the output. Likewise, optimizing the integer part word-length can significantly reduce the cost when the application is tolerant to a low probability of overflow. Overflows lead to errors with high amplitude and thus their occurrence must be limited. For the word-length optimization, the challenge is to evaluate efficiently the effect of overflow and unsmooth errors on the application quality metric. The high amplitude of the error requires using simulation based-approach to evaluate their effects on the quality. In this thesis, we aim at accelerating the process of quality metric evaluation. We propose a new framework using selective simulations to accelerate the simulation of overflow and un- smooth error effects. This approach can be applied on any C based digital signal processing applications. Compared to complete fixed -point simulation based approaches, where all the input samples are processed, the proposed approach simulates the application only when an error occurs. Indeed, overflows and unsmooth errors must be rare events to maintain the system functionality. Consequently, selective simulation allows reducing significantly the time required to evaluate the application quality metric. 1 Moreover, we focus on optimizing the integer part, which can significantly decrease the implementation cost when a slight degradation of the application quality is acceptable. Indeed, many applications are tolerant to overflows if the probability of overflow occurrence is low enough. Thus, we exploit the proposed framework in a new integer word-length optimization algorithm. The combination of the optimization algorithm and the selective simulation technique allows decreasing significantly the optimization time.

Thesis (M.S.E.C.E.)--Baylor University, 2008. / Includes bibliographical references (p. 322-323)

Techn. Hochsch., Diss. u.d.T.: Hoffmann, Andreas: A methodology for the efficient design of application-specific instruction-set processors using the machine description language LISA--Aachen, 2002.

Thesis (M.S. in Electrical Engineering)--Naval Postgraduate School, March 2005. / Thesis Advisor(s): Douglas J. Fouts. Includes bibliographical references (p. 61). Also available online.