We present a MPI based software library for computing the fast Fourier transforms on massively parallel, distributed memory architectures. Similar to established transpose FFT algorithms, we propose a parallel FFT framework that is based on a combination of local FFTs, local data permutations and global data transpositions. This framework can be generalized to arbitrary multi-dimensional data and process meshes. All performance relevant building blocks can be implemented with the help of the FFTW software library. Therefore, our library offers great flexibility and portable performance. Likewise FFTW, we are able to compute FFTs of complex data, real data and even- or odd-symmetric real data. All the transforms can be performed completely in place. Furthermore, we propose an algorithm to calculate pruned FFTs more efficiently on distributed memory architectures. For example, we provide performance measurements of FFTs of size 512^3 and 1024^3 up to 262144 cores on a BlueGene/P architecture.

We study anomalous diffusion on fractals with a static external field applied. We utilise the master equation to calculate particle distributions and from that important quantities as for example the mean square displacement <r^2(t)>. Applying different bias amplitudes on several regular Sierpinski carpets we obtain maximal drift velocities for weak field strengths. According to <r^2(t)>~t^(2/d_w), we determine random walk dimensions of d_w<2 for applied external fields. These d_w corresponds to superdiffusion, although diffusion is hindered by the structure of the carpet, containing dangling ends. This seems to result from two competing effects arising within an external field. Though the particles prefer to move along the biased direction, some particles get trapped by dangling ends. To escape from there they have to move against the field direction. Due to the by the bias accelerated particles and the trapped ones the probability distribution gets wider and thus d_w<2. / In dieser Arbeit untersuchen wir anomale Diffusion auf Fraktalen unter Einwirkung eines statisches äußeres Feldes. Wir benutzen die Mastergleichung, um die Wahrscheinlichkeitsverteilung der Teilchen zu berechnen, um daraus wichtige Größen wie das mittlere Abstandsquadrat <r^2(t)> zu bestimmen. Wir wenden unterschiedliche Feldstärken bei verschiedenen regelmäßigen Sierpinski-Teppichen an und erhalten maximale Driftgeschwindigkeiten für schwache Feldstärken. Über <r^2(t)>~t^{2/d_w} bestimmen wir die Random-Walk-Dimension d_w als d_w<2. Dieser Wert für d_w entspricht der Superdiffusion, obwohl der Diffusionsprozess durch Strukturen des Teppichs, wie Sackgassen, behindert wird. Es schient, dass dies das Ergebnis zweier konkurrierender Effekte ist, die durch das Anlegen eines äußeren Feldes entstehen. Einerseits bewegen sich die Teilchen bevorzugt entlang der Feldrichtung. Andererseits gelangen einige Teilchen in Sackgassen. Um die Sackgassen, die in Feldrichtung liegen, zu verlassen, müssen sich die Teilchen entgegen der Feldrichtung bewegen. Somit sind die Teilchen eine gewisse Zeit in der Sackgasse gefangen. Infolge der durch das äußere Feld beschleunigten und der gefangenen Teilchen, verbreitert sich die Wahrscheinlichkeitsverteilung der Teilchen und somit ist d_w<2.

We investigate the numerical solution of stable Sylvester equations via iterative schemes proposed for computing the sign function of a matrix. In particular, we discuss how the rational iterations for the matrix sign function can efficiently be adapted to the special structure implied by the Sylvester equation. For Sylvester equations with factored constant term as those arising in model reduction or image restoration, we derive an algorithm that computes the solution in factored form directly. We also suggest convergence criteria for the resulting iterations and compare the accuracy and performance of the resulting methods with existing Sylvester solvers. The algorithms proposed here are easy to parallelize. We report on the parallelization of those algorithms and demonstrate their high efficiency and scalability using experimental results obtained on a cluster of Intel Pentium Xeon processors.

