Swift Transition Weight Analysis for Asynchronous Finite State Machines

J.-L. Yang, C.-F. Tai, and S.-M. Lin (Taiwan)


Markov chain, transition probability, asynchronous, self timed, optimization, burst-mode


We discuss the interpretation of the extracted information on transition-weight in a graphic-based transition diagram, then compare Markov chain k-step process and Monte Carlo simulation with the proposed method, common loop search (CLS), for the same transitional probability problems. The CLS method is to identify the most common loops in the transition graphic, which is very useful technique for optimization in various VLSI applications. In this paper, we use a set of asynchronous finite state machines to verify the CLS method. The test results show that our method runs about 4 times faster than the other two methods; and our CLS method derives the identical result pattern as the Markov chain process for more than 70% of the test cases. Although the results provided by CLS are not always 100% matching to the corresponding result of the state transition probability analysis, the approximation are good enough for optimization purposes.

Important Links:

Go Back