Tuesday, 12 December 2017

Session 4: Adaptive Systems

Integrated Estimation and Tracking of Performance Model Parameters with Autoregressive Trends

Authors:

Tao Zheng (Carleton University)
Marin Litoiu (York University)
Murray Woodside (Carleton University)

Abstract:

Adaptive management of a software service system can take advantage of a performance model which can predict the effect of proposed changes, before they are deployed. As the system varies over time the model parameters can be tracked by an estimator such as a Kalman Filter, so that decisions can be updated. The filter is valuable when parameters are "hidden" and cannot be directly measured without excessive cost (as is usually the case for the CPU time of a service). Because there may be significant delays in some management control actions (especially in deploying a new replica of a service), it is also important to be able to predict the changes ahead somewhat in time, that is, to predict the trends. The trend predictor itself needs to be estimated from observed trends in the model parameters. This work uses an autoregressive model for trend prediction and integrates it with the parameter estimator, in a single Kalman Filter, using auxiliary states for the parameter evolution process. This paper describes how the trend model is constructed, and evaluates its effectiveness. It compares the overall performance predictions to a simpler trend predictor using linear extrapolation of the fitted parameter time-series, which turns out to be almost as good. The approach is validated on a real system running a benchmark web application.

DOI: 10.1145/1958746.1958772

Full text: PDF

[#][]

Adaptive Run-Time Performance Optimization Through Scalable Client Request Rate Control

Authors:

Guenther Starnberger (Vienna University of Technology)
Lorenz Froihofer (Vienna University of Technology)
Karl M. Goeschka (Vienna University of Technology)

Abstract:

Today's Internet-scale computing systems often run at a low average load with only occasional peak performance demands. Consequently, computing resources are often overdimensioned, leading to high costs. While load control techniques between clients and servers can help to better utilize a given system, these techniques can place a significant communication and computation load on servers. To improve on these issues, we contribute with scalable techniques for client-request rate control, achieved through integration of (i) a scalable distributed feedback channel to transmit control information from the server to the clients with (ii) decoupling strategies that allow to constrain and filter client requests directly at the client, illustrated in the area of first-price sealed-bid online auctions, and (iii) a PID (Proportional-Integral-Derivative) controller that adaptively controls the input parameters of those decoupling strategies to facilitate an optimal server utilization. In contrast to related work, we can hence optimize server load directly at the source through rate control of the clients. Our evaluations show that this setup supports large sets of clients before the controller becomes unstable.

DOI: 10.1145/1958746.1958773

Full text: PDF

[#][]

Tracking Adaptive Performance Models Using Dynamic Clustering of User Classes

Authors:

Hamoun Ghanbari (York University)
Cornel Barna (York University)
Marin Litoiu (York University)
Murray Woodside (Carleton University)
Tao Zheng (University of Waterloo)
Johnny Wong (University of Waterloo)
Gabriel Iszlai (IBM Toronto Lab)

Abstract:

Estimation techniques have been largely applied to track hidden performance parameters (e.g. service demands) of web based software systems. In this paper we investigate dynamic multiclass modeling of such systems, with variable classes of service, aiming at finding a low complexity model yet with enough accuracy. We propose a combination of clustering algorithm and tracking filter for effective grouping of classes of services. The tracking estimator is based on a layered queuing model with parameters for CPU demands and the user load intensity of each class of service. Clustering uses the K-means algorithm. The target application is autonomic control of web clusters, where changes occur at different rates and amplitudes and at random time instants. Experiments show that the tracking is effective, and reveal good filter settings for different variations.

DOI: 10.1145/1958746.1958774

Full text: PDF

[#][]

Dynamic Selection of Implementation Variants of Sequential Iterated Runge-Kutta Methods with Tile Size Sampling

Authors:

Natalia Kalinnik (University of Bayreuth)
Matthias Korch (University of Bayreuth)
Thomas Rauber (University of Bayreuth)

Abstract:

This paper describes an efficient self-adaptive procedure for iterated Runge-Kutta (IRK) methods, a class of solution methods for initial value problems (IVPs) of ordinary differential equations (ODEs). IRK methods execute a potentially large number of discrete time steps to compute the solution of the IVP. The performance of an IRK solver may strongly depend on the specific characteristics of the given IVP and the hardware architecture on which the solver is executed. To address this problem, this paper applies dynamic auto-tuning to the sequential execution of IRK methods. Auto-tuning is a promising technique to avoid time consuming and extensive manual tuning. Our self-adaptive IRK solver utilizes the time-stepping nature of the IRK method. It selects the fastest implementation variant for the given IVP on the target architecture from a candidate pool during the first time steps. Then, the fastest implementation variant is used to compute all remaining time steps. The different implementation variants in the candidate pool have been developed by modifications of the loop structure of the basic algorithm. For those implementation variants that use loop tiling, we consider different tile sizes during the auto-tuning phase to further improve the performance of the self-adaptive IRK solver. Runtime experiments demonstrate the efficiency of the self-adaptive IRK solver for different IVPs on different hardware architectures.

DOI: 10.1145/1958746.1958775

Full text: PDF

[#][]

Performance Sensitive Self-Adaptive Service-Oriented Software Using Hidden Markov Models

Authors:

Diego Perez-Palacin (Universidad de Zaragoza)
José Merseguer (Universidad de Zaragoza)

Abstract:

Service Oriented Architecture (SOA) is a paradigm where applications are built on services offered by third party providers. Behavior of providers evolves and makes a challenge the performance prediction of SOA applications. A proper decision about when a provider should be substituted can dramatically improve the performance of the application. We propose hidden Markov models (HMM) to help service integrators to foretell the current state of third-parties. The paper leverages different algorithms that change providers based on predictions about their states. We also integrate these algorithms and HMMs in an architectural solution to coordinate them with other challenges in the SOA world.

DOI: 10.1145/1958746.1958776

Full text: PDF

[#][]