Browse Theses

This thesis addresses the problem of analyzing asynchronous sequential circuits. Our first contribution is a unified mathematical framework which enables us to derive a theory applicable to gate circuits, as well as to the more modern MOS circuits. We then study the behavior of asynchronous circuits using the abstract framework together with several different delay and race models.

The first race model developed is the "extended multiple winner" (XMW) model in which each logic component has an arbitrary finite delay. For this model we prove that the set of state variables used to analyze a circuit can be reduced to a minimal set of feedback variables, without any loss of state transition and hazard information. (This contrasts sharply with previously known models.) Secondly, we prove that ternary simulation (which is very efficient) yields the same results as the XMW analysis (which is intractable).

The XMW model is closely related to delay-independent circuits, i.e. to circuits that operate correctly, no matter what the component delays are. Using the XMW theory, it is shown that the class of delay-independent circuits is quite small, and that many common sequential behaviors cannot be realized delay-independently. The main reason for this is the unrealistic assumption that component delays can be arbitrary.

To overcome the limitations of the XMW model, we derive two race models that are more realistic. The "almost-equal-delay" model makes the somewhat idealized assumption that all component delays are approximately equal. The "extended bounded-delay" model assumes that each delay is bounded by a lower and an upper limit. These intuitive notions are formalized, and practical algorithms are developed for race analyses using these models.

Finally, we derive a number of complexity results for the race analysis problem using different delay models.