Many parallel applications from scientific computing use MPI collective communication operations to collect or distribute data. Since the execution times of these communication operations increase with the number of participating processors, scalability problems might occur. In this article, we show for different MPI implementations how the execution time of collective communication operations can be significantly improved by a restructuring based on orthogonal processor structures with two or more levels. As platform, we consider a dual Xeon cluster, a Beowulf cluster and a Cray T3E with different MPI implementations. We show that the execution time of operations like MPI Bcast or MPI Allgather can be reduced by 40% and 70% on the dual Xeon cluster and the Beowulf cluster. But also on a Cray T3E a significant improvement can be obtained by a careful selection of the processor groups. We demonstrate that the optimized communication operations can be used to reduce the execution time of data parallel implementations of complex application programs without any other change of the computation and communication structure. Furthermore, we investigate how the execution time of orthogonal realization can be modeled using runtime functions. In particular, we consider the modeling of two-phase realizations of communication operations. We present runtime functions for the modeling and verify that these runtime functions can predict the execution time both for communication operations in isolation and in the context of application programs.

Für die schnelle Visualisierung großer Modelle werden sogenannte Echtzeit-Visualisierungsverfahren (real time rendering techniques) eingesetzt. Durch parallele Verarbeitung der Objektdaten auf Multicore-CPUs ist es möglich, die Geschwindigkeit der Darstellung gegenüber GPU-basierten Verfahren weiter zu erhöhen. Insbesondere wurde die Möglichkeit untersucht, das Occlusion-Culling mit Hilfe der CPU durchzuführen. Dabei konnte speziell das Worst-Case-Verhalten verbessert werden. Mit der Anzahl der Systemkomponenten (z.B. Trackingsystem, Beamer, Rechner) steigt die Trägheit (Latenz) des Gesamtsystems, was eine Echtzeitverarbeitung der Daten deutlich erschwert. Durch Bewegungsvorhersagen, die speziell an das Nutzerverhalten im Rahmen der Anwendung angepasst sind, können auftretende Latenzen kompensiert werden. Die Entwicklungen erfolgten im Kontext einer immersiven Tischtennissimulation. Tischtennis gehört zu den schnellsten Sportarten und repräsentiert somit eine anspruchsvolle Umgebung. Ein weiterer wichtiger Aspekt bei der Interaktion mit virtuellen Umgebungen ist die Natürlichkeit (Intuitivität) der Benutzeroberfläche. Durch eine möglichst direkte (aus der Realität bekannte) Umsetzung der Benutzerbewegungen in Systembefehle wird eine höchstmögliche Effektivität im Umgang mit dem System erzielt. Im Rahmen einer Designanwendung wurden Interaktionstechniken realisiert, die den alltäglichen Bewegungsabläufen nachempfunden sind.

In dieser Arbeit wurde ein Verfahrung zur Random-Walk-Simulation auf fraktalen Strukturen untersucht. Es dient der Simulation von Diffusion in porösen Materialien. Konkret wurde der Mastergleichungsansatz zur Simulation eines Random Walks auf Sierpiński-Teppichen für GPGPUs (General Purpose Graphics Processing Units) in drei verschiedenen Versionen implementiert: Zunächst wurde die gesamte Fläche in einem zweidimensionalen Array gespeichert. Danach wurde eine Version untersucht, bei der nur die begehbaren Felder abgespeichert wurden. Diese Vorgehensweise spart Speicher, da die Sierpiński-Teppiche meist nur dünn besetzt sind. Weiter wurde die Implementierung verbessert, indem die Fläche jeweils dynamisch erweitert wird, wenn die Simulation an den Rand des vorhandenen Gebietes stößt. Die genutzten Grafikprozessoren arbeiten nach dem SIMD-Prinzip. Daher wurde zusätzlich untersucht, ob sich Laufzeitverbesserungen ergeben, wenn der Code dahingehend optimiert wird. Die Ergebnisse zeigen, dass sich in der Tat eine kürzere Laufzeit ergibt, wenn nur noch begehbare Felder abgespeichert werden. Noch weiter kann die Laufzeit mit der dynamischen Erweiterung der Simulationsfläche verkürzt werden. Optimierungen für die SIMD-Arbeitsweise der Prozessoren bringen jedoch keine Laufzeitver besserung. / This thesis investigates an algorithm for random walk simulations on fractal structures. Its purpose is the simulation of diffusion in porous materials. Indeed the master equation approach for the simulation of random walks on Sierpiński carpets has been implemented for GPGPUs (general purpose graphics processing units) in three different versions: In the first approach the whole carpet has been saved in a two-dimensional array. Secondly a version was investigated that only saves the present cells. This strategy saves memory as Sierpiński carpets are generally sparse. The implementation has been further improved by extending the carpet dynamically each time when the simulation reaches its current border. The graphics processing units that were used have a SIMD architecture. Therefore it has been investigated additionally if optimization for the SIMD architecture leads to performance improvements. The results show that execution time does indeed decrease if only present cells are being saved. It can be decreased further by dynamically extending the carpet. Optimizations for the SIMD architecture did not result in a reduced execution time.

