The semantic analysis phase of a compiler must translate abstract syntax into abstract machine code. It can do this after type-checking, or at the same time.

Though it is possible to translate directly to real machine code, this hinders portability and modularity. Suppose we want compilers for N different source languages, targeted to M different machines. In principle this is N · M compilers (Figure 7.1a), a large implementation task.

An intermediate representation (IR) is a kind of abstract machine language that can express the target-machine operations without committing to too much machine-specific detail. But it is also independent of the details of the source language. The front end of the compiler does lexical analysis, parsing, semantic analysis, and translation to intermediate representation. The back end does optimization of the intermediate representation and translation to machine language.

A portable compiler translates the source language into IR and then translates the IR into machine language, as illustrated in Figure 7.1b. Now only N front ends and M back ends are required. Such an implementation task is more reasonable.

Even when only one front end and one back end are being built, a good IR can modularize the task, so that the front end is not complicated with machine-specific details, and the back end is not bothered with information specific to one source language.

Chapters 2–11 have described the fundamental components of a good compiler: a front end, which does lexical analysis, parsing, construction of abstract syntax, type-checking, and translation to intermediate code; and a back end, which does instruction selection, dataflow analysis, and register allocation.

What lessons have we learned? I hope that the reader has learned about the algorithms used in different components of a compiler and the interfaces used to connect the components. But the author has also learned quite a bit from the exercise.

My goal was to describe a good compiler that is, to use Einstein's phrase, “as simple as possible – but no simpler.” I will now discuss the thorny issues that arose in designing Tiger and its compiler.

Nested functions. Tiger has nested functions, requiring somemechanism (such as static links) for implementing access to nonlocal variables. But many programming languages in widespread use -C, C++, Java – do not have nested functions or static links. The Tiger compiler would become simpler without nested functions, for then variables would not escape, and the FindEscape phase would be unnecessary. But there are two reasons for explaining how to compile nonlocal variables. First, there are programming languages where nested functions are extremely useful – these are the functional languages described in Chapter 15. And second, escaping variables and the mechanisms necessary to handle them are also found in languages where addresses can be taken (such as C) or with call-by-reference (such as C++).

Introduction

In [Udd84, Udd86, Ebe89, UV88] the notions delay insensitivity, independent alphabet and absence of computation interference have been defined for directed processes. In this section we investigate to what extent these notions apply to handshake processes.

Definition A.O (directed process)

A directed process T is a triple (iT,oT,tT), in which iT and oT are disjoint sets of symbols and tT is a non-empty, prefix-closed subset of (iT ∪ oT).

A handshake process is not a directed process: the alphabet of a handshake process has more structure and the trace set is not prefix closed. However, to every handshake process P there corresponds a directed process, viz. (iP,oP,tP≤) .

All port structures in this appendix have no internal ports.

Composability

Composability of traces captures the notion that symbols communicated between processes arrive no earlier than they were sent. Consider directed processes P and Q such that iP = oQ and oP = iQ. Let s ∈ tP and t ∈ tQ. Composability restricts the way the pair (s,t) may evolve from (ε,ε). Let a ∈ iQ (and therefore a ∈ oP). Then ε is composable to a, but the converse is not true, because a must be sent by P before it can be received by Q. Similarly, for b ∈ oQ, we have b composable to ε. Also, trace s is composable to ta if s is composable to t and a is on its way, i.e. len.(t⌈a) < len.(s⌈a).

Handshake circuits and the associated compilation method from CSP-based languages were conceived during 1986 at Philips Research Laboratories. A first IC (7000 transistors) was designed using experimental tools to manipulate and analyze handshake circuits (then called “abstract circuits”) and to translate them into standard-cell netlists. The IC realized a subfunction of a graphics processor [SvB88] and proved “first-time-right” (September 1987). Extensive measurements hinted at interesting testability and robustness properties of this type of asynchronous circuit [vBS88].

Encouraged by these early results the emphasis of the research shifted from the design of the graphics processor to VLSI programming, compilation methods, and tool design. Generalization and systematization of the translation method resulted in an experimental silicon compiler during spring 1990 [vBKR+91]. Section 9.0 describes these compilation tools and their application to a simple Compact Disc error decoder.

A second test chip was designed and verified during the autumn of 1991 [vBBK+93, RS93]. In addition to some test structures, the IC contains a simple processor, including a four-place buffer, a 100-counter, an incrementer, an adder, a comparator, and a multiplier in the Galois field GF(28). The Tangram program was fully automatically compiled into a circuit consisting of over 14 thousand transistors. Section 9.1 discusses this chip and its performance in detail. This chapter concludes with an appraisal of asynchronous circuits in Section 9.2.

VLSI programming and compilation

Experiences with VLSI programming and compilation will be presented from a programmer's viewpoint.

In Chapter 6 we have developed a handshake semantics for Tangram. An alternative semantics for Tangram can be based on failure processes [BHR84]. Failure processes form the underlying model of CSP [Hoa85], and are the basis for a well-established theory for CSP, including a powerful calculus [RH88].

