Automated circuit design

Claim 1

A method for fabricating a digital circuit, said method comprising the steps of: generating a tree graph comprising a multiplicity of nodes and respective children, each of said nodes corresponding to a digital function within said digital circuit and each of said children representing an input for one of the digital functions; for each of a multiplicity of said nodes, if the node is an AND gate, determining s cell =s of node itself plus summation (s of each child-1), if the node is an OR gate, determining s cell =max (s of each child), and if the node is an Inverter, determining s cell =s of child plus 1, wherein s=1 for an Inverter, s=n for an n input AND gate, and s=1 for an n input OR gate; and fabricating the circuit based on a physical representation of a plurality of partial subgraphs rooted at respective nodes which have "s cell " values less than or equal to a specified number, each of said partial subgraphs comprising the respective root node and one or more descendants of said root node.

Claim 2

A method for fabricating a digital circuit, said method comprising the steps of: generating a tree graph comprising a multiplicity of nodes and respective children, each of said nodes corresponding to a digital function within said digital circuit and each of said children representing an input for one of the digital functions; for each of a multiplicity of said nodes, if the node is an AND gate, determining s cell =s of node itself plus summation (s of each child-1), if the node is an OR gate, determining s cell =max (s of each child), and if the node is an Inverter, determining s cell =s of child plus 1, wherein s=1 for an Inverter, s=n for an n input AND gate, and s=1 for an n input OR gate; and fabricating the circuit based on a physical representation of a plurality of partial subgraphs rooted at respective nodes which have "s cell " values less than or equal to a specified number, each of said partial subgraphs comprising the respective root node and one or more descendants of said root node.

Claim 6

A method for designing a digital circuit using a multiplicity of cells, each of said cells comprising a plurality of digital components, said method comprising the steps of: selecting a maximum number of series transistors to be permitted in any one cell; generating a tree graph representing said digital circuit, said tree graph comprising a multiplicity of nodes and respective children, each of said nodes corresponding to a digital function within said digital circuit and each of said children representing an input for one of the digital functions; executing the following algorithm at a multiplicity of said nodes to determine at each of said nodes a number of series transistors "s" required by a cell rooted at said node: if the node is an AND gate, s=s of node itself plus summation [s of each child-1] if the node is an OR gate, s=max [s of each child] if the node is an Inverter, s=s of child plus 1 wherein s=1 for an Inverter; s=n for an n input AND gate; and s=1 for an n input OR gate; selecting a partial subgraph rooted at each of said nodes which has an "s" value less than or equal to said maximum number, each of said partial subgraphs comprising the respective root node and one or more descendents of said root node; fetching or generating data describing a physical representation of one or more of the selected partial subgraphs; and fabricating the circuit using said data for said fetched or generated cells.

Claim 7

A method for designing a digital circuit using a multiplicity of cells, each of said cells comprising a plurality of digital components, said method comprising the steps of: selecting a maximum number of series transistors to be permitted in any one cell; generating a tree graph representing said digital circuit, said tree graph comprising a multiplicity of nodes and respective children, each of said nodes corresponding to a digital function within said digital circuit and each of said children representing an input for one of the digital functions; executing the following algorithm at a multiplicity of said nodes to determine at each of said nodes a number of series transistors "s" required by a cell rooted at said node: if the node is an AND gate, s=s of node itself plus summation [s of each child-1] if the node is an OR gate, s=max [s of each child] if the node is an Inverter, s=s of child plus 1 wherein s=1 for an Inverter; s=n for an n input AND gate; and s=1 for an n input OR gate; selecting a partial subgraph rooted at each of said nodes which has an "s" value less than or equal to said maximum number, each of said partial subgraphs comprising the respective root node and one or more descendents of said root node; fetching or generating data describing a physical representation of one or more of the selected partial subgraphs; and fabricating the circuit using said data for said fetched or generated cells.

Claim 11

A method for designing a digital circuit using a multiplicity of cells, each of cells comprising a plurality of digital components, said method comprising the steps of: selecting a maximum delay to be permitted in any one cell; generating a tree graph representing said cell, said tree graph comprising a multiplicity of nodes and respective children, each of said nodes corresponding to a digital function within said digital circuit and each of said children representing an input for said digital function; executing the following algorithm at a root node of said cell to determine a number of series pull-down transistors "s" required by said node: if the node is an AND gate, s=s of node itself plus summation [s of each child-1] if the node is an OR gate, s=max [s of each child] if the node is an Inverter, s=s of child plus 1 wherein s=1 for an Inverter; s=n for an n input AND gate; and s=1 for an n input OR gate; executing the following algorithm at a root node of said cell to determine a number of parallel pull-up transistors "p" required by said node: if the root is an AND gate, p=max[p of each child] if the root is an OR gate, p=p of root plus sum[p of each child-1] if the root is an Inverter, p=p of child plus 1 wherein p=1 for an inverter, p=1 for an n input AND gate, and p=n for an n input OR gate; estimating delay through said cell based on the equation: delay=K×(2×p+s) where K is a technology dependent parameter proportional to the fall time of a unit size transistor; and if the estimated delay exceeds said predetermined limit, rejecting said cell, and if the estimated delay does not exceed said predetermined limit, fabricating said circuit using said cell.

Claim 12

A method for designing a digital circuit using a multiplicity of cells, each of cells comprising a plurality of digital components, said method comprising the steps of: selecting a maximum delay to be permitted in any one cell; generating a tree graph representing said cell, said tree graph comprising a multiplicity of nodes and respective children, each of said nodes corresponding to a digital function within said digital circuit and each of said children representing an input for said digital function; executing the following algorithm at a root node of said cell to determine a number of series pull-down transistors "s" required by said node: if the node is an AND gate, s=s of node itself plus summation [s of each child-1] if the node is an OR gate, s=max [s of each child] if the node is an Inverter, s=s of child plus 1 wherein s=1 for an Inverter; s=n for an n input AND gate; and s=1 for an n input OR gate; executing the following algorithm at a root node of said cell to determine a number of parallel pull-up transistors "p" required by said node: if the root is an AND gate, p=max[p of each child] if the root is an OR gate, p=p of root plus sum[p of each child-1] if the root is an Inverter, p=p of child plus 1 wherein p=1 for an inverter, p=1 for an n input AND gate, and p=n for an n input OR gate; estimating delay through said cell based on the equation: delay=K×(2×p+s) where K is a technology dependent parameter proportional to the fall time of a unit size transistor; and if the estimated delay exceeds said predetermined limit, rejecting said cell, and if the estimated delay does not exceed said predetermined limit, fabricating said circuit using said cell.