Optimizing The Ordering Of The Inputs To Large Commutative-Associative Trees Of Logic Gates
AssigneeSynopsys, Inc.
InventorsBogdan Craciun, Brent Gregory, Jaime Wong, William Clark Naylor, JR.
Life of this patent
Estimating the term…
Abstract
A method of optimizing a netlist for a circuit comprising identifying a logic tree with a single output and a plurality of interchangeable inputs, and calculate the optimal permutation of the plurality of inputs. The method further comprising modify the netlist based on the optimal permutation, and optimizing the modified netlist.
Claims20
A method of optimizing ordering inputs to large commutative-associative trees of a plurality of logic gates when designing an integrated circuit comprising:
- building a plurality of pin arrays by traversing a netlist representation of the integrated circuit from a plurality of potential root pins associated with plurality of logic gates through fan-in;
- collecting interchangeable input pins into a wave-front set until a stop condition is encountered;
- building a bipartite graph to find a permutation of connections into the input pins of a selected pin array, wherein the permutation is based on a cost analysis;
- modifying the netlist based on the permutation;
- and
- optimizing the modified netlist.
A method of designing an integrated circuit comprising:
- receiving a netlist representation of an integrated circuit, including a plurality of pins;
- building a plurality of pin arrays by traversing the netlist representation from a plurality of potential root pins associated with plurality of logic gates;
- selecting a pin array and collecting interchangeable input pins until a stop condition is encountered;
- building a bipartite graph to find a permutation of connections into the input pins of the selected pin array, wherein the permutation is based on a cost analysis;
- modifying the netlist representation based on the permutation;
- and
- optimizing the modified netlist.
A system of designing an integrated circuit comprising:
- a memory to receive and store a netlist representation of an integrated circuit, including a plurality of pins;
- a processor to implement a building logic to traverse the netlist representation from a plurality of potential root pins associated with plurality of logic gates and build a plurality of pin arrays;
- the processor to implement a graph logic to select a pin array and collect interchangeable input pins until a stop condition is encountered and build a bipartite graph to find a permutation of connections into the input pins of the selected pin array, wherein the permutation is based on a cost analysis;
- and
- the processor to implement a netlist logic to modify the netlist representation based on the permutation and optimize the modified netlist;
- and
- the memory to store optimized modified netlist.
Dependencies are inferred from the claim text.