Method and apparatus for specifying encoded sub-networks

• US 20040019857A1
• Filed: 01/31/2002
• Published: 01/29/2004
• Est. Priority Date: 01/31/2002
• Status: Active Grant

• Current Assignee: Cadence Design Systems Limited (Cadence Group)
• Original Assignee: Cadence Design Systems Limited (Cadence Group)
• Inventors: Teig, Steven, Hetzel, Asmus
• Granted Patent: US 7,076,760 B2
• Time in Patent Office: Days
• US Class Current: 716/1
• CPC Class Codes: G06F 30/30 Circuit design

Abstract

Some embodiments of the invention provide a method for pre-tabulating sub-networks. This method (1) generates a sub-network that performs a function, (2) generates a parameter based on this function, and (3) stores the sub-network in a storage structure based on the generated parameter. In some embodiments, the generated sub-network has several circuit elements. Also, in some embodiments, the generated sub-network performs a set of two or more functions. Some embodiments store each generated sub-network in an encoded manner. Some embodiments provide a method for producing a circuit description of a design. This method (1) selects a candidate sub-network from the design, (2) identifies an output function performed by the sub-network, (3) based on the identified output function, identifies a replacement sub-network from a storage structure that stores replacement sub-networks, and (4) replaces the selected candidate sub-network with the identified replacement sub-network in certain conditions. In some embodiments, this method is performed to map a design to a particular technology library. Some embodiments provide a data storage structure that stores a plurality of sub-networks based on parameters derived from the output functions of the sub-networks.

Claims

1. A method of pre-tabulating a sub-network that has a set of circuit elements, the method comprising:

a) defining a graph that has one node for each circuit element of the sub-network;

b) generating an encoded representation of the graph;

c) storing the encoded representation.

2. The method of claim 1, wherein generating the encoded representation includes generating an encoded representation of each node.

3. The method of claim 2,

wherein the graph represents the topology of circuit elements of the sub-network,

wherein the set of circuit elements includes circuit elements that are interconnected,

wherein, for the interconnection between each pair of interconnected circuit elements, the graph includes an interconnect-edge between the pair of nodes that represent the pair of connected circuit elements,

wherein generating each encoded node representation includes

specifying a node identifier that specifies the start of an encoded description of the encoded node, and

specifying an encoded representation for each edge connected to the node.

4. The method of claim 3, wherein specifying each encoded edge representation includes:

specifying an edge identifier that denotes the start of an encoded description of the encoded edge, and

specifying a node index that identifies another node connected to the edge.

5. The method of claim 1,

wherein the graph represents the topology of the circuit elements of the sub-network,

wherein the set of circuit elements includes circuit elements that are interconnected,

wherein, for the interconnection between each pair of interconnected circuit elements, the graph includes an interconnect-edge between the pair of nodes that represent the pair of connected circuit elements,

wherein generating an encoded representation of the graph includes for each node,

specifying a node identifier that denotes the start of an encoded description of the node,

specifying an edge identifier that denotes the start of an encoded description of each edge connected to the node,

for each edge connected to the node, specifying a node index that identifies another node connected to the edge.

6. The method of claim 1, wherein the encoded representation is a bit string.

7. The method of claim 1, wherein the method pre-tabulates a plurality of sub-networks, wherein each sub-network has a set of circuit elements, the method comprising:

a) defining a plurality of graphs, wherein each graph has a set of nodes,

b) generating an encoded representation for each graph,

c) storing the encoded representation for each graph.

8. The method of claim 7,

wherein each graph represents the topology of the circuit elements of at least one sub-networks.

wherein the set of graphs includes a set of multi-node graphs, wherein each graph in the set of multi-node graphs include a set of edges that connect the set of nodes of the graph,

wherein generating an encoded representation of each graph includes for each node of the graph,

specifying a node identifier that denotes the start of an encoded description of the node,

specifying an edge identifier that denotes the start of an encoded description of each edge connected to the node,

for each edge connected to the node, specifying a node index that identifies another node connected to the edge.

9. The method of claim 8 further comprising:

specifying different sets of local functions for each graph, wherein each set of local function for each particular graph includes one local function for each node of the particular graph, and the combination of each graph with one of the set of local functions specified for the graph specifies a sub-network.

10. The method of claim 9 further comprising:

a) storing the graph and the local functions;

b) for each particular specified sub-network, storing an identifier that specifies the set of particular local functions and the particular graph that specify the particular sub-network.

11. The method of claim 10, wherein the identifier for each particular sub-network specifies the locations for storing the set of particular graph that specify the particular sub-network.

12. The method of claim 10, wherein the identifier for each particular sub-network is a set of indices that specifies the set of particular local functions and the particular graph for the particular sub-network.

13. The method of claim 12, wherein the set of indices for each particular sub-network. includes a graph index and a set of function indices, wherein the graph index identifies the particular graph for the particular sub-network, and each function index identifies a particular local function of the particular sub-network.

14. The method of claim 10, wherein defining the graphs comprises defining graphs up to a particular threshold complexity that relates to at least one structural attribute of the graphs.

15. The method of claim 10 further comprising:

a) identifying a set of output functions for each particular specified sub-network. from the set of local functions used to specify the sub-network;

b) generating a parameter for each sub-network based on the identified set of output functions for each sub-network;

c) storing the generated parameters in the storage structure; and

d) associating the stored parameter for each sub-network with the identifier for the sub-network

16. An encoded representation of a graph that represents the topology of circuit elements of a sub-network, wherein the graph has one node for each circuit element, the encoded representation comprising an encoded representation of each node.

17. The encoded graph representation of claim 16,

wherein some of the circuit elements are connected by an interconnect line, and

wherein, for the interconnect line between each pair of connected circuit elements, the graph includes an interconnect-edge between the pair of nodes that represent the pair of connected circuit elements,

wherein each encoded node representation includes (i) a node identifier that specifies the start of an encoded description of the encoded node, and (ii) an encoded representation for each edge connected to the node.

18. The encoded graph representation of claim 17, wherein each encoded edge representation includes (i) an edge identifier that specifies the start of an encoded description of the encoded edge, and (ii) a node index that specifies another node connected to the edge.

19. The encoded graph representation of claim 18, wherein the graph is a directed acyclic graph that has a number of levels, and the other node specified by each node index of each edge is a graph node at a lower level than the graph node that has the encoded representation that contains the edge'"'"'s encoded representation.

20. The method of claim 19, wherein nodes at the lowest level do not receive the output of any other node, and nodes at a level other than the lowest level receive the output of at least one other node, and nodes at the higher levels depend on the output of more nodes at different levels than nodes at the lower levels.

21. The method of claim 19, wherein the encoded representation is a bit string, and the node index indices are encoded with varying bit length.

22. An encoded representation of a graph that represents the topology of interconnected circuit elements of a sub-network, wherein the graph has one node for each circuit element, wherein the nodes are interconnected by edges in the same manner that the circuit elements corresponding to the nodes are connected, the encoded representation comprising:

for each node,

a node identifier that specifies the start of an encoded description of the node,

an edge identifier that specifies the start of an encoded description of each edge connected to the node,

for each edge connected to the node, a node index that specifies another node connected to the edge.

23. The encoded graph representation of claim 22, wherein the graph is a directed acyclic graph that has a number of levels, and the other node specified by each node index of each edge is a graph node at a lower level than the graph node that the node index for which the node index is specified.

24. The method of claim 22, wherein the encoded representation is a bit string, and the node indices are encoded with varying bit length.