Refine
Year of publication
Document Type
- In Proceedings (43)
- Article (30)
- ZIB-Report (6)
- Other (4)
- Book chapter (3)
- Poster (2)
- Doctoral Thesis (1)
- Master's Thesis (1)
Is part of the Bibliography
- no (90)
Keywords
- DHT (2)
- Cache-Simulator (1)
- Grid computing (1)
- Kostenmodell (1)
- Microbenchmarks (1)
- P2P (1)
- Paxos (1)
- Range Queries (1)
- SMP-System (1)
- Speicherhierarchie (1)
XtreemFS & Scalaris
(2013)
The Grid Application Toolkit: Toward Generic and Easy Appliction Programming Interfaces for the Grid
(2005)
Self-Adaptation in Large-Scale Systems: A Study on Structured Overlays Across Multiple Datacenters
(2009)
Achieving efficient many-to-many communication on a given network topology is a challenging task when many data streams from different sources have to be scattered concurrently to many destinations with low variance in arrival times. In such scenarios, it is critical to saturate but not to congest the bisectional bandwidth of the network topology in order to achieve a good aggregate throughput. When there are many concurrent point-to-point connections, the communication pattern needs to be dynamically scheduled in a fine-grained manner to avoid network congestion (links, switches), overload in the node’s incoming links, and receive buffer overflow. Motivated by the use case of the Compressed Baryonic Matter experiment (CBM), we study the performance and variance of such communication patterns on a Cray XC40 with different routing schemes and scheduling approaches. We present a distributed Data Flow Scheduler (DFS) that reduces the variance of arrival times from all sources at least 30 times and increases the achieved aggregate bandwidth by up to 50%.
Peer-to-Peer Computing
(2010)
We present a middleware to store multidimensional data sets on Internet-scale distributed systems and to efficiently perform range queries on them. Our structured overlay network \emph{SONAR (Structured Overlay Network with Arbitrary Range queries)} puts keys which are adjacent in the key space on logically adjacent nodes in the overlay and is thereby able to process multidimensional range queries with a single logarithmic data lookup and local forwarding. The specified ranges may have arbitrary shapes like rectangles, circles, spheres or polygons. Empirical results demonstrate the routing performance of SONAR on several data sets, ranging from real-world data to artificially constructed worst case distributions. We study the quality of SONAR's routing information which is based on local knowledge only and measure the indegree of the overlay nodes to find potential hot spots in the routing process. We show that SONAR's routing table is self-adjusting, even under extreme situations, keeping always a maximum of $\lceil \log N \rceil$ routing entries.
Global grid environments do not only provide massive aggregated computing power but also an unprecedented amount of distributed storage space. Unfortunately, dynamic changes caused by component failures, local decisions, and irregular data updates make it difficult to efficiently use this capacity. In this paper, we address the problem of improving data availability in the presence of unreliable components. We present an analytical model for determining an optimal combination of distributed replica catalogs, catalog sizes, and replica servers. Empirical simulation results confirm the accuracy of our theoretical analysis. Our model captures the characteristics of highly dynamic environments like peer-to-peer networks, but it can also be applied to more centralized, less dynamic grid environments like the European {\em DataGrid}.
Multilevel Checkpoint/Restart for Large Computational Jobs on Distributed Computing Resources
(2019)
General solutions of state machine replication have to ensure that all replicas apply the same commands in the same order, even in the presence of failures. Such strict ordering incurs high synchronization costs due to the use of distributed consensus or a leader.
This paper presents a protocol for linearizable state machine replication of conflict-free replicated data types (CRDTs) that neither requires consensus nor a leader. By leveraging the properties of state-based CRDTs—in particular the monotonic growth of a join semilattice—synchronization overhead is greatly reduced. In addition, updates just need a single round trip and modify the state ‘in-place’ without the need for a log. Furthermore, the message size overhead for coordination consists of a single counter per message. While reads in the presence of concurrent updates are not wait-free without a coordinator, we show that more than 97 % of reads can be handled in one or two round trips under highly concurrent accesses.
Our protocol achieves high throughput without auxiliary processes such as command log management or leader election. It is well suited for all practical scenarios that need linearizable access on CRDT data on a fine-granular scale.
General solutions of state machine replication have to ensure that all replicas apply the same commands in the same order, even in the presence of failures. Such strict ordering incurs high synchronization costs caused by distributed consensus or by the use of a leader.
This paper presents a protocol for linearizable state machine replication of conflict-free replicated data types (CRDTs) that neither requires consensus nor a leader. By leveraging the properties of state-based CRDTs - in particular the monotonic growth of a join semilattice - synchronization overhead is greatly reduced. In addition, updates just need a single round trip and modify the state `in-place' without the need for a log. Furthermore, the message size overhead for coordination consists of a single counter per message. While reads in the presence of concurrent updates are not wait-free without a coordinator, we show that more than 97% of reads can be handled in one or two round trips under highly concurrent accesses.
Our protocol achieves high throughput without auxiliary processes like command log management or leader election. It is well suited for all practical scenarios that need linearizable access on CRDT data on a fine-granular scale.
Learned clauses minimization (LCM) let to performance improvements of modern SAT solvers especially in solving hard SAT instances. Despite the success of LCM approaches in sequential solvers, they are not widely incorporated in parallel SAT solvers. In this paper we explore the potential of LCM for parallel SAT solvers by defining multiple LCM approaches based on clause vivification, comparing their runtime in different SAT solvers and discussing reasons for performance gains and losses. Results show that LCM only boosts performance of parallel SAT solvers on a fraction of SAT instances. More commonly applying LCM decreases performance. Only certain LCM approaches are able to improve the overall performance of parallel SAT solvers.
Improving I/O Performance Through Colocating Interrelated Input Data and Near-Optimal Load Balancing
(2018)
Most distributed file systems assign new files to storage servers randomly. While working well in some situations, this does not help to optimize the input performance for most MapReduce computations’ data access patterns. In this work, we consider an access pattern where input files are partitioned
into groups of heterogeneous size. Each group is accessed by exactly one process. We design and implement a data placement strategy that places these file groups together on the same storage server. This colocation approach is combined with near-optimal storage load balancing. To do so, we use a classical scheduling approximation algorithm to solve the NP hard group assignment problem. We argue that local processing is not only beneficial because of reduced network traffic, but especially because it imposes an even resource schedule. Our experiments, based on the parallel processing of remote sensing images, reveal an enormous reduction of network traffic and up to 39 % faster input read times. Further, simulations show that our approximate assignments limit storage server imbalances to less than 5 % above the theoretical minimum, in contrast to more than 85 % with random assignment.
\textsf{\itshape{GuiGen}} is a comprehensive set of tools for creating customized graphical user interfaces (GUIs). It draws from the concept of computing portals, which are here seen as interfaces to application-specific computing services for user communities. While \textsf{\itshape{GuiGen}} was originally designed for the use in computational grids, it can be used in client/server environments as well. Compared to other GUI generators, \textsf{\itshape{GuiGen}} is more versatile and more portable. It can be employed in many different application domains and on different target platforms. With \textsf{\itshape{GuiGen}}, application experts (rather than computer scientists) are able to create their own individually tailored GUIs.
Geomultisens – a common automatic processing and analysis system for multi-sensor satellite data
(2016)
Typical applications in data science consume, process and produce large amounts of data, making disk I/O one of the dominating — and thus worthwhile optimizing — factors of their overall performance. Distributed processing frameworks, such as Hadoop, Flink and Spark, hide a lot of complexity from the programmer when they parallelize these applications across a compute cluster. This exacerbates reasoning about I/O of both the application and the framework, through the distributed file system, such as HDFS, down to the local file systems.
We present SFS (Statistics File System), a modular framework to trace each I/O request issued by the application and any JVM-based big data framework involved, mapping these requests to actual disk I/O.
This allows detection of inefficient I/O patterns, both by the applications and the underlying frameworks, and builds the basis for improving I/O scheduling in the big data software stack.
\\{\bf Zusammenfassung:} Kostenmodelle dienen der Ermittlung von Programmlaufzeiten, zum Vergleich der Effizienz von Algorithmen und zur Analyse des Verhaltens von Speicherhierarchien. Ein neuartiges Kostenmodell ist das Latency-of-Data-Access (LDA) Modell, das mehrere hierarchische Speicherebenen mit unterschiedlichen Latenzzeiten berü{}cksichtigt. In dieser Diplomarbeit wird ein Simulator fü{}r Speicherhierarchien prä{}sentiert, der die Berechnung von Programmausfü{}hrungszeiten nach dem LDA-Modell erlaubt. Mit Hilfe des Simulators wird die These geprü{}ft, da\ss{} mit diesem Modell die Ausfü{}hrungszeit eines Programms adä{}quat abgeschä{}tzt werden kann. Mit dem Simulator ist es erstmals praktikabel mö{}glich, Programmausfü{}hrungszeiten nach dem LDA-Modell zu bestimmen. Der Simulator kann fü{}r Systeme mit unterschiedlichen Speicherarchitekturen konfiguriert werden und unterstü{}tzt Mehrprozessorsysteme mit gemeinsamem Speicher (SMP-Systeme) mit verschiedenen Kohä{}renzprotokollen. Der Simulator kann mit den Ergebnissen von Microbenchmarks konfiguriert werden, die die Architekturparameter einer Speicherhierarchie messen. Die Ergebnisse bestä{}tigen die These nicht nur fü{}r Einzelprozessorsysteme, sondern auch fü{}r SMP-Systeme, wo gleichzeitig interagierende Prozessoren gegenseitig ihre Zugriffssequenz auf Zwischenspeicher beeinflussen. Zusä{}tzlich wurde eine neue Einsatzmö{}glichkeit des LDA-Modells entwickelt, um die Ausfü{}hrungszeit von Programmteilen zu bestimmen. Einzelne Zugriffskosten kö{}nnen einem mehrerer parallel laufender Modelle zugeordnet werden. Dadurch kö{}nnen Kosten, die Zugriffe auf einzelne Speicherbereiche verursachen, separat bestimmt werden. Diese Profiling-Technik erlaubt Optimierungen an Datenstrukturen und Speicherzugriffsmustern durch prä{}zise und gezielte Informationsproduktion.Cost models are used to determine the execution time of programs, to compare the efficiency of algorithms, and to analyse the behaviour of memory hierarchies. The Latency-of-Data-Access (LDA) model that takes into account multiple hierarchical memory levels with different latencies, is a newly proposed, innovative cost model. In this diploma-thesis, a simulator for memory hierarchies is presented that allows the calculation of execution times using the LDA-model. The simulator is used to prove the claim that the execution time of a program can be accurately estimated with the LDA-model. With the simulator, it is for the first time possible to determine the execution time of programs with this model in a practical way. The simulator can be configured for systems with various cache architectures and supports shared memory (SMP) multiprocessor systems with different cache coherence protocols. The simulator can be configured with the results from microbenchmarks which measure the architectural properties of a memory hierarchy. The results confirm the claim not only for single processor systems, but also for SMP systems, where concurrently interacting processors influence each others cache access sequence. Additionally, a new field of usage of the LDA-model was developed to determine execution times of program parts. Single access costs can be assigned to one of several parallel running models. As an example the costs of accesses to different memory areas can be split and determined separately. This profiling technique allows to optimise data structures and memory access patterns of sequential and parallel SMP programs by precise production of information.
Kostenmodelle dienen der Ermittlung von Programmlaufzeiten, zum Vergleich der Effizienz von Algorithmen und zur Analyse des Verhaltens von Speicherhierarchien. Ein neuartiges Kostenmodell ist das Latency-of-Data-Access (LDA) Modell, das mehrere hierarchische Speicherebenen mit unterschiedlichen Latenzzeiten berücksichtigt. In dieser Diplomarbeit wird ein Simulator für Speicherhierarchien präsentiert, der die Berechnung von Programmausführungszeiten nach dem LDA-Modell erlaubt. Mit Hilfe des Simulators wird die These geprüft, daß mit diesem Modell die Ausführungszeit eines Programms adäquat abgeschätzt werden kann. Mit dem Simulator ist es erstmals praktikabel möglich, Programmausführungszeiten nach dem LDA-Modell zu bestimmen. Der Simulator kann für Systeme mit unterschiedlichen Speicherarchitekturen konfiguriert werden und unterstützt Mehrprozessorsysteme mit gemeinsamem Speicher (SMP-Systeme) mit verschiedenen Kohärenzprotokollen. Der Simulator kann mit den Ergebnissen von Microbenchmarks konfiguriert werden, die die Architekturparameter einer Speicherhierarchie messen. Die Ergebnisse bestätigen die These nicht nur für Einzelprozessorsysteme, sondern auch für SMP-Systeme, wo gleichzeitig interagierende Prozessoren gegenseitig ihre Zugriffsse-quenz auf Zwischenspeicher beeinflussen. Zusätzlich wurde eine neue Einsatzmöglichkeit des LDA-Modells entwickelt, um die Ausführungszeit von Programmteilen zu bestimmen. Einzelne Zugriffskosten können einem mehrerer parallel laufender Modelle zugeordnet werden. Dadurch können Kosten, die Zugriffe auf einzelne Speicherbereiche verursachen, separat bestimmt werden. Diese Profiling-Technik erlaubt Optimierungen an Datenstrukturen und Speicherzugriffsmustern durch präzise und gezielte Informationsproduktion.
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.
\newcommand{\chordsharp}{Chord$^\##$} Data lookup is a fundamental problem in peer-to-peer systems: Given a key, find the node that stores the associated object. Chord and other P2P algorithms use distributed hash tables (DHTs) to distribute the keys and nodes evenly across a logical ring. Using an efficient routing strategy, DHTs provide a routing performance of $O (\log N)$ in networks of $N$ nodes. While the routing performance has been shown to be optimal, the uniform key distribution makes it impossible for DHTs to support range queries. For range queries, consecutive keys must be stored on lo gically neighboring nodes. In this paper, we present an enhancement of Chord that eliminates the hash function while keeping the same routing performance. The resulting algorithm, named \chordsharp{}, provides a richer function ality while maintaining the same complexity. In addition to Chord, \chordsharp{} adapts to load imbalance.
User-defined and system-level checkpointing have contrary properties. While user-defined checkpoints are smaller and simpler to recover, system-level checkpointing better knows the global system's state and parameters like the expected mean time to failure (MTTF) per node. Both approaches lead to non-optimal checkpoint time, intervals, sizes, or I/O bandwidth when concurrent checkpoints conflict and compete for it.
We combine user-defined and system-level checkpointing to exploit the benefits and avoid the drawbacks of each other. Thus, applications frequently offer to create checkpoints. The system accepts such offers according to the current status and implied costs to recalculate from the last checkpoint or denies them, i.e., immediately lets continue the application without checkpoint creation. To support this approach, we develop economic models for multi-application checkpointing on shared I/O resources that are dedicated for checkpointing (e.g. burst-buffers) by defining an appropriate goal function and solving a global optimization problem.
Using our models, the checkpoints of applications on a supercomputer are scheduled to effectively use the available I/O bandwidth and minimize the failure overhead (checkpoint creations plus recalculations). Our simulations show an overall reduction in failure overhead of all nodes of up to 30% for a typical supercomputer workload (HLRN). We can also derive the most cost effective burst-buffer bandwidth for a given node's MTTF and application workload.