Self-stabilizing Balls & Bins in Batches

A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modelled as static balls into bins processes, where m balls (tasks) are to be distributed to n bins (servers). In a seminal work, [Azar et al.; JoC'99] proposed the sequential strategy Greedy[d] for n = m. When thrown, a ball queries the load of d random bins and is allocated to a least loaded of these. [Azar et al.; JoC'99] showed that d=2 yields an exponential improvement compared to d=1. [Berenbrink et al.; JoC'06] extended this to m ⇒ n, showing that the maximal load difference is independent of m for d=2 (in contrast…

Improving LSM‐trie performance by parallel search

Multiple-Choice Balanced Allocation in (Almost) Parallel

We consider the problem of resource allocation in a parallel environment where new incoming resources are arriving online in groups or batches.

Building a Medical Research Cloud in the EASI-CLOUDS Project

The demand for IT resources is constantly growing in the scientific area. The ability to store and process increasing amounts of data has transformed many research disciplines, like the life-sciences, which now rely on complex data processing and data analytics. Cloud environments are able to integrate and encapsulate possibly distributed resources and allow convenient and on-demand access to the corresponding services, tools, and complete work environments. The European research project EASI-CLOUDS (http://www. easi-clouds.eu) develops a platform for a convenient service delivery with special regard to service integration, monitoring, management, and Service Level Agreement (SLA) negotiati…

Constant Time Garbage Collection in SSDs

Building a medical research cloud in the EASI-CLOUDS project

Summary The demand for Information Technology (IT) resources is constantly growing in the scientific area. The ability to store and process increasing amounts of data has transformed many research disciplines like the life sciences, which now rely on complex data processing and data analytics. Cloud computing can provide researchers with scalable and easy-to-use hardware and software resources and allows on-demand access to services, tools, or even complete work environments. The European research project EASI-CLOUDS has developed a service delivery platform with special regard to service integration, monitoring and management, and the negotiation of service level agreements. In order to de…

And Now for Something Completely Different: Running Lisp on GPUs

The internal parallelism of compute resources increases permanently, and graphics processing units (GPUs) and other accelerators have been gaining importance in many domains. Researchers from life science, bioinformatics or artificial intelligence, for example, use GPUs to accelerate their computations. However, languages typically used in some of these disciplines often do not benefit from the technical developments because they cannot be executed natively on GPUs. Instead existing programs must be rewritten in other, less dynamic programming languages. On the other hand, the gap in programming features between accelerators and common CPUs shrinks permanently. Since accelerators are becomi…

FederatedCloudSim

Recent developments show that the standardization of cloud service descriptions and exchange leads the way for the rise of cloud federations. In these federations CSPs (cloud service providers) can use resources of other CSPs in the case of a lack of local resources or they can add remote services to their catalogue. Cloud federations again demand for cloud brokers which offer the resources and services of different CSPs transparently to the users. Research of cloud federations in the real world is very complex and expensive as distributed hard- and software scenarios are needed. Therefore we present FederatedCloudSim, a very flexible cloud simulation framework that can be used to simulate …

Deduplication Potential of HPC Applications’ Checkpoints

HPC systems contain an increasing number of components, decreasing the mean time between failures. Checkpoint mechanisms help to overcome such failures for long-running applications. A viable solution to remove the resulting pressure from the I/O backends is to deduplicate the checkpoints. However, there is little knowledge about the potential to save I/Os for HPC applications by using deduplication within the checkpointing process. In this paper, we perform a broad study about the deduplication behavior of HPC application checkpointing and its impact on system design.

Accelerating Application Migration in HPC

It is predicted that the number of cores per node will rapidly increase with the upcoming era of exascale supercomputers. As a result, multiple applications will have to share one node and compete for the (often scarce) resources available on this node. Furthermore, the growing number of hardware components causes a decrease in the mean time between failures. Application migration between nodes has been proposed as a tool to mitigate these two problems: Bottlenecks due to resource sharing can be addressed by load balancing schemes which migrate applications; and hardware errors can often be tolerated by the system if faulty nodes are detected and processes are migrated ahead of time.

Distributing Storage in Cloud Environments

Cloud computing has a major impact on today's IT strategies. Outsourcing applications from IT departments to the cloud relieves users from building big infrastructures as well as from building the corresponding expertise, and allows them to focus on their main competences and businesses. One of the main hurdles of cloud computing is that not only the application, but also the data has to be moved to the cloud. Networking speed severely limits the amount of data that can travel between the cloud and the user, between different sites of the same cloud provider, or indeed between different cloud providers. It is therefore important to keep applications near the data itself. This paper investig…

Self-stabilizing Balls & Bins in Batches

A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modeled as static balls into bins processes, where $m$ balls (tasks) are to be distributed to $n$ bins (servers). In a seminal work, Azar et al. proposed the sequential strategy \greedy{d} for $n=m$. When thrown, a ball queries the load of $d$ random bins and is allocated to a least loaded of these. Azar et al. showed that $d=2$ yields an exponential improvement compared to $d=1$. Berenbrink et al. extended this to $m\gg n$, showing that the maximal load difference is independent of $m$ for $d=2$ (in contrast to $d=1$). W…

Pure Functions in C: A Small Keyword for Automatic Parallelization

AbstractThe need for parallel task execution has been steadily growing in recent years since manufacturers mainly improve processor performance by increasing the number of installed cores instead of scaling the processor’s frequency. To make use of this potential, an essential technique to increase the parallelism of a program is to parallelize loops. Several automatic loop nest parallelizers have been developed in the past such as PluTo. The main restriction of these tools is that the loops must be statically analyzable which, among other things, disallows function calls within the loops. In this article, we present a seemingly simple extension to the C programming language which marks fun…

Scalable Monitoring System for Clouds

Although cloud computing has become an important topic over the last couple of years, the development of cloud-specific monitoring systems has been neglected. This is surprising considering their importance for metering services and, thus, being able to charge customers. In this paper we introduce a monitoring architecture that was developed and is currently implemented in the EASI-CLOUDS project. The demands on cloud monitoring systems are manifold. Regular checks of the SLAs and the precise billing of the resource usage, for instance, require the collection and converting of infrastructure readings in short intervals. To ensure the scalability of the whole cloud, the monitoring system mus…

VarySched: A Framework for Variable Scheduling in Heterogeneous Environments

Despite many efforts to better utilize the potential of GPUs and CPUs, it is far from being fully exploited. Although many tasks can be easily sped up by using accelerators, most of the existing schedulers are not flexible enough to really optimize the resource usage of the complete system. The main reasons are (i) that each processing unit requires a specific program code and that this code is often not provided for every task, and (ii) that schedulers may follow the run-until-completion model and, hence, disallow resource changes during runtime. In this paper, we present VarySched, a configurable task scheduler framework tailored to efficiently utilize all available computing resources in…

Randomized renaming in shared memory systems.

Abstract Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m . The problem is called tight if m = n , and loose if m > n . In recent years renaming came to the fore again and new algorithms were developed. For tight renaming in asynchronous shared memory systems, Alistarh et al. describe a construction based on the AKS network that assigns all names within O ( log n ) steps per process. They also show that, depending on the size of the name space, loose renaming can be done considerably faster. For m = ( 1 + ϵ ) ⋅ n and constant ϵ , they achieve a step complexity of O ( log log n ) . In this paper we consider tight as well as loos…

Balls into non-uniform bins

Balls-into-bins games for uniform bins are widely used to model randomized load balancing strategies. Recently, balls-into-bins games have been analysed under the assumption that the selection probabilities for bins are not uniformly distributed. These new models are motivated by properties of many peer-to-peer (P2P) networks, which are not able to perfectly balance the load over the bins. While previous evaluations try to find strategies for uniform bins under non-uniform bin selection probabilities, this paper investigates heterogeneous bins, where the "capacities" of the bins might differ significantly. We show that heterogeneous environments can even help to distribute the load more eve…

Hyperion

Indexes are essential in data management systems to increase the speed of data retrievals. Widespread data structures to provide fast and memory-efficient indexes are prefix tries. Implementations like Judy, ART, or HOT optimize their internal alignments for cache and vector unit efficiency. While these measures usually improve the performance substantially, they can have a negative impact on memory efficiency. In this paper we present Hyperion, a trie-based main-memory key-value store achieving extreme space efficiency. In contrast to other data structures, Hyperion does not depend on CPU vector units, but scans the data structure linearly. Combined with a custom memory allocator, Hyperion…

Computing the Probability for Data Loss in Two-Dimensional Parity RAIDs

Parity RAIDs are used to protect storage systems against disk failures. The idea is to add redundancy to the system by storing the parity of subsets of disks on extra parity disks. A simple two-dimensional scheme is the one in which the data disks are arranged in a rectangular grid, and every row and column is extended by one disk which stores the parity of it.In this paper we describe several two-dimensional parity RAIDs and analyse, for each of them, the probability for dataloss given that f random disks fail. This probability can be used to determine the overall probability using the model of Hafner and Rao. We reduce subsets of the forest counting problem to the different cases and show…

Sorted deduplication: How to process thousands of backup streams

The requirements of deduplication systems have changed in the last years. Early deduplication systems had to process dozens to hundreds of backup streams at the same time while today they are able to process hundreds to thousands of them. Traditional approaches rely on stream-locality, which supports parallelism, but which easily leads to many non-contiguous disk accesses, as each stream competes with all other streams for the available resources. This paper presents a new exact deduplication approach designed for processing thousands of backup streams at the same time on the same fingerprint index. The underlying approach destroys the traditionally exploited temporal chunk locality and cre…

Financial Evaluation of SLA-based VM Scheduling Strategies for Cloud Federations

In recent years, cloud federations have gained popularity. Small as well as big cloud service providers (CSPs) join federations to reduce their costs, and also cloud management software like OpenStack offers support for federations. In a federation, individual CSPs cooperate such that they can move load to partner clouds at high peaks and possibly offer a wider range of services to their customers. Research in this area addresses the organization of such federations and strategies that CSPs can apply to increase their profit.In this paper we present the latest extensions to the FederatedCloudSim framework that considerably improve the simulation and evaluation of cloud federations. These si…

Scheduling shared continuous resources on many-cores

We consider the problem of scheduling a number of jobs on m identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement rj∈[0,1]. The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of r_j, it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their processing speeds, have been studied under the term discrete-continuous scheduling. Known results are either very pessimistic or heuristic in nature. In this paper, …

LoneStar RAID

The need for huge storage archives rises with the ever growing creation of data. With today’s big data and data analytics applications, some of these huge archives become active in the sense that all stored data can be accessed at any time. Running and evolving these archives is a constant tradeoff between performance, capacity, and price. We present the LoneStar RAID, a disk-based storage architecture, which focuses on high reliability, low energy consumption, and cheap reads. It is designed for MAID systems with up to hundreds of disk drives per server and is optimized for “write once, read sometimes” workloads. We use dedicated data and parity disks, and export the data disks as individu…

Smart grid-aware scheduling in data centres

In several countries the expansion and establishment of renewable energies result in widely scattered and often weather-dependent energy production, decoupled from energy demand. Large, fossil-fuelled power plants are gradually replaced by many small power stations that transform wind, solar and water power into electrical power. This leads to changes in the historically evolved power grid that favours top-down energy distribution from a backbone of large power plants to widespread consumers. Now, with the increase of energy production in lower layers of the grid, there is also a bottom-up flow of the grid infrastructure compromising its stability. In order to locally adapt the energy deman…

Migration Techniques in HPC Environments

Process migration is an important feature in modern computing centers as it allows for a more efficient use and maintenance of hardware. Especially in virtualized infrastructures it is successfully exploited by schemes for load balancing and energy efficiency. One can divide the tools and techniques into three groups: Process-level migration, virtual machine migration, and container-based migration.

Evaluation of SLA-based decision strategies for VM scheduling in cloud data centers

Service level agreements (SLAs) gain more and more importance in the area of cloud computing. An SLA is a contract between a customer and a cloud service provider (CSP) in which the CSP guarantees functional and non-functional quality of service parameters for cloud services. Since CSPs have to pay for the hardware used as well as penalties for violating SLAs, they are eager to fulfill these agreements while at the same time optimizing the utilization of their resources.In this paper we examine SLA-aware VM scheduling strategies for cloud data centers. The service level objectives considered are resource usage and availability. The sample resources are CPU and RAM. They can be overprovision…