Asynchronous Circuits

Frontmatter

Chapter 1. Introductory Examples

Abstract

Digital circuits are normally designed as networks of interconnected components. There are two basic approaches to the coordination of the activities of such components: synchronous and asynchronous.

Janusz A. Brzozowski, Carl-Johan H. Seger

Chapter 2. Mathematical Background

Abstract

Our goal in this chapter is to establish a mathematical foundation for the following chapters. We provide here brief introductions to set theory, Boolean algebra, ternary algebra, and directed graph theory. The material is presented rather concisely, and the reader may wish to refer to some introductory texts for additional explanations [5, 6, 25, 115]. We point out that, while most of the material in this chapter appears frequently in basic texts on discrete mathematics, this is not the case for the section on ternary algebra.

Janusz A. Brzozowski, Carl-Johan H. Seger

Chapter 3. Delay Models

Abstract

The customary model of a logic gate is its Boolean function. It should be clear that this model does not take into account all of the properties of a physical gate. For example, physical gates have delays associated with their operation. Thus, if an input of a gate changes at some time, its output will respond to this change only at some later time, whereas the Boolean function model treats the response as instantaneous. In this chapter we consider the basic properties of delays, and introduce a number of mathematical models of delays. First, however, we discuss the possible behaviors of the environment of a circuit.

Janusz A. Brzozowski, Carl-Johan H. Seger

Chapter 4. Gate Circuits

Abstract

Gate circuits have been in use for a number of years, are generally well known, and are relatively easy to model mathematically. In this chapter we define several gate circuit classes, some reflecting topological properties and others arising from behavioral characteristics. We show how gate circuits can be modeled in a very general, mathematically precise, framework. In the next chapter we show how modern MOS circuits can also be modeled in our framework; this enables us later to derive a theory applicable to gates as well as MOS circuits. For additional information concerning gate circuits the reader should refer to a basic text on logic design, for example [25, 77, 88, 94].

Janusz A. Brzozowski, Carl-Johan H. Seger

Chapter 5. CMOS Transistor Circuits

Abstract

The theory that has been developed so far has been presented in terms of gates, albeit very general gates, i.e., components capable of realizing arbitrary Boolean functions. In practice, most VLSI circuits are implemented with MOS transistors as basic building blocks. Unfortunately, the theory developed for gates is not adequate for many MOS transistor circuits. In this chapter we show how these circuits can be modeled in our general framework.

Janusz A. Brzozowski, Carl-Johan H. Seger

Chapter 6. Up-Bounded-Delay Race Models

Abstract

In this chapter we describe a formal model for the analysis of the behavior of asynchronous circuits modeled by networks in which the delays are inertial and have only upper bounds. The analysis is limited to a single transition: Suppose the network is in a given state and the input is kept constant. We would like to know what is the “outcome” of the transition, i.e., what are the possible states of the network a “long” time after the input change, i.e., after the “transients have died down.” The analysis of the circuit behavior in response to a sequence of input changes can then be carried out as a series of such transition analyses. We postpone the discussion of the response to an input sequence until Chapters 11–13.

Janusz A. Brzozowski, Carl-Johan H. Seger

Chapter 7. Ternary Simulation

Abstract

As we have seen in Chapter 6, the race analysis methods—that examine all possible successors of a given state—are computationally intractable. We now describe a method that is quite efficient and produces results that can be viewed as a summary of the results produced by the multiple-winner methods. For many purposes, such summarized results are sufficient.

Janusz A. Brzozowski, Carl-Johan H. Seger

Chapter 8. Bi-Bounded Delay Models

Abstract

The race models discussed so far correspond to delays that are only bounded from above; consequently, the ratio between two delays can be arbitrarily large. The use of such models often leads to very conservative results. For example, suppose a GMW analysis indicates a possible timing problem, say a critical race. It may be the case that, unless the delay in one particular gate is greater than the sum of the delays in a large number of other gates, this critical race will always be resolved in the same way. To obtain more realistic results, we must place some constraints on the relative values of gate and wire delays.

