Universiẗat, Diss., 2001--Mannheim.

Thesis (Ph. D.)--University of Texas at Austin, 2007. / Vita. Includes bibliographical references.

Techn. Universiẗat, Diss., 2003--Berlin.

University, Diss., 2004--Heidelberg.

Thesis (Ph. D.)--Lehigh University, 2006. / Includes vita. Includes bibliographical references (leaves 121-133).

The growing complexity of integrated circuits and the large variety of architectures of Field Programmable Gate Arrays (FPGAs) require sophisticated logic design tools. In the beginning of the eighties the research in logic design was concentrated on the development of fast two-level AND-OR logic minimizers like the well known ESPRESSO. However, most logic functions have a smaller and often faster circuit realization as a multi-level circuit. Thus, synthesis tools emerged for the minimization of the circuit area in a multi-level realization. Most of these synthesis tools are based on the "unate paradigm". Therefore, the synthesis methods are only advantageous for functions having a minimal circuit realization based on AND-OR gates. However, many common functions have a minmal circuit realization having a mix of AND, OR and EXOR gates like counters, adders, multipliers, and parity generators. Therefore, the design of such functions with synthesis tools based on the "unated paradigm" is very inefficient. Circuits incorporating the EXOR gate have received less attention than AND-OR circuits because the EXOR gate was perceived as slower and larger in terms of its circuit realization than the AND and the OR gate. However, the upcoming of Field Programmable Gate Arrays (FPGAs) like the Xilinx Table-Look-Up (TLU) architecture the Actel ACTâ„¢ series and the CLi 6000 series from Concurrent Logic, which allow the realization of the EXOR gate with the same speed and circuit cost as the AND and OR gate, eliminates the disadvantages of the EXOR gate over the AND and OR gate. Thus, there is a strong need for logic synthesis tools that take advantage of EXOR gates. The mapping to the new FPGAs recently obtained an increased interest. The developed synthesis algorithms for FPGAs are based on the mapping and restructuring of the Directed Acyclic Graph (DAG) representation of the logic function. Even though the new FPGAs allow the realization of the EXOR gate without any speed and circuit size penalty in comparison to the AND and OR gate, the synthesis methods have been based on the "unate paradigm". To overcome the disadvantages of the current logic synthesis tools with respect to (nearly) linear functions and FPGA synthesis, this dissertation introduces an extended theory of spectral methods for multiple-valued input, incompletely specified binary output logic. The spectral methods have not been popular in logic synthesis because of their four major drawbacks: (1) the computational complexity, especially if no Fast Transform exists, (2) the memory requirement to store the function in the necessary minterm representation, (3) they cannot take efficiently advantage of incompletely specified functions, (4) suitable only for few applications in logic synthesis. To overcome the two last stated drawbacks, this dissertation introduces the T spectrum. The T spectrum separates the information obtained for the specified and not specified parts of the underlying function. Thus, it is possible to determine directly the contribution of the specified and the not specified part of the function to a single spectral coefficient. Moreover, the T spectrum is an extension of the known spectra like Walshtype, Adding, Arithmetic, and Reed-Muller spectra to any orthogonal and nonorthogonal transform describing logic functions. Thus, transforms can be constructed that describe certain gate structures, as for example the realizable functions of a FPGA macrocell. This allows the development of special synthesis algorithms for the different types of FPGA architectures. As an exemplification of this method, a complete multi-level synthesis algorithm is introduced for the circuit realization with multiplexer modules, which form the basic macrocell of the Actel ACfâ„¢ FPGA series. Additionally, this dissertation presents the classification of the applications of spectral methods in logic synthesis into three categories: (1) The decomposition of logic functions based on the information obtained by the computation of a single spectrum. As an example the linearization procedure developed by Karpowsky is generalized to incompletely specified multi-output Boolean functions. The linearization procedure is based on the computation of the Rademacher-Walsh spectrum with a following decomposition of the underlying function based on high value spectral coefficients. (2) The circuit realization of a logic function based on the repetitive application of (1). This synthesis method is exemplified by an multi-level synthesis algorithm for multiplexer gates. (3) The realization of a logic function as an AND-EXOR circuit based on a GF 2 (Galois Field (2)) spectrum. The GF 2 transforms exhibit the property that they describe a realization of the underlying function as a two-level AND-EXOR circuit. The Multiple-Valued Input Kronecker Reed-Muller (MIKRM) form is introduced as an application of GF 2 transforms. To overcome the drawbacks of spectral methods concerning the computational complexity and high memory requirements, this dissertation presents a computation method for spectra from disjoint representations. The introduced application of the disjoint cube representation and the Ordered Decision Diagrams for the computation of spectra proves to be an ideal concept. Thus, this dissertation presents general synthesis methods based on new spectral methods that overcome the deficiencies of current logic synthesis methods with respect to the synthesis for FPGAs as well as the computational complexity and memory requirements of spectral methods.

