Library

Description: Im Mai 2009 wurde Wolfram|Alpha gestartet, ein Service, der seinen Namen von seinem Entwickler, dem britischen Mathematiker Stephen Wolfram, ableitet. Dem Benutzer soll nicht nur eine Liste von Webseiten als Ergebnis auf Anfragen geliefert werden, sondern Antworten auf konkrete Fragen geben. In diesem Report soll gezeigt werden, warum sichWolframjAlpha von Suchmaschinen abgrenzt und was die Berechnung von Antworten auf natürlichsprachliche Fragen möglich machen kann.

Description: Wolfram|Alpha was started in May 2009 and it's a service whose name derives from the british mathematician Stephen wolfram. As a result for a request the user is not just supported with a list of websites but with answers for concrete questions. In this report it will be shown why Wolfram|Alpha seperates from search engines and moreover what makes the computation of answers for natural language queries possible.

Description: Executing applications in the Grid often requires access to multiple geographically distributed resources. In a Grid environment, these resources belong to different administrative domains, each employing its own scheduling policy. That is, at which time an activity (e.g., compute job, data transfer) is started, is decided by the resource's local management system. In such an environment, the coordinated execution of distributed applications requires guarantees on the quality of service (QoS) of the needed resources. Reserving resources in advance is an accepted means to obtain QoS guarantees from a single provider. The challenge, however, is to coordinate advance reservations of multiple resources. This work presents a system architecture and mechanisms to coordinate multiple advance reservations -- called co-reservations -- for delivering QoS guarantees to complex applications. We formally define the co-reservation problem as an optimization problem. The presented model supports three dimensions of freedom: the start time, the duration and the service level of a reservation. Requests and resources are described in a simple language. After matching the static properties and requirements of either side in a mapping, the reservation mechanism probes information about the future status of the resources. The versatile design of the probing step allows the efficient processing of requests, but also lets the resources express their preferences among the myriads of reservation candidates. Next, the best mapping is found through an implementation of the formal co-reservation model. Then, the mapping has to be secured, i.e., resources need to be allocated to a co-reservation candidate with all-or-nothing semantics. We study several goal-driven sequential and concurrent allocation mechanisms and define schemes for handling allocation failures. Finally, we introduce the concept of virtual resources for seamlessly embedding co-reservations into Grid resource management.

Description: Die Ausführung von Anwendungen erfordert oft mehrere, geographisch verteilte Ressourcen. In Grid-Umgebungen gehören diese Ressourcen zu verschiedenen administrativen Organisationen, wobei jede ihre eigene Schedulingregeln verwendet. Das bedeutet, zu welcher Zeit eine Aktivität gestartet wird (z.B. ein Rechenjob), wird vom lokalen Ressourcenmanagementsystem entschieden. Die koordinierte Ausführung von verteilten Anwendungen erfordert Dienstgütegarantien für die benötigten Ressourcen. Das Reservieren von Ressourcen im Voraus ist ein Mittel, um Dienstgütegarantien von einem einzelnen Ressourcenanbieter zu erhalten. Die Herausforderung in dieser Arbeit ist, Vorausreservierungen von mehreren Ressourcen zu koordinieren. Es wird ein System für die Koordinierung mehrerer Vorausreservierungen -- Co-Reservierungen genannt -- für die Bereitstellung von Dienstgütegarantien vorgestellt. Wir definieren das Co-Reservierungsproblem als Optimierungsproblem. Das vorgestellte Modell unterstützt drei Freiheitsgrade: die Startzeit, die Dauer und die Dienstgüte einer Reservierung. Anfragen und Ressourcen werden in einer einfachen Sprache beschrieben. Nachdem statische Eigenschaften und Anforderungen beider Seiten überprüft wurden, ermittelt der Reservierungsmechanismus Informationen über den zukünftigen Zustand der Ressourcen. Dieser Schritt ist so allgemein gehalten, daß er sowohl ein effizientes Bearbeiten der Anfragen erlaubt als auch den Ressourcen ermöglicht ihre Präferenzen auszudrücken. Im Anschluss wird die optimale Zuweisung von Anfragen zu Ressourcen ermittelt. Im letzten Schritt muss diese Zuweisung umgesetzt werden, d.h., entweder alle oder keine Ressource wird allokiert. Es werden mehrere sequentielle und parallele Allokationsverfahren vorgestellt sowie deren Auswirkung auf verschiedene Metriken untersucht. Die Einbettung von Co-Reservierungen in das Grid-Ressourcenmanagement wird anhand des Konzeptes der virtuellen Ressource dargestellt.

