Detailansicht
Investigation of strategies for the parallel computation of eigenvectors of block tridiagonal matrices
parallel twisted block factorizations
Michael Moldaschl
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Betreuer*in
Wilfried Gansterer
DOI
10.25365/thesis.16304
URN
urn:nbn:at:at-ubw:1-30294.70151.299469-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Heutzutage ist es essenziell das Berechnen auf viele Recheneinheiten parallelisieren und neue Hardware und deren neuen Merkmale effizient verwenden zu können. Die Algorithmen, welche zum Beispiel in LAPACK verwendet werden, sind für den sequentiellen Ablauf konstruiert und sind in deren Parallelisierung limitiert. Außerdem ist ScaLAPACK nicht für gemeinsam genutzten Speicher, wie auch in den Ergebnissen dieser Masterarbeit zu sehen ist, optimiert. Deswegen ist es notwendig andere Algorithmen zu finden bei denen die Arbeit einfacher auf großen Systemen basierend auf einer multi-core Architektur verteilt werden können. Weiters ist es wichtig die Struktur spezieller Probleme auszunutzen. Die twisted block Faktorisierung kann verwendet werden um Eigenvektoren von Block-Tridiagonalen-Matrizen zu berechnen. Aus all diesen Gründen wird dieser Algorithmus, mit der Möglichkeit auf viele unabhängige Operationen, auf aktueller Harware parallelisiert um auch Aspekte von neuen Hardwarearchitekturen zu analysieren.
Verschiedene Parallelisierungsstrategien sind entwickelt und implementiert worden um zu evaluieren wie die twisted block Faktorisierung am effizientesten parallelisiert werden kann. Die Evaluierung zeigt das die Parallelisierungsstrategien effizienter sind als die getestete ScaLAPACK-Routine und neue Prozessoreigenschaften können den Speedup eines parallelen Programms stark beeinflussen. Außerdem zeigt die detaillierte Analyse der Laufzeit die neue Aufgabe effiziente Funktionen für multi-core Systeme erstellen zu müssen. Die numerische Genauigkeit ist nicht der Hauptaspekt der Arbeit, aber eine sehr interessante Korrelation zwischen dem Abstand der Eigenwerte und der Orthogonalität der Eigenvektoren wurde gefunden.
Abstract
(Englisch)
Today it is essential that the computation can be parallelized on many computing units and new hardware and their new features can be used efficiently. The algorithms used for example in LAPACK are constructed for sequential process and are limited in their parallelization and furthermore ScaLAPACK is not optimized for shared memory systems like we can also see in the results of this master thesis. Therefore it is necessary to look for other algorithms where the work can be easier distributed on large systems based on a multi-core architecture. Furthermore it is important to exploit the structure of specific problems. The twisted block factorization can be used to compute the eigenvectors of a block tridiagonal matrix. For all this reasons this algorithm, with the possibility of many independent operations, is parallelized on state-of-the-art hardware to mention also the aspects of new hardware architectures.
Different parallelization strategies are investigated and implemented to evaluate how the twisted block factorization can be parallelized most efficiently. The evaluation shows that the parallelization strategies are more efficient than the tested ScaLAPACK-Routine and new CPU features are able to strongly influence the speedup of parallel programs. Furthermore the detailed analysis of the runtime shows the new challenge of creating an efficient function on a multi-core system. The numerical accuracy is not the main aspect of this work, but a very interesting correlation between the distance of the eigenvalues and the orthogonality of the eigenvectors was found.
Schlagwörter
Schlagwörter
(Englisch)
Eigenproblem twisted block factorization inverse iteration Block Tridiagonal Matrix Parallelization
Schlagwörter
(Deutsch)
Eigenwertproblem Twisted Block Faktorisierung Inverse Iteration Block Tridiagonalmatrix Parallelisierung
Autor*innen
Michael Moldaschl
Haupttitel (Englisch)
Investigation of strategies for the parallel computation of eigenvectors of block tridiagonal matrices
Hauptuntertitel (Englisch)
parallel twisted block factorizations
Paralleltitel (Deutsch)
Untersuchung von Strategien für die parallele Berechnung von Eigenvektoren von block tridiagonalen Matrizen ; Parallele twisted block Faktorisierungen
Publikationsjahr
2011
Umfangsangabe
69 S. : graph. Darst.
Sprache
Englisch
Beurteiler*in
Wilfried Gansterer
Klassifikationen
54 Informatik > 54.50 Programmierung: Allgemeines ,
54 Informatik > 54.80 Angewandte Informatik
AC Nummer
AC08807954
Utheses ID
14620
Studienkennzahl
UA | 066 | 940 | |