Research Projects at the Embedded Computing Systems Groups
Funding: Austrian Science Fund (FWF)
Time Frame: 01. 01. 2016 - 31. 12. 2018
Contact Persons: Ulrich Schmid
This project is devoted to the development of the theoretical foundations, models, algorithms and analysis techniques for relaxed distributed agreement in directed dynamic networks. Such networks are characterized by (i) sets of participants (processes) that are a priori unknown and potentially time-varying, (ii) rapidly changing uni-directional connectivity between processes, and (iii) the absence of central control. Instantiated, e.g., by (wireless) sensor networks and ad-hoc networks, such dynamic networks are becoming ubiquitous in many applications nowadays. A natural approach to build robust services despite the dynamic nature of such networks would be to use distributed consensus to agree system-wide on (fundamental) parameters like schedules, operating frequencies, operating modes etc. Unfortunately, however, in larger-scale dynamic networks, this is usually impossible, since solving consensus requires a well-connected and temporarily stable network topology. In order to overcome this fundamental limitation, we propose to consider gracefully degrading variants of consensus, in particular, approximate agreement, where decision values may slightly deviate from each other, and k-set agreement, which may deliver up to k different decisions in case of bad network conditions that e.g. lead to k isolated network partitions. In our project, we will develop network assumptions that both allow to solve, say, k-set agreement, and have some reasonable assumption coverage in real systems. Therefore, our focus will be on weakest (necessary and sufficient) conditions and the analysis of the resulting assumption coverage. Other central part of our project is the development of solution algorithms and their correctness proofs. Particular emphasis will be put on performance of our algorithms, since there is a tradeoff between weak network conditions and the communication and memory complexity of solutions algorithms. Overall, the project shall yield new insights into the fundamental limitations of dynamic networks as well as the development of novel algorithms that solve distributed agreement problems reliably even under very weak communication guarantees.
Funding: Austrian Science Fund (FWF)
Partners: Graz University of Technology (coordinator), Vienna University of Technology, Institute of Science and Technology Austria, Johannes Kepler University Linz, University of Salzburg.
Time Frame: 01. 03. 2015 - 01. 03. 2019
Contact Persons: Ulrich Schmid
RiSE/SHiNE pursues the long term vision of a hardware/software system design process supported by automatic formal methods based on model checking, decision procedures, and game theory. Simultaneously, the National Research Network has the strategic goal to establish and strengthen Austria as an international hot spot in this research area. In the first three years of the 4-year funding period (Period I), we have made important steps towards both the scientific and the strategic goal. A key lesson from Period I was that non-functional aspects of system quality and correctness are critical, hard to achieve manually, and highly amenable to rigorous reasoning. We view the second period of RiSE 2015–2019 as an opportunity to position Computer Aided Verification closer to other fields of computer science which address non-functional aspects in a rigorous manner. In Period II, nine Project Part Leaders and six (mostly) junior Task Leaders will build upon the foundations established in the first years. The new Tasks that we propose either derive from a cross cutting “collaboration topic” of Period I or are new topics introduced by the recently hired faculty. All Tasks will be jointly investigated by two PIs. While the Research Clusters of Period I reflected the individual expertise of the PIs, we will now organize our Tasks along intersecting Research Lines. Each Research Line of Period II will address a non-functional aspect such as concurrency, probabilistic behavior, reliability, and quantitative measures (timing and resource consumption). This focus reflects a broader understanding of correctness beyond the Boolean notion of functional correctness that was central in Period I. Thus, our thrust will go beyond verification of functional specifications to computer aided design of programs that fulfill both functional and non-functional properties. We have therefore subtitled the second funding Period Systematic Methods in Systems Engineering, or SHiNE. SHiNE project part PP05: Reconciling Distributed and Real-Time Computing (Schmid, Bartocci). Modern distributed systems, ranging from systems-on-chip (SoC) to electronic commerce networks, must be resilient to failures and maintain specified response time bounds. The Tasks of PP05 is devoted to a continuous-time modeling & analysis framework for such systems:
- Task US1: Modeling and Analysis of Distributed Systems with Non-Zero-Time Computations (Applications). The abstraction of discrete, instantaneous state transitions inherently “defines away” queueing and scheduling issues and thus does not adequately match real systems. The situation is even worse in case of algorithms implemented in hardware, as abstracting continuous computations by discrete state transitions “defines away” metastability of discrete-valued signals/states and the impossibility to build an arbiter. The problem is further exacerbated by incorporating fault-tolerance, in particular, self-stabilization, which requires solutions that recover from system states without any synchrony. In a collaboration with PP07 (Chatterjee), which has already been established in RiSE, PP02 (Henzinger) and PP08 (Biere), we will develop the foundations and solution methods for a suitable real-time analysis framework.
- Task EBUS2: Modeling and Analysis of Parametric, Probabilistic and Parameterized Timed Systems (Ezio Bartocci) (Applications). To master the overwhelming complexity of manual correctness proofs of continuous-time distributed systems, computer-aided methods that can deal with symbolic timing parameters (“parametric”) and symbolic system sizes (“parameterized”) are required. Besides the question of how to deal with the overwhelming complexity, answering the question of how to incorporate (probabilistic) faults will be addressed in collaboration with PP12 (Grosu), PP07 (Chatterjee) and PP11 (Kirsch). In order to extend our framework to also cover message-passing distributed systems with parameterized system size, novel abstraction techniques and/or cutoff results will be developed in a collaboration with PP03 (Veith).
Accelerator-based Experimental Analysis and Simulation Modeling of Single-Event Transients in VLSI Circuits (EASET)
Funding: FWF stand-alone project
Collaborators: Institute of Electrodynamics, Microwave and Circuit Engineering
TU Wien (prof. Zimmermann)
Time Frame: 01. 04. 2014 - 31. 03. 2017
Due to the steadily decreasing feature sizes of modern VLSI circuits, which are in the nanometer range (< 100 nm) nowadays, single-event effects (SEEs) are increasingly dominating the fault rate of VLSI circuits. SEEs occur when junctions of transistors are hit by ionized particles. Such particles primarily originate in high-energy cosmic radiation, affecting a chip either directly (at high altitudes, i.e., in space and aerospace) or indirectly, via interaction with the atmosphere. The primary concern in modern VLSI circuits are transient SEEs: An ionized particle deposits charge along its track, which in turn can cause a single-event transient (SET) signal pulse (0.1-1 ns range). If a sufficiently strong SET propagates to a storage element, it can be latched, thereby producing a single-event upset (SEU).
Robust circuit design, in particular, for critical applications, hence needs models that accurately describe SETs/SEUs and are easy and efficient to use at early design stages. Such models both allow (a) to assess the radiation tolerance of different architectural designs and hardening techniques and (b) to estimate the final error rate of a circuit. The preferred method to accomplish this is simulation-based fault injection at the (analog) electrical level: Typically, a Spice model of the circuit (derived automatically from the design using technology libraries) is augmented with Spice models that simulate SET generation in critical parts of the circuit. The most commonly approach here is single-ended injection of a double-exponential current into the drain of a transistor.
Obviously, the suitability of this method for validating the effectiveness of radiation-hardening measures and predicting soft-error rates stands or falls with the availability of accurate Spice models for SET generation: If it fails to cover important scenarios, one might e.g. overlook situations where radiation-hardening fails. Unfortunately, there is evidence that standard double-exponential Spice models are susceptible to such problems, with respect to several aspects: (1) Inadequate model structure, (2) calibration of model parameters, and (3) SEEs affecting multiple transistors.
Any attempt to developing Spice models that accurately model SET generation (including the above complications) in nanometer VLSI circuits requires a combination of both (a) a detailed understanding of the physical/electrical processes involved and (b) a comprehensive experimental evaluation of SET pulses arising in real circuits. The project EASET is devoted to this purpose: It will use results from accurate analog SET measurements in carefully designed measurement ASICs under micro-beam irradiation to (i) guide the development and (ii) calibrate detailed 3D physical/hybrid TCAD simulation models. The latter is a very powerful means for researching the SET generation process and its parameters in VLSI circuits, and thus also the appropriate basis for developing and validating novel SET generation Spice models for complex nanometer VLSI circuits, which are the primary intended outcome of the project.
The measurement ASICs will include on the one hand the circuits under test, e.g. circuits based on basic combinational and sequential logic and possibly some other topologies like ring oscillators. On the other hand the ASICs will include high speed analog measurement amplifiers which must have minimum influence on the investigated circuit nodes, and they have to include high speed analog 50Ω-output drivers. Additional analog high speed multiplexers are necessary due to the large number of investigated circuit nodes. Consequently, EASET not only addresses interesting fundamental research questions, but also provides results that are relevant in practice. The required competence is ensured by running it as a joint project between the Institut für Technische Informatik and the Institute of Electrodynamics, Microwave and Circuit Engineering at TU Wien, which also includes external collaborations with radiation physics experts e.g. at the GSI in Darmstadt and the PTB in Braunschweig.