Publications
246 results found
Haggarty OJ, Knottenbelt WJ, Bradley JT, 2008, Distributed Response Time Analysis of GSPN Models with MapReduce, International Symposium on Performance Evaluation Computer and Telecommunication Systems, Publisher: SOC MODELING SIMULATION INT-SCS, Pages: 82-90
- Author Web Link
- Cite
- Citations: 1
Dingle NJ, Knottenbelt WJ, Wang L, 2008, SERVICE LEVEL AGREEMENT SPECIFICATION, COMPLIANCE PREDICTION AND MONITORING WITH PERFORMANCE TREES, European Simulation and Modelling Conference, Publisher: EUROSIS, Pages: 137-144
- Author Web Link
- Open Access Link
- Cite
- Citations: 3
Wang L, Dingle NJ, Knottenbelt WJ, 2008, Natural Language Specification of Performance Trees, 5th European Performance Engineering Workshop, Publisher: SPRINGER-VERLAG BERLIN, Pages: 141-151, ISSN: 0302-9743
- Author Web Link
- Cite
- Citations: 1
Brien DK, Dingle NJ, Knottenbelt WJ, et al., 2008, A Parallel and Distributed Analysis Pipeline for Performance Tree Evaluation, 5th International Conference on the Quantitative Evaluation of Systems, Publisher: IEEE COMPUTER SOC, Pages: 237-238
Lebrecht AS, Dingle NJ, Knottenbelt WJ, 2008, A response time distribution model for zoned RAID, 15th International Conference on Analytical and Stochastic Modelling Techniques and Applications, Publisher: SPRINGER-VERLAG BERLIN, Pages: 144-157, ISSN: 0302-9743
- Author Web Link
- Cite
- Citations: 4
Kulatunga H, Argent-Katwala A, Knottenbelt W, 2007, Cluster grid based response-time analysis module for the PIPE tool, Pages: 51-52
Generalized Stochastic Petri Nets (GSPNs) are a widely used high-level formalism used for modelling discrete-event systems. The Platform Independent Petri net Editor (PIPE) is an open source software project that allows creation, analysis and simulation of Petri Nets. This tool paper presents a PIPE module for response-time analysis of a Petri net's underlying Continuous Time Markov Chain (CTMC). Jobs are submitted via a web interface, from within PIPE or from a browser. The parallel computations are run using Grid Engine on a cluster hosted at Imperial College London. © 2007 IEEE.
Au-Yeung S, Knottenbelt W, Harrison P, 2007, Approximate Queueing Network Analysis of Patient Treatment Times, 2nd International Conference on Performance Evaluation Methodologies and Tools, Publisher: ICST, Pages: 1-12
We develop an approximate generating function analysis (AGFA) technique which approximates the Laplace transform of the probability density function of customer response time in networks of queues with class-based priorities. From the approximated Laplace transform, we derive the first two moments of customer response time. This technique is applied to a model of a large hospitalÆs Accident and Emergency department for which we obtain the mean and standard deviation of total patient service time. We experiment with different patient-handling priority schemes and compare the AGFA moments with the results from a discrete event simulation.
Bonet P, Puigjaner R, Lladó C, et al., 2007, PIPE v2.5: A Petri Net Tool for Performance Modelling, 23rd Latin American Conference on Informatics (CLEI 2007), Pages: 1-12
The Petri net modeling formalism allows for the convenient graphical visualization of system models, as well as the analysis of correctness and performance properties. Petri Nets theory has been widely used to implement a variety of modeling and evaluation tools. This paper surveys various of these tools and describes some recent extensions to a freely available and open-source platform-independent Petri net tool called PIPE. The extensions comprise: an increase in modeling power through the introduction of inhibitor arcs, a new analysis module for generating siphons and traps, some new interface features and various presentation improvements. We will illustrate system modeling and analysis with inhibitor arcs in a case study of a token ring network.
Kulatunga H, Argent-Katwala A, Knottenbelt W, 2007, Cluster Grid based Response-time Analysis Module for the PIPE Tool, QEST 2007, 4th International Conference on the Quantitative Evaluation of Systems, Publisher: IEEE Computer Society, Pages: 51-52
Generalized Stochastic Petri Nets (GSPNs) are a widely used high-level formalism used for modelling discrete-event systems. The Platform Independent Petri net Editor (PIPE) is an open source software project that allows creation, analysis and simulation of Petri Nets. This tool paper presents a PIPE module for response-time analysis of a Petri netÆs underlying Continuous Time Markov Chain (CTMC). Jobs are submitted via a web interface, from within PIPE or from a browser. The parallel computations are run using Grid Engine on a cluster hosted at Imperial College London.
Lebrecht A, Knottenbelt W, 2007, Response Time Approximations in Fork-Join Queues, 23rd Annual UK Performance Engineering Workshop (UKPEW), Pages: 1-8
Fork-join queueing networks model a network of parallel servers in which an arriving job splits into a number of subtasks that are serviced in parallel. Fork-join queues can be used to model disk arrays. A response time approximation of the fork-join queue is presented that attempts to comply with the additional constraints of modelling a disk array. This approximation is compared with existing analytical approximations of the fork-join queueing network.
Knottenbelt W, Bradley J, 2007, Tackling Large State Spaces in Performance Modelling, Formal Methods for Performance Evaluation, Publisher: Springer, Pages: 318-370
Stochastic performance models provide a powerful way of capturing and analysing the behaviour of complex concurrent systems. Traditionally, performance measures for these models are derived by generating and then analysing a (semi-)Markov chain corresponding to the modelÆs behaviour at the state-transition level. However, and especially when analysing industrial-scale systems, workstation memory and compute power is often overwhelmed by the sheer number of states. This chapter explores an array of techniques for analysing stochastic performance models with large state spaces. We concentrate on explicit techniques suitable for unstructured state spaces and show how memory and run time requirements can be reduced using a combination of probabilistic algorithms, disk-based solution techniques and communication-efficient parallelism based on hypergraph-partitioning. We apply these methods to different kinds of performance analysis, including steady-state and passage-time analysis, and demonstrate them on case study examples.
Au-Yeung SWM, Harrison PG, Knottenbelt WJ, 2007, Approximate queueing network analysis of patient treatment times
We develop an approximate generating function analysis (AGFA) technique which approximates the Laplace transform of the probability density function of customer response time in networks of queues with class-based priorities. From the approximated Laplace transform, we derive the first two moments of customer response time. This technique is applied to a model of a large hospital's Accident and Emergency department for which we obtain the mean and standard deviation of total patient service time. We experiment with different patient-handling priority schemes and compare the AGFA moments with the results from a discrete event simulation. Copyright 2007 ICST.
Suto T, Bradley JT, Knottenbelt WJ, 2007, Performance trees: Expressiveness and quantitative semantics, 4th International Conference on the Quantitative Evaluation of Systems, Publisher: IEEE COMPUTER SOC, Pages: 41-+
- Author Web Link
- Cite
- Citations: 8
Trifunovic A, Knottenbelt W, 2006, A General Graph Model for Representing Exact Communication Volume in Parallel Sparse Matrix-Vector Multiplication, 21st International Symposium on Computer and Information Sciences (ISCIS 2006), Pages: 813-824
In this paper, we present a new graph model of sparse matrix decomposition for parallel sparse matrixûvector multiplication. Our model differs from previous graph-based approaches in two main respects. Firstly, our model is based on edge colouring rather than vertex partitioning. Secondly, our model is able to correctly quantify and minimise the total communication volume of the parallel sparse matrixûvector multiplication while maintaining the computational load balance across the processors. We show that our graph edge colouring model is equivalent to the fine-grained hypergraph partitioning-based sparse matrix decomposition model. We conjecture that the existence of such a graph model should lead to faster serial and parallel sparse matrix decomposition heuristics and associated tools.
Suto T, Bradley JT, Knottenbelt WJ, 2006, Performance Trees: A New Approach to Quantitative Performance Specification, MASCOTS'06, 14th IEEE International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems, Publisher: IEEE Computer Society
Knottenbelt W, Harrison P, 2006, Quantiles of Sojourn Times, Computer System Performance Modeling in Perspective: A Tribute to the Work of Prof Kenneth C Sevcik, Publisher: Imperial College Press, Pages: 156-194
Fast response times and the satisfaction of response time quantile targets are important performance criteria for almost all transaction processing, computer-communication and other operational systems. However, response time quantiles tend to be difficult to obtain in stochastic models, even when the mean value of the response time has a relatively simple mathematical expression. Expressions have been obtained for the Laplace transform of the probability density function of sojourn times in many queueing models, including some complex single queues and networks of simple queues. These can sometimes be inverted analytically, giving an explicit expression for the density as a function of time, but more often numerical inversion is necessary. More generally, interesting sojourn times can be expressed in terms of passage times between states in continuous time Markov and semi-Markov chains. Quantiles for these can be computed in principle but can require extensive computational resources, both in terms of processing time and memory. Consequently, until recently, only trivial problems could be solved by this direct method. With recent technological advances, including the widespread use of clusters of workstations and limited availability of parallel supercomputers, very large Markov and semi-Markov chains can be solved directly for passage time densities, allowing many realistic systems to be investigated. This paper reviews the various approaches taken to compute sojourn time quantiles in systems ranging from simple queues to arbitrary semi-Markov chains, by the authors and others, over the past twenty years and more.\r\n
Suto T, Bradley J, Knottenbelt W, 2006, Performance Trees: A New Approach to Quantitative Performance Specification, MASCOTS'06, 14th IEEE International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems, Publisher: IEEE Computer Society
Bradley J, Dingle N, Harder U, et al., 2006, Response Time Densities and Quantiles in Large Markov and Semi-Markov Models, Performance Evaluation of Parallel, Distributed and Emergent Systems, Publisher: Nova Science Publishers, Inc, Pages: 3-41, ISBN: 1-59454-817-X
Response time quantiles reflect user-perceived quality of service more accurately than mean or average response time measures. Consequently, on-line transaction processing benchmarks, telecommunications Service Level Agreements and emergency services legislation all feature stringent 90th percentile response time targets. This chapter describes a range of techniques for extracting response time densities and quantiles from large-scale Markov and semi-Markov models of real-life systems. We describe a method for the computation of response time densities or cumulative distribution functions which centres on the calculation and subsequent numerical inversion of their Laplace transforms. This can be applied to both Markov and semi-Markov models. We also review the use of uniformization to calculate such measures more efficiently in purely Markovian models. We demonstrate these techniques by using them to generate response time quantiles in a semi-Markov model of a high-availability web-server. We show how these techniques can be used to analyse models with state spaces of 10^7 states and above.
Au-Yeung SWM, Harrison PG, Knottenbelt WJ, 2006, A queueing network model of patient flow in an accident and emergency department, 20th European Simulation and Modelling Conference (ESM 2006), Publisher: EUROSIS, Pages: 60-+
- Author Web Link
- Cite
- Citations: 13
Bradley JT, de Jager DV, Knottenbelt WJ, et al., 2005, Hypergraph Partitioning for Faster Parallel PageRank Computation, EPEW'05, Proceedings of the 2nd European Performance Evaluation Workshop, Publisher: Springer-Verlag, Pages: 155-171, ISSN: 0302-9743
The PageRank algorithm is used by search engines such as Google to order web pages. It uses an iterative numerical method to compute the maximal eigenvector of a transition matrix derived from the web's hyperlink structure and a user-centred model of web-surfing behaviour. As the web has expanded and as demand for user-tailored web page ordering metrics has grown, scalable parallel computation of PageRank has become a focus of considerable research effort. In this paper, we seek a scalable problem decomposition for parallel PageRank computation, through the use of state-of-the-art hypergraph-based partitioning schemes. These have not been previously applied in this context. We consider both one and two-dimensional hypergraph decomposition models. Exploiting the recent availability of the Parkway 2.1 parallel hypergraph partitioner, we present empirical results on a gigabit PC cluster for three publicly available web graphs. Our results show that hypergraph-based partitioning substantially reduces communication volume over conventional partitioning schemes (by up to three orders of magnitude), while still maintaining computational load balance. They also show a halving of the per-iteration runtime cost when compared to the most effective alternative approach used to date.
Harder U, Johnson MW, Bradley JT, et al., 2005, Observing internet worm and virus attacks with a small network telescope, Proceedings of PASM 2005 proceedings of the 2nd workshop on practical applications of stochastic modelling, Publisher: Elsevier, Pages: 47-59, ISSN: 1571-0661
, 2005, Proceedings of PASM 2004, 1st International Workshop on Practical Applications of Stochastic Modelling, Publisher: Elsevier
Recent years have seen not only significant theoretical advances in stochastic modelling and associated formalisms but also the increasing availability of high-powered computing facilities in academia and industry alike. The workshop on Practical Applications of Stochastic Modelling (PASM) was created out of a desire to harness these developments by encouraging the application of stochastic modelling formalisms to large-scale real-world systems.\r\n\r\nThe first PASM workshop was held in the Royal Society, London, in September 2004 and we were very pleased to be able to showcase some excellent examples of how formalisms such as stochastic Petri nets, stochastic process algebras, queueing networks and SANs can be used to tackle realistic and diverse stochastic modelling problems.\r\n\r\nThe contributions presented here covered examples of practical and topical interest such as peer-to-peer (P2P) file sharing networks, security protocols, electronic voting systems, parallel programming environments and RAID arrays.\r\n\r\nIt takes a great deal of effort and imagination to tackle the problems inherent in complex systems. We would like to thank everyone who submitted a paper - accepted or not - for taking on this challenge and for helping to contribute to a vibrant workshop. We would also like to thank Joost-Pieter Katoen for an excellent invited presentation on stochastic behaviour of agent negtiation in autonomous wireless devices and Michael Mislove of ENTCS for help and advice in preparing this volume.\r\n\r\nAlso due recognition are the programme committee who put in a stalwart effort to ensure a high quality refereeing process (every submission received at least four reviews):\r\n\r\n- Marco Bernardo\r\n- Mario Bravetti\r\n- Gianfranco Ciardo\r\n- Tod Courtney\r\n- David Daly\r\n- Dan Deavours\r\n- Tony Field\r\n- Stephen Gilmore\r\n- Roberto Gorrieri\r\n- Boudewijn Haverkort\r\n- Graham Horton\r\n- Pieter Kritzinger\r\n- Gethin Norman\r\n- Mohamed Ould-Khaoua\r\n
, 2005, Proceedings of the First International Workshop on Practical Applications of Stochastic Modelling, PASM 2004, London, UK, September 4, 2004, Publisher: Elsevier
Thomas N, Bradley JT, Knottenbelt WJ, 2004, Stochastic Analysis of Scheduling Strategies in a Grid-based Resource Model, Publisher: IEE, Pages: 232-239
In this paper, we consider a model inspired by a scenario found in Grid-based scheduling systems. Scheduling is performed remotely without access to up-to-date resource availability and usage information. We model this system as a collection of queues where servers break down and are subsequently repaired. There is a delay before the scheduler learns of failures, as such requests may continue to arrive into a resource queue for some time after active service has ceased. We consider the queues to be persistent under failure, however these queues have finite capacity; therefore there is the possibility that queues become full, causing job-loss. We use stochastic process algebra and stochastic probes to analyse this model to find steady state measures and passage time distributions. The effect of the duration of any delay on information propagation on the system response time and job loss is investigated and evaluated numerically.
, 2004, Practical Applications of Stochastic Modelling 2004, PASM 2004, Practical Applications of Stochastic Modelling, Imperial College London
Recent years have seen not only significant theoretical advances in stochastic modelling and associated formalisms but also the increasing availability of high-powered computing facilities in academia and industry alike. The workshop on Practical Applications of Stochastic Modelling (PASM) was created out of a desire to harness these developments by encouraging the application of stochastic modelling formalisms to large-scale real-world systems.\r\n\r\nWe are, therefore, pleased to showcase in the very first workshop proceedings some excellent examples of how formalisms such as stochastic Petri nets, stochastic process algebras, queueing networks and SANs can be applied to diverse topical systems of practical interest such as peer-to-peer (P2P) file sharing networks, security protocols,electronic voting systems, parallel programming environments and RAID arrays.\r\n\r\nIt takes a great deal of effort and imagination to tackle the problems inherent in complex systems. We would like to thank everyone who submitted a paper - accepted or not - for taking on this challenge and for helping to contribute to a vibrant workshop.\r\n\r\nWe would also like to thank our invited speaker, Joost-Pieter Katoen, not to mention the programme committee who put in a stalwart effort to ensure a high quality refereeing process (with every submission receiving at least four reviews):\r\n\r\n * Marco Bernardo\r\n * Mario Bravetti\r\n * Gianfranco Ciardo\r\n * Tod Courtney\r\n * David Daly\r\n * Dan Deavours\r\n * Tony Field\r\n * Stephen Gilmore\r\n * Roberto Gorrieri\r\n * Boudewijn Haverkort\r\n * Graham Horton\r\n * Pieter Kritzinger\r\n * Gethin Norman\r\n * Mohamed Ould-Khaoua\r\n * Dave Parker\r\n * Nigel Thomas
, 2004, Proceedings of PASM 2004, the 1st International Workshop on Practical Applications of Stochastic Modelling
Dingle N, Harrison P, Knottenbelt W, 2004, Uniformization and Hypergraph Partitioning for the Distributed Computation of Response Time Densities in Very Large Markov Models, Journal of Parallel and Distributed Computing, Vol: 64, Pages: 908-920
Dingle N, Harrison P, Knottenbelt W, 2004, Uniformization and Hypergraph Partitioning for the Distributed Computation of Response Time Densities in Very Large Markov Models, Journal of Parallel and Distributed Computing, Vol: 64, Pages: 908-920
Bradley JT, Dingle NJ, Knottenbelt WJ, et al., 2004, Hypergraph-based Parallel Computation of Passage Time Densities in Large Semi-Markov Models, Linear Algebra and Its Applications, Vol: 386, Pages: 311-334
Passage time densities and quantiles are important performance and quality of service metrics, but their numerical derivation is, in general, computationally expensive. We present an iterative algorithm for the calculation of passage time densities in semi-Markov models, along with a theoretical analysis and empirical measurement of its convergence behaviour. In order to implement the algorithm efficiently in parallel, we use hypergraph partitioning to minimise communication between processors and to balance workloads. This enables the analysis of models with very large state spaces which could not be held within the memory of a single machine. We produce passage time densities and quantiles for very large semi-Markov models with over 15 million states and validate the results against simulation.
Trifunovic A, Knottenbelt WJ, 2004, A parallel algorithm for multilevel k-way hypergraph partitioning, 3rd International Symposium on Parallel and Distributed Computing (ISPDC 2004), Publisher: IEEE Computer Soc, Pages: 114-121
This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.