Funded by the Austrian Science Foundation (FWF), project SIC (P26436).
Funding period: November 2013 to September 2018.
Circuit components may fail permanently, e.g., due to manufacturing defects and electrical wear-out, or transiently e.g., due to ionizing particles, cross-talk and temporary out-of-spec operating conditions. There is a large body of work on how to decrease probabilities of such faults on circuit-level, e.g., by choice of material and cell design, and on software-level. However, significantly less was known about algorithmic techniques on circuit-level.
Aim of the project was to fill this gap. Distributed computing traditionally studies the behavior of networks of communicating processes in presence of faults. Interestingly, VLSI circuits can be viewed as distributed systems at several levels of abstraction: from gates that communicate via binary signals, to components in a network on chip (NoC). We thus studied distributed algorithms that can be efficiently implemented directly in hardware, providing robust services to other hardware components or the application layer. Examples of such services are robust clock synchronization, clock frequency adaptation in presence of voltage droops, communication infrastructure on a chip, etc.
Typically processes of such a distributed system are highly restricted in communication primitives and computational power in comparison to the processes that are classically studied in software inspired distributed systems. The study of faithful distributed computing models that capture the particulates of distributed algorithms at circuit-level was a major first step for such an approach: existing algorithms that, e.g., provide services like a synchronized distributed clock signal, were prohibitively costly in the communication and computation primitives they used, had (fault) assumptions that were not compatible with gate-level algorithms, or performance measures that rendered them useless at gate-level. A focus of the SIC project was on self-stabilizing algorithms: a system solves a problem in a self-stabilizing way if, starting from an arbitrarily corrupted state, it solves the problem in the suffix of an execution. Self-stabilizing algorithms are of great interest for missions where state corruption cannot easily be removed by maintenance or manual reset; e.g., in space missions.
| [34] |
Jürgen Maier, Matthias Függer, Thomas Nowak, and Ulrich Schmid.
Transistor-level analysis of dynamic delay models.
In IEEE International Symposium on Asynchronous Circuits and
Systems (ASYNC), 2019. [ bib ] |
| [33] |
Jürgen Maier and Andreas Steininger.
Efficient metastability characterization for schmitt-triggers.
In IEEE International Symposium on Asynchronous Circuits and
Systems (ASYNC), 2019. [ bib ] |
| [32] |
Matthias Függer, Attila Kinali, Christoph Lenzen, and Ben Wiederhake.
Fast all-digital clock frequency adaptation circuit for voltage droop
tolerance.
In IEEE International Symposium on Asynchronous Circuits and
Systems (ASYNC), pages 68-77, May 2018. [ bib | DOI | hal | url ] |
| [31] |
Florian Huemer, Thomas Polzer, and Andreas Steininger.
Using a duplex time-to-digital converter for metastability
characterization of an fpga.
In 2018 IEEE 21st International Symposium on Design and
Diagnostics of Electronic Circuits Systems (DDECS), pages 141-146, April
2018. [ bib | DOI ] |
| [30] |
Matthias Függer, Jürgen Maier, Robert Najvirt, Thomas Nowak, and Ulrich
Schmid.
A faithful binary circuit model with adversarial noise.
In Design, Automation & Test in Europe (DATE), pages
1327-1332. IEEE, 2018. [ bib | hal | url | preprint ] |
| [29] |
Stephan Friedrichs, Matthias Függer, and Christoph Lenzen.
Metastability-containing circuits.
IEEE Transactions on Computers, 67(8), 2018. [ bib | DOI | hal | url | arxiv long version ] |
| [28] |
Matthias Függer, Thomas Nowak, and Manfred Schwarz.
Tight bounds for asymptotic and approximate consensus.
In ACM Symposium on Principles of Distributed Computing (PODC),
pages 325-334, New York, NY, USA, 2018. ACM. [ bib | DOI | hal | url | arxiv long version ] |
| [27] |
Martin Biely, Peter Robinson, Ulrich Schmid, Manfred Schwarz, and Kyrill
Winkler.
Gracefully degrading consensus and k-set agreement in directed
dynamic networks.
Theoretical Computer Science, 726:41-77, 2018. [ bib | DOI | url ] |
| [26] |
Thomas Polzer, Florian Huemer, and Andreas Steininger.
Refined metastability characterization using a time-to-digital
converter.
Microelectronics Reliability, 80:91 - 99, 2018. [ bib | DOI | url ] |
| [25] |
Martin Perner and Ulrich Schmid.
Self-stabilizing high-speed communication in multi-synchronous GALS
architectures.
In 24th IEEE International Symposium on On-Line Testing And
Robust System Design, IOLTS 2018, Platja D'Aro, Spain, July 2-4, 2018,
pages 157-164, 2018. [ bib | DOI | url ] |
| [24] |
Robert Najvirt, Thomas Polzer, and Andreas Steininger.
Measuring metastability with free-running clocks.
In 23rd IEEE International Symposium on Asynchronous Circuits
and Systems (ASYNC), pages 18-24, May 2017. [ bib | DOI ] |
| [23] |
Thomas Polzer, Florian Huemer, and Andreas Steininger.
Measuring metastability using a time-to-digital converter.
In IEEE 20th International Symposium on Design and Diagnostics
of Electronic Circuits Systems (DDECS), pages 116-121, April 2017. [ bib | DOI ] |
| [22] |
Ghaith Tarawneh, Matthias Függer, and Christoph Lenzen.
Metastability tolerant computing.
In IEEE International Symposium on Asynchronous Circuits and
Systems (ASYNC), pages 25-32, 2017. [ bib | DOI | hal | url | preprint ] |
| [21] |
Matthias Függer, Attila Kinali, Christoph Lenzen, and Thomas Polzer.
Metastability-aware memory-efficient time-to-digital converter.
In IEEE International Symposium on Asynchronous Circuits and
Systems (ASYNC), pages 49-56, 2017. [ bib | hal | url | preprint ] |
| [20] |
Matthias Függer, Thomas Nowak, and Manfred Schwarz.
Brief announcement: Lower bounds for asymptotic consensus in dynamic
networks.
In 31st International Symposium on Distributed Computing
(DISC), Leibniz International Proceedings in Informatics (LIPIcs), pages
51:1-51:3, 2017. [ bib | DOI | hal | url | preprint | arxiv long version ] |
| [19] |
Thomas Polzer and Andreas Steininger.
A model for the metastability delay of sequential elements.
Journal of Circuits, Systems, and Computers, 26(8):1-22, 2017. [ bib | DOI ] |
| [18] |
Andreas Steininger, Jürgen Maier, and Robert Najvirt.
The metastable behavior of a schmitt-trigger.
In 22nd IEEE International Symposium on Asynchronous Circuits
and Systems (ASYNC), pages 57-64, May 2016. [ bib | DOI ] |
| [17] |
Thomas Polzer, Robert Najvirt, Florian Beck, and Andreas Steininger.
On the appropriate handling of metastable voltages in fpgas.
Journal of Circuits, Systems and Computers, 25(03), 2016. [ bib | DOI | arXiv | url ] |
| [16] |
Danny Dolev, Matthias Függer, Christoph Lenzen, Martin Perner, and Ulrich
Schmid.
HEX: Scaling honeycombs is easier than scaling clock trees.
Journal of Computer and System Sciences, 82(5):929-956, 2016. [ bib | url ] |
| [15] |
Matthias Függer, Thomas Nowak, and Ulrich Schmid.
Unfaithful glitch propagation in existing binary circuit models.
IEEE Transactions on Computers, 65(3):964-978, 2016. [ bib | hal | url ] |
| [14] |
Bernadette Charron-Bost, Matthias Függer, and Thomas Nowak.
Fast, robust, quantizable approximate consensus.
In 43rd International Colloquium on Automata, Languages, and
Programming (ICALP), volume 55, pages 137:1-137:14, 2016. [ bib | hal | url ] |
| [13] |
Manfred Schwarz, Kyrill Winkler, and Ulrich Schmid.
Fast consensus under eventually stabilizing message adversaries.
In Proceedings of the 17th International Conference on
Distributed Computing and Networking, ICDCN '16, pages 7:1-7:10, New York,
NY, USA, 2016. ACM. [ bib | DOI | url ] |
| [12] |
Andreas Steininger, Robert Najvirt, and Jürgen Maier.
Does cascading schmitt-trigger stages improve the metastable
behavior?
In 2016 Euromicro Conference on Digital System Design (DSD),
pages 372-379, Aug 2016. [ bib | DOI ] |
| [11] |
Robert Najvirt and Andreas Steininger.
How to synchronize a pausible clock to a reference.
In 21st IEEE International Symposium on Asynchronous Circuits
and Systems, pages 9-16, May 2015. [ bib | DOI ] |
| [10] |
Matthias Függer, Robert Najvirt, Thomas Nowak, and Ulrich Schmid.
Towards binary circuit models that faithfully capture physical
solvability.
In Design, Automation & Test in Europe (DATE), pages
1455-1460, 2015. [ bib | hal | url ] |
| [9] |
Bernadette Charron-Bost, Matthias Függer, Jennifer L. Welch, and Josef
Widder.
Time complexity of link reversal routing.
ACM Transactions on Algorithms, 11(3):18:1-18:39, January
2015. [ bib | url ] |
| [8] |
Robert Najvirt, Matthias Függer, Thomas Nowak, Ulrich Schmid, Michael
Hofbauer, and Kurt Schweiger.
Experimental validation of a faithful binary circuit model.
In Proceedings of the 25th Edition on Great Lakes Symposium on
VLSI (GLSVLSI), pages 355-360. ACM, 2015. [ bib | hal | url ] |
| [7] |
Matthias Függer, Alexander Kößler, Thomas Nowak, Ulrich Schmid, and
Martin Zeiner.
The effect of forgetting on the performance of a synchronizer.
Performance Evaluation, 93:1-16, 2015. [ bib | hal | url ] |
| [6] |
Martin Biely, Peter Robinson, Ulrich Schmid, Manfred Schwarz, and Kyrill
Winkler.
Gracefully degrading consensus and k-set agreement in directed
dynamic networks.
In Networked Systems - Third International Conference, NETYS
2015, Agadir, Morocco, May 13-15, 2015, Revised Selected Papers, pages
109-124, 2015. [ bib | DOI | url ] |
| [5] |
Robert Najvirt and Andreas Steininger.
A versatile and reliable glitch filter for clocks.
In Power and Timing Modeling, Optimization and Simulation
(PATMOS), 2015 25th International Workshop on, pages 140-147, Sept 2015. [ bib | DOI ] |
| [4] |
Robert Najvirt and Andreas Steininger.
A pausible clock with crystal oscillator accuracy.
In Circuit Theory and Design (ECCTD), 2015 European Conference
on, pages 1-4, Aug 2015. [ bib | DOI ] |
| [3] |
Danny Dolev, Matthias Függer, Ulrich Schmid, and Christoph Lenzen.
Fault-tolerant algorithms for tick-generation in asynchronous logic:
Robust pulse generation.
J. ACM, 61(5):30:1-30:74, September 2014. [ bib | url ] |
| [2] |
Robert Najvirt and Andreas Steininger.
Equivalence of clock gating and synchronization with applicability to
gals communication.
In Proceedings of the 24th International Workshop on Power and
Timing Modeling, Optimization and Simulation. IEEE, 2014. [ bib | DOI ] |
| [1] |
Danny Dolev, Matthias Függer, Markus Posch, Ulrich Schmid, Andreas
Steininger, and Christoph Lenzen.
Rigorously modeling self-stabilizing fault-tolerant circuits: An
ultra-robust clocking scheme for systems-on-chip.
Journal of Computer and System Sciences, 80(4):860-900, 2014. [ bib | url ] |
(list generated by bibtex2html)