7 - Tangram → handshake circuits

Summary

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.