Janusz A. Brzozowski, Carl-Johan H. Seger

Chapter 9. Complexity of Race Analysis

Abstract

Two questions naturally arise in connection with the analysis of a transition caused by an input change: 1) Will the network eventually reach a unique (binary) stable state? 2) Will the network be in a unique (binary) state at time t? We call the first question the “stable-state reachability” (SSR) problem and the second the “limited reachability” (LR) problem. Both questions can be answered by using the race analysis algorithms presented in earlier chapters. Some of these algorithms are highly efficient, whereas others appear to require time exponential in the size of the network to be analyzed. In this chapter we explore the inherent computational complexity of these analysis problems. We assume the reader is familiar with the standard terminology for NP-completeness, as described in [55]. The work given here is based mainly on [122, 123].

Janusz A. Brzozowski, Carl-Johan H. Seger

Chapter 10. Regular Languages and Finite Automata

Abstract

This chapter provides an introduction to the theory of regular languages and finite automata. These concepts will be used in the following chapters for describing behaviors of asynchronous circuits and for specifying abstract behaviors. The theory of regular languages and finite automata is now well established as one of the important basic tools of computer science. We present this theory in a somewhat different way than is done in most textbooks, because we feel that our approach is more general and permits us to establish the relationship between regular languages and finite automata in a very natural way. For a general introduction to regular languages and finite automata, see one of the many texts on this subject, for example [65, 77, 100, 120]; for material closer to our treatment see [16, 17, 20].

Janusz A. Brzozowski, Carl-Johan H. Seger

Chapter 11. Behaviors and Realizations

Abstract

In previous chapters we have discussed the analysis of a network when it is started in a stable state and some inputs are changed, and then held constant at their new values. This is only part of the analysis problem. A complete analysis also involves the network behavior in response to a sequence of input changes, some of which may occur while the network is unstable, if fundamental-mode operation is not used. We consider such behaviors in this chapter.

Janusz A. Brzozowski, Carl-Johan H. Seger

Chapter 12. Types of Behaviors

Abstract

In this chapter, we consider several types of behaviors that may be used for specifying and analyzing asynchronous circuits. Section 12.1 shows how a number of behaviors may be associated with a simple OR gate. In Section 12.2, we consider the classical primitive flow table specifications. We point out some deficiencies of the flow table approach, and we compare it with our formal model of behaviors. In Section 12.3 we discuss the derivation of behaviors of networks operated in fundamental mode. General fundamental-mode behaviors can be abbreviated to the “direct” behaviors described in Section 12.4, if transient states are of no interest. Moreover, many behaviors encountered in practice are even more restricted. For this reason, we introduce in Section 12.5 the class of “serial” behaviors. These behaviors will be used again in Chapters 13 and 14.

Janusz A. Brzozowski, Carl-Johan H. Seger

Chapter 13. Limitations of Up-Bounded Delay Models

Abstract

In this chapter we study the behavior of the so-called delay-insensitive (DI) circuits in response to sequences of input changes. The correctness of the behaviors of such circuits is independent of the relative delays in their components and wires. It will be shown that the class of behaviors realizable by delay-insensitive circuits is quite restricted.

Janusz A. Brzozowski, Carl-Johan H. Seger

Chapter 14. Symbolic Analysis

Abstract

The race analysis algorithms and the behaviors introduced so far in this book all use the tacit assumption that the states of a network are represented explicitly. Since the state space grows exponentially with the size of the network, such a representation can only be used for relatively small circuits. In this chapter we consider representing states and other similar objects symbolically.

Janusz A. Brzozowski, Carl-Johan H. Seger

Chapter 15. Design of Asynchronous Circuits

Abstract

Most of this chapter is based on an article by Scott Hauck.¹ However, we have adapted this material to the style of the book, omitted certain topics, significantly changed other topics, and added new material.

Janusz A. Brzozowski, Scott Hauck, Carl-Johan H. Seger

Backmatter