Solution of large sparse linear fixed-point problems lies at the heart of many important performance analysis calculations. These calculations include steady-state, transient and passage-time computations in discrete-time Markov chains, continuous-time Markov chains and semi-Markov chains. In recent years, much work has been done to extend the application of asynchronous iterative solution methods to different contexts. This work has been motivated by the potential for faster solution, more efficient use of the communication channel and access to memory, and simplification of task management and programming. In this paper, we show how the key performance metrics mentioned above can be transformed into problems which can be solved using asynchronous iterative methods with guaranteed convergence - using the full breadth of Chazan and Miranker's classes of asynchronous iterations. We introduce the application of asynchronous iterative solution methods within this context by applying several algorithm variants to steady-state analysis of a GSPN model of a flexible manufacturing system. We show that for varying numbers of processors and different problem sizes one of these algorithm variants offers consistently better wall time until convergence, a consistently better communication profile, and often requires fewer update iterations than a standard parallel Jacobi algorithm, seemingly benefiting from a form of Gauss-Seidel effect.
Submitted to PEJ 3 March 2009. Accepted 20 August 2010.
The associated presentation was given on 3 June 2011 as part of the Numerical Analysis and Scientific Computing Seminar series, School of Mathematics/MIMS, The University of Manchester.
Information from pubs.doc.ic.ac.uk/asynchronous-performance-methods.