Safety and mission critical systems are currently deployed in many different fields where there is a greater presence of high energy particles (e.g.\ aerospace). The use of field programmable gate arrays (FPGAs) within safety critical systems is becoming more prevalent due to the design and cost benefits their use provides. The effects of externally caused faults on these safety critical systems cannot be neglected. In particular, high energy particle striking a circuit can cause a voltage change in the circuit known as a soft error. The effects these soft errors will have on the circuit needs to be understood in order to ensure that the systems will function properly in the event soft errors do occur. In this thesis a tool is designed to facilitate the run-time injection of soft errors into a hardware circuit running on a FPGA. The tool allows for the control over the number of injections that can be performed and control over the rate that the injections will occur at. Additionally the tool records time stamps of when injections occur and time stamps of when errors are detected. This recorded data allows for the analysis of designs in conditions prone to soft errors. The implemented tool allows for design time parametrization and run time configuration, allowing a multitude of tests to be run for a single compiled design. The tool also eliminates the need for a host computer after configuration by generating the injection locations and times on the FPGA. Eliminating the host computer allows for faster testing when compared to other methods as data transfer times are greatly reduced. The implemented tool was run on classical examples of redundant structures, such as duplication with comparison and triple modular redundancy as well as a non-redundant structure to establish a baseline. The results of multiple tests run on each structure are analyzed to illustrate the uses of the tool and how the tool may be used to test other designs. / Thesis / Master of Applied Science (MASc)

Time-triggered communication is widely used throughout several industry do- mains, primarily for reliable and real-time capable data transfers. However, existing time-triggered technologies are designed for terrestrial usage and not directly applicable to space applications due to the harsh environment. In- stead, specific hardware must be developed to deal with thermal, mechanical, and especially radiation effects. SpaceWire, as an event-triggered communication technology, has been used for years in a large number of space missions. Its moderate complexity, her- itage, and transmission rates up to 400 MBits/s are one of the main ad- vantages and often without alternatives for on-board computing systems of spacecraft. At present, real-time data transfers are either achieved by prior- itization inside SpaceWire routers or by applying a simplified time-triggered approach. These solutions either imply problems if they are used inside dis- tributed on-board computing systems or in case of networks with more than a single router are required. This work provides a solution for the real-time problem by developing a novel clock synchronization approach. This approach is focused on being compatible with distributed system structures and allows time-triggered data transfers. A significant difference to existing technologies is the remote clock estimation by the use of pulses. They are transferred over the network and remove the need for latency accumulation, which allows the incorporation of standardized SpaceWire equipment. Additionally, local clocks are controlled decentralized and provide different correction capabilities in order to handle oscillator induced uncertainties. All these functionalities are provided by a developed Network Controller (NC), able to isolate the attached network and to control accesses. / Zeitgesteuerte Datenübertragung ist in vielen Industriezweigen weit verbreitet, primär für zuverlässige und echtzeitfähige Kommunikation. Bestehende Technologien sind jedoch für den terrestrischen Gebrauch konzipiert und aufgrund der rauen Umgebung nicht direkt auf Weltraumanwendungen anwendbar. Stattdessen wird spezielle Hardware entwickelt, um Strahlungseffekten zu widerstehen sowie thermischen und mechanischen Belastungen standzuhalten. SpaceWire wurde als ereignisgesteuerte Kommunikationstechnologie entwickelt und wird seit Jahren in einer Vielzahl von Weltraummissionen verwendet. Dessen erfolgreiche Verwendung, überschaubare Komplexität, und Übertragungsraten bis zu 400 MBit/s sind einige seiner Hauptvorteile. Derzeit werden Datenübertragungen in Echtzeit entweder durch Priorisierung innerhalb von SpaceWire Router erreicht, oder durch Anwendung von vereinfachten zeitgesteuerten Ansätzen. Diese Lösungen implizieren entweder Probleme in verteilten Systemarchitekturen oder in SpaceWire Netzwerken mit mehreren Routern. Diese Arbeit beschreibt eine Uhrensynchronisation, die bestimmte Eigenschaften von SpaceWire ausnutzt, um das Echtzeitproblem zu lösen. Der Ansatz ist dabei kompatibel mit verteilten Systemstrukturen und ermöglicht eine zeitgesteuerte Datenübertragung.

