Imperial College London
Alternate

ProfessorWilliamKnottenbelt

Faculty of Engineering, Department of Computing

Professor of Applied Quantitative Analysis
 
 
 
//

Contact

 

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

 
 
//

Location

 

E363ACE ExtensionSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@inproceedings{Knottenbelt:2000:10.1016/S0166-5316(99)00061-9,
author = {Knottenbelt, W and Harrison, P and Mestern, M and Kritzinger, P},
doi = {10.1016/S0166-5316(99)00061-9},
pages = {127--148},
publisher = {Elsevier},
title = {A Probabilistic Dynamic Technique for the Distributed Generation of Very Large State Spaces},
url = {http://dx.doi.org/10.1016/S0166-5316(99)00061-9},
year = {2000}
}
Download

RIS format (EndNote, RefMan)

TY  - CPAPER
AB  - 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.
AU  - Knottenbelt,W
AU  - Harrison,P
AU  - Mestern,M
AU  - Kritzinger,P
DO  - 10.1016/S0166-5316(99)00061-9
EP  - 148
PB  - Elsevier
PY  - 2000///
SN  - 0166-5316
SP  - 127
TI  - A Probabilistic Dynamic Technique for the Distributed Generation of Very Large State Spaces
UR  - http://dx.doi.org/10.1016/S0166-5316(99)00061-9
UR  - http://hdl.handle.net/10044/1/795
ER  -
Download