University, Diss., 2003--Bremen.

Zugl.: Karlsruhe, Univ., Diss., 2008 / Hergestellt on demand

Optimized implementations of blocking and nonblocking collective operations are most important for scalable high-performance applications. Offloading such collective operations into the communication layer can improve performance and asynchronous progression of the operations. However, it is most important that such offloading schemes remain flexible in order to support user-defined (sparse neighbor) collective communications. In this work, we describe an operating system kernel-based architecture for implementing an interpreter for the flexible Group Operation Assembly Language (GOAL) framework to offload collective communications. We describe an optimized scheme to store the schedules that define the collective operations and show an extension to profile the performance of the kernel layer. Our microbenchmarks demonstrate the effectiveness of the approach and we show performance improvements over traditional progression in user-space. We also discuss complications with the design and offloading strategies in general.

Optimized implementations of blocking and nonblocking collective operations are most important for scalable high-performance applications. Offloading such collective operations into the communication layer can improve performance and asynchronous progression of the operations. However, it is most important that such offloading schemes remain flexible in order to support user-defined (sparse neighbor) collective communications. In this work, we describe an operating system kernel-based architecture for implementing an interpreter for the flexible Group Operation Assembly Language (GOAL) framework to offload collective communications. We describe an optimized scheme to store the schedules that define the collective operations and show an extension to profile the performance of the kernel layer. Our microbenchmarks demonstrate the effectiveness of the approach and we show performance improvements over traditional progression in user-space. We also discuss complications with the design and offloading strategies in general.:1 Introduction 1.1 Related Work 2 The GOAL API 2.1 API Conventions 2.2 Basic GOAL Functionality 2.2.1 Initialization 2.2.2 Graph Creation 2.2.3 Adding Operations 2.2.4 Adding Dependencies 2.2.5 Scratchpad Buffer 2.2.6 Schedule Compilation 2.2.7 Schedule Execution 2.3 GOAL-Extensions 3 ESP Transport Layer 3.1 Receive Handling 3.2 Transfer Management 3.2.1 Known Problems 4 The Architecture of ESPGOAL 4.1 Control Flow 4.1.1 Loading the Kernel Module 4.1.2 Adding a Communicator 4.1.3 Starting a Schedule 4.1.4 Schedule Progression 4.1.5 Progression by ESP 4.1.6 Unloading the Kernel Module 4.2 Data Structures 4.2.1 Starting a Schedule 4.2.2 Transfer Management 4.2.3 Stack Overflow Avoidance 4.3 Interpreting a GOAL Schedule 5 Implementing Collectives in GOAL 5.1 Recursive Doubling 5.2 Bruck's Algorithm 5.3 Binomial Trees 5.4 MPI_Barrier 5.5 MPI_Gather 6 Benchmarks 6.1 Testbed 6.2 Interrupt coalescing parameters 6.3 Benchmarking Point to Point Latency 6.4 Benchmarking Local Operations 6.5 Benchmarking Collective Communication Latency 6.6 Benchmarking Collective Communication Host Overhead 6.7 Comparing Different Ways to use Ethernet NICs 7 Conclusions and Future Work 8 Acknowledgments

Skalierbares schlüssel-basiertes Routing in verteilten Systemen ist eine Methode zur Weiterleitung von Nachrichten zu den für die Partition verantwortlichen Maschinen. Diese Technik findet Verwendung in Key-Value Speichersystemen, Content Distribution Networks oder auch beim Media Streaming. Einer der Gründe für die Verbreitung ist die Einfachheit der Routingabstraktion, bei welcher der Entwickler sich nicht um die Details des Gruppenmanagements oder Datenreplikation kümmern muss. Auf der anderen Seite sind die meisten schlüssel-basierten Routingverfahren optimistische Verfahren, bei denen der Datenzugriff keine strenge Konsistenz bietet. In dieser Arbeit präsentieren wir das System Recode mit dem schlüssel-basierten Routingabstraktion routecast, welches eine strengere Zugriffssemantik ermöglicht. Dabei garantiert routecast, dass Nachrichten eines bestimmten Schlüssels in der gleichen Reihenfolge an alle Replikate geliefert werden. Mit Hilfe dieser strengeren Garantien können auch Anwendungen wie Koordinations- oder Metadatendienste bzw. konsistente Speichersysteme das schlüssel-basierte Routing verwenden. Recode ist außerdem rekonfigurierbar bei Veränderungen der zur Verfügung stehenden Maschinen sowie bei Auslastungsänderung. Es ist ein komplett dezentralisiertes System und enthält damit keinen single-point of failure oder Systemengpass. Die drei Hauptbeiträge der Arbeit sind 1) die Abstraktion der Gruppenkommunikation unter Verwendung von Primary/Backup mit Leases für ein failover des Primary, 2) die Entwicklung und die Algorithmen der routcast-Primitive, 3) Mechanismen zur atomaren Rekonfiguration des dezentralen Schlüsselraumes. Um die Einfachheit unseres Ansatzes zu betonen, beschreiben wir außerdem drei verschiedene Anwendungen aufbauend auf Recode. Abschließend zeigen wir durch die Evaluation von Recode in einer Cluster-Umgebung die Leistungsfähigkeit. / Scalable key-based routing in distributed systems, where a mes- sage is forwarded towards a machine responsible for a partition in a large key space, has been used in many services such as key-value stores, content distribution networks and media streaming. This success can mainly be attributed to the simplicity of the route ab- straction, a developer does not need to care about the mechanisms for membership management, load balancing or data replication. A limitation, however, is that most key-based routing solutions are best-effort, which means that only eventually consistent data access is possible. This thesis presents a system (Recode) with a key-based routing primitive called routecast which provides strong delivery semantics. More specifically, routecast guarantees that a message for a key is delivered in the same total order at a set of replicas. With stronger guarantees, applications such as coordination and metadata services as used in large storage systems or consistent key-value stores can use key-based routing. Additionally, Recode aims to be both re- configurable, to handle changes to the machines running the service and updates to the workload, and fully decentralized which means there is no single point of failure or bottleneck. We make three main contributions in this thesis: 1) a group com- munication abstraction using primary/backup with leases for pri- mary fail-over, 2) the design and algorithms of the routecast-primitive and, 3) mechanisms for atomic reconfiguration of a decentralized key space. Each part of the system is broken up into modules and presented with a specification and a set of algorithms. To validate the simplicity claim, we describe how to implement three different applications on top of Recode. Finally, we evaluate Recode in a cluster environment and show that the performance is competitive.

This paper describes the creation of a Bavarian dialect lexicon that is based on social media and that was translated by means of crowdsourcing. In the process, we first obtain a corpus of dialect samples from the social network Facebook. For the translation of the dialect words to standard German, we involve the members of the social network, which allows us to produce a crowdsourced lexicon of Bavarian dialect words.

No description available.