An important scientific innovation rarely makes its way by gradually winning over and converting its opponents: it rarely happens that Saul becomes Paul. What does happen is that its opponents gradually die out and that the growing generation is familiarized with the idea from the beginning.
--Max Planck

I must govern the clock, not be governed by it.
--Golda Meir

All pain disappears, it's the nature of my circuitry.
--nine inch nails

In 1969, Stephen Unger published his classic textbook on asynchronous circuit design. This book presented a comprehensive look at the asynchronous design methods of the time. In the 30 years hence, there have been numerous technical publications and even a few books [37, 57, 120, 203, 224, 267, 363, 393], but there has not been another textbook. This book attempts to fill this void by providing an updated look at asynchronous circuit design in a form accessible to a student who simply has some background in digital logic design.

An asynchronous circuit is one in which synchronization is performed without a global clock. Asynchronous circuits have several advantages over their synchronous counterparts, including:

1. Elimination of clock skew problems. As systems become larger, increasing amounts of design effort is necessary to guarantee minimal skew in the arrival time of the clock signal at different parts of the chip. In an asynchronous circuit, skew in synchronization signals can be tolerated.

2. Average-case performance. In synchronous systems, the performance is dictated by worst-case conditions. The clock period must be set to be long enough to accommodate the slowest operation even though the average delay of the operation is often much shorter. In asynchronous circuits, the speed of the circuit is allowed to change dynamically, so the performance is governed by the average-case delay.

3. Adaptivity to processing and environmental variations. The delay of a VLSI circuit can vary significantly over different processing runs, supply voltages, and operating temperatures. Synchronous designs have their clock rate set to allow correct operation under some allowed variations. Due to their adaptive nature, asynchronous circuits operate correctly under all variations and simply speed up or slow down as necessary.

4. Component modularity and reuse. In an asynchronous system, components can be interfaced without the difficulties associated with synchronizing clocks in a synchronous system.

5. Lower system power requirements. Asynchronous circuits reduce synchronization power by not requiring additional clock drivers and buffers to limit clock skew. They also automatically power-down unused components. Finally, asynchronous circuits do not waste power due to spurious transitions.

6. Reduced noise. In a synchronous design, all activity is locked into a very precise frequency. The result is nearly all the energy is concentrated in very narrow spectral bands at the clock frequency and its harmonics. Therefore, there is substantial electrical noise at these frequencies. Activity in an asynchronous circuit is uncorrelated, resulting in a more distributed noise spectrum and a lower peak noise value.

Despite all these potential advantages, asynchronous design has seen limited usage to date. Although there are many reasons for this, perhaps the most serious is a lack of designers with experience in asynchronous design. This textbook is a direct attempt at addressing this problem by providing a means for graduate or even undergraduate courses to be created that teach modern asynchronous design methods. I have used it in a course which includes both undergraduates and graduates. Lectures and other material used in this and future courses will be made available on our Web site: http : //www. async. elen. utah. edu/book/. This book may also be used for self-study by engineers who would like to learn about modern asynchronous design methods. Each chapter includes numerous problems for the student to try out his or her new skills.

The history of asynchronous design is quite long. Asynchronous design methods date back to the 1950s and to two people in particular: Huffman and Muller. Every asynchronous design methodology owes its roots to one of these two men. Huffman developed a design methodology for what is known today as fundamental-mode circuits [170]. Muller developed the theoretical underpinnings of speed-independent circuits [279]. Unger is a member of the "Huffman School," so his textbook focused primarily on fundamental-mode circuit design with only a brief treatment of Muller circuits. Although I am a student of the "Muller School," in this book we present both design methods with the hope that members of both schools will grow to understand each other better, perhaps even realizing that the differences are not that great.

Since the early days, asynchronous circuits have been used in many interesting applications. In the 1950s and 1960s at the University of Illinois, Muller and his colleagues used speed-independent circuits in the design of the ILLIAC and ILLIAC II computers [46]. In the early days, asynchronous design was also used in the MU-5 and Atlas mainframe computers. In the 1970s at Washington University in St. Louis, asynchronous macromodules were developed [87]. These modules could be plugged together to create numerous special-purpose computing engines. Also in the 1970s, asynchronous techniques were used at the University of Utah in the design of the first operational dataflow computer [102, 103] and at Evans and Sutherland in design of the first commercial graphics system.

Due to the advantages cited above, there has been a resurgence of interest in asynchronous design. There have been several recent successful design projects. In 1989, researchers at Caltech designed the first fully asynchronous microprocessor [251, 257, 258]. Since that time, numerous other researchers have produced asynchronous microprocessors of increasing complexity [10, 13, 76, 134, 135, 138, 191, 259, 288, 291, 324, 379, 406]. Commercially, asynchronous circuits have had some recent success. Myranet uses asynchronous circuits coupled with pipeline synchronization [348] in their router design. Philips has designed numerous asynchronous designs targeting low power [38, 136, 192, 193]. Perhaps the most notable accomplishment to come out of this group is an asynchronous 80C51 microcontroller, which is now used in a fully asynchronous pager being sold by Philips. Finally, the RAPPID project at Intel demonstrated that a fully asynchronous instruction-length decoder for the x86 instruction set could achieve a threefold improvement in speed and a twofold improvement in power compared with the existing synchronous design [141, 142, 143, 144, 330, 367].

In the time of Unger's text, there were perhaps only a handful of publications each year on asynchronous design. As shown in Figure 0.1, this rate of publication continued until about 1985, when there was a resurgence of interest in asynchronous circuit design [309]. Since 1985, the publication rate has grown to well over 100 technical publications per year. Therefore, although Unger did a superb job of surveying the field, this author has his work cut out for him. In the sources section at the end of each chapter, the interested reader is pointed to an extensive bibliography (over 400 entries) to probe deeper. Although an attempt has been made to give a flavor of the major design methodologies being developed and used, it is impossible even to reference every paper published on asynchronous design, as the number of entries in the asynchronous bibliography [3091 now exceeds 1400. The interested reader should consult this bibliography and the proceedings from the recent symposiums on asynchronous circuits and systems [14, 15, 16, 17, 18, 19, 201.

The book is organized as follows. In Chapter 1 we introduce the asynchronous design problem through a small example illustrating the differences among the various timing models used. In Chapter 2 we introduce the concept of asynchronous communication and describe a methodology for specifying asynchronous designs using VHDL. In Chapter 3 we discuss various asynchronous protocols. In Chapter 4 we introduce graphical representations that are used for asynchronous design. In Chapter 5 we discuss Huffman circuits and in Chapter 6 we describe Muller circuits. In Chapter 7 we develop techniques for timing analysis and optimization which can lead to significant improvements in circuit quality. In Chapter 8 we introduce methods for the analysis and verification of asynchronous circuits. Finally, in Chapter 9 we give a brief discussion of issues in asynchronous application.

Chris J. Myers