ylfink@water.waterloo.edu (ylfink) (03/28/88)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
THEORY/VLSI SEMINAR
- Tuesday, March 29, 1988
Mr. Carl-Johan Seger, a graduate student of this
department, will speak on ``A Unified Framework for
Race Analysis of Asynchronous Networks''.
TIME: 3:30 PM
ROOM: MC 5097
ABSTRACT
The analysis problem for asynchronous circuits is
difficult because the behavior of a circuit depends
very much on the delays in its components. Classical
analysis methods are complicated and sometimes
incorrect. Furthermore, since many MOS circuits cannot
be described accurately by gate models, methods that
can be used also for switch-level models are needed.
We first discuss an abstract framework for describing
asynchronous circuits. This framework enables us to
derive a theory of asynchronous circuits that is
applicable to gate circuits as well as to the more
modern MOS circuits.
We then demonstrate how this framework can be used to
study the behavior of a circuit when the delays can be
arbitrary, but finite. For such a delay assumption, the
extended multiple winner (XMW) race model is developed.
For this model we show 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, in which
different choices of feedback lines can yield
completely different results. This latter result
settles the longstanding open problem when feedback
analysis is correct.
We conclude the talk by discussing the relation between
the XMW model and speed-independent circuits. We also
briefly discuss some less ``pessimistic'' race models:
the almost-equal-delay model and the bounded-delay
model.