Truly distributed approaches to Orthogonalization and orthogonal iteration on the basis of gossip algorithms
Hana Straková · 2013
Gossip bzw. epidemische Algorithmen sind Kommunikationsprotokolle in welchen Knoten ausschlieslich mit zufallig bestimmten unmittelbaren Nachbarn Nachrichten austauschen. Aufgrund ihrer randomisierten Kommunikation sind diese Algorithmen auserst flexibel bzgl. der zu Grunde liegenden Hardwareinfrastruktur, sowie der Netzwerktopologie. Daruber hinaus konnen 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 hauptsachlich fur 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 naturliche 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. Daruber hinaus zeigen wir, wie mit Hilfe einer verteilten QR Faktorisierung lineare Regressionsprobleme uber verteilten (Mess-)Daten gelost werden konnen. Aufgrund der Spezifika dezentraler verteilter Systeme ist es nicht bzw. nur sehr schwer moglich existierende Algorithmen aus der parallelen Datenverarbeitung direkt zu ubernehmen, da diese an Regularitatsanforderungen gebunden sind, die verteilte Systeme nicht erfullen. Daher ist es eine Notwendigkeit spezifische (verteilte) Algorithmen fur 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 Empfangern, durch einen verteilten Algorithmus, die Kooperation wahrend des Dekodierens von Signalen einer Gruppe von Sendern ermoglicht. Anwendungen der verteilten Orthogonalen Iteration finden sich unter anderem in der Netzwerkanalyse, wo z. B. mittels spezifischer Eigenwerte und Eigenvektoren Aussagen uber die Konnektivitat des Netzwerks getroffen werden konnen. Zunachst fuhren 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 erhalt. Daruber 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 mussen, sind nur einfachste lokale Synchronisationsmechanismen von Noten, 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 konnen. Zusatzlich liefert der Einsatz von gossip-basierten Elementaroperationen auch substantiell robustere bzw. fehlertolerante Algorithmen (im Vergleich zu existierenden Methoden). Abschliesend prasentieren wir erste Schritte in Richtung einer MPI Implementierung der untersuchten gossip-basierten Algorithmen fur Parallelrechner. Diese Untersuchungen dienen zur Quantifizierung des Mehraufwands den verteilte Algorithmen mit sich bringen. Konkret prasentieren wir erste Vergleiche mit etablierten parallelen Routinen wie MPI_Allreduce bzw. der PBLAS Routine pdgemv die in ScaLAPACK Verwendung findet.