Imperial College London

ProfessorWilliamKnottenbelt

Faculty of EngineeringDepartment of Computing

Professor of Applied Quantitative Analysis
 
 
 
//

Contact

 

+44 (0)20 7594 8331w.knottenbelt Website

 
 
//

Location

 

E363ACE ExtensionSouth Kensington Campus

//

Summary

 

Publications

Publication Type
Year
to

185 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

Conference paper

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.

Conference paper

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

Conference paper

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

Book

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

Conference paper

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

Conference paper

Barnham K, Connolly J, Rohr C, 2003, Preface, ISSN: 0268-1242

Conference paper

Bradley J, Dingle N, Harrison P, Knottenbelt Wet 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

Conference paper

Bradley JT, Dingle NJ, Harrison PG, Knottenbelt WJet 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.

Conference paper

Bradley JT, Dingle NJ, Knottenbelt WJ, Wilson HJet 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

Conference paper

Bradley JT, Dingle NJ, Harrison PG, Knottenbelt WJet 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

Conference paper

Bradley JT, Dingle NJ, Gilmore ST, Knottenbelt WJet 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.

Conference paper

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

Conference paper

Bradley JT, Dingle NJ, Harrison PG, Knottenbelt WJet 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

Conference paper

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

Conference paper

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.

Conference paper

Bradley JT, Dingle NJ, Knottenbelt WJ, Wilson HJet 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

Conference paper

Bradley JT, Dingle NJ, Gilmore ST, Knottenbelt WJet 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

Conference paper

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

Conference paper

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

Conference paper

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.

Conference paper

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

Conference paper

Harrison PG, Knottenbelt WJ, 2002, Passage time distributions in large Markov chains, Performance Evaluation Review, Vol: 30, Pages: 77-85, ISSN: 0163-5999

Journal article

Bradley JT, Knottenbelt WJ, Harrison PG, Vowden CJet 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

Conference paper

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

Conference paper

Bradley JT, Knottenbelt WJ, Harrison PG, Vowden CJet 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

Conference paper

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

Conference paper

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

Journal article

Knottenbelt W, Harrison P, Mestern M, Kritzinger Pet 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.

Conference paper

Harrison PG, Knottenbelt WJ, 2000, Passage Time Distributions in Large Markov Chains, IFIP Working Group 7.3 & University of Central Florida Symposium on Advanced Performance Modeling (SAPM), Orlando, Florida

Conference paper

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.

Request URL: http://wlsprd.imperial.ac.uk:80/respub/WEB-INF/jsp/search-html.jsp Request URI: /respub/WEB-INF/jsp/search-html.jsp Query String: id=00159431&limit=30&person=true&page=6&respub-action=search.html