Production Based Specification

Andrew Crews, Andrew Seawright, Forrest Brewer

Objective

Most current sequential synthesis techniques rely on a deterministic finite automata (DFA) model at some point in the synthesis process. It has been shown, however, that the DFA can potentially explode even for machines which have a fairly simple circuit implementation. In these cases, the finite state machine (FSM) must be partitioned and constructed as several separate interacting FSM's. This partitioning makes verification and optimization difficult, since interactions that occur between the FSM's are obscured.

Production Based Specification (PBS) is an extended regular expression based language for specification of sequential machines. Regular expression languages, like PBS, inherently represent FSM's in a non-deterministic finite automata (NDFA) model. A regular expression directly corresponds to a NDFA state transition graph with one state for each identifier in the regular expression.

An example NDFA and corresponding regular expression.

Extensions to PBS allow succinct descriptions of machines that may have an inefficient regular expression description. These extensions create a language which is applicable for construction of :

  1. Reactive machines which perform computations in response to inputs such as complex communication protocols,
  2. Machines which are naturally described as hierarchical compositions of interacting submachines, such as complex data-path controllers.
The PBS compiler provided here makes full use of these operators, and has an efficient construction algorithm which does operates in polynomial time compared to the size of the specification. Note this compiler is no longer supported -- but uses the Homebrew BDD package.

Publications

[1] A. Seawright, F. Brewer, "High Level Symbolic Construction Techniques for High Performance Sequential Synthesis," 30th DAC, pp 424-428, June 1993.
[2] A. Seawright, F. Brewer, "Clairvoyant: A Synthesis System for Production-Based Specification," IEEE Trans. on VLSI, pp 172-185, June 1994.
[3] A. Seawright, Grammar-Based Specifications and Synthesis for Synchronous Digital Hardware Design, Ph. D. Thesis, Univ. of California, Santa Barbara, June 1994.