Hypergraph-based Parallel Computation of Passage Time Densities in Large Semi-Markov Models
File(s)
Accepted version
Author(s)
Bradley, JT
Dingle, NJ
Knottenbelt, WJ
Wilson, HJ
Type
Journal Article
Abstract
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.
Date Issued
2004-07
Citation
Linear Algebra and Its Applications, 2004, 386, pp.311-334
ISSN
0024-3795
Publisher
Elsevier
Start Page
311
End Page
334
Journal / Book Title
Linear Algebra and Its Applications
Volume
386
Copyright Statement
© 2004 Elsevier Inc. All rights reserved. NOTICE: this is the author’s version of a work that was accepted for publication in Linear Algebra and Its Applications. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in LINEAR ALGEBRA AND ITS APPLICATIONS, VOL:386, (2004) DOI:10.1016/j.laa.2003.12.018
Identifier
http://pubs.doc.ic.ac.uk/semi-markov-laa/
Source Volume Number
386
Publication Status
Published