Description: Aktuelle Entwicklungen zeigen, dass Peer-to-Peer (P2P) Anwendungen wie Skype oder Bittorrent im Internet immer mehr an Bedeutung gewinnen. In den letzten Jahren hat es einen explosionsartigen Anstieg an Nutzern und Daten in solchen Netzen gegeben. Dabei stellt der eigentliche Dateitransfer zwischen zwei Rechnern kein großes Problem mehr dar und auch der Speicherbedarf für die große Menge an Daten kann durch die Weiterentwicklung der Hardware gut gedeckt werden. Das eigentliche Problem liegt vielmehr darin, den Rechner zu finden, der die gewünschten Daten hat. Client-Server Architekturen, wie zum Beispiel Napster, haben sich als ungünstig herausgestellt. Wenige Server, die eine große Anzahl an Clients bedienen müssen, sind einerseits sehr anfällig gegenüber Angriffen und Ausfällen (Single Point of Failure)und kommen auch nicht mit der ständig wachsenden Anzahl an Nutzern zurecht. Verteilte Hashtabellen (DHT) bieten hier einen guten Lösungsansatz, der mit einer großen Anzahl an Nutzern skaliert und ausfallsicher ist. Andere dezentrale Lösungen, wie zum Beispiel das P2P Netzwerk Gnutella haben zwar das Problem des Single Point of Failure gelöst, jedoch haben sie starke Nachteile bei der Suche nach Keys. Bei einer Suche wird ein Broadcast verwendet (jeder schickt die Anfrage an jeden weiter) und damit ein enormer Netzwerkverkehr erzeugt. In "Why Gnutella Can't Scale. No, Really" wird erklärt, dass eine Suchanfrage bei Standardeinstellungen in der Clientsoftware einen Netzwerkverkehr von 17MB erzeugt. Deswegen wird zusätzlich eine Lösung benötigt, die Keys und Values geordnet verteilt, damit sie gezielt gesucht werden können. Aus diesem Grund beschäftigt sich die folgende Arbeit mit einer völlig dezentralen Architektur, die außerdem eine sinnvolle Platzierung der Keys vornimmt. Die dezentrale Architektur hat den Vorteil, dass die Endgeräte den Hauptteil des Dienstes selbst erbringen und damit jeder zusätzliche Teilnehmer seine eigenen Ressourcen beisteuert. Diese Arbeit präsentiert Chord#, eine dezentrale, skalierbare und selbstorganisierende verteilte Hashtabelle. Chord# wurde ausgewählt, da in dieser Arbeit auch Wert auf Bereichsabfragen gelegt wurde. Diese sind zum Beispiel bei dem Chord Algorithmus nicht möglich, da dieser eine Hashfunktion für die Keys verwendet und somit die Daten zwar gleichmäßig aber unsortiert auf die Teilnehmer verteilt. Es wird in dieser Arbeit gezeigt, dass mit Hilfe von Chord# auch ohne die Hashfunktion gute Ergebnisse erzielt werden. Außerdem können durch den Verzicht auf die Hashfunktion Bereichsabfragen ermöglicht werden. Dafür wird der Chord# Algorithmus in Java implementiert (ca. 1500 Zeilen Code) und in dem Forschungsnetz PlanetLab ausführlich auf Laufzeiten, Instandhaltungskosten und Skalierung getestet.

Description: Recent developments show that peer-to-peer (p2p) applications, such as Skype or Bittorrent have become increasingly important in the internet. Over the last years there has been a rapid growth of both users and data in such networks. However, the actual file transfer between two peers is not really an issue anymore. The same holds true for data storage, since the new hardware grants users enough space to store their data. The real problem is finding the peers that possess the desired data. Client-server architectures like Napster have proven to be ineffective addressing that problem. One or few servers being responsible for many peers are vulnerable to attacks or failures (single point of failure). Additionally, they are unable to cope with the rapidly growing number of peers. Distributed hashtables (DHT) are a good approach to solve these problems, since they scale nicely with large numbers of peers and provide a high tolerance for errors. Other decentralized solutions like the p2p network Gnutella solved the problem of Single Point of Failure but show considerable disadvantages when searching for keys. The peers in Gnutella use a broadcast (sending the message to all peers they know)resulting in massive traffic. According to "Why Gnutella Can't Scale. No, Really.", each search using standard client settings yields 17MB traffc. This calls for a different solution, distributing keys and values to peers quickly and efficiently so they can be found fast. For that reason this thesis focuses on a fully distributed architecture using organized key placement. One major advantage of distributed architecture is the fact, that the peers do most of the work themselves. This way, new peers joining the network add resources to it. This thesis presents Chord#, a scalable, self-organizing and completely decentralized DHT. It has been chosen due to its capability to allow range queries. The regular Chord algorithm does not support range queries, because of the hashfunction it uses to evenly distribute the keys among the peers. This results in similar or logical coherent keys most likely not being close together in the network. This thesis shows Chord# achieving same results as Chord - regarding performance costs - without the hashfunction. In dropping the hashfunction this algorithm allows the use of range queries. The Chord# algorithm is implemented in Java (about 1500 lines of code) and thoroughly tested in the research network PlanetLab. The results are evaluated regarding performance, maintenance and scalability.

