Tuesday, 12 December 2017

Session: 1: Performance Prediction Techniques for Software and Systems

On the Accuracy of Cache Sharing Models

Authors:

Vlastimil Babka (Charles University)
Peter Libič (Charles University)
Tomásš Martinec (Charles University)
Petr Tůma (Charles University)

Abstract:

Memory caches significantly improve the performance of workloads that have temporal and spatial locality by providing faster access to data. Current processor designs have multiple cores sharing a cache. To accurately model a workload performance and to improve system throughput by intelligently scheduling workloads on cores, we need to understand how sharing caches between workloads affects their data accesses.

Past research has developed analytical models that estimate the cache behavior for combined workloads given the stack distance profiles describing these workloads. We extend this research by presenting an analytical model with contributions to accuracy and composability - our model makes fewer simplifying assumptions than earlier models, and its output is in the same format as its input, which is an important property for hierarchical composition during software performance modeling.

To compare the accuracy of our analytical model with earlier models, we attempted to reproduce the reported accuracy of those models. This proved to be difficult. We provide additional insight into the major factors that influence analytical model accuracy.

DOI: 10.1145/2188286.2188294

Full text: PDF

[#][]

Systematic Adoption of Genetic Programming for Deriving Software Performance Curves

Authors:

Michael Faber (Karlsruhe Institute of Technology)
Jens Happe (SAP Research)

Abstract:

Measurement-based approaches to software performance engineering apply analysis methods (e.g., statistical inference or machine learning) on raw measurement data with the goal to build a mathematical model describing the performancerelevant behavior of a system under test (SUT). The main challenge for such approaches is to find a reasonable trade-off between minimizing the amount of necessary measurement data used to build the model and maximizing the model's accuracy. Most existing methods require prior knowledge about parameter dependencies or their models are limited to only linear correlations. In this paper, we investigate the applicability of genetic programming (GP) to derive a mathematical equation expressing the performance behavior of the measured system (software performance curve). We systematically optimized the parameters of the GP algorithm to derive accurate software performance curves and applied techniques to prevent overfitting. We conducted an evaluation with a representative MySQL database system. The results clearly show that the GP algorithm outperforms other analysis techniques like inverse distance weighting (IDW) and multivariate adaptive regression splines (MARS) in terms of model accuracy.

DOI: 10.1145/2188286.2188295

Full text: PDF

[#][]

Fluid Limits of Queueing Networks with Batches

Authors:

Luca Bortolussi (University of Trieste)
Mirco Tribastone (Ludwig-Maximillians-Universität Munich)

Abstract:

This paper presents an analytical model for the performance prediction of queueing networks with batch services and batch arrivals, related to the fluid limit of a suitable singleparameter sequence of continuous-time Markov chains and interpreted as the deterministic approximation of the average behaviour of the stochastic process. Notably, the underlying system of ordinary differential equations exhibits discontinuities in the right-hand sides, which however are proven to yield a meaningful solution. A substantial numerical assessment is used to study the quality of the approximation and shows very good accuracy in networks with large job populations.

DOI: 10.1145/2188286.2188296

Full text: PDF

[#][]

An Approximate Solution for Ph/Ph/1 and Ph/Ph/1/N Queues

Authors:

Alexandre Brandwajn (University of California Santa Cruz)
Thomas Begin (University Lyon 1)

Abstract:

We propose a simple approximation to assess the steady-state probabilities of the number of customers in Ph/Ph/1 and Ph/Ph/1/N queues, as well as probabilities found on arrival, including the probability of buffer overflow for the Ph/Ph/1/N queue. The phase-type distributions considered are assumed to be acyclic. Our method involves iteration between solutions of an M/Ph/1 queue with state-dependent arrival rate and a Ph/M/1 queue with state-dependent service rate. We solve these queues using simple and efficient recurrences. By iterating between these two simpler models our approximation divides the state space, and is thus able to easily handle phase-type distributions with large numbers of stages (which might cause problems for classical numerical solutions). The proposed method converges typically within a few tens of iterations, and is asymptotically exact for queues with unrestricted queueing room. Its overall accuracy is good: generally within a few percent of the exact values, except when both the inter-arrival and the service time distributions exhibit low variability. In the latter case, especially under moderate loads, the use of our method is not recommended.

DOI: 10.1145/2188286.2188297

Full text: PDF

[#][]