Pattern matching on large graphs is the foundation for a variety of application domains. The continuously increasing size of the underlying graphs requires highly parallel in-memory graph processing engines that need to consider non-uniform memory access (NUMA) and concurrency issues to scale up on modern multiprocessor systems. To tackle these aspects, a fine-grained graph partitioning becomes increasingly important. Hence, we present a classification of graph partitioning strategies and evaluate representative algorithms on medium and large-scale NUMA systems in this paper. As a scalable pattern matching processing infrastructure, we leverage a data-oriented architecture that preserves data locality and minimizes concurrency-related bottlenecks on NUMA systems. Our in-depth evaluation reveals that the optimal partitioning strategy depends on a variety of factors and consequently, we derive a set of indicators for selecting the optimal partitioning strategy suitable for a given graph and workload.

Nichtlineare Finite-Element-Probleme sind unentbehrlich für die Modellierung und Simulation im Bereich der Mechanik. Für die Lösung solcher Probleme sind schnelle und robuste Algorithmen unverzichtbar. Nichtlineare FETI--DP-Verfahren haben ihre Robustheit und Skalierbarkeit für Probleme der nichtlinearen Strukturmechanik nachgewiesen. Typischerweise werden diese nichtlinearen FETI--DP-Verfahren in Kombination mit dem Newton-Verfahren oder Varianten des Newton-Verfahrens verwendet. Diese Verfahren sind nicht global konvergent. In der vorliegenden Arbeit wird gezeigt, wie nichtlineares FETI--DP unter Verwendung einer exakten differenzierbaren Penalty-Funktion oder mittels eines SQP-Verfahren globalisiert werden kann. Es werden Standardkonvergenzaussagen, unter direkter Verwendung von nichtlinearer Elimination, welche ein zentraler Baustein für nichtlineares FETI--DP ist, bewiesen. Numerische Ergebnisse zeigen, dass die Robustheit und Skalierbarkeit durch die Globalisierung erhalten bleiben.

