32 search hits
-
Parallel Low-Storage Runge-Kutta Solvers for ODE Systems with Limited Access Distance
(2010)
-
Matthias Korch
Thomas Rauber
- We consider the solution of initial value problems (IVPs) of large systems of ordinary differential equations (ODEs) for which memory space requirements determine the choice of the integration method. In particular, we discuss the space-efficient sequential and parallel implementation of embedded Runge-Kutta (RK) methods. We focus on the exploitation of a special structure of commonly appearing ODE systems, referred to as "limited access distance", to improve scalability and memory usage. Such systems may arise, for example, from the semi-discretization of partial differential equations (PDEs). The storage space required by classical RK methods is directly proportional to the dimension n of the ODE system and the number of stages s of the method. We propose an implementation strategy based on a pipelined processing of the stages of the RK method and show how the memory usage of this computation scheme can be reduced to less than three storage registers by an overlapping of vectors without compromising the choice of method coefficients or the potential for efficient stepsize control. We analyze and compare the scalability of different parallel implementation strategies in detailed runtime experiments on different parallel architectures.
-
Ansätze zur flexiblen Navigation in Prozessabläufen
(2009)
-
Christoph Günther
- Prozessnavigationssysteme oder Workflow Management Systeme (WFMS) sind ein wesentlicher Bestandteil vieler Betriebe und Organisationen. Aktuell zeigen sich einige Probleme wie Inakzeptanz durch die Benutzer und Effizienzverlust in Betriebsprozessen, da derzeit gängige Systeme starr und unflexibel sind. In dieser Arbeit soll ein wesentlich flexiblerer Ansatz betrachtet werden. Es wird nur noch ein Rahmen vorgegeben, der den Erfolg des Workflow sicher stellt. Die Entscheidung der Prozessschrittabfolge wird hierbei nur beratend unterstützt, dem Benutzer jedoch die Entscheidung überlassen. Das System sucht also alle möglichen nächsten Prozessschritte und schlägt sie dem Benutzer vor. Durch die große Anzahl der Kombinationsmöglichkeiten sind innovative Ansätze gefordertum ein performantes System zu bieten. In dieser Arbeit werden Probleme aufgezeigt, diskutiert und gelöst um am Ende einen sehr performanten und hochflexiblen Ansatz zur Prozessnavigation vorzustellen.
-
Multi-View Reconstruction in-between Known Environments
(2010)
-
Stefan Kuhn
Dominik Henrich
- We present a novel multi-view 3D reconstruction algorithm which unifies the advantages of several recent reconstruction approaches. Based on a known environment causing occlusions and on the cameras pixel grid discretization, an irregular partitioning of the reconstruction space is chosen. Reconstruction artifacts are rejected by using plausibility checks based on additional information about the objects to be reconstructed. The binary occupancy decision is solely performed in reconstruction space instead of fusing back-projected silhouettes in image space. Hierarchical data structures are used to reconstruct the objects progressively focusing on boundary regions. Thus, the algorithm can be stopped at any time with a certain conservative level of detail. Most parts of the algorithm may be processed in parallel using GPU programming techniques. The main application domain is the surveillance of real environments like in human/robot coexistence and cooperation scenarios.
-
Erweiterung des Threadmodelles fur den Einsatz in verteilten und heterogenen Systemumgebungen
(2009)
-
Raik Nagel
- Für die klassischen distributed memory und shared memory Architekturen kann bei der Programmierung auf bewährte nachrichten- und threadbasierte Programmiermodelle zurückgegriffen werden. Die weite Verbreitung und Akzeptanz dieser Modelle ermöglicht den portablen Einsatz und die Migration von bestehenden Programmen auf andere gleichartige Computersysteme. In verteilten heterogenen Systemumgebungen, die aus einer Vielzahl von unterschiedlichen Computerknoten bestehen und über ein Netzwerk miteinander verbunden sind, wird meistens ein nachrichtenbasiertes Programmiermodell verwendet. Neben praktischen Problemen, wie der Sicherstellung der korrekten Datendarstellung beim Nachrichtenaustausch zwischen Knoten mit unterschiedlicher Prozessorarchitektur, ergeben sich weitere Fragestellungen, die eine Erstellung und Portierung von Programmen für solche Ausführungsumgebungen erschweren. So ist man beispielsweise bei der Verwendung einer MPI-Bibliothek meist an ein Netzwerk gebunden und kann oft Systeme mit unterschiedlichen Prozessorarchitekturen nicht gleichzeitig verwenden. Im ersten Teil der vorliegenden Arbeit wird das Modell einer hybriden Programmierumgebung vorgestellt. Durch die Verwendung von Konzepten aus den thread- und nachrichtenbasierten Programmiermodellen soll eine leichte Einarbeitung in das System und ein breites Einsatzgebiet ermöglicht werden. Im Anschluß an die Spezifikationen und Definitionen der Programmierumgebung und des Programmiermodelles wird die hierfür erstellte Prototypimplementierung beschrieben. Diese Prototypimplementierung erlaubt die Ausführung von Programmen in verteilten heterogenen Systemumgebungen und zeichnet sich durch eine hohe Modularität aus. Dies bedeutet, daß nahezu jede Komponente des Systems austauschbar ist und Funktionen bereitstellt, welche in der allgemeinen Spezifikation der Umgebung definiert werden. F"ur verschiedene Zielsetzungen des Anwenders, wie z.B. die Sicherheit der Datenübertragung oder eine hohe Fehlertoleranz der gesamten Kommunikation, lassen sich so unterschiedliche Komponenten in das Laufzeitsystem einbinden, ohne das Benutzerprogramm neu erstellen oder anpassen zu müssen. Die Benutzung und Einbindung von bereits existierenden, externen Implementierungen für solche Anforderungen ist ebenfalls möglich und reduziert den Entwicklungsaufwand neuer Komponenten des Laufzeitsystems. In der Arbeit wird das unter anderen anhand der TSpaces-Bibliothek von IBM als alternatives Speichersystem demonstriert. Die sich im zweiten Teil der Arbeit anschließenden Kapitel befassen sich mit mehreren Umsetzungen von numerischen Algorithmen für die erstellte Prototypimplementierung der beschriebenen Programmierumgebung. Die erzielten Ergebnisse zeigen, daß die im Vorfeld definierten Ziele erreicht werden können und die resultierenden Programme mit unterschiedlichen Systemkonfigurationen lauffähig sind.
-
Multi-View Reconstruction of Unknown Objects in the Presence of Known Occlusions
(2009)
-
Stefan Kuhn
Dominik Henrich
- We present a general method for reconstructing unknown objects (e.g. humans) within a known environment (e.g. tables, racks, robots) which usually has occlusions. These occlusions have to be considered since parts of the unknown objects might be hidden in some or even all camera views. Besides grayscale and color cameras also depth sensors are considered. In order to avoid cluttered reconstructions, plausibility checks are used to eliminate reconstruction artifacts which actually do not contain any unknown object. One application is a supervision/surveillance system for safe human/robot-coexistence and –cooperation. Experiments for a voxel-based implementation are given.
-
Effiziente taskbasierte Programmausführung irregulärer Applikationen mit adaptiver Lastbalancierung
(2009)
-
Ralf Hoffmann
- Zur parallelen Ausführung irregulärer Applikationen auf Parallelrechnern mit gemeinsamem Speicher eignet sich ein taskbasierter Ansatz, da durch eine dynamische Lastverteilung einzelner Tasks geeignet auf die irreguläre Abarbeitungsstruktur der Applikation reagiert werden kann. In dieser Arbeit wird das KOALA-Framework zur Abarbeitung feingranularer Tasks paralleler Programme vorgestellt. Es wird ein adaptiver Taskpool beschrieben, der effizient auf wechselnde Lastzustände innerhalb einer Applikation reagieren kann. Durch adaptiv angepasste Taskblöcke kann der adaptive Taskpool auch bei einer sehr großen Anzahl von ausführungsbereiten Tasks mit nur wenigen Operationen Taskumverteilungen durchführen, um die Berechnungen möglichst gleichmäßig auf die Prozessoren zu verteilen. Verschiedene irreguläre Applikationen werden getestet, um die unterschiedlichen Taskpool-Implementierungen zu vergleichen. Dabei erzielen die adaptiven Taskpools im Gegensatz zu konventionellen Taskpools bei allen untersuchten Applikationen gute Ergebnisse. Die einzelnen funktionalen Bestandteile des KOALA-Frameworks können ohne Änderungen in der Applikation ausgetauscht werden. Eine spezielle Implementierung der Lock-Komponente erlaubt so die Nutzung von Hardware-Operationen zur effizienten Synchronisation der beteiligten Threads. Weiterhin wird eine Profiling-Komponente vorgestellt, mit der die Taskstruktur einer Applikation analysiert werden kann. An einem Fallbeispiel werden Engstellen in einer Applikation identifiziert, durch deren Behebung eine erhebliche Verbesserung der Laufzeit erreicht werden konnte.
-
Evaluation der Leistungsfähigkeit von gemischt-parallelen Programmen in homogenen und heterogenen Umgebungen unter Berücksichtigung effizienter Schedulingstrategien
(2008)
-
Sascha Hunold
- Die gemischt-parallele Formulierung von Programmen, welche aus kooperierenden Multiprozessor- Tasks (M-Tasks) bestehen, erlaubt einen höheren Grad an Parallelität als gewöhnliche datenparallele Implementierungen. Um diesen höheren Parallelitätsgrad auszunutzen, bedarf es effizienter gemischt-paralleler Realisierungen von Algorithmen, einer guten Infrastruktur zur Ausführung der Programme und leistungsfähigen Scheduling-Algorithmen, die die einzelnen M-Tasks auf die bestmögliche Menge von Prozessoren abbilden. Im ersten Teil der vorliegenden Arbeit werden exemplarisch verschiedene gemischt-parallele Realisierungen der Matrixmultiplikation zweier dicht besetzter Matrizen untersucht. Dazu werden Algorithmen (z. B. die Matrixmultiplikation nach Strassen) so umstrukturiert, dass die resultierenden Verfahren aus hierarchisch organisierten, datenparallelen Multiprozessor- Tasks bestehen. Durch die abstraktere Beschreibung von Problemen mittels kooperierender Tasks lassen sich Algorithmen einfacher miteinander kombinieren. In dieser Arbeit wurden verschiedene gemischt-parallele Algorithmen zu neuen Poly-Algorithmen zusammengesetzt, wobei die gemischt-parallele Variante von Strassens Algorithmus als Ausgangsalgorithmus gewählt wurde. Die so entstandenen Poly-Algorithmen zur Matrixmultiplikation wurden in einer Vielzahl von Experimenten mit der Leistung datenparalleler Implementierungen auf homogenen parallelen und verteilten Systemen verglichen. Dabei zeigte sich, dass die gemischt-parallelen Varianten für viele Konfigurationen kürzere Laufzeiten als die datenparallelen Algorithmen erreichen. Gemischt-parallele Programme lassen sich als gerichteter azyklischer Graph (DAG) beschreiben. Diese Darstellung ist sehr gut für eine verteilte Abarbeitung der einzelnen Knoten (M-Tasks) über Clustergrenzen hinaus geeignet. Trotzdem benötigt man eine entsprechende Software-Infrastruktur, um gemischt-parallele Programme auf verschiedenen Clustern auszuführen. Aus diesem Grund wurde im Rahmen dieser Arbeit TGrid entwickelt, um gemischt-parallele Applikationen im Grid auszuführen. TGrid ist zum einen eine Middleware, die verschiedene heterogene Systeme zu einem kooperierenden System zusammenfügt. Zum anderen bietet TGrid eine Programmierschnittstelle, um gemischtparallel Programme zu formulieren und diese mit Hilfe der Middleware auszuführen. Die TGrid-Middleware ermöglicht die Co-Allokation von Ressourcen für eine einzige gemischtparallele Anwendung, d. h. ein einziges Programm kann durch mehrere Cluster parallel abgearbeitet werden. Eine weitere wichtige Eigenschaft ist die Unterstützung der automatischen Datenumverteilung zwischen M-Tasks. Der Programmierer muss dazu nur die Abbildung der Ausgangsdatenstrukturen auf die Eingangsdatenstrukturen zweier M-Tasks definieren. Die eigentliche Datenkommunikation übernimmt das TGrid-System. Für eine effiziente Ausführung gemischt-paralleler Programme in Clustern und Multiclustern (Cluster aus Clustern) ist auch die Frage zu klären, in welcher Reihenfolge die ausführbereiten Tasks abgearbeitet werden sollen. Das Ausführen von dynamisch erzeugten M-Taskgraphen in Multiclustern führt zu einer neuen Klasse von Scheduling-Problemen. Deshalb werden in der vorliegenden Arbeit zwei Algorithmen (RePA und DMHEFT) für das Scheduling von dynamisch generierten Taskgraphen entwickelt und deren Leistungsfähigkeit mit Compile-Zeit-Verfahren wie MHEFT verglichen. Da TGrid auch für die Ausführung von statisch definierten Taskgraphen genutzt werden kann, wird ein neuer zweistufiger Scheduling-Algorithmus (RATS) vorgestellt, welcher zu Compile-Zeit arbeitet. Dieser Algorithmus versucht durch gezielte Änderung der Prozessor- Allokation von Tasks, die Kosten der Datenumverteilung zu reduzieren. Nach genauer Analyse mittels Grid-Simulationen konnte festgestellt werden, dass RATS deutlich kürzere Ablaufpläne als andere zweistufige Verfahren, wie z. B. HCPA, auf homogenen Clustern produziert. Zusammenfassend zeigt die vorliegende Arbeit, wie gemischt-parallele Algorithmen entwickelt und effizient ausgeführt werden können. In homogenen parallelen Systemen ermöglichen diese gemischt-parallelen Anwendungen bessere Laufzeiten als datenparallele Implementierungen. Die Arbeit verdeutlicht auch, dass eine gemischt-parallele Formulierung von Algorithmen eine effiziente Ausführung von parallelen Verfahren in Grid-Umgebungen (Multiclustern) erlaubt, die mit anderen parallelen Programmiermodellen in diesen nicht zu erreichen ist.
-
Konzeption und prototypische Implementierung eines Frameworks zur automatisierten Softwaremessung
(2008)
-
Bernhard Daubner
- Im Rahmen der betriebswirtschaftlichen Unternehmenssteuerung sind sogenannte Management-Cockpits oder Managementunterstützungssysteme schon länger bekannt. Dabei handelt es sich um EDV-Systeme zur Visualisierung entscheidungsrelevanter Daten, welche insbesondere der Unternehmensleitung auf Knopfdruck wesentliche Kenngrößen (Key Performance Indicators) des Unternehmens darstellen. Analog dazu sollen Projektleitstände den Projektleitern entsprechende Kenngrößen der laufenden IT-Projekte darstellen. Derartige Kennzahlen sind beispielsweise die Testabdeckung, der Fertigstellungsgrad, die Code-Qualität oder der bereits erbrachte Arbeitsaufwand. Diese Softwaremaße sollten dazu von den Messwerkzeugen automatisiert erfasst werden können. Aktuell verfügbare Anwendungen zur Softwaremessung sind jedoch entweder stark an bestimmte Prozessmodelle oder Entwicklungsumgebungen gebunden, können teilweise selbst keine Messwerte ermitteln und dienen somit als reine Visualisierungswerkzeuge oder können nur eingeschränkt von den Anwendern konfiguriert oder erweitert werden. Im Rahmen dieser Arbeit wird daher ein Framework zur automatisierten Softwaremessung vorgestellt. Zu dessen wesentlichen Anforderungen gehören die weitgehende Automatisierung des Messprozesses und die Möglichkeit, die zu erhebenden Softwaremaße unabhängig von einem konkreten Projekt definieren zu können. Dazu werden Kontextinformationen bestimmt, welche als Anknüpfungspunkte für die zu erhebenden Softwaremaße dienen. Ein Kontext kann dabei eine bestimmte Aktivität des zugrunde liegenden Vorgehensmodells, eine Projektphase oder eine zu implementierende Funktionalität sein. Dadurch ist es beispielsweise möglich, Umfangsmessungen auf bestimmte Projektphasen oder auf Komponenten, durch die bestimmte Funktionalitäten implementiert werden, einzuschränken. Im Gegensatz zu vielen anderen Messwerkzeugen, die entweder nur die Vermessung von bereits erstellten Artefakten erlauben oder Softwaremaße nur auf der Ebene des Gesamtprojekts ermitteln können, ermöglicht es der hier dargestellte Ansatz, Softwaremaße in Bezug auf einen bestimmten Kontext zu definieren. Die konkrete Ausprägung der letztendlich zu messenden Entitäten muss zum Zeitpunkt der Definition des Softwaremaßes noch nicht bekannt sein. Dadurch kann erreicht werden, dass Softwaremaße standardisiert und über Projektgrenzen hinweg konsistent ermittelt werden können. Als prototypische Implementierung dieses Softwaremessungsansatzes wird ein Framework dargestellt, welches auf einer Open-Source-Projektverwaltungssoftware basiert. Dieses Framework, welches entsprechende API-Funktionen zur Ermittlung einfacher Softwaremaße zur Verfügung stellt, erlaubt die flexible Definition komplexer Softwaremaße, welche dann zur Projektlaufzeit automatisiert ermittelt und gegebenenfalls visualisiert werden können. Zur Definition der zu erhebenden Softwaremaße wird auf die Konfigurationsmöglichkeiten der zugrunde liegenden Projektverwaltungssoftware zurückgegriffen. Dadurch können bei der Softwaremessung bereits vorhandene Projektinformationen wiederverwendet werden. Um die Tragfähigkeit des in dieser Arbeit dargestellten Ansatzes unter Beweis zu stellen, wird die Evaluierung dieses Messwerkzeuges anhand zweier studentischer Softwareentwicklungsprojekte dargestellt.
-
Integral point sets over Z_n^m
(2007)
-
Axel Kohnert
Sascha Kurz
- There are many papers studying properties of point sets in the Euclidean space or on integer grids, with pairwise integral or rational distances. In this article we consider the distances or coordinates of the point sets which instead of being integers are elements of Z_n, and study the properties of the resulting combinatorial structures.
-
Symmetric functions in MAGMA
(2007)
-
Axel Kohnert
- We describe two algorithms which were used to implement symmetric functions in the computer algebra system MAGMA. We describe one algorithm based on the work of Lascoux and Schutzenberger for the multiplication. One further algorithm is given for the computation of plethysms.
