Browse Prior Art Database

Compiling Communicating Processes . into Delay-Insensitive VLSI Circuits

IP.com Disclosure Number: IPCOM000127948D
Original Publication Date: 1986-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 12 page(s) / 38K

Publishing Venue

Software Patent Institute

Related People

Alain J. Martin: AUTHOR [+3]

Abstract

If VLSI is an adequate technology to implement highly concurrent computations (71, it should be possible to apply to VLSI the already well-established design methods for dis-tributed programming. Ideally, a distributed computation should be described in a notation that can be compiled into a VLSI-circuit as well into code for a stored-program computer. The method described in this paper is a step in that direction. At the moment, the term "compiling" means a "systematic, semantics-preserving transformation". The ultimate goal of the transformation being carried out automatically has not yet been achieved, although we believe that it is not remote. In the method we propose, the computation is initially described as a set of communi-cating processes in the notation of (3], which is somewhat similar to C.A.R. Hoare's CSP [2]. This first description is the reference solution, which has to be proved correct. The program is then compiled into a delay-insensitive circuit by applying a series of semantics-preserving transformations. Hence the circuit obtained is correct by construction: all semantic prop-erties that can be proved of the program hold for the circuit as well. Following [11], a circuit is called delay-insensitive when its correct operation is inde-pendent of any assumption on delays in operators and wires, except that the delays are 1 finite. Consequently, such circuits do not use a clock signal: sequencing is enforced entirely by communication mechanisms. Delay-insensitive circuits have been known and used for their elegance, versatility, and robustness, which result from the ideal separation of concerns they provide between the mathematical and physical aspects of circuit design. The first modern survey on the topic is (101, where such circuits are called self-timed. A different approach-the macro-module approach-is described in [8]. Closer to our method is the recent work at Eindhoven University of Technology, a good survey of which is [9]. A circuit is a network of elementary operators (and, or, C-element, arbiter, synchro-nizer, wire, fork). The specification of an operator is a so-called production rule set, where a production rule is a "weaker" form of guarded command, and a production rule set a "weaker" form of repetition. The compilation relies essentially on the four-phase (also called four-cycle) handshaking expansion of the communications. After expansion, the program of each process is compiled into a production rule set from which ail explicit sequencing has been removed. By matching those production rules to those describing the operators, the programs are identified with networks of operators. The method has already been applied to a whole spectrum of problems, some of them, such as distributed mutual exclusion (4], and fair arbitration (5J, being quite difficult. The results are beyond our original expectations. For many circuits, especially complex ones, the compiled circuits are superior to their "hand-designed" counterparts, which are often more complex and not entirely delay-insensitive. We first present the program notation and the VLSI operators that constitute the "object code". We then describe the four steps of the compilation and illustrate the method with a number of simple examples.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Compiling Communicating Processes . into Delay-Insensitive VLSI Circuits

. Alain J. Martin ,. Department of Computer Science California Institute of Technology Pasadena CA 91125, USA 5210:TR:86

31 December 1985 to appear in: Journal of Distributed Computing, vo1.1, no.3, 1988

1. Introduction

If VLSI is an adequate technology to implement highly concurrent computations (71, it should be possible to apply to VLSI the already well-established design methods for dis-tributed programming. Ideally, a distributed computation should be described in a notation that can be compiled into a VLSI-circuit as well into code for a stored-program computer. The method described in this paper is a step in that direction. At the moment, the term "compiling" means a "systematic, semantics-preserving transformation". The ultimate goal of the transformation being carried out automatically has not yet been achieved, although we believe that it is not remote.

In the method we propose, the computation is initially described as a set of communi-cating processes in the notation of (3], which is somewhat similar to C.A.R. Hoare's CSP [2]. This first description is the reference solution, which has to be proved correct. The program is then compiled into a delay-insensitive circuit by applying a series of semantics-preserving transformations. Hence the circuit obtained is correct by construction: all semantic prop-erties that can be proved of the program hold for the circuit as well.

Following [11], a circuit is called delay-insensitive when its correct operation is inde-pendent of any assumption on delays in operators and wires, except that the delays are finite. Consequently, such circuits do not use a clock signal: sequencing is enforced entirely by communication mechanisms. Delay-insensitive circuits have been known and used for their elegance, versatility, and robustness, which result from the ideal separation of concerns they provide between the mathematical and physical aspects of circuit design. The first modern survey on the topic is (101, where such circuits are called self-timed. A different approach-the macro-module approach-is described in [8]. Closer to our method is the recent work at Eindhoven University of Technology, a good survey of which is [9]. A circuit is a network of elementary operators (and, or, C-element, arbiter, synchro-nizer, wire, fork). The specification of an operator is a so-called production rule set, where a production rule is a "weaker" form of guarded command, and a production rule set a "weaker" form of repetition. The compilation relies essentially on the four-phase (also called four-cycle) handshaking expansion of the communications. After expansion, the program of each process is compiled into a production rule set from which ail explicit sequencing has been removed. By matching those production rules to those describing the operators, the programs are ide...