BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CSL-TR-94-644
       ENTRY:: December 21, 1994
ORGANIZATION:: Stanford University, Computer Systems Laboratory
       TITLE:: Synthesis of Asynchronous Controllers for Heterogeneous
               Systems
        TYPE:: Thesis
        TYPE:: Technical Report
      AUTHOR:: Yun, Kenneth Yi
        DATE:: August 1994
       PAGES:: 142
    ABSTRACT:: There are two synchronization mechanisms used in digital
               systems: synchronous and asynchronous. Synchronous or
               asynchronous refers to whether the system events occur in
               lock-step based on a clock or not. Today's system components
               typically employ the synchronous paradigm primarily because
               of the availability of the rich set of design tools and
               algorithms and, perhaps, because of the designers' perception
               of ``ease of design'' and the lack of alternatives. Even so,
               the interfaces among the system components do not strictly
               adhere to the synchronous paradigm because of the cost
               benefit of mixing modules operating at different clock rates
               and modules with asynchronous interfaces. This thesis
               addresses the problem of how to synthesize controllers
               operating in heterogeneous systems - systems with components
               employing different synchronization mechanisms.

               We introduce a new design style called extended-burst-mode.
               The extended-burst-mode design style covers a wide spectrum
               of sequential circuits ranging from delay-insensitive to
               synchronous. We can synthesize multiple-input change
               asynchronous finite state machines, and many circuits that
               fall in the gray area between synchronous and asynchronous
               which are difficult or impossible to synthesize automatically
               using existing methods. Our implementation of
               extended-burst-mode machines uses standard combinational
               logic, generates low-latency outputs and guarantees freedom
               from hazards at the gate level.

               We present a complete set of automated sequential synthesis
               algorithms: hazard-free state assignment, hazard-free state
               minimization, and critical-race-free state encoding. We also
               describe two radically different hazard-free combinational
               synthesis methods: two-level sums-of-products implementation
               and multiplexor trees implementation. Existing theories for
               hazard-free combinational synthesis are extended to handle
               non-monotonic input changes. A set of requirements for
               freedom from logic hazards is presented for each
               combinational synthesis method. Experimental data from a
               large set of examples are presented and compared to competing
               methods, whenever possible.

               To demonstrate the effectiveness of the design style and the
               synthesis tool, the design of a commercial-scale SCSI
               controller data path is presented. This design is
               functionally compatible with an existing high performance
               commercial chip and meets the ANSI SCSI-2 standard.
       NOTES:: [Adminitrivia V1/Prg/19941221]
         END:: STAN//CSL-TR-94-644