nach oben

2008 | Buch

Kapitel lesen Erstes Kapitel lesen

Computer Performance Engineering

5th European Performance Engineering Workshop, EPEW 2008, Palma de Mallorca, Spain, September 24-25, 2008. Proceedings

herausgegeben von: Nigel Thomas, Carlos Juiz

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the proceedings of the Fifth European Performance Engineering Workshop, EPEW 2008, held in Palma de Mallorca, Spain, in September 24-25, 2008. The 17 papers presented in this volume, together with abstracts of 2 invited papers, were carefully reviewed and selected from 39 submissions. The topics covered are software performance engineering; stochastic process algebra and SANs; performance query specification and measurement; computer and communications networks; queueing theory and Markov chains; and applications.

Inhaltsverzeichnis

Frontmatter

Invited Papers

Performance and Dependability Evaluation: Successes, Failures and Challenges

Abstract

Over the last 40 years, the field of model-based performance and dependability evaluation has seen important developments, successes and scientific breakthroughs. However, the field has not matured into a key engineering discipline which is heavily called upon by computer system and software engineers, even though it is well-known that already the use of simple analytical models can result in better insight in system performance. In the area of communication system design, performance evaluation has become more of a mainstream activity, albeit almost exclusively using discrete-event simulation techniques.

What circumstances made that almost all of our excellent work on analytical performance and dependability evaluation did not find the acceptance and use we think it deserves?

On the basis of an historical account of the major developments in the area over the last 40 years, I will address probable reasons for the relatively moderate success and acceptance of model-based performance and dependability evaluation. What did we do right, what did we do wrong? Which circumstances led to successes, and where did we fail?

Based on the gathered insights, I will discuss upcoming challenges for the field and recommend research directions for the decade to come.

Boudewijn R. Haverkort

Partial Evaluation of PEPA Models for Fluid-Flow Analysis

Abstract

We present an application of partial evaluation to performance models expressed in the PEPA stochastic process algebra [1]. We partially evaluate the state-space of a PEPA model in order to remove uses of the cooperation and hiding operators and compile an arbitrary sub-model into a single sequential component. This transformation is applied to PEPA models which are not in the correct form for the application of the fluid-flow analysis for PEPA [2]. The result of the transformation is a PEPA model which is amenable to fluid-flow analysis but which is strongly equivalent [1] to the input PEPA model and so, by an application of Hillston’s theorem, performance results computed from one model are valid for the other. We apply the method to a Markovian model of a key distribution centre used to facilitate secure distribution of cryptographic session keys between remote principals communicating over an insecure network.

Allan Clark, Adam Duguid, Stephen Gilmore, Mirco Tribastone

Software Performance Engineering

An Empirical Investigation of the Applicability of a Component-Based Performance Prediction Method

Abstract

Component-based software performance engineering (CBSPE) methods shall enable software architects to assess the expected response times, throughputs, and resource utilization of their systems already during design. This avoids the violation of performance requirements. Existing approaches for CBSPE either lack tool support or rely on prototypical tools, who have only been applied by their authors. Therefore, industrial applicability of these methods is unknown. On this behalf, we have conducted a controlled experiment involving 19 computer science students, who analysed the performance of two component-based designs using our Palladio performance prediction approach, as an example for a CBSPE method. Our study is the first of its type in this area and shall help to mature CBSPE to industrial applicability. In this paper, we report on results concerning the prediction accuracy achieved by the students and list several lessons learned, which are also relevant for other methods than Palladio.

Anne Martens, Steffen Becker, Heiko Koziolek, Ralf Reussner

A Calibration Framework for Capturing and Calibrating Software Performance Models

Abstract

Software performance engineering could benefit from combining modeling and testing techniques, if performance models could be derived more cheaply and more easily. This work investigates how known testing and estimation methodologies can be combined in a calibration framework, to provide and maintain performance models in sync with a developing product or component library. There are two main aspects. The first addresses a major barrier in practice, the calibration of model parameters that represent quantities that cannot easily be measured directly. This work calibrates these “hidden parameters” efficiently using a Kalman Filter. The second is the exploitation of the filter estimator to control the calibration framework, for example to terminate a test when accuracy is sufficient, and to design tests for parameter coverage. The technique is demonstrated on simulated data and on an implemented Voice-over-IP (VoIP) system.

Xiuping Wu, Murray Woodside

Performance Evaluation of Embedded ECA Rule Engines: A Case Study

Abstract

Embedded systems operating on high data workloads are becoming pervasive. ECA rule engines provide a flexible environment to support the management, reconfiguration and execution of business rules. However, modeling the performance of a rule engine is challenging because of its reactive nature. In this work we present the performance analysis of an ECA rule engine in the context of a supply chain scenario. We compare the performance predictions against the measured results obtained from our performance tool set, and show that despite its simplicity the performance prediction model is reasonably accurate.