The availability of two distinct semantics for the same program notation suggests several questions, including:

1. 0. Is the handshake-process semantics consistent with the failure semantics? If so, in what sense?

2. 1. Can VLSI programmers use calculi that are based on failure semantics?

The last question is of obvious practical significance.

This appendix starts with a description of failure processes. By means of a simple example it is shown that an embedding of failure processes into all-active handshake processes does not exist. By choosing a more subtle link between handshake semantics and failure semantics, we arrive at positive answers to the above questions.

Failure processes

This subsection describes a process model based on failures. The description below is rather concise; for a more extensive treatment the reader is referred to [BHR84], [BR85] and [Hoa85].

An alphabet structure defines an alphabet as a set of communications.

Definition B.O (alphabet of an alphabet structure)

Let A be an alphabet structure.

1. A communication of A is a pair a: v, such that a ∈ cA and v ∈ TA.a.

2. The alphabet of A is the set of all communications of A and is denoted by aA.

This chapter introduces further Tangram constructs out of which more interesting programs can be described. These constructs include expressions, guarded selection, guarded repetition, and choice. The choice construct supports mixed input and output guards. Guarded selection and choice also introduce nondeterminism.

These constructs are introduced by means of concise and telling examples, namely a simple FIR filter, a median filter, a block sorter, a greatest common divisor, modulo-N counters, various stacks (including a specialization as a priority queue), and a nacking arbiter. In many cases handshake circuits are presented and explained with reference to the Tangram program text. Where relevant, circuit size, speed, and power consumption are analyzed.

FIR filter

A Finite Impulse Response (FIR) filter is a component with a single input port and a single output port. Input and output communications strictly alternate, starting with an input. For a FIR filter of order N the output values are specified as follows. The value of the ith output, i ≥ N, is a weighted sum of the N + 1 most recent input values. The N + 1 weight factors are generally referred to as the filter coefficients. The first N output values are left unspecified.

A very simple FIR filter is used to introduce Tangram expressions and their translation into handshake circuits.

This book is about the design of asynchronous VLSI circuits based on a programming and compilation approach. It introduces handshake circuits as an intermediate architecture between the algorithmic programming language Tangram and VLSI circuits.

The work presented in this book grew out of the project “VLSI programming and compilation into asynchronous circuits” being conducted at Philips Research Laboratories Eindhoven, since 1986. Our original motivation was to increase the productivity of VLSI design by treating circuit design as a programming activity. We chose asynchronous circuits as target for automatic silicon compilation, because asynchronous circuits simplified the translation process and made it easier to take advantage from the abundantly available parallelism in VLSI. Later we discovered that the potential for low power consumption inherent in asynchronous circuits may turn out to be highly relevant to battery-powered products.

The core of this book is about handshake circuits. A handshake circuit is a network of handshake components connected by handshake channels, along which components interact exclusively by means of handshake signaling. It presents a theoretical model of handshake circuits, a compilation method, and a number of VLSI-implementation issues. This core is sandwiched between an informal introduction to VLSI programming and handshake circuits on the one side and a discussion on practical experiences including tooling and chip evaluations on the other side.

Introduction

The most interesting operation on handshake processes is parallel composition. Parallel composition is defined only for connectable processes. Connectability of handshake processes captures the idea that ports form the unit of connection (as opposed to individual port symbols), and that a passive port can only be connected to a single active port and vice versa. A precise definition will be given later.

The communication between connectable handshake processes is asynchronous: the sending of a signal by one process and the reception of that signal by another process are two distinct events. Asynchronous communication is more complicated than synchronized communication, because of the possible occurrence of interference. The concept of interference with respect to voltage transitions has been mentioned in Section 0.1. Interference with respect to symbols occurs when one process sends a symbol and the other process is not ready to receive it. The receptiveness of handshake processes and the imposed handshake protocol exclude the possibility of interference. We are therefore allowed to apply the simpler synchronized communication in the definition of parallel composition of handshake processes.

Another complication is, however, the possibility of divergence: an unbounded amount of internal communication, which cannot be distinguished externally from deadlock. From an implementation viewpoint divergence is undesirable: it forms a drain on the power source, without being productive.

The external behavior of the parallel composition of connectable P and Q will be denoted by P ∥ Q, which is again a handshake process.

Introduction

Tangram is a VLSI-programming language based on CSP, and has much in common with the programming language OCCAM [INM89] (see Section 2.7 for some of the differences). The main construct of Tangram is the command. Commands are either primitive commands, such as a?x and x := x + 1, or composite commands, such as R; S and R ∥ S, where R and S are commands themselves.

Execution of a command may result in a number of communications with the environment through external ports. Another form of interaction with the environment is the reading from and writing into external variables. A Tangram program is a command without external variables, prefixed by an explicit definition of its external ports.

Not all compositions of commands are valid in Tangram. For instance, in a sequential composition the two constituent commands must agree on the input/output direction of their common ports. Also, two commands composed in parallel may not write concurrently into a common variable. Similarly, concurrent reading from and writing into a common variable is not allowed. Section 6.1 defines the syntax of Tangram, including these composition rules. The meaning of each command is described informally.

