Synthesis of Self-timed VLSI Circuits from Graph-theoretic Specifications

From bibtex.

Abstract

This thesis presents an approach for direct and efficient synthesis of self-timed (asynchronous) control circuits from formal specifications called Signal Tranaition Graph.a (STGs ). Control circuits synthesized from this graph model are .apeetl-independent and capable of perfoming concurrent operation. 'The property of speed-independence means that the circuit operates correctly regardless of variations in delays of logic gates, thus implying that the circuit is hazard-free under any combination of gate delays. The capability of STGs for explicitly specifying concurrent operations internal to a. control circuit is unique to this model, unlike other approaches based on Finite State Ma.chines. STGs are a form of interpreted Petri nets, in which transitions in a. net are interpreted as transitions of signals in a control circuit. While other synthesis approaches based on Petri nets have not been very successful, we have developed a number of analytical results which establish the equivalence between the static structure of nets (their syntax) and their underlying firing sequence semantics-an analytical approach called structure theory of Petri nets. This equivalence permits the characterization of the low-level properties of control circuits in terms of STG syntax: the properties of deadlock-free and hazard-free of circuits are characterized as syntactic propeties of livene.u and peraistency of STGs. A preliminary STG specification of a control circuit can be modified into one which is live and persistent, from which a deadlock-free and hazard-free logic implementation can be derived mechanically. STGs allow efficient synthesis of control circuits by using a method of decomposition based on a graph-theoretic technique called contniction. Instead of implementing a logic circuit from a STG directly, it can first be decomposed into a number of contracted nets, one for each signal generated by the control circuit. A logic element can then be determined from each contracted net, and the composition of logic elements produces the final circuit implementation.