Pablo E. Guerrero, Kai Sachs, Stephan Butterweck, Alejandro Buchmann

Stochastic Process Algebra and SANs

Towards State Space Reduction Based on T-Lumpability-Consistent Relations

Abstract

Markovian behavioral equivalences can be exploited for state space reduction before performance evaluation takes place. It is known that Markovian bisimilarity corresponds to ordinary lumpability and that Markovian testing and trace equivalences correspond to a coarser exact relation we call T-lumpability. While there exists an ordinary-lumpability-consistent aggregation algorithm, this is not the case with T-lumpability. Based on the axiomatization of Markovian testing and trace equivalences, we provide a sufficient condition for T-lumpability that can easily be embedded in the aggregation algorithm for ordinary lumpability, thus enhancing the potential for exact state space reduction. We also identify a class of systems – those providing incremental services – for which the resulting aggregation algorithm turns out to be useful.

Marco Bernardo

A Ticking Clock: Performance Analysis of a Circadian Rhythm with Stochastic Process Algebra

Abstract

We apply performance analysis techniques to a biological modelling problem, that of capturing and reproducing the Circadian rhythm. A Circadian rhythm provides cells with a clock by which to regulate their behaviour. We consider two distinct stochastic models of the Circadian rhythm – one unbounded and the other bounded. We consider a fluid approximation of the models, and, by conversion to a set of ordinary differential equations, we are able to reproduce the correct rhythm. We show that with a bounded model, the clock phase can be affected by modifying the ability to manufacture some proteins.

Jeremy T. Bradley

Assembly Code Analysis Using Stochastic Process Algebra

Abstract

Currently compilers contain a large number of optimisations which are based on a set of heuristics that are not guaranteed to be effective to improve the performance metrics. In this paper, we propose a strategy which allows us the analysis and the choice of the best optimisation, by focusing on the hot part of an assembly code. In our approach, for each optimisation applied, the code of the hot loop is extracted and its dependency graph generated. Finally, and in order to select the best optimisation, the generated graphs are analytically analysed using stochastic process algebra.

Lamia Djoudi, Leïla Kloul

Product Form Steady-State Distribution for Stochastic Automata Networks with Domino Synchronizations

Abstract

We present a new kind of synchronization which allows Continuous Time Stochastic Automata Networks (SAN) to have a product form steady-state distribution. Unlike previous models on SAN with product form solutions, our model allows synchronization between three automata but functional rates are not allowed. The synchronization is not the usual ”Rendez-Vous” but an ordered list of transitions. Each transition may fail. When a transition fails, the synchronization ends but all the transitions already executed are kept. This synchronization is related to the triggered customer movement between queues in a network and this class of SAN is a generalization of Gelenbe’s networks with triggered customer movement.

Jean-Michel Fourneau

Performance Query Specification and Measurement

State-Aware Performance Analysis with eXtended Stochastic Probes

Abstract

We define a mechanism for specifying performance queries which combine instantaneous observations of model states and finite sequences of observations of model activities. We realise these queries by composing the state-aware observers (called eXtended Stochastic Probes (XSP)) with a model expressed in a stochastically-timed process algebra. Our work has been conceived in the context of the process algebra PEPA. However the ideas involved are relevant to all timed process algebras with an underlying discrete-state representation such as a continuous-time Markov chain.

Allan Clark, Stephen Gilmore

Computer and Communications Networks

Natural Language Specification of Performance Trees

Abstract

The accessible specification of performance queries is a key challenge in performance analysis. To this end, we seek to combine the intuitive aspects of natural language query specification with the expressive power and flexibility of the Performance Tree formalism. Specifically, we present a structured English grammar for Performance Trees, and use it to implement a Natural Language Query Builder (NLQB) for the Platform Independent Petri net Editor (PIPE). The NLQB guides users in the construction of performance queries in an iterative fashion, presenting at each step a range of natural language alternatives that are appropriate in the query context. We demonstrate our technique in the specification of performance queries on a model of a hospital’s Accident and Emergency department.

Lei Wang, Nicholas J. Dingle, William J. Knottenbelt

Recurrent Method for Blocking Probability Calculation in Multi-service Switching Networks with BPP Traffic

Abstract

This paper presents a new approximate analytical recurrent calculation method of the occupancy distribution and the blocking probability in switching networks which are offered multi-service traffic streams generated by Binomial (Engset) & Poisson (Erlang) & Pascal traffic sources (BPP traffic). The method is based on the concept of effective availability. The proposed calculation algorithm is based on the recurrent calculation of blocking probability in subsequent subsystems of the switching network. These calculations involve determination of occupancy distributions in interstage links as well as in the outgoing links. These distributions are calculated by means of the full-availability group model and the limited-availability group model. The results of analytical calculations of the blocking probabilities are compared with the simulation results of 3-stage and 5-stage switching networks.

