Wednesday, 13 December 2017

Session 5: Modelling and Tools and Methodologies

Session Chair: John Henning (Sun Microsystems)

A General Result for Deriving Product-Form Solutions in Markovian Models

Authors:

Andrea Marin (Università Cá Foscari di Venezia)
Maria Grazia Vigliotti (Imperial College London)

Abstract:

In this paper we provide a general method to derive product-form solutions for stochastic models. We take inspiration from the Reversed Compound Agent Theorem and we provide a different formulation using labeled automata, a generalization which encompasses a bigger class of product-form solutions, and a new proof based on the solution of the system of global balance equations. We show that our result may have practical applications in the performance evaluation of complex software and hardware architectures and can be the base for the development of new analysis tools or the extension of existing ones.

DOI: 10.1145/1712605.1712632

Full text: PDF

[#][]

A Markovian Futures Market for Computing Power

Authors:

Fernando Martínez Ortuno (Imperial College London)
Uli Harder (Imperial College London)
Peter G. Harrison (Imperial College London)

Abstract:

In this paper we describe aspects of a market model for Grid computing. In particular we concentrate on Grid computing provided by a peer-to-peer network architecture. In this network nodes can either buy or sell computing power in exchange for money. Building on previous publications we develop a mathematical market model using Markov chains. The behaviour of each agent in the market is described by a Markov chain of decisions on buying, selling or holding. Considering the contributions of all agents, we calculate the global Markov chain of the market state as a whole, by making use of a concept of market pressure that reduces the state space of the entire market model. We show that the Markov chain model describes the market behaviour seen in a simulation extremely well. In a similar way to other perishable commodity markets like fish and electricity, we also provide a model for trading future contracts on the purchase and sale of computing power in this market. Using Markov Decision Processes we derive an optimal trading strategy. This work introduces a pioneer mathematical model for future global peer-to-peer Grid computing architectures like MaGoG (Middleware for activating the Global open Grid), where we have derived a global transition probability matrix that determines the behaviour of the market by summing up the contributions of different kinds of market participants.

DOI: 10.1145/1712605.1712633

Full text: PDF

[#][]

Relating Layered Queueing Networks and Process Algebra Models

Authors:

Mirco Tribastone (The University of Edinburgh)

Abstract:

This paper presents a process-algebraic interpretation of the Layered Queueing Network model. The semantics of layered multi-class servers, resource contention, multiplicity of threads and processors are mapped into a model described in the stochastic process algebra PEPA. The accuracy of the translation is validated through a case study of a distributed computer system and the numerical results are used to discuss the relative strengths and weaknesses of the different forms of analysis available in both approaches, i.e., simulation, mean-value analysis, and differential approximation.

DOI: 10.1145/1712605.1712634

Full Text: PDF

[#][]

Synthesising PEPA Nets from IODs for Performance Analysis

Authors:

Juliana Bowles (University of St-Andrews)
Leila Kloul (University of Versailles)

Abstract:

The object-based Unified Modeling Language (UML) is a popular medium for effective design of most systems. PEPA nets are a performance modelling technique which offers capabilities for capturing notions such as location, synchronisation and message passing, and are thus suited for performance modelling of mobile and distributed software. In this paper, we provide a new constructive approach that links both models by deriving a PEPA net which realises the same language (legal set of traces) as a given Interaction Overview Diagram (IOD) in UML2. We prove that the languages are strongly consistent (equivalent) by establishing the one-to-one correspondence between the traces of the models.

DOI: 10.1145/1712605.1712635

Full text: PDF

[#][]

A Page Fault Equation for Dynamic Heap Sizing

Authors:

Y. C. Tay (National University of Singapore)
X. R. Zong (Duke University)

Abstract:

For garbage-collected applications, dynamically-allocated objects are contained in a heap. Programmer productivity improves significantly if there is a garbage collector to automatically de-allocate objects that are no longer needed by the applications. However, there is a run-time performance overhead in garbage collection, and this cost is sensitive to heap size H: a smaller H will trigger more collection, but a large H can cause page faults, as when H exceeds the size M of main memory allocated to the application.

This paper presents a Heap Sizing Rule for how H should vary with M. The Rule can help an application trade less page faults for more garbage collection, thus reducing execution time. It is based on a heap-aware Page Fault Equation that models how the number of page faults depends on H and M. Experiments show that this rule outperforms the default policy used by JikesRVM's heap size manager. Specifically, the number of faults and the execution time are reduced for both static and dynamically changing M.

DOI: 10.1145/1712605.1712636

Full text: PDF

[#][]