Equilibrium: an elasticity controller for parallel tree search in the cloud
- PDF / 1,791,283 Bytes
- 35 Pages / 439.37 x 666.142 pts Page_size
- 15 Downloads / 190 Views
Equilibrium: an elasticity controller for parallel tree search in the cloud Stefan Kehrer1 · Wolfgang Blochinger1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Elasticity is considered to be the most beneficial characteristic of cloud environments, which distinguishes the cloud from clusters and grids. Whereas elasticity has become mainstream for web-based, interactive applications, it is still a major research challenge how to leverage elasticity for applications from the high-performance computing (HPC) domain, which heavily rely on efficient parallel processing techniques. In this work, we specifically address the challenges of elasticity for parallel tree search applications. Well-known meta-algorithms based on this parallel processing technique include branch-and-bound and backtracking search. We show that their characteristics render static resource provisioning inappropriate and the capability of elastic scaling desirable. Moreover, we discuss how to construct an elasticity controller that reasons about the scaling behavior of a parallel system at runtime and dynamically adapts the number of processing units according to user-defined cost and efficiency thresholds. We evaluate a prototypical elasticity controller based on our findings by employing several benchmarks for parallel tree search and discuss the applicability of the proposed approach. Our experimental results show that, by means of elastic scaling, the performance can be controlled according to user-defined thresholds, which cannot be achieved with static resource provisioning. Keywords Cloud computing · High-performance computing · Task Parallelism · Elasticity of parallel computations
* Stefan Kehrer stefan.kehrer@reutlingen‑university.de Wolfgang Blochinger wolfgang.blochinger@reutlingen‑university.de 1
Parallel and Distributed Computing Group, Reutlingen University, Reutlingen, Germany
13
Vol.:(0123456789)
S. Kehrer, W. Blochinger
1 Introduction The cloud evolved into an attractive execution environment for high-performance computing (HPC) with benefits such as on-demand access to compute resources, pay-per-use, and elasticity [20, 23, 55, 59, 80, 81]. Former performance issues inherent to standard cloud environments such as heterogeneous processing speeds as well as low network throughput and high network latency (resulting from virtualization and resource pooling) have been addressed by novel concepts to make cloud environments HPC-aware [23, 32, 53, 84]. As of today, many cloud providers, including Amazon Web Services (AWS)1 and Microsoft Azure,2 offer HPC-aware cloud environments, i.e., cloud environments optimized for HPC [2, 85]. Recently, a single cloud-based parallel system built on top of AWS has been listed in the TOP500 list3 at rank 136. Whereas HPC-aware cloud environments enable the migration of existing parallel applications without modifications [45], elasticity, which is often considered to be the most beneficial cloud-specific property [1, 22], gives rise to a fundamentally new c
Data Loading...
