The characteristics of irregular algorithms make a parallel implementation difficult, especially for PC clusters or clusters of SMPs. These characteristics may include an unpredictable access behavior to dynamically changing data structures or strong irregular coupling of computations. Problems are an unknown load distribution and expensive irregular communication patterns for data accesses and redistributions. Thus the parallel implementation of irregular algorithms on distributed memory machines and clusters requires a special organizational mechanism for a dynamic load balance while keeping the communication and administration overhead low. We propose task pool teams for implementing irregular algorithms on clusters of PCs or SMPs. A task pool team combines multithreaded programming using task pools on single nodes with explicit message passing between different nodes. The dynamic load balance mechanism of task pools is generalized to a dynamic load balance scheme for all distributed nodes. We have implemented and compared several versions for task pool teams. As application example, we use the hierarchical radiosity algorithm, which is based on dynamically growing quadtree data structures annotated by varying interaction lists expressing the irregular coupling between the quadtrees. Experiments are performed on a PC cluster and a cluster of SMPs.

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.

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.

Zugl.: Ulm, Univ., Diss., 2006 u.d.T.: Frenz, Stefan: Zuverlässiger verteilter Speicher mit transaktionaler Konsistenz / Hergestellt on demand

Es werden Probleme der Langzeitarchivierung diskutiert, sowohl aus Anwendersicht als auch Betreibersicht. Konkret wird das Speicherungskonzept von MONARCH vorgestellt, mit dem versucht wird, die aufgeworfenen Probleme der Langzeitarchivierung zu loesen.

The characteristics of irregular algorithms make a parallel implementation difficult, especially for PC clusters or clusters of SMPs. These characteristics may include an unpredictable access behavior to dynamically changing data structures or strong irregular coupling of computations. Problems are an unknown load distribution and expensive irregular communication patterns for data accesses and redistributions. Thus the parallel implementation of irregular algorithms on distributed memory machines and clusters requires a special organizational mechanism for a dynamic load balance while keeping the communication and administration overhead low. We propose task pool teams for implementing irregular algorithms on clusters of PCs or SMPs. A task pool team combines multithreaded programming using task pools on single nodes with explicit message passing between different nodes. The dynamic load balance mechanism of task pools is generalized to a dynamic load balance scheme for all distributed nodes. We have implemented and compared several versions for task pool teams. As application example, we use the hierarchical radiosity algorithm, which is based on dynamically growing quadtree data structures annotated by varying interaction lists expressing the irregular coupling between the quadtrees. Experiments are performed on a PC cluster and a cluster of SMPs.

Edsger W. Dijkstra prägte im Jahr 1974 den Begriff Selbststabilisierung (self-stabilization) in der Informatik. Ein System ist selbststabilisierend, wenn es von jedem denkbaren Zustand aus nach einer endlichen Anzahl von Aktionen ein stabiles Verhalten erreicht. Im Mittelpunkt dieser Arbeit steht der Entwurf selbststabilisierender Algorithmen. Wir stellen eine Petrinetz-basierte Methode zum Entwurf selbststabilisierender Algorithmen vor. Wir validieren unsere Methode an mehreren Fallstudien: Ausgehend von algorithmischen Ideen existierender Algorithmen beschreiben wir jeweils die die schrittweise Entwicklung eines neuen Algorithmus. Dazu gehört ein neuer randomisierter selbststabilisierender Algorithmus zur Leader Election in einem Ring von Prozessoren. Dieser Algorithmus ist abgeleitet aus einem publizierten Algorithmus, von dem wir hier erstmals zeigen, daß er fehlerhaft arbeitet. Wir weisen die Speicherminimalität unseres Algorithmus nach. Ein weiteres Ergebnis ist der erste Algorithmus, der ohne Time-Out-Aktionen selbststabilisierenden Tokenaustausch in asynchronen Systemen realisiert. Petrinetze bilden einen einheitlichen formalen Rahmen für die Modellierung und Verifikation dieser Algorithmen. / In 1974, Edsger W. Dijkstra suggested the notion of self-stabilization. A system is self-stabilizing if regardless of the initial state it eventually reaches a stable behaviour. This thesis focuses on the design of self-stabilizing algorithms. We introduce a new Petri net based method for the design of self-stabilizing algorithms. We validate our method on several case studies. In each of the case studies, our stepwise design starts from an algorithmic idea and leads to a new self-stabilizing algorithm. One of these algorithms is a new randomized self-stabilizing algorithm for leader election in a ring of processors. This algorithm is derived from a published algorithm which we show to be incorrect. We prove that our algorithm is space-minimal. A further result is the first algorithm for token-passing in a asynchronous environment which works without time-out actions. Petri nets form a unique framework for modelling and verification of these algorithms.

