Accelerating Markovian analysis of asynchronous systems using string-based state compression
作者： Aiguo Xie , P.A. Beerel
DOI: 10.1109/ASYNC.1998.666510
关键词:
摘要: This paper presents a methodology to speed up the stationary analysis of large Markov chains that model asynchronous systems. Instead directly working on original chain, we propose analyze smaller chain obtained via novel technique called string-based state compression. Once is solved, solution process expansion. The method especially powerful when has small feedback vertex set, which happens often an Experimental results show can yield reductions more than order magnitude in run time and facilitate larger systems possible using traditional techniques.
sci-hub.se 参考文章(20)
H. Hulgaard, T. Amon, S.M. Burns, G. Borriello, Timing analysis of timed event graphs with bounded delays using algebraic techniques conference on decision and control. ,vol. 1, pp. 959- 960 ,(1994) , 10.1109/CDC.1994.410932
Peter A. Beerel, Vida Vakilotojar, Ayoob E. Dooply, Kenneth Y. Yun, Julio Arceo, A Low-Control-Overhead Asynchronous Differential Equation Solver european solid state circuits conference. pp. 352- 355 ,(1996)
Sungju Park, S.B. Akers, A Graph Theoretic Approach to Partial Scan Design by K-Cycle Elimination international test conference. pp. 303- 311 ,(1992) , 10.1109/TEST.1992.527837
K.Y. Yun, R.P. Donohue, Pausible clocking: a first step toward heterogeneous systems international conference on computer design. pp. 118- 123 ,(1996) , 10.1109/ICCD.1996.563543
Gerardo Rubino, None, ON WEAK LUMPABILITY IN MARKOV CHAINS Journal of Applied Probability. ,vol. 26, pp. 446- 457 ,(1989) , 10.1017/S0021900200038055
Gerardo Rubino, Bruno Sericola, Sojourn times in finite Markov processes Journal of Applied Probability. ,vol. 26, pp. 744- 756 ,(1989) , 10.2307/3214379
G. Smith, R. Walford, The identification of a minimal feedback vertex set of a directed graph IEEE Transactions on Circuits and Systems. ,vol. 22, pp. 9- 15 ,(1975) , 10.1109/TCS.1975.1083961
G. W. Stewart, Simultaneous iteration for computing invariant subspaces of non-Hermitian matrices Numerische Mathematik. ,vol. 25, pp. 123- 136 ,(1976) , 10.1007/BF01462265
J. Teich, L. Thiele, S. Sriram, M. Martin, Performance analysis and optimization of mixed asynchronous synchronous systems IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 16, pp. 473- 484 ,(1997) , 10.1109/43.631210
Mark R. Greenstreet, Kenneth Steiglitz, Bubbles can make self-timed pipelines fast Journal of Vlsi Signal Processing Systems for Signal Image and Video Technology. ,vol. 2, pp. 139- 148 ,(1990) , 10.1007/BF00935211