Publications
246 results found
Bradley JT, Knottenbelt WJ, 2004, The ipc/HYDRA tool chain for the analysis of PEPA models, Los Alamitos, 1st international conference on the quantitative evaluation of systems (QEST 2004), Enschede, Netherlands, Publisher: IEEE Computer Soc, Pages: 334-335
Trifunovic A, Knottenbelt WJ, 2004, Towards a parallel disk-based algorithm for multilevel k-way hypergraph partitioning, Proceedings of 18th international parallel and distributed processing symposium (IPDPS'04), 2004, Pages: 236-242
Thomas N, Bradley JT, Knottenbelt WJ, 2004, Semi-blind scheduling in a finite capacity system, Proceedings of 20th UK performance engineering workshop (UKPEW 2004), Bradford, UK, July 2004, Pages: 38-47
Trifunovic A, Knottenbelt WJ, 2004, Towards a parallel disk-based algorithm for multilevel k-way hypergraph partitioning (Available on CD-ROM), Proceedings of 5th workshop on parallel and distributed scientific and engineering computing, Santa Fe, New Mexico, USA, April 2004, Pages: 1-8
Bradley JT, Knottenbelt WJ, 2004, Proceedings of the First International Workshop on Practical Applications of Stochastic Modelling (PASM 2004). Electronic notes in theoretical computer science. Vol.128, London, Publisher: Elsevier
Trifunovic A, Knottenbelt WJ, 2004, Parkway 2.0: a parallel multilevel hypergraph partitioning tool, Berlin, Computer and information sciences - ISCIS 2004: 19th international symposium, Kemer-Antalya, Turkey, 27 - 29 October 2004, Publisher: Springer-Verlag, Pages: 789-800
Au-Yeung S, Dingle N, Knottenbelt W, 2004, Efficient approximation of response time densities and quantiles in stochastic models, 4th international workshop on software and performance, WOSP2004, Publisher: ACM, Pages: 151-155
Bradley JT, Knottenbelt WJ, 2004, The ipc/HYDRA tool chain for the analysis of PEPA models, Los Alamitos, 1st International Conference on the Quantitative Evaluation of Systems (QEST 2004), Enschede, Netherlands, Publisher: IEEE Computer Soc, Pages: 334-335
PEPA is a popular stochastic process algebra and a powerful formalism for describing performance models of communication and computer systems. We augment the current state-of-the-art in the analysis of PEPA models by presenting a tool set that can not only perform steady-state and transient analysis, but also response time analysis. Response time densities and quantiles are important performance metrics which are used to specify service level agreements (SLAs) and benchmarks. HYDRA is a tool specialising in response time analysis of large Markov systems based on stochastic Petri nets. By using the Imperial PEPA compiler (ipc), we can generate a HYDRA model from a PEPA model and obtain steady-state, transient and response time measures based on the original PEPAdescription.
Bradley J, Dingle N, Harrison P, et al., 2003, Distributed Computation of Passage Time Quantiles and Transient State Distributions in Large Semi-Markov Models, PMEO-PDS 2003, International Workshop on Performance Modeling, Evaluation, and Optimization of Parallel and Distributed Systems, Publisher: IEEE Computer Society Press
Bradley JT, Dingle NJ, Harrison PG, et al., 2003, Distributed computation of transient state distributions and passage time quantiles in large semi-Markov models, PMEO-PDS 2003, International Workshop on Performance Modeling, Evaluation, and Optimization of Parallel and Distributed Systems, Publisher: IEEE, Pages: 281-837, ISSN: 1530-2075
Semi-Markov processes (SMPs) are expressive tools for modelling parallel and distributed systems; they are a generalisation of Markov processes that allow for arbitrarily distributed sojourn times. This paper presents an iterative technique for transient and passage time analysis of large structurally unrestricted semi-Markov processes. Our method is based on the calculation and subsequent numerical inversion of Laplace transforms and is amenable to a highly scalable distributed implementation. Results for a distributed voting system model with up to 1.1 million states are presented and validated against simulation. (C) 2006 Elsevier B.V. All rights reserved.
Bradley JT, Dingle NJ, Harrison PG, et al., 2003, Performance queries on semi-markov stochastic petri nets with an extended continuous stochastic logic, Los Alamitos, 10th international workshop on Petri Nets and performance models (PNPM 2003), Urbana, Illinois, Publisher: IEEE Computer Soc, Pages: 62-71
Bradley JT, Dingle NJ, Gilmore ST, et al., 2003, Derivation of passage-time densities in PEPA models using ipc: the imperial PEPA compiler, Los Alamitos, 11th IEEE/ACM international symposium on modeling, analysis and simulation of computer telecommunications systems (MASCOTS 2003), Orlando, Florida, Publisher: IEEE Computer Soc, Pages: 344-351
We present a technique for defining and extracting passage-time densities from high-level stochastic process algebra models. Our high-level formalism is PEPA, a popular Markovian process algebra for expressing compositional performance models. We introduce ipc, a tool which can process PEPA-specified passage-time densities and models by compiling the PEPA model and passage specification into the DNAmaca formalism. DNAmaca is an established modelling language for the low-level specification of very large Markov and semi-Markov chains. We provide performance results for ipc/DNAmaca and comparisons with another tool which supports PEPA, PRISM. Finally, we generate passage-time densities and quantiles for a case study of a high-availability web server.
Bradley JT, Dingle NJ, Gilmore ST, et al., 2003, Extracting passage times from PEPA models with the HYDRA tool: a case study, UKPEW'03, proceedings of 19th annual UK performance engineering workshop, University of Warwick, July 2003, Pages: 79-90
Bradley JT, Dingle NJ, Knottenbelt WJ, et al., 2003, Hypergraph-based parallel computation of passage time densities in large semi-Markov models, NSMC'03, proceedings of the 4th international workshop on numerical solutions of Markov chains, University of Illinois at Urbana-Champaign, September 2003, Pages: 99-120
Bradley JT, Dingle NJ, Knottenbelt WJ, 2003, Exact aggregation strategies for semi-Markov performance models, San Diego CA, International Symposium on Performance Evaluation of Computer and Telecommunication Systems, Montreal, Canada, 2003, Publisher: SCS, Pages: 755-762
Semi-Markov modelling paradigms are more expressive than their Markovian counterparts but are equally vulnerable to the state space explosion problem. This paper addresses this issue by presenting an exact state-by-state aggregation algorithm for semi-Markov models. Empirical evidence shows that the computational complexity of our method depends critically on the order in which the states are aggregated. We investigate different state-ordering strategies and find one that aggregates a large proportion (circa 75%) of our example state spaces at minimal cost. This leaves a significantly smaller model which can then be analysed for performance-related quantities such as passage-time quantiles. We demonstrate our technique on several examples, including a 541,280 state model which is reduced to 173,101 states.
Bradley JT, Dingle NJ, Knottenbelt WJ, et al., 2003, Hypergraph-based parallel computation of passage time densities in large semi-Markov models, NSMC'03, proceedings of the 4th international workshop on numerical solutions of Markov chains, University of Illinois at Urbana-Champaign, September 2003, Pages: 99-120
Bradley JT, Dingle NJ, Knottenbelt WJ, 2003, Exact aggregation strategies for semi-Markov performance models, San Diego CA, International symposium on performance evaluation of computer and telecommunication systems, 2003, Publisher: SCS, Pages: 755-762
Bradley JT, Dingle NJ, Harrison PG, et al., 2003, Performance queries on semi-markov stochastic petri nets with an extended continuous stochastic logic, Los Alamitos, 10th international workshop on Petri Nets and performance models (PNPM 2003), Publisher: IEEE Computer Society, Pages: 62-71
Dingle NJ, Harrison PG, Knottenbelt WJ, 2003, HYDRA: hypergraph-based distributed response-time analyser, Athens, International conference on parallel and distributed processing techniques and applications, Las Vegas, Nevada, 2003, Publisher: C S R e A Press, Pages: 215-219
Dingle NJ, Harrison PG, Knottenbelt WJ, 2003, HYDRA: hypergraph-based distributed response-time analyser, Athens, International conference on parallel and distributed processing techniques and applications, Las Vegas, Nevada, 2003, Publisher: C S R e A Press, Pages: 215-219
Dingle N, Harrison P, Knottenbelt W, 2002, Response Time Densities in Generalised Stochastic Petri Net Models., 3rd International Workshop on Software and Performance (WOSP 2002), Publisher: ACM, Pages: 46-54
Generalised Stochastic Petri nets (GSPNs) have been widely used to analyse the performance of hardware and software systems. This paper presents a novel technique for the numerical determination of response time densities in GSPN models. The technique places no structural restrictions on the models that can be analysed, and allows for the high-level specification of multiple source and destination markings, including any combination of tangible and vanishing markings. The technique is implemented using a scalable parallel Laplace transform inverter that employs a modified Laguerre inversion technique. We present numerical results, including a study of the full distribution of end-to-end response time in a GSPN model of the Courier communication protocol software. The numerical results are validated against simulation.
Dingle N, Harrison P, Knottenbelt W, 2002, Response time densities in generalised stochastic petri net models, 3rd International Workshop on Software and Performance (WOSP 2002), Publisher: ACM, Pages: 46-54
Harrison PG, Knottenbelt WJ, 2002, Passage time distributions in large Markov chains, Performance Evaluation Review, Vol: 30, Pages: 77-85, ISSN: 0163-5999
Bradley JT, Knottenbelt WJ, Harrison PG, et al., 2002, Transient and passage-time distributions in semi-Markov processes, UKPEW'02: proceedings of 18th annual UK performance engineering workshop, Glasgow, July 2002, Pages: 153-162
Bradley JT, Knottenbelt WJ, Harrison PG, et al., 2002, Transient and passage-time distributions in semi-Markov processes, UKPEW'02: proceedings of 18th annual UK performance engineering workshop, Glasgow, July 2002, Pages: 153-162
Dingle NJ, Knottenbelt WJ, 2002, Distributed solution of large markov models using asynchronous iterations and graph partitioning, Proceedings of 18th UK performance engineering workshop (UKPEW 2002), Pages: 27-34
Dingle N, Harrison P, Knottenbelt W, 2002, Response time densities in generalised stochastic petri net models, 3rd international workshop on software and performance, Rome, 2002, Publisher: ACM, Pages: 46-54
Davies I, Knottenbelt WJ, Kritzinger PS, 2002, Symbolic methods for the state space exploration of GSPN models, Berlin, 12th international conference on modelling techniques and tools for computer performance evaluation (TOOLS 2002), London, England, Publisher: Springer-Verlag, Pages: 188-199
Knottenbelt WJ, Zertal S, Harrison PG, 2001, Performance analysis of three implementation strategies for distributed lock management, IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES, Vol: 148, Pages: 176-187, ISSN: 1350-2387
- Author Web Link
- Open Access Link
- Cite
- Citations: 2
Knottenbelt W, Harrison P, Mestern M, et al., 2000, A Probabilistic Dynamic Technique for the Distributed Generation of Very Large State Spaces, Publisher: Elsevier, Pages: 127-148, ISSN: 0166-5316
Conventional methods for state space exploration are limited to the analysis of small systems because they suffer from excessive memory and computational requirements. We have developed a new dynamic probabilistic state exploration algorithm which addresses this problem for general, structurally unrestricted state spaces.\r\n\r\nOur method has a low state omission probability and low memory usage that is independent of the length of the state vector. In addition, the algorithm can be easily parallelised. This combination of probability and parallelism enables us to rapidly explore state spaces that are an order of magnitude larger than those obtainable using conventional exhaustive techniques.\r\n\r\nWe derive a performance model of this new algorithm in order to quantify its benefits in terms of distributed run-time, speedup and efficiency. We implement our technique on a distributed-memory parallel computer and demonstrate results which compare favourably with the performance model. Finally, we discuss suitable choices for the three hash functions upon which our algorithm is based.
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.