Detailansicht
Truly distributed approaches to Orthogonalization and orthogonal iteration on the basis of gossip algorithms
Hana Strakova
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Betreuer*in
Wilfried Gansterer
URN
urn:nbn:at:at-ubw:1-30047.72507.957564-6
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Gossip bzw. epidemische Algorithmen sind Kommunikationsprotokolle in welchen Knoten ausschließlich mit zufällig bestimmten unmittelbaren Nachbarn Nachrichten austauschen. Aufgrund ihrer randomisierten Kommunikation sind diese Algorithmen äußerst flexibel bzgl. der zu Grunde liegenden Hardwareinfrastruktur, sowie der Netzwerktopologie. Darüber hinaus können sie vielerlei Fehler wie z. B. den Verlust von Nachrichten tolerieren und die erzielte Genauigkeit kann mit dem Gesamtaufwand abgewogen werden. Gossip-basierte Algorithmen wurden bisher hauptsächlich für elementare Operationen wie Aggregationen (Summation oder Durchschnittsbildung) bzw. allgemeiner, zur Verbreitung von Information in Netzwerken eingesetzt. Entsprechend stellen sich dezentrale verteilte Systeme wie P2P- oder Sensornetzwerke als natürliche Zielplatformen dar.
Das Hauptaugenmerk dieser Arbeit liegt auf der Entwicklung und Untersuchung von verteilten Matrixalgorithmen welche auf gossip-basierten Aggregationsalgorithmen beruhen. Insbesondere untersuchen wir einen verteilten Gram-Schmidt Orthogonalisierungsprozess zur Berechnung von QR Faktorisierungen und eine verteile Orthogonale Iteration zur Berechnung der dominierenden Eigenpaare einer Matrix. Darüber hinaus zeigen wir, wie mit Hilfe einer verteilten QR Faktorisierung lineare Regressionsprobleme über verteilten (Mess-)Daten gelöst werden können.
Aufgrund der Spezifika dezentraler verteilter Systeme ist es nicht bzw. nur sehr schwer möglich existierende Algorithmen aus der parallelen Datenverarbeitung direkt zu übernehmen, da diese an Regularitätsanforderungen gebunden sind, die verteilte Systeme nicht erfüllen. Daher ist es eine Notwendigkeit spezifische (verteilte) Algorithmen für derartige dezentrale Systeme zu entwickeln.
Nebst der Entwicklung verteilter Algorithmen zeigen wir auch einige potentielle Anwendungen dieser auf. Eine Anwendung der verteilten Orthogonalisierung stammend aus der Telekommunikation ist distributed sphere decoding. Dabei wird einer Gruppe von Empfängern, durch einen verteilten Algorithmus, die Kooperation während des Dekodierens von Signalen einer Gruppe von Sendern ermöglicht. Anwendungen der verteilten Orthogonalen Iteration finden sich unter anderem in der Netzwerkanalyse, wo z. B. mittels spezifischer Eigenwerte und Eigenvektoren Aussagen über die Konnektivität des Netzwerks getroffen werden können.
Zunächst führen wir in dieser Arbeit einen gossip-basierten verteilen Gram-Schmidt Orthogonalisierungsprozess ein und zeigen theoretisch sowie experimentell, dass dieser die numerischen Eigenschaften der klassischen Variante erhält. Darüber hinaus untersuchen wir experimentell in wie weit sich die Synchronisation zwischen den Knoten auf die Genauigkeit der berechneten Resultate auswirkt. Obwohl die Knoten klarerweise untereinander kooperieren müssen, sind nur einfachste lokale Synchronisationsmechanismen von Nöten, um genaue Ergebnisse zu liefern.
Darauf aufbauend untersuchen wir eine verteilte Orthogonale Iteration als Anwendungsbeispiel der verteilten QR Faktorisierung. Neben Untersuchungen zur Konvergenz und numerischen Genauigkeit, illustrieren wir auch wie Genauigkeit und Aufwand zur Reduzierung der Kommunikationskosten gegeneinander abgewogen werden können. Zusätzlich liefert der Einsatz von gossip-basierten Elementaroperationen auch substantiell robustere bzw. fehlertolerante Algorithmen (im Vergleich zu existierenden Methoden).
Abschließend präsentieren wir erste Schritte in Richtung einer MPI Implementierung der untersuchten gossip-basierten Algorithmen für Parallelrechner. Diese Untersuchungen dienen zur Quantifizierung des Mehraufwands den verteilte Algorithmen mit sich bringen. Konkret präsentieren wir erste Vergleiche mit etablierten parallelen Routinen wie MPI_Allreduce bzw. der PBLAS Routine pdgemv die in ScaLAPACK Verwendung findet.
Abstract
(Englisch)
Gossip or epidemic algorithms are communication protocols based on randomized information exchange in nodes' neighborhoods. Thanks to the randomized communication they are very flexible with respect to the underlying hardware infrastructure, they can operate on arbitrary topologies and tolerate various types of failures. Moreover, they have the ability to trade invested cost for final accuracy, which may lead to significant cost reductions. The natural target systems are loosely coupled decentralized distributed systems, such as P2P networks or sensor networks. So far, gossip-based algorithms have been utilized mostly for simple operations, such as aggregation (summation or averaging), information spreading or estimating size of a network.
The main focus of this thesis is on design and investigation of truly distributed matrix algorithms based on gossip-style data aggregation algorithms. Due to the specific properties of highly distributed loosely coupled systems, traditional parallel algorithmic approaches (designed for tightly coupled systems like shared-memory systems or multicore architectures) have important drawbacks, such as strong assumptions on static and known topology, reliable components and full synchronization of nodes. Hence, there is a need to design fully distributed algorithms for which these assumptions can be relaxed.
In particular, we focus on distributed Gram-Schmidt orthogonalization for computing a QR factorization, and on distributed orthogonal iteration for computing the principal eigenpairs of a matrix. We also show how distributed QR factorization can be used for solving a linear regression problem over distributed data. Concrete motivating applications for distributed orthogonalization arise, for example, in telecommunications for various computations in mobile and wireless sensor networks. An example is distributed sphere decoding, a distributed algorithm allowing a group of receiving nodes to cooperate while decoding a signal sent by a group of transmitters. Distributed orthogonalization is also an important building block for more complex distributed algorithms, such as distributed least squares solvers, eigensolvers, etc.
The need for distributed computation of eigenvalues and eigenvectors may also arise in network analysis. Some crucial properties of a graph, such as how well the graph is connected, can be determined by computing eigenvalues of the Laplacian matrix of the graph. Information about the connectivity of a graph can be found from the second smallest eigenvalue which is called the algebraic connectivity of a graph. In practice this can be applied, e.g., for detecting bottlenecks in computer networks or for analyzing relationships in social networks.
We first introduce a gossip-based distributed algorithm for Gram-Schmidt orthogonalization and we show experimentally as well as theoretically that the distributed algorithm preserves the numerical properties of the classical centralized algorithm. Moreover, we experimentally observe the influence of the level of synchronization between the nodes on the accuracy of the result. Although our algorithm requires some cooperation between nodes, very weak synchronization strategy based only on local information is sufficient for achieving accurate results.
Then, we investigate distributed orthogonal iteration as an illustrative example of using QR factorization as a building block. Apart from investigating numerical accuracy and convergence, we illustrate how accuracy-performance trade-offs can lead to significant reduction of communication cost. Moreover, using gossip-based building blocks substantially improves the robustness and fault tolerance compared to existing approaches.
Last but not least, we discuss first steps towards MPI implementations of the gossip-based algorithms for parallel computers in an effort to estimate runtime overhead of the distributed algorithms. We present first results of several runtime comparisons to standard parallel approaches, such as MPI_Allreduce or PBLAS routine pdgemv commonly used in ScaLAPACK.
Schlagwörter
Schlagwörter
(Englisch)
distributed algorithms gossip algorithms QR factorization orthogonal iteration network analysis analysis of algorithms communication cost numerical accuracy parallel algorithms MPI
Schlagwörter
(Deutsch)
verteilte Algorithmen gossip Algorithmen QR Faktorisierung Orthogonale Iteration Netzwerkanalyse Algorithmenanalyse Kommunikationsaufwand numerische Genauigkeit parallele Algorithmen MPI
Autor*innen
Hana Strakova
Haupttitel (Englisch)
Truly distributed approaches to Orthogonalization and orthogonal iteration on the basis of gossip algorithms
Paralleltitel (Deutsch)
Verteilte Methoden zur Orthogonalisierung und Orthogonalen Iteration basierend auf Gossip Algorithmen
Publikationsjahr
2013
Umfangsangabe
178 S. : graph. Darst.
Sprache
Englisch
Beurteiler*innen
Richard Vuduc ,
Marian Vajtersic
AC Nummer
AC11020522
Utheses ID
26214
Studienkennzahl
UA | 786 | 880 | |