Partikelsimulationen repräsentieren eine Klasse von daten- und rechenintensiven Simulationsanwendungen, die in unterschiedlichen Bereichen der Wissenschaft und der industriellen Forschung zum Einsatz kommen. Der hohe Berechnungsaufwand der eingesetzten Lösungsmethoden und die großen Datenmengen, die zur Modellierung realistischer Probleme benötigt werden, machen die Nutzung paralleler Rechentechnik hierfür unverzichtbar. Parallelrechner mit verteiltem Speicher stellen dabei eine weit verbreitete Architektur dar, bei der eine Vielzahl an parallel arbeitenden Rechenknoten über ein Verbindungsnetzwerk miteinander Daten austauschen können. Die Berechnung von Wechselwirkungen zwischen Partikeln stellt oft den Hauptaufwand einer Partikelsimulation dar und wird mit Hilfe schneller Lösungsmethoden, wie dem Barnes-Hut-Algorithmus oder der Schnellen Multipolmethode, durchgeführt. Effiziente parallele Implementierungen dieser Algorithmen benötigen dabei eine Sortierung der Partikel nach ihren räumlichen Positionen. Die Sortierung ist sowohl notwendig, um einen effizienten Zugriff auf die Partikeldaten zu erhalten, als auch Teil von Optimierungen zur Erhöhung der Lokalität von Speicherzugriffen, zur Minimierung der Kommunikation und zur Verbesserung der Lastbalancierung paralleler Berechnungen. Die vorliegende Dissertation beschäftigt sich mit der Entwicklung eines effizienten parallelen Sortierverfahrens und der dafür benötigten Kommunikationsoperationen zur Datenumverteilung in Partikelsimulationen. Hierzu werden eine Vielzahl existierender paralleler Sortierverfahren für verteilten Speicher analysiert und mit den Anforderungen von Seiten der Partikelsimulationsanwendungen verglichen. Besondere Herausforderungen ergeben sich dabei hinsichtlich der Aufteilung der Partikeldaten auf verteilten Speicher, der Gewichtung zu sortierender Daten zur verbesserten Lastbalancierung, dem Umgang mit doppelten Schlüsselwerten sowie der Verfügbarkeit und Nutzung speichereffizienter Kommunikationsoperationen. Um diese Anforderungen zu erfüllen, wird ein neues paralleles Sortierverfahren entwickelt und in die betrachteten Anwendungsprogramme integriert. Darüber hinaus wird ein neuer In-place-Algorithmus für der MPI_Alltoallv-Kommunikationsoperation vorgestellt, mit dem der Speicherverbrauch für die notwendige Datenumverteilung innerhalb der parallelen Sortierung deutlich reduziert werden kann. Das Verhalten aller entwickelten Verfahren wird jeweils isoliert und im praxisrelevanten Einsatz innerhalb verschiedener Anwendungsprogramme und unter Verwendung unterschiedlicher, insbesondere auch hochskalierbarer Parallelrechner untersucht.

Die komplexen Interaktionen von Aerosolen, Wolken und Niederschlag werden in aktuellen Vorhersagemodellen nur ungenügend dargestellt. Simulationen mit spektraler Beschreibung von Wolkenprozessen können zu verbesserten Vorhersagen beitragen, sind jedoch weitaus rechenintensiver. Die Beschleunigung dieser Simulationen erfordert eine hochparallele Ausführung. In dieser Arbeit wird ein Konzept zur Kopplung spektraler Wolkenmikrophysikmodelle mit atmosphärischen Modellen entwickelt, das eine effiziente Nutzung der heute verfügbaren Parallelität der Größenordnung von 100.000 Prozessorkernen ermöglicht. Aufgrund des stark variierenden Rechenaufwands ist dafür eine hochskalierbare dynamische Lastbalancierung des Wolkenmikrophysikmodells unumgänglich. Dies wird durch ein hierarchisches Partitionierungsverfahren erreicht, das auf raumfüllenden Kurven basiert. Darüber hinaus wird eine hochskalierbare Verknüpfung von dynamischer Lastbalancierung und Modellkopplung durch ein effizientes Verfahren für die regelmäßige Bestimmung der Überschneidungen zwischen unterschiedlichen Partitionierungen ermöglicht. Durch die effiziente Nutzung von Hochleistungsrechnern ermöglichen die Ergebnisse der Arbeit die Anwendung spektraler Wolkenmikrophysikmodelle zur Simulation realistischer Szenarien auf hochaufgelösten Gittern. / Current forecast models insufficiently represent the complex interactions of aerosols, clouds and precipitation. Simulations with spectral description of cloud processes allow more detailed forecasts. However, they are much more computationally expensive. Reducing the runtime of such simulations requires a highly parallel execution. This thesis presents a concept for coupling spectral cloud microphysics models with atmospheric models that allows for efficient utilization of today\'s available parallelism in the order of 100.000 processor cores. Due to the strong workload variations, highly scalable dynamic load balancing of the cloud microphysics model is essential in order to reach this goal. This is achieved through a hierarchical partitioning method based on space-filling curves. Furthermore, a highly scalable connection of dynamic load balancing and model coupling is facilitated by an efficient method to regularly determine the intersections between different partitionings. The results of this thesis enable the application of spectral cloud microphysics models for the simulation of realistic scenarios with high resolution grids by efficient use of high performance computers.