No description available.

De nos jours, la complexité de la conception des circuits intégrés et du logiciel croit régulièrement, faisant croître le besoin de la vérification dans chaque étape du cycle de conception. Le prototypage matériel sur une plateforme multi-FPGA présente le meilleur compromis entre le temps de conception d'un circuit et le temps d'exécution d'une application par ce circuit. Pour l'implémenter sur cette plateforme, une opération de partitionnement est effectuée avant de créer des partitions capables de s'intégrer dans chaque FPGAPar conséquent, des signaux coupés à l'interface des partitions doivent passer d'un FPGA à un autre. Cependant, le nombre de traces physiques inter-FPGA est limité ce qui crée des problèmes de routabilité du circuit prototypé. Cette thèse touche surtout la partie post-partitionnement et s'intéresse au problème deroutage inter-FPGA. Ainsi, les principaux travaux de cette thèse sont les suivants :Dans un premier temps, nous nous intéressons au développement d'un générateur debenchmarks qui permet, à l'aide d'une description architecturale simple du benchmark, de générer un circuit modélisé avec le langage de description matérielle VHDL. Le générateur utilise un ensemble de composants ce qui donne aux benchmarks un aspect réel semblable à celui des circuits industriels. Ces circuits de tests nous serviront pour évalue rles performances des techniques développées dans cette thèse. Dans un deuxième temps, nous proposons de développer un outil spécifique qui intervient après le partitionnement pour prendre en compte la contrainte liée à la limitation du nombre d'interconnexion entre les FPGAs. Cet outil est basé sur une approcheitérative visant à réduire le taux de multiplexage (nombre de signaux qui partagent un seul _l physique). Le routage en lui même est assuré par l'algorithme de routage Pathfinder adapté. Cet algorithme servira comme point de départ pour les techniques de routage développées durant cette thèse. Des adaptations adéquates seront faites pour cibler un ré-seau de routage inter-FPGA. Dans une deuxième partie, nous essayons de déterminer la meilleure forme du signal à router (bi-points ou multi-points) ainsi que le graphe de routage utilisé. Pour cela, nous proposons des scénarios de test a_n de sélectionner les critères qui donnent la fréquence de fonctionnement la plus performante. Par la suite, nous présentons une description détaillée des IPs de multiplexage utilisés.Ces IPs sont insérés dans les parties émettrices et réceptrices d'un canal de communication. Ces IPs incluent des composants spécifiques appelés SERDES pour assurer la sérialisation/déserialisation des données à transmettre. L'insertion de ces composants peut créer des problèmes de routabilité intra-FPGA. Ainsi, dans une deuxième partie, nous proposons un algorithme de placement basé sur l'estimation de la congestion afin d'améliorer la routabilité du circuit. / This thesis mainly deals with the post-partitioning task and addresses the problem of inter-FPGA routing. Thus, the main contributions of this thesis are: Firstly, we focus on the development of a benchmark generator which, using a simple architectural description of the benchmark, generates a circuit modelled with the hardware description language VHDL. The generator uses a set of industrial components providing benchmarks with real behaviour similar to that of industrial circuits. These benchmarks are used to evaluate the performance of the techniques developed in this thesis. In a second step , we propose a speci_c tool which acts after the partitioning to handle the constraints related to the limited number of interconnection between FPGAs. This tool is based on an iterative approach and aims to reduce the multiplexing ratio (the number of signals that share the same physical wire). The routing task itself is operated by the Pathfinder routing algorithm which is widely used by academic and industrial researchers . This algorithm is used as a starting point for routing techniques developed in this thesis . In a second part , we try to identify the best shape of the routed signals and the appropriate routing graph. For this reason, we propose scenarios to select criteria that give the best system frequency. Finally, we present a detailed description of the architecture of the multiplexing IPs. These IPs are inserted in the transmitting and receiving FPGAs of a communication channel. These IPs include speci_c components called SERDES for serialization/deserialization of the data. The insertion of these IPs can create problems of intra-FPGA routability. Thus, in a second part, we propose a placement algorithm based on congestion estimation to improve the routability of the circuit.