Modelling Fault-tolerant Asynchronous Logic (FATAL)

The aim of the FATAL project is the development of the mathematical/formal foundations of a framework for the hierarchical modeling and analysis of fault-tolerant asynchronous VLSI circuits, using fault-tolerant distributed algorithms knowledge in conjunction with the experimental assessment of both radiation-induced failures and metastability in modern VLSI technology. FATAL is a joint project between the Institut für Technische Informatik and the Institut für Elektrische Mess- und Schaltungstechnik at TU Wien. Designing VLSI circuits, which nowadays accommodate billions on transistors operating at GHz clock speeds, is becoming more and more difficult: In addition to managing the ever increasing functional complexity, chip designers are also confronted with increased manufacturing cost and decreasing yield, the "erosion" of the convenient synchronous abstraction, power dissipation problems, and increasing failure rates. As a consequence, modern VLSI chips are increasingly considered as more or less loosely-coupled systems of interacting subsystems - the advent of Systems-on-Chip. Such devices, however, have much in common with the loosely-coupled distributed computing systems that have been studied by the fault-tolerant distributed algorithms community for decades. In the course of the latter research, a wealth of different computing and failure models, algorithms & protocols, and theoretical results regarding solvability of problems and achievable performance have been established. Some recent work confirms that part of this knowledge can indeed be applied successfully in the VLSI context. A key feature of FATAL is the support of model/specification-based design and analysis: Both composition of existing circuits/specifications (bottom-up approach) and decomposition of a higher-level circuit/specification into lower-level ones (top-down approach) will be supported. Particular emphasis will be put on a detailed modeling of the relation between circuits and their environment. To master the proof complexity, these features will be accompanied by hierarchical correctness proofs and performance analysis techniques. In sharp contrast to current practice in VLSI design, which considers failures as something exceptional that occurs with (very) small probability, FATAL will be based on the deterministic approach usually employed in distributed algorithms research, where failures are considered part of normal operation: A circuit will be described by the set of all possible behaviors, even if such a behavior is extremely unlikely to be encountered in practice. Consequently, our approach facilitates deterministic correctness proofs and worst case performance analyses (probabilities can be assigned to behaviors later on, however). Among the challenges that must be met are the need for incorporating a continuous notion of time, the very fine-grained concurrency caused by a huge number of asynchronously computing logic gates, and the severe resource limitations encountered in VLSI circuits, which make even basic operations like sending a message or adding up two numbers very expensive. A pivotal part of FATAL is the definition of suitable (that is, realistic but easy to handle) failure models. Our goal is the development of a hierarchy of failure models of increasing severity, which can be used to describe the observable behavior of (faulty) circuits at a reasonably high level of abstraction. Identifying such models requires an in-depth exploration of the observable failures in modern VLSI chips. For "classic" sources of errors, there is a huge body of work to rely upon. This is not the case for radiation-induced errors, however, which are increasingly dominating the failure rate of deep submicron VLSI circuits. The same is true for metastability phenomena, which are particularly dangerous for fault-tolerant asynchronous circuits: Metastability can overcome any error containment boundary and, hence, invalidate any architectural dependability concept and correctness proof. FATAL will hence include a systematic experimental evaluation of both radiation-induced failures and metastability. Two custom VLSI circuits will be specifically designed and manufactured for this purpose, which poses unique technological challenges: Both advanced analog and digital circuitry must be integrated on the same chip, which creates intricate analog design problems and prohibits the usage of digital standard libraries. Moreover, the design must be accompanied with very accurate simulation models, which rules out push-button design flows. Finally, both radiation-hardened and radiation-sensitive devices must be integrated on the same chip, which is definitely a non-standard requirement.

The aim of the FATAL project was the development of the foundations of a framework for the hierarchical modeling and analysis of fault-tolerant asynchronous very-large scale integrated (VLSI) circuits, in conjunction with the experimental study of radiation-induced failures and metastability. FATAL was a joint project of the Institute of Computer Engineering (E182) and the Institute of Electrodynamics, Microwave and Circuit Engineering (E354) at TU Vienna.Modern VLSI chips are increasingly considered as more or less loosely-coupled systems of interacting subsystems (Systems-on-Chip), which have much in common with the distributed computing systems that have been studied by the fault-tolerant distributed systems community for decades. In FATAL, we utilized/adapted some of the existing computing and failure models, algorithms & protocols, and theoretical results regarding solvability of problems and achievable performance in the VLSI context, and created specifically tailored new instances where needed. The major accomplishments of FATAL are:A novel continuous-time, discrete-value modeling and analysis framework specifically designed for fault-tolerant asynchronous circuits. Rather than on discrete zero-time state transitions, it is based on continuous computations, supports hierarchical composition and decomposition of models and implementations, and modular correctness proofs at low abstraction levels. In sharp contrast to the current practice in VLSI design, failures are considered part of normal operation, and formally captured by allowing the behavior of a faulty circuit to deviate from its specification, according to some failure model.Given that single-event transients (SETs), caused by ionizing particles hitting the transistors of a VLSI circuit, are the dominant source of errors in nanometer technology, substantial efforts in FATAL were devoted to SET measurement and modeling activities: Specifically designed on-chip analog sense amplifiers were used for the low-intrusive measurement of the detailed SET voltage pulse shapes occurring in typical digital target circuits (such as inverters and Muller C-gates) in micro-beam irradiation experiments. The results were used for calibrating a detailed physical circuit simulation and a double-exponential SET-injection-based analog simulation model. The latter has been used for the validation of the design of a comprehensive digital SET long-term monitoring ASIC.An inevitable problem in asynchronous digital circuits is metastability, which originates in the inability to always determine the precise order of state transitions occurring in different parts of a circuit. In case of a state-holding device like a memory cell, this could lead to intermediate-valued states or fast oscillations. A substantial part of FATAL has been devoted to the experimental evaluation of metastability generation in modern VLSI technology, as well as to identifying ways of incorporating it in our all-digital FATAL modeling and analysis framework.We are happy to say that we made substantial scientific progress in all these major areas in FATAL, and will be able to continue our efforts in two recently granted FWF projects.