This thesis deals with the development and investigation of composite-cavity (CC) organic microresonators comprising a vertical cavity (VC) and a distributed feedback structure (DFB). Prepared as separate devices, these two resonators are extensively investigated and characterized by their far-field radiation patterns, emission spectra, and dispersion characteristics. Although the vertical and lateral systems are based on entirely different concepts leading to distinct symmetries, confinement mechanisms, and processes of optical feedback, devices produced with the same set of materials show comparable lasing thresholds. The different angular dispersions of cavity and waveguide (WG) resonances are employed in a laterally structured vertical-cavity surface-emitting laser (VCSEL), where a periodic grating serves as a diffractive coupler between these two regimes. A coherent interaction of the vertical and horizontal system is observed as pronounced anticrossings of parabolic and linear dispersion curves in the far-field spectra. As a result from this coherent coupling, the hybridized WG-VCSEL modes show stimulated emission in far-field regions, where the individual photonic structures would not reach the lasing threshold in a decoupled scenario. Efficient optical feedback in surface-normal and in-plane direction is achieved by combining a VC and a second-order DFB structure in a continuous tunable CC microresonator. The optical coupling is due to a first-order light diffraction on a second-order Bragg grating and, in the degenerate case, can be as efficient as the coupling observed in more classical cascade coupled cavities. When the system is non-degenerate, the diffraction efficiency is suppressed because of sub-coherence-length dimensions of the composite-cavity and both resonators tend to operate as independent structures, without experiencing substantial losses due to diffraction on the distributed-feedback grating. Dispersion characteristics of multiple resonances are recorded and related to calculated modes, their field profiles, and coupling efficiencies. In combination with the analysis of input-output measurements, the lasing characteristics of vertical and lateral resonances are controlled by adjusting specific design parameters of the system. For identical resonance energies, the distinct resonators show coherent interaction in the cross-coupled configuration, if the quality of the resonances and the cross-coupling efficiency meet the condition of strong photon-photon interaction. This resonant coupling has a fundamental impact on dispersion and lasing characteristics of the system. / Die vorliegende Arbeit beschäftigt sich mit der Entwicklung und Untersuchung von organischen Mikroresonatoren, die eine Kompositkavität aus einem Oberflächenemitter und einem Resonator mit verteilter Rückkopplung (DFB) beinhalten. Diese beiden Resonatortypen werden zunächst als separate Strukturen hergestellt, untersucht und über deren Intensitätsverteilungen im Fernfeld, Emissionsspektren und Dispersionseigenschaften charakterisiert. Die vertikalen und lateralen Strukturen basieren auf unterschiedlichen Konzepten, die zu völlig verschiedenartigen Symmetrien, Mechanismen des elektromagnetischen Einschlusses und Arten der optischen Rückkopplung führen. Nichtsdestotrotz weisen diese Resonatoren, die mit dem gleichen Materialsatz hergestellt wurden, ähnliche Laserschwellen auf. Die unterschiedliche winkelabhängige Dispersion von Vertikal- und Wellenleitermoden werden in einem lateral strukturierten Oberflächenemitter (VCSEL) ausgenutzt. In dieser Struktur dient eine periodisches Gitter als Kopplungselement zwischen diesen beiden Bereichen. Eine kohärente Wechselwirkung zwischen vertikalem und horizontalem System zeigt sich durch das Auftreten von ausgeprägten Antikreuzungspunkten parabolischer und gerader Dispersionskurven in den winkelaufgelösten Emissionsspektren. Die Folge dieser kohärenten Kopplung ist das Entstehen von Lasermoden in Bereichen des Fernfelds, wo die einzelnen Resonatoren im entkoppelten Zustand die Laserschwelle nicht erreichen würden. Eine wirksame optische Rückkopplung sowohl in Richtung der Oberflächennormalen als auch in lateraler Richtung wird durch die Kombination einer VCSEL und einer DFB-Struktur zweiter Ordnung in einem kontinuierlich durchstimmbaren Kompositresonator erreicht. Die optische Kopplung wird durch Beugung erster Ordnung am Bragg-Gitter zweiter Ordnung realisiert. Im entarteten Fall werden Kopplungseffizienzen beobachtet, die vergleichbar mit denen klassisch kaskadengekoppelter Mikrokavitäten sind. Für verschiedene Energieeigenwerte der zwei Resonatorkomponenten führt die im Vergleich zur Kohärenzlänge geringe Ausdehnung der Kompositkavität zu einer nahezu unabhängigen Tätigkeit der beiden Resonatoren mit nur geringen Verlusten durch Beugung an der periodischen Struktur. Die Dispersionseigenschaften von mehreren Resonanzen werden gemessen und berechneten Moden, deren Feldverteilungen und Kopplungseffizienzen zugeordnet. In Verbindung mit der Analyse der Intensitäten der Lasermoden in Abhängigkeit der Pumpleistung werden die Laserschwellen durch die Anpassung spezifischer Designparameter kontrolliert. Für identische Resonanzenergien weisen die unterschiedlichen Resonatoren eine kohärente Wechselwirkung auf, falls die Qualität der Moden und die Beugungseffizienz die Bedingung für starke Photon-Photon-Kopplung erfüllen. Diese resonante Kopplung zeigt einen fundamentalen Einfluss auf die Dispersions- und Lasereigenschaften im Kompositsystem.

