US 5,469,367 AGranted

Methodology and apparatus for modular partitioning for the machine design of asynchronous circuits

AssigneeUniversity Technologies International Inc.

InventorsRuchir Puri, Jun Gu

Life of this patent

Estimating the term…

Loading patent…

Abstract

A machine methodology for designing asynchronous circuits utilizes a modular approach for the synthesis of asynchronous circuits from signal transition graphs, partitions the signal transition graph into a number of simpler and more manageable modules. Each modular graph is then individually solved. The results of the small graphs are then integrated together to provide a solution to the asynchronous circuit design problem as defined by a given asynchronous behavioral specification. A satisfiability solver for Boolean output function utilizing a binary decision diagram is incorporated in one embodiment which is comprised of a structural SAT formula preprocessor and a complete, incremental SAT processor which is specifically designed to find an optimal solution. The preprocessor compresses a large size SAT formula representing a circuit into a number of smaller SAT formulas. Each small size SAT formula is then solved by the BDD SAT processor. The results of these subsolutions are then integrated together to contribute to the solution of the original larger design problem.

Claims19

Dependent claims

A computer implemented method for machine design of an asynchronous digital circuit on a semiconductor material having at least one output comprising the steps of:

defining asynchronous behavioral specifications for said asynchronous digital circuit to be designed;
generating a signal transition graph corresponding to said asynchronous behavioral specifications for said asynchronous digital circuit;
generating a complete state graph from said signal transition graph;
generating a modular state graph from said complete state graph for an output o.sub.i ;
generating state signal assignments to satisfy predetermined design constraints for said modular state graph;
propagating state signal assignments upward from said modular state graph to said complete state graph;
repeating said steps of generating said modular state graph, generating said state signal assignments, and propagating said state signals from said modular graph to said complete state graph for each output of said asynchronous digital circuit;
generating expanded state signals in said complete state graphs;
generating a design for logic circuits from said expanded complete state graph meeting each of said predetermined constraints and satisfying said asynchronous behavioral specification, and laying out said design for said logic circuits on said semiconductor material,
whereby practical asynchronous digital circuits are machine designed and laid out on said semiconductor material with minimized circuit structure and minimized circuit area implementation on said semiconductor material.

7 more elements

Dependencies are inferred from the claim text.