Mariusz Głąbowski

An Approximate Model of the WCDMA Interface Servicing a Mixture of Multi-rate Traffic Streams with Priorities

Abstract

The paper presents an approximate method for blocking probability determination in the WCDMA interface of the UMTS network with priorities. In our considerations we use a new model of the full-availability group servicing multi-rate traffic with priorities. In the proposed model we assume that a new call with a higher priority can terminate connections already in service if they are characterized by a lower priority than a new call. The proposed scheme is applicable for cost-effective WCDMA resource management in 3G mobile networks and can be easily applied to network capacity calculations.

Damian Parniewicz, Maciej Stasiak, Janusz Wiewióra, Piotr Zwierzykowski

Queueing Theory and Markov Chains

Performance Analysis of Dynamic Priority Shifting

Abstract

We investigate the benefit of priority shifting for resource allocation in systems with a shared resource, where higher priority implies better service. Priority schemes where priority levels are assigned fixed shares of the resource experience underutilisation if there are only low-priority tasks present. In these situations, lower priority tasks can be ‘shifted up’ to higher priority. This increases overall system utilisation and improves the service experienced by low-priority tasks. We present a shifting framework, study its properties and develop a Petri net model for a shifting algorithm. We analyse the model in order to identify situations where shifting of priorities is beneficial.

Philipp Reinecke, Katinka Wolter, Johannes Zapotoczky

Performance Analysis of a Priority Queue with Place Reservation and General Transmission Times

Abstract

In this paper, we analyze a discrete-time single-server queue with two classes of packet arrivals and a reservation-based scheduling discipline. The objective of this discipline is to give a certain priority to (delay-sensitive) packets of class 1 and at the same time to avoid packet starvation for the (delay-tolerant) packets of class 2. This is achieved by the introduction of a reserved place in the queue that can be taken by a future arrival of class 1. Both classes contain packets with generally distributed transmission times.

By means of a probability generating functions approach, both the class-1 and the class-2 packet delay are studied. By some numerical examples, the delay performance of the Reservation discipline is compared to that of the classical Absolute Priority (AP) and First-In First-Out (FIFO) scheduling disciplines.

Bart Feyaerts, Sabine Wittevrongel

Analysis of BMAP/G/1 Vacation Model of Non-M/G/1-Type

Abstract

In this paper we present the analysis of BMAP/G/1 vacation models of non-M/G/1-type in a general framework. We provide new service discipline independent formulas for the vector generating function (GF) of the stationary number of customers and for its mean, both in terms of quantities at the start of vacation.

We present new results for vacation models with gated and G-limited disciplines. For both models discipline specific systems of equations are setup. Their numerical solution are used to compute the required quantities at the start of vacation.

Zsolt Saffer, Miklós Telek

Applications

Stochastic Bounds for Partially Generated Markov Chains: An Algebraic Approach

Abstract

We propose several algorithms to obtain bounds based on Censored Markov Chains to analyze partially generated discrete time Markov chains. The main idea is to avoid the generation of a huge (or even infinite) state space and to truncate the state space during the visit. The approach is purely algebraic and provides element-wise and stochastic bounds for the CMC.

Ana Bušić, Jean-Michel Fourneau

Evaluation of P2P Algorithms for Probabilistic Trust Inference in a Web of Trust

Abstract

The problem of finding trust paths and estimating the trust one can place in a partner arises in various application areas, including virtual organisations, authentication systems and reputation systems. We study the use of peer-to-peer algorithms for finding trust paths and probabilistically assessing trust values in systems where trust is organised similar to the ‘web of trust’. We do this through discrete event simulation of random as well as scale free trust networks based on flooding as well as selective search algorithms. Our main conclusion is that in many situations these algorithms can be seen as belonging to a single class of algorithms that perform equally, and only differ through (and are sensitive to) parameter choices. We will also see that flooding is the only applicable method if one stresses the requirement for finding all trust paths, and if networks are less connected.

Huqiu Zhang, Aad van Moorsel

Approximation for Multi-service Systems with Reservation by Systems with Limited-Availability

Abstract

The paper presents a new method for modeling systems with reservation. The method is based on the generalized ideal grading model servicing multi-rate traffic. The paper proposes an algorithm for determining such an availability value in the ideal grading that causes blocking equalization of different classes of calls. The proposed method was worked out for integer and non-integer values of the availability parameters. A comparison of the analytical results with the simulation data proves high accuracy of the proposed method.

Maciej Stasiak, Sławomir Hanczewski

Backmatter

Titel: Computer Performance Engineering
herausgegeben von: Nigel Thomas
Carlos Juiz
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-87412-6
Print ISBN: 978-3-540-87411-9
DOI: https://doi.org/10.1007/978-3-540-87412-6