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

<p> Architecture Description Languages were developed to support the abstract level of software structuring that is the subject matter of software architecture. CommUnity is an ADL built on co-ordination principles and a categorical framework to support the composition of specifications of components to form the system's specification. However, an important problem of CommUnity is the lack of support for specifying the system's architectural changes in both the set of components and the connections between them.</p> <p> This thesis presents DynaComm, an extension of CommUnity to support hierarchical design and dynamic reconfiguration of component based systems. Several new language constructs are introduced into DynaComm: subsystems are coarse grained components which are considered as the basic unit for the construction of systems, connectors encapsulate a component interaction pattern that can organize the possibly complicated interactions between the components of a subsystem. We also propose the idea of interface manager to solve the problem of incorrectly synchronized actions in CommUnity, and the concept of population manager to manage the live instances of components in a subsystem, through which we can model potentially complicated dynamic reconfigurations in a system.</p> <p> To use the semantics of CommUnity in defining the semantics of DynaComm, a "normalization" technique is introduced to transform the parameterized (indexed) actions into "normal" actions of CommUnity and reduce the specification of connectors and subsystems to flat CommUnity designs, so that we can derive the system's semantics in a certain state.</p> <p> Two illustrative examples, fault-tolerant dynamic client-server and vending machine systems, are also given to show the usage of DynaComm in modeling complicated and dynamic systems.</p> / Thesis / Master of Science (MSc)

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.

The goal of the proposed research is to provide efficient methods for defining, selecting and encoding multi-modal control programs. To this end, modes are recovered from system observations, i.e. quantized input-output strings are converted into consistent mode sequences within the Motion Description Language (MDL) framework. The design of such modes can help identify and predict the behaviors of complex systems (e.g. biological systems such as insects) and inspire the design and control of robust semi-autonomous systems (e.g. navigating robots). In this work, the efficiency of a method will be defined by the complexity and expressiveness of specific control programs. The insistence on low-complexity programs is originally motivated by communication constraints on the computer control of semi-autonomous systems, but also by our belief that, as complex as they may look, natural systems indeed use short motion schemes with few basic behaviors. The attention is first focused on the design of such short-length, few-distinct-modes mode sequences within the MDL framework. Optimal control problems are then addressed. In particular, given a mode sequence, the question of deciding when the system should switch from one mode to another in order to achieve some reachability requirements is studied. Finally, we propose to investigate how sampling strategies affect complexity and reachability, and how an acceptable trade-off between these conflicting entities can be reached.

Many emerging controls applications have seen increased operational complexity due to the deployment of embedded, networked systems that must interact with the physical environment. In order to manage this complexity, we design different control modes for each system and use motion description languages (MDL) to specify a sequence of these controllers to execute at run-time. Unfortunately, current MDL frameworks lose some of the important details (i.e. power, spatial, or communication capabilities) that affect the execution of the control modes. This work presents several computational tools that work towards closing MDL's specification-to-execution gap, which can result in undesirable behavior of complex systems at run-time. First, we develop the notion of an MDL compiler for control specifications with spatial, energy, and temporal constraints. We define a new MDL for networked systems and develop an algorithm that automatically generates a supervisor to prevent incorrect execution of the multi-agent MDL program. Additionally, we derive conditions for checking if an MDL program satisfies actuator constraints and develop an algorithm to insert new control modes that maintain actuator bounds during the execution of the MDL program. Finally, we design and implement a software architecture that facilitates the development of control applications for systems with power, actuator, sensing, and communication constraints.