Detailansicht
Towards truly distributed computing
uniting theory, algorithms and practice
Gerhard Niederbrucker
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Betreuer*in
Wilfried Gansterer
DOI
10.25365/thesis.33365
URN
urn:nbn:at:at-ubw:1-30421.32450.562759-1
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Wissenschaftliche Berechnungen profitieren heutzutage oft von der Leistungsfähigkeit (großer) Parallelrechner. Solch parallele Systeme beeindrucken durch schnelle Gleitpunktarithmetik, tiefe Speicherhierarchien und ausgeklügelte Verbindungsnetze. Darüber hinaus können durch entsprechende Programmiertechnologien die Eigenschaften solcher Systeme zur Gänze kontrolliert und ausgeschöpft werden. Als Gegenstück zu parallelen Systemen betrachten wir verteilte Systeme (z.B. Sensornetzwerke), in welchen keinerlei globale Kontrollmechanismen verfügbar sind und die Kommunikation auf benachbarte Knoten beschränkt ist. Darüber hinaus betrachten wir unzuverlässige verteilte Systeme, wo etwa die Kommunikation (unbemerkt) fehlschlagen kann. Daher führen selbst einfachste Fragestellungen zu herausfordernden Problemen. Unsere Untersuchungen beschränken sich dabei nicht auf klassische Ausprägungen verteilter Systeme, sondern zielen insbesondere auch auf zukünftige Höchstleistungsrechner ab, welchen zunehmend Eigenschaften verteilter System prophezeit werden.
Unser Hauptaugenmerk liegt auf dem Bereitstellen beweisbar robuster, fundamentaler Berechnungsroutinen unter realistischen Annahmen bezüglich (der Zuverlässigkeit von) verteilten Umgebungen. Im Zuge dessen behalten wir stets sowohl theoretische als auch praktische Aspekte im Auge. Auf diese Weise decken wir Probleme hinsichtlich der praktischen Anwendbarkeit bestimmter Methoden und deren Analysen auf. Unsere Beiträge bestehen unter anderem aus einer Konvergenztheorie für eine große Klasse verteilter Aggregationsalgorithmen, welche, im Gegensatz zu existierenden Resultaten, einzig auf lokalen Annahmen beruht. Darauf aufbauend zeigen wir, wie man generisch beweisbar robuste Algorithmen ableiten kann, welche den Herausforderungen in realen verteilten Systemen gewachsen sind. Aufgrund der iterativen Natur der betrachteten Algorithmen, ist es naheliegend zu fragen, wie ein Knoten lokal das Erreichen der Zielgenauigkeit feststellen kann. Wir untersuchen dieses gemeinhin vernachlässigte Problem und tragen Methoden zur rein lokalen Genauigkeitsbestimmung bei.
Zusätzlich zum Hauptteil dieser Arbeit, aber auf demselben mathematischen Hintergrund aufbauend, entwickeln wir schnelle und genaue iterative Löser für ein großes strukturiertes Eigenwertproblem aus der Biochemie. Konkret betrachten wir die Berechnung der Quasispezies im so genannten Quasispezies Modell, welche geleichbedeutend mit dem Auffinden des dominierenden Eigenvektors einer speziell strukturierten Matrix ist. Unsere Resultate stellen dabei ein Tandem aus neuartigen, die Problemstruktur einbeziehenden Algorithmen und deren effizienter (paralleler) Implementierung dar. In Summe können wir dadurch die handhabbare Problemdimension substantiell erhöhen und gleichzeitig auch allgemeinere Modellannahmen behandeln.
Abstract
(Englisch)
Today, scientific computations often benefit from the computational power of (large scale) parallel computers. Such parallel systems impress by fast floating-point arithmetic, deep memory hierarchies and sophisticated interconnection networks. Moreover, appropriate programming technologies allow to fully exploit and control the entire functionality of these platforms. As a counterpart to parallel systems, we consider distributed systems (e.g., sensor networks) which do not provide global control mechanisms and where the communication capabilities are limited to simple point-to-point communication between neighboring nodes. Furthermore, we consider unreliable distributed systems, e.g., the communication between nodes may (silently) fail. Therefore, even aiming at imitating elementary parallel computations on a distributed system raises many challenging problems. Our investigations do not only target classical instances of distributed systems, such as sensor networks, but also future high performance systems, due to the predicted distributed nature of these systems.
Our central objective is to provide provably reliable fundamental computing functionality, such as the distributed computation of aggregates, under realistic assumptions on (the reliability of) distributed environments. In the course of that, we consistently take theoretical as well as practical points of view into account. In doing so, we reveal several issues concerning the practical applicability of existing methods and their analyses. Our contributions consist among others of a convergence theory for a large class of distributed aggregation algorithms, which---in contrast to existing work---solely builds upon purely local assumptions. On top of that, we show how to generically derive provably reliable algorithms which can successfully cope with the challenges posed by real distributed systems. Due to the iterative nature of the algorithms we consider, the question how a node can locally reason whether or not it already reached a certain target accuracy, is apparent. We investigate this commonly neglected problem and contribute methods for purely local accuracy estimation.
In addition to the main thread of this thesis---but building upon the same mathematical background---we develop fast and accurate iterative solvers for a large scale structured eigenvalue problem arising in computational biology. More specifically, we consider the computation of the quasispecies in the so-called quasispecies model, which is tantamount to finding the dominating eigenvector of a certain data-sparse matrix. Our results constitute a tandem of novel structure-aware algorithms and their efficient (parallel) implementation on modern hardware. Altogether, we substantially raise the computationally tractable problem dimensions and generalize the applicable model assumptions.
Schlagwörter
Schlagwörter
(Englisch)
Distributed aggregation Fault tolerance Gossip algorithms Consensus algorithms Exascale HPC GPU Quasispecies
Schlagwörter
(Deutsch)
Verteilte Aggregation Fehlertoleranz Gossip Algorithmen Consensus Algorithmen Exascale HPC GPU Quasispezies
Autor*innen
Gerhard Niederbrucker
Haupttitel (Englisch)
Towards truly distributed computing
Hauptuntertitel (Englisch)
uniting theory, algorithms and practice
Publikationsjahr
2014
Umfangsangabe
XIII, 183 S. : Ill., graph. Darst.
Sprache
Englisch
Beurteiler*innen
Robert Elsässer ,
Peter Arbenz
AC Nummer
AC12020977
Utheses ID
29634
Studienkennzahl
UA | 786 | 880 | |