초록 ▼

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 embo

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.

대표청구항 ▼

1. A method of pre-tabulating sub-networks, the method comprising: specifying a plurality of sub-networks, each sub-network specified by a graph and a set of local functions, the graph for each sub-network comprising a plurality of nodes with each node representing a circuit element in the sub-netwo

1. A method of pre-tabulating sub-networks, the method comprising: specifying a plurality of sub-networks, each sub-network specified by a graph and a set of local functions, the graph for each sub-network comprising a plurality of nodes with each node representing a circuit element in the sub-network and having an associated function in the set of local functions, each node's associated local function representing a function performed by the circuit element represented by the node;identifying a set of output functions for each sub-network based on the set of local functions used to specify the sub-network;generating a parameter for each sub-network based on the identified set of output functions for each sub-network; andby a computer, storing the graph and the set of local functions of each sub-network in a storage structure indexed by the generated parameter of the sub-network. 2. The method of claim 1, wherein a particular sub-network includes multiple circuit elements. 3. The method of claim 1, wherein the parameter for a particular sub-network is a set of indices for storing the graph and the set of local functions of the particular sub-network in the storage structure, wherein the set of indices includes an index for each output function performed by the particular sub-network. 4. The method of claim 3, wherein the storage structure is a relational database, and the indices in the set of indices are numerical indices. 5. The method of claim 1, wherein a particular sub-network has a set of input variables, wherein generating the parameter for the particular sub-network comprises: identifying one of local functions in the set of local functions as a pivot function;using the pivot function to specify a configuration for the input variables; andbased on the specified input-variable configuration, specifying an index for each output function. 6. The method of claim 5, wherein using the pivot function to specify an input-variable configuration comprises: identifying a canonic representation of the pivot function; andselecting an input-variable configuration that results in the canonic representation of the pivot function as the specified input-variable configuration. 7. The method of claim 6 further comprising generating a truth table representation of the pivot function, wherein identifying a canonic representation comprises identifying a canonic representation of the truth table representation of the pivot function. 8. The method of claim 6 further comprising condensing the canonic representation to obtain a condensed representation of the pivot function. 9. The method of claim 6 further comprising specifying a condensed representation of each non-pivot function based on the selected input-variable configuration. 10. The method of claim 1 further comprising defining the graph that specifies the sub-network, wherein the graph is defined up to a particular threshold complexity. 11. A non-transitory computer readable medium storing a computer program for pre-tabulating sub-networks for execution, the computer program comprising sets of instructions for: specifying a plurality of sub-networks, each sub-network specified by a graph and a set of local functions, the graph for each sub-network comprising a plurality of nodes with each node representing a circuit element in the sub-network and having an associated function in the set of local functions, each node's associated local function representing a function performed by the circuit element represented by the node;identifying a set of output functions for each sub-network based on the set of local functions used to specify the sub-network;generating a parameter for each sub-network based on the identified set of output functions for each sub-network; andstoring the graph and the set of local functions of each sub-network in a storage structure indexed by the generated parameter of the sub-network. 12. The non-transitory computer readable medium of claim 11, wherein each parameter has a numerical value. 13. The non-transitory computer readable medium of claim 11, wherein the set of output functions for a particular sub-network comprises at least 3 output functions. 14. The non-transitory computer readable medium of claim 11, wherein a particular sub-network comprises multiple circuit elements. 15. The non-transitory computer readable medium of claim 14, wherein a synthesizer can independently analyze each circuit element. 16. The non-transitory computer readable medium of claim 14, wherein each circuit element of the particular sub-network has an output and each circuit element's output provides a result for one of output functions performed by the sub-network. 17. The non-transitory computer readable medium of claim 11, wherein the set of instructions for generating the parameter for the sub-network comprises a set of instructions for generating the parameter based on a symbolic representation of an output function. 18. The non-transitory computer readable medium of claim 17, wherein the symbolic representation is a binary decision diagram (BDD) representation. 19. The non-transitory computer readable medium of claim 17, wherein the symbolic representation is a truth table representation. 20. The non-transitory computer readable medium of claim 17, wherein the symbolic representation is a Boolean expression. 21. A system comprising: at least one processor for executing sets of instructions; anda memory storing a computer program for pre-tabulating sub-networks, the computer program comprising sets of instructions to be executed by the processor, the sets of instructions for: specifying a plurality of sub-networks, each sub-network specified by a graph and a set of local functions, the graph for each sub-network comprising a plurality of nodes with each node representing a circuit element in the sub-network and having an associated function in the set of local functions, each node's associated local function representing a function performed by the circuit element represented by the node;identifying a set of output functions for each sub-network based on the set of local functions used to specify the sub-network;generating a parameter for each sub-network based on the identified set of output functions for each sub-network; andstoring the graph and the set of local functions of each sub-network in a storage structure indexed by the generated parameter of the sub-network. 22. The system of claim 21, wherein the parameter is an index for storing the graph and the set of local functions of each sub-network in the storage structure. 23. The system of claim 21, wherein the parameter is a set of indices for storing the graph and the set of local functions of the sub-network in the storage structure. 24. The system of claim 21, wherein the parameter is a numerical index.