For a subset of the Tangram commands the handshake-process denotations are given in Section 6.3. This subset is referred to as Core Tangram.

Tangram

The main syntactic constructs of Tangram are program, command, guarded-command set, and expression. With each construct we associate a so-called alphabet structure: a set of typed ports and variables.

Introduction

Handshake circuits are proposed as an intermediary between communicating processes (Tangram programs) and VLSI circuits. Chapter 7 describes the translation of Tangram programs into handshake circuits. This chapter is concerned with the realization of handshake circuits as efficient and testable VLSI circuits. First we observe that the fine-grained parallelism available in VLSI circuits matches the fine-grained concurrency in handshake circuits nicely. The mapping of handshake circuits to VLSI circuits can therefore be relatively direct.

A rather naive mapping is suggested by the following correspondence:

1. a channel corresponds to a set of wires, one per symbol;

2. an event with name a corresponds to a voltage transition along wire a;

3. each handshake component corresponds to a VLSI circuit that satisfies the specification at the transition level.

There is no doubt that the above mapping can result in functional circuits. In general, however, the resulting circuits will be prohibitive in size, poor in performance, probably hard to initialize, and impractical to test for fabrication faults. Concerns for circuit size, performance, initialization and testability are therefore recurring themes in this chapter.

A full treatment of all relevant VLSI-realization issues is beyond the scope of this monograph. Issues that directly relate to (properties of) handshake circuits have been selected for a relatively precise treatment; other topics are sketched more briefly. This chapter discusses:

• peephole optimization: the replacement of subcircuits by cheaper ones;

• relaxation of the receptiveness requirement of handshake processes;

• […]

Introduction

So far the quiescent trace set of a handshake process was specified in one of the following forms: by enumeration, by a predicate, by a state graph, or by parallel composition of other handshake processes.

For many handshake processes none of the above forms may be convenient. An example of such a process is the process that first behaves like P and then, “after successful termination of P”, behaves like Q. Of course, such sequential composition of the handshake processes P and Q requires a notion of successful termination of a process. A sequential handshake process is a handshake process in which that notion is incorporated.

The aim of this chapter is to develop a model for sequential handshake processes and a calculus for these processes. An important application of this calculus is the description of the handshake components required for the compilation of Tangram. Another application is the semantics of Tangram itself.

Sequential handshake processes

A sequential handshake process is a handshake process, some of whose traces are designated as terminal traces, i.e. traces that lead to successful termination. In a sequential composition these terminal traces can be prefixed to traces of the subsequent sequential handshake process.

Let T denote the set of quiescent traces and let U denote the set of terminal traces of sequential handshake process P. Sets T and U must satisfy a number of conditions, which are introduced informally.

Introduction

The topic of this chapter is the translation of Tangram programs into handshake circuits. Let T be a Tangram program. In Chapter 6 we have defined the meaning of T as the handshake process H-T. The translation to handshake circuits is presented as a mathematical function C, from the set of Tangram programs to the set of handshake circuits. Thus, C-T is a handshake circuit, and handshake process ∥.C.T is the behavior of that circuit. Function C is designed such that

where .P was defined as #[: P] (see Definition 6.7). That is, the translation preserves all the nondeterminism of the program. From a practical viewpoint it is sufficient to realize

in which the behavior of the handshake circuit is a refinement of the handshake behavior of the Tangram program. It may be expected that this relaxed form results in cheaper handshake circuits. The advantage of defining the most nondeterministic handshake circuit of T is that alternative translation functions that synthesize more deterministic circuits can readily be derived from it. Some of these alternatives will be indicated.

Also, we have chosen to translate a Tangram program into the handshake circuit with the most internal parallelism. In particular, all guards of a guarded command are evaluated in parallel, as are the two subexpressions of a binary operation. In general this leads to the fastest implementation, but not necessarily the most area-efficient one. If the VLSI programmer wishes a more sequential handshake circuit he can specify such at the Tangram level.

Introduction

A handshake is a means of synchronization among communicating mechanisms. In its simplest form it involves two mechanisms connected by a pair of so-called links, one for sending signals and one for receiving signals. The sending of a signal and the reception of a signal are atomic actions, and constitute the possible events by which a mechanisms can interact with its environment.

A signal sent by one mechanism is bound to arrive at the other mechanism, after a finite, non-zero amount of time. Hence, this form of communication is asynchronous; the sending and the arrival of a signal correspond to two distinct events. It is assumed that a link allows at most one signal to be on its way. Consequently, a signal sent must arrive at the other end of the link before the next one can be sent. When the traveling time of a signal along the link is unknown, the only way to know that a signal has arrived at the other side is to be so informed by the other mechanism. The other link in the pair performs the acknowledgement.

Such a causally ordered sequence of events is called a handshake. The two mechanisms involved play different (dual) roles in a handshake. One mechanism has the active role: it starts with the sending of a request and then waits for an acknowledgement. The other mechanism has the passive role: it waits for a request to arrive and responds by acknowledging.