Die vorliegende Arbeit beschäftigt sich mit der Entwicklung und Optimierung von Terahertz-Quantenkaskadenlasern (THz-QCLs) für die Anwendung als Lokaloszillator in THz-Heterodyndetektoren, insbesondere für die Detektion der astronomisch wichtigen Sauerstoff (OI) Linie bei 4.75 THz. Hierfür wurden zunächst unterschiedliche QCL-Heterostrukturen untersucht. Basierend auf einer Heterostruktur, welche schnelle Intersubbandübergänge über Streuung an Phononen ausnutzt, konnten QCLs mit hoher Ausgangsleistung und niedriger Betriebsspannung bei 3 THz erzielt werden. Während diese Laser auf dem Materialsystem GaAs/Al_xGa_(1-x)As mit $x=0.15$ basieren, führt die Erhöhung des Al-Anteils auf x=0.25 für ähnliche Strukturen zu sehr niedrigen Schwellstromdichten. Durch schrittweise Optimierungen gelang es, QCLs zu realisieren, die bei 4.75 THz emittieren. Mit Hilfe von lateralen Gittern erster Ordnung für die verteilte Rückkopplung (DFB) konnten Einzelmoden-Dauerstrichbetrieb mit hoher Ausgangsleistung, sowie Einzelmoden-Betrieb innerhalb des spezifizierten Frequenzbereichs bei 4.75 THz erzielt werden. Eine allgemeine Methode zur Bestimmung der DFB-Kopplungskonstanten erlaubt eine gute Beschreibung der Laser innerhalb der etablierten Theorie der gekoppelten Moden für DFB-Laser mit reflektiven Endfacetten. Oft steht das Auftreten negativer differentieller Leitfähigkeit bei höheren Feldstärken und die damit verbundenen Bildung von elektrischer Felddomänen (EFDs) im Konflikt mit einem stabilen Betrieb der THz-QCLs. Es wird gezeigt, dass stationäre EFDs mit Diskontinuitäten in der statischen Licht-Strom-Spannungskennlinie verbunden sind, während Selbstoszillationen, verursacht durch nicht-stationäre EFDs, eine zeitliche Modulation der Ausgangsleistung bewirken. Mit Hilfe einer effektiven Driftgeschwindigkeit für QCLs lassen sich viele der beobachteten Phänomene durch die nichtlinearen Transportgleichungen für schwach gekoppelte Übergitter beschreiben. / This thesis presents the development and optimization of terahertz quantum-cascade lasers (THz QCLs) as sources for heterodyne receivers. A particular focus is on single-mode emitters for the heterodyne detection of the important astronomic oxygen (OI) line at 4.75 THz. Various active-region designs are investigated. High-output-power THz QCLs with low operating voltages and emission around 3 THz are obtained for an active region, which involves phonon-assisted intersubband transitions. While these QCLs are based on a GaAs/Al_xGa_(1-x)As heterostructure with x=0.15, similar heterostructures with x=0.25 allowed for very low threshold current densities. By successive modifications of the active-region design, THz QCLs have been optimized toward the desired frequency at 4.75 THz. To obtain single-mode operation, first-order lateral distributed-feedback (DFB) gratings are investigated. It shows that such gratings allow for single-mode operation in combination with high continuous-wave (cw) output powers. A general method is presented to calculate the coupling coefficients of lateral gratings. In conjunction with this method, the lasers are well described by the coupled-mode theory of DFB lasers with two reflective end facets. Single-mode operation within the specified frequency bands at 4.75 THz is demonstrated. Stable operation of THz QCLs is often in conflict with the occurrence of a negative differential resistance (NDR) regime at elevated field strengths and the formation of electric-field domains (EFDs). Stationary EFDs are shown to be related to discontinuities in the cw light-current-voltage characteristics, while non-stationary EFDs are related to current self-oscillations and cause a temporal modulation of the output power. To model such effects, the nonlinear transport equations of weakly coupled superlattices are adopted for QCLs by introducing an effective drift velocity-field relation.

Eine Herausforderung der Parallelverarbeitung ist das Erreichen von Skalierbarkeit großer paralleler Anwendungen für verschiedene parallele Systeme. Das zentrale Problem ist, dass die Ausführung einer Anwendung auf einem parallelen System sehr gut sein kann, die Portierung auf ein anderes System in der Regel jedoch zu schlechten Ergebnissen führt. Durch die Verwendung des Programmiermodells der parallelen Tasks mit Abhängigkeiten kann die Skalierbarkeit für viele parallele Algorithmen deutlich verbessert werden. Die Programmierung mit parallelen Tasks führt zu Task-Graphen mit Abhängigkeiten zur Darstellung einer parallelen Anwendung, die auch als gemischt-parallele Anwendung bezeichnet wird. Die Grundlage für eine effiziente Abarbeitung einer gemischt-parallelen Anwendung bildet ein geeigneter Schedule, der eine effiziente Abbildung der parallelen Tasks auf die Prozessoren des parallelen Systems vorgibt. Für die Berechnung eines Schedules werden Schedulingalgorithmen eingesetzt. Ein zentrales Problem bei der Bestimmung eines Schedules für gemischt-parallele Anwendungen besteht darin, dass das Scheduling bereits für Single-Prozessor-Tasks mit Abhängigkeiten und ein paralleles System mit zwei Prozessoren NP-hart ist. Daher existieren lediglich Approximationsalgorithmen und Heuristiken um einen Schedule zu berechnen. Eine Möglichkeit zur Berechnung eines Schedules sind layerbasierte Schedulingalgorithmen. Diese Schedulingalgorithmen bilden zuerst Layer unabhängiger paralleler Tasks und berechnen den Schedule für jeden Layer separat. Eine Schwachstelle dieser Schedulingalgorithmen ist das Zusammenfügen der einzelnen Schedules zum globalen Schedule. Der vorgestellte Algorithmus Move-blocks bietet eine elegante Möglichkeit das Zusammenfügen zu verbessern. Dies geschieht durch eine Verschmelzung der Schedules aufeinander folgender Layer. Obwohl eine Vielzahl an Schedulingalgorithmen für gemischt-parallele Anwendungen existiert, gibt es bislang keine umfassende Unterstützung des Schedulings durch Programmierwerkzeuge. Im Besonderen gibt es keine Schedulingumgebung, die eine Vielzahl an Schedulingalgorithmen in sich vereint. Die Vorstellung der flexiblen, komponentenbasierten und erweiterbaren Schedulingumgebung SEParAT ist der zweite Fokus dieser Dissertation. SEParAT unterstützt verschiedene Nutzungsszenarien, die weit über das reine Scheduling hinausgehen, z.B. den Vergleich von Schedulingalgorithmen und die Erweiterung und Realisierung neuer Schedulingalgorithmen. Neben der Vorstellung der Nutzungsszenarien werden sowohl die interne Verarbeitung eines Schedulingdurchgangs als auch die komponentenbasierte Softwarearchitektur detailliert vorgestellt.