Table of Contents
Preface.
Acknowledgments.
Introduction.
Communication Channels.
Communication Protocols.
Graphical Representations.
Huffman Circuits.
Muller Circuits.
Timed Circuits.
Verification.
Applications.
Appendix A: VHDL Packages.
Appendix B: Sets and Relations.
References.
Index.
Forewords & Introductions
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
Read an Excerpt
Wine is bottled poetry.
--Robert Louis Stevenson
Wine gives courage and makes men more apt for passion.
--Ovid
I made wine out of raisins so I wouldn't have to wait for it to age.
--Steven Wright
In this chapter we use a simple example to give an informal introduction to many of the concepts and design methods that are covered in this book. Each of the topics in this chapter is addressed more formally in much more detail in subsequent chapters.
1.1 Problem Specification
In a small town in southern Utah, there's a little winery with a wine shop nearby. Being a small town in a county that thinks Prohibition still exists, there is only one wine patron. The wine shop has a single small shelf capable of holding only a single bottle of wine. Each hour, on the hour, the shopkeeper receives a freshly made bottle of wine from the winery which he places on the shelf. At half past each hour, the patron arrives to purchase the wine, making space for the next bottle of wine. Now, the patron has learned that it is very important to be right on time. When he has arrived early, he has found an empty shelf, making him quite irate. When he has arrived late, he has found that the shopkeeper drank the last bottle of wine to make room for the new bottle. The most frustrating experience was when he arrived at just the same time that the shopkeeper was placing the bottle on the shelf. In his excitement, he and the shopkeeper collided, sending the wine bottle to the floor, shattering it, so that no one got to partake of that lovely bottle of wine.
This synchronous method of wine shopping went on for some time, with all parties being quite happy. Then one day (in the mid-1980s), telephone service arrived in this town. This was a glorious invention which got the town really excited. The patron got a wonderful idea. He knew the winery could operate faster if only he had a way to purchase the wine faster. Therefore, he suggested to the shopkeeper, "Say, why don't you give me a call when the wine arrives?" This way he could avoid showing up too early, frustrating his fragile temperament. Shortly after the next hour, he received a call to pick up the wine. He was so excited that he ran over to the store. On his way out, he suggested to the shopkeeper, "Say, why don't you give the folks at the winery a call to tell them you have room for another bottle of wine?" This is exactly what the shopkeeper did; and wouldn't you know it, the wine patron got another call just 10 minutes later that a new bottle had arrived. This continued throughout the hour. Sometimes it would take 10 minutes to get a call while other times it would take as long as 20 minutes. There was even one time he got a call just five minutes after leaving the shop (fortunately, he lived very close by). At the end of the hour, he realized that he had drunk 5 bottles of wine in just one hour!
At this point, he was feeling a bit woozy, so he decided to take a little snooze. An hour later, he woke up suddenly quite upset. He realized that the phone had been ringing off the hook. "Oh my gosh, I forgot about the wine!" He rushed over, expecting to find that the shopkeeper had drunk several bottles of his wine, but to his dismay, he saw one bottle on the shelf with no empties laying around. He asked the shopkeeper, "Why did they stop delivering wine?" The shopkeeper said, "Well, when I did not call, they decided that they had better hold up delivery until I had a place on my shelf."
From that day forward, this asynchronous method of wine shopping became the accepted means of doing business. The winery was happy, as they sold more wine (on average). The shopkeeper's wife was happy, as the shopkeeper never had to drink the excess. The patron was extremely happy, as he could now get wine faster, and whenever he felt a bit overcome by his drinking indiscretion, he could rest easy knowing that he would not miss a single bottle of wine.
Loading...