Description: One of the biggest impacts on the performance of a Distributed Hash Table (DHT), once established, is its ability to balance load among its nodes. DHTs supporting range queries for example suffer from a potentially huge skew in the distribution of their items since techniques such as consistent hashing can not be applied. Thus explicit load balancing schemes need to be deployed. Several such schemes have been developed and are part of recent research, most of them using only information locally available in order to scale to arbitrary systems. Gossiping techniques however allow the retrieval of fairly good estimates of global information with low overhead. Such information can then be added to existing load balancing algorithms that can use the additional knowledge to improve their performance. Within this thesis several schemes are developed that use global information like the average load and the standard deviation of the load among the nodes to primarily reduce the number of items an algorithm moves to achieve a certain balance. Two novel load balancing algorithms have then been equipped with implementations of those schemes and have been simulated on several scenarios. Most of these variants show better balance results and move far less items than the algorithms they are based on. The best of the developed algorithms achieves a 15-30% better balance and moves only about 50-70% of the number of items its underlying algorithm moves. This variation is also very robust to erroneous estimates and scales linearly with the system size and system load. Further experiments with self-tuning algorithms that set an algorithm’s parameter according to the system’s state show that even more improvements can be gained if additionally applied. Such a variant based on the algorithm described by Karger and Ruhl shows the same balance improvements of 15-30% as the variant above but reduces the number of item movements further to 40-65%.

Description: Entwurf und Entwicklung eines eingebetteten Hauptspeicher-Datenbanksystems mit Snapshot-Reads.

Description: Design and implementation of an embedded main memory database with snapshot reads.

Description: Das Ziel dieser Arbeit ist die Schaffung einer Zugriffs-Komponente für das Grid-Datenmanagement-System ZIB-DMS, das dessen transparente Einbindung in den Verzeichnisbaum eines Linux-Systems erlaubt. Dazu wird unter Verwendung des FUSE-Rahmenwerkes ein Userspace-Dateisystem mit Anbindung an das ZIB-DMS konzipiert und implementiert. Im Fokus stehen dabei die Abbildung der erweiterten Verwaltungsmechanismen des Systems auf die limitierte Schnittstelle hierarchischer Dateisysteme und die dazu notwendigen Änderungen am ZIB-DMS.

Description: The goal of this work is to create an access component for the Grid data management system ZIB-DMS, that allows a transparent integration into the directory tree of a Linux system. For this purpose the FUSE framework is used to design and implement a userspace file system with connections to the ZIB-DMS. The focus is on the mapping of the extended management mechanisms of the system to the limited interface of hierarchical file systems and the therefore necessary changes to ZIB-DMS.

Description: We present a framework for transactional data access on data stored in a DHT. It allows to atomically read and write items and to run distributed transactions consisting of a sequence of read and write operations on the items. Items are symmetrically replicated in order to achieve durability of data stored in the SON. To provide availability of items despite the unavailability of some replicas, operations on items are quorum-based. They make progress as long as a majority of replicas can be accessed. Our framework processes transactions optimistically with an atomic commit protocol that is based on Paxos atomic commit. We present algorithms for the whole framework with an event based notation. Additionally we discuss the problem of lookup inconsistencies and its implications on the one-copy serializability property of the transaction processing in our framework.

Description: When planning teams for projects with specific goals, employees of a company have to group together so well, that all necessary knowledge for conquering the project’s challenges are met within the member’s skills. A tool that facilitates semantic web technologies can support the team recruiter, who is responsible for chosing the members of the team, in terms of finding the most efficient combinations of the company’s employees based on their expertises.

Description: Key/value stores which are built on structured overlay networks often lack support for atomic transactions and strong data consistency among replicas. This is unfortunate, because consistency guarantees and transactions would allow a wide range of additional application domains to benefit from the inherent scalability and fault-tolerance of DHTs. The Scalaris key/value store supports strong data consistency and atomic transactions. It uses an enhanced Paxos Commit protocol with only four communication steps rather than six. This improvement was possible by exploiting information from the replica distribution in the DHT. Scalaris enables implementation of more reliable and scalable infrastructure for collaborative Web services that require strong consistency and atomic changes across multiple items.

Description: Basierend auf einem vorhandenen Ansatz zur Einführung von anisotropen Tetraedern im Randbereich eines reinen Tetraedergitters wird ein Gittergenerator für hybride Gitter implementiert. Das hybride Gitter besteht in Randnähe primär aus anisotropen Prismen und im Inneren der Geometrie aus isotropen Tetraedern. Eine erhöhte Auflösung im Randbereich soll zu besseren Ergebnissen von numerischen Strömungssimulationen führen, für welche eine problemangepasste Diskretisierung des zu untersuchenden Gebietes benötigt wird. In dem zuvor genannten Ansatz wird eine Reihe von Übergangselementen vorgeschlagen, die an scharfen Kanten der Oberfläche platziert werden sollen. Im Rahmen dieser Diplomarbeit wird die Idee der Übergangselemente aufgegriffen und bei hybriden Gittern eingesetzt, um auch komplexe Eingabegeometrien vergittern zu können. Der ursprüngliche Gittergenerierungprozess wird überarbeitet und erweitert. Eine neue Menge an Übergangselementen wird eingeführt, es werden gekrümmte Extrusionsvektoren verwendet und es wird die Auswertung der medialen Oberfläche vorgenommen, um Überschneidungen im hybriden Gitter zu vermeiden. Der Gittergenerator wird als Modul in das Visualisierungs- und Analyseprogramm Amira implementiert und die erstellten hybriden Gitter werden auf ihre Elementqualität und die Güte der Strömungssimulationsergebnisse hin überprüft.

Description: Based on an existing approach for the introduction of anisotropic tetrahedra near the surface boundary of a tetrahedral grid a grid generator for hybrid grids is implemented. The hybrid grid consists near the surface boundary primarily of anisotropic prisms and inside the geometry of isotropic tetrahedra. An increased resolution near the boundary should lead to better results of numerical flow simulations, which needs a problem specific discretization of the analyzed domain. In the aforementioned approach a set of transition elements is suggested, which should be placed at sharp surface corners. As a part of this diploma thesis the concept of using transition elements is applied for creating hybrid grids even for very complex input geometries. The initial grid generation process is revised and enhanced. A new set of transition elements is introduced, curved extrusion vectors are used and the medial surface is evaluated to avoid intersections in the hybrid grid. The grid generator is implemented as a module for the visualization and analysis tool Amira and the element quality of the generated hybrid grids and the quality of flow simulations performed on the grids are tested.

Description: We study performance and scaling of the Berlin Quantum Chromodynamics Program (BQCD) on the SGI Altix 4700 at Leibniz Supercomputing Centre (LRZ). We employ different communication methods (MPI, MPI with two OpenMP threads per process, as well as the shmem library) and run the MPI version on the two types of nodes of that machine. For comparison with other machines we made performance measurements on an IBM p690 cluster and a Cray XT4.

Description: In dieser Arbeit wird eine Serie von Remeshing-Verfahren um die Berücksichtigung von nicht-mannigfaltigen Dreiecksvernetzungen und Merkmalskantenzügen erweitert. Die betrachteten Verfahren arbeiten im Wesentlichen lokal. Daher können die im Rahmen dieser Arbeit entwickelten Erweiterungen, die nicht-mannigfaltige Kantenzüge und Merkmalskantenzüge betreffen, separat beschrieben werden. Dabei wird ein Ansatz verfolgt, beide Arten von besonderen Kantenzügen aufgrund ihrer Gemeinsamkeiten einheitlich zu behandeln. Dieser besteht zum einen darin, eine Korrespondenz zwischen Kantenzügen auf der Eingabe- und der Ausgabefläche zu erhalten, indem die Remeshing-Operationen auf den Kantenzügen in entsprechend eingeschränkter Weise verwendet werden. Zum anderen wird beschrieben, wie die Abtastdichte der Kantenzüge dynamisch an die Abtastdichte der Umgebung angepasst werden kann, um für weitgehende Isotropie in der Nähe von Merkmalskantenzügen zu sorgen.

Description: A unified approach for consistent remeshing of arbitrary non-manifold triangle meshes with additional user-defined feature lines is presented. The method is based on local operations only and produces meshes of high regularity and triangle quality while preserving the geometry as well as topology of the feature lines as well as the input mesh.

Description: This work introduces a novel streamline seeding technique based on dual streamlines that are orthogonal to the vector field, instead of tangential. The greedy algorithm presented here produces a net of orthogonal streamlines that is iteratively refined resulting in good domain coverage and a high degree of continuity and uniformity. The algorithm is easy to implement and efficient, and it naturally extends to curved surfaces.

Description: In dieser Arbeit wird eine neue Strategie zur Platzierung von Stromlinien vorgestellt. Hierzu werden zusätzliche duale Stromlinien verwendet, die --im Gegensatz zur üblichen Definition-- orthogonal zum Vektorfeld verlaufen. Der vorgestellte Greedy-Algorithmus berechnet ein Netz aus orthogonalen Stromlinien, welches iterativ verfeinert wird, was zu einer guten Abdeckung der Domäne und einer gleichmäßigen Verteilung der Stromlinien führt. Es handelt sich um einen einfach zu implementierenden und effizienten Algorithmus, der direkt auf gekrümmten Oberflächen anwendbar ist.