| In some applications, well-designed asynchronous systems can dramatically outperform their synchronous counterparts in terms of average speed. One recent example is the Revolving Asynchronous Intel Pentium Processor Instruction Decoder (RAPPID) which achieves 3 times higher average throughput than its comparable synchronous counterpart [103, 115]. Such systems must be highly concurrent and optimized for their average-case performance. Unfortunately, analyzing the performance of asynchronous systems is challenging, and there is an extreme lack of supporting CAD tools. This thesis presents two categories of performance analysis methodologies. The methods in the first category compute the theoretical (or exact) values of average performance metrics by modeling systems using Markov chains, and subsequently solving the models using Markovian analysis. The thesis developed several novel methods to attack the state explosion problem associated with Markovian analysis of large systems. The methods in the second category compute lower and upper bounds on performance metrics of systems that are modeled using stochastic timed Petri nets. The bounds are derived using finite net executions, and are evaluated using statistical methods. These methods do not require a state-level analysis, and thus can handle systems of very large size. As an example, a Petri net model of RAPPID with over 900 transitions and 500 places has been successfully analyzed. The resulting bounds are typically much sharper than using any other known method, and are in fact very close to the theoretical values. Moreover, the theory behind the bounding techniques provides a foundation for performance optimization of complex asynchronous circuits and systems. As one of their distinct features, the techniques in both categories are developed to handle arbitrarily distributed delays in order to increase the modeling power. All these techniques have been extensively tested and each represents the current state-of-the-art in its own respect. Due to the generality of the problems addressed, the potential applications of the work presented in this thesis are well beyond asynchronous circuits and systems. For instance, they are directly applicable to a wide class of discrete event systems such as embedded systems, database systems and security-oriented networks. |
