Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26788
Titel: Metastability-containing circuits, parallel distance problems, and terrain guarding
Verfasser: Friedrichs, Stephan
Sprache: Englisch
Erscheinungsjahr: 2017
SWD-Schlagwörter: Halbleiterschaltung
Berechenbarkeit
Algorithmus
Graph
Geometrie
Freie Schlagwörter: semiconductor circuit
computability
algorithm
graph
geometry
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: We study three problems. The first is the phenomenon of metastability in digital circuits. This is a state of bistable storage elements, such as registers, that is neither logical 0 nor 1 and breaks the abstraction of Boolean logic. We propose a time- and value-discrete model for metastability in digital circuits and show that it reflects relevant physical properties. Further, we propose the fundamentally new approach of using logical masking to perform meaningful computations despite the presence of metastable upsets and analyze what functions can be computed in our model. Additionally, we show that circuits with masking registers grow computationally more powerful with each available clock cycle. The second topic are parallel algorithms, based on an algebraic abstraction of the Moore-Bellman-Ford algorithm, for solving various distance problems. Our focus are distance approximations that obey the triangle inequality while at the same time achieving polylogarithmic depth and low work. Finally, we study the continuous Terrain Guarding Problem. We show that it has a rational discretization with a quadratic number of guard candidates, establish its membership in NP and the existence of a PTAS, and present an efficient implementation of a solver.
Wir betrachten drei Probleme, zunächst das Phänomen von Metastabilität in digitalen Schaltungen. Dabei geht es um einen Zustand in bistabilen Speicherelementen, z.B. Registern, welcher weder logisch 0 noch 1 entspricht und die Abstraktion Boolescher Logik unterwandert. Wir präsentieren ein zeit- und wertdiskretes Modell für Metastabilität in digitalen Schaltungen und zeigen, dass es relevante physikalische Eigenschaften abbildet. Des Weiteren präsentieren wir den grundlegend neuen Ansatz, trotz auftretender Metastabilität mit Hilfe von logischem Maskieren sinnvolle Berechnungen durchzuführen und bestimmen, welche Funktionen in unserem Modell berechenbar sind. Darüber hinaus zeigen wir, dass durch Maskingregister in zusätzlichen Taktzyklen mehr Funktionen berechenbar werden. Das zweite Thema sind parallele Algorithmen die, basierend auf einer Algebraisierung des Moore-Bellman-Ford-Algorithmus, diverse Distanzprobleme lösen. Der Fokus liegt auf Distanzapproximationen unter Einhaltung der Dreiecksungleichung bei polylogarithmischer Tiefe und niedriger Arbeit. Abschließend betrachten wir das kontinuierliche Terrain Guarding Problem. Wir zeigen, dass es eine rationale Diskretisierung mit einer quadratischen Anzahl von Wächterpositionen erlaubt, folgern dass es in NP liegt und ein PTAS existiert und präsentieren eine effiziente Implementierung, die es löst.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-69660
hdl:20.500.11880/26801
http://dx.doi.org/10.22028/D291-26788
Erstgutachter: Lenzen, Christoph
Tag der mündlichen Prüfung: 11-Sep-2017
SciDok-Publikation: 14-Sep-2017
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
thesis_20170912_final.pdf2,73 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.