Scalable boolean methods in a modern synthesis flow
Techniques and systems for optimizing a logic network are described. Some embodiments automatically identify scenarios where Boolean methods are best driven by truth tables, binary decision diagrams (BDDs) or satisfiability (SAT). Some embodiments use circuit partitioning techniques that are based on hash-tables and topological sorting, and that are capable of grouping nodes with high simplification likelihood and still are able to efficiently scale to large circuits. Some embodiments feature a generalized resubstitution framework based on computing, and implementing, the Boolean difference between two nodes. Some embodiments include enhancements to (i) gradient-based and-inverter-graph (AIG) optimization, (ii) heterogeneous elimination for kerneling, and (iii) revisitation of maximum set of permissible functions (MSPF) computation with BDDs.
1. A non-transitory computer-readable storage medium comprising stored instructions, which when executed by a processor, cause the processor to:
analyze a set of characteristics of the logic network, the set of characteristics including a count of primary inputs of the logic network;
select a logic optimization engine based on said analyzing, the logic optimization engine being selected from a group comprising a truth-table based logic optimization engine, a binary decision diagram (BDD) based logic optimization engine, and a satisfiability (SAT) based logic optimization engine; and
optimize the logic network by using the logic optimization engine.
2. The non-transitory computer-readable storage medium of claim 1 , wherein the set of characteristics includes a depth of an and-inverter-graph (AIG) decomposition of the logic network.
3. The non-transitory computer-readable storage medium of claim 1 , wherein the set of characteristics includes a ratio between a count of internal nodes of the logic network and the count of primary inputs of the logic network.
4. The non-transitory computer-readable storage medium of claim 1 , wherein the set of characteristics includes a monotonicity characteristic that indicates whether or not the logic network shows monotonicity.
5. The non-transitory computer-readable storage medium of claim 1 , wherein the set of characteristics includes a symmetry characteristic that indicates whether or not the logic network shows symmetry.
6. The non-transitory computer-readable storage medium of claim 1 , wherein said selecting the logic optimization engine comprises selecting the truth-table based logic optimization engine when the count of primary inputs of the logic network is less than a first predetermined value.
7. The non-transitory computer-readable storage medium of claim 6 , wherein said selecting the logic optimization engine comprises selecting the BDD based logic optimization engine when the count of primary inputs of the logic network is greater than or equal to a first predetermined value, but less than a second predetermined value.
8. The non-transitory computer-readable storage medium of claim 7 , wherein said selecting the logic optimization engine comprises selecting the SAT based logic optimization engine when the count of primary inputs of the logic network is greater than or equal to the second predetermined value.
9. A method for optimizing a logic network, the method comprising:
automatically analyzing, by a processor, a set of characteristics of the logic network, the set of characteristics including a count of primary inputs of the logic network;
automatically selecting a logic optimization engine based on said analyzing, the logic optimization engine being selected from a group comprising a truth-table based logic optimization engine, a binary decision diagram (BDD) based logic optimization engine, and a satisfiability (SAT) based logic optimization engine; and
automatically optimizing the logic network by using the logic optimization engine.
10. The method of claim 9 , wherein the set of characteristics includes a depth of an and-inverter-graph (AIG) decomposition of the logic network.
11. The method of claim 9 , wherein the set of characteristics includes a ratio between a count of internal nodes of the logic network and the count of primary inputs of the logic network.
12. The method of claim 9 , wherein the set of characteristics includes a monotonicity characteristic that indicates whether or not the logic network shows monotonicity.
13. The method of claim 9 , wherein the set of characteristics includes a symmetry characteristic that indicates whether or not the logic network shows symmetry.
14. The method of claim 9 , wherein said selecting the logic optimization engine comprises selecting the truth-table based logic optimization engine when the count of primary inputs of the logic network is less than a first predetermined value.
15. The method of claim 14 , wherein said selecting the logic optimization engine comprises selecting the BDD based logic optimization engine when the count of primary inputs of the logic network is greater than or equal to a first predetermined value, but less than a second predetermined value.
16. The method of claim 15 , wherein said selecting the logic optimization engine comprises selecting the SAT based logic optimization engine when the count of primary inputs of the logic network is greater than or equal to the second predetermined value.
17. A system comprising:
a memory storing instructions; and
a processor, coupled with the memory and to execute the instructions, the instructions when executed cause the processor to:
analyze a set of characteristics of the logic network, the set of characteristics including a count of primary inputs of the logic network;
select a logic optimization engine based on said analyzing, the logic optimization engine being selected from a group comprising a truth-table based logic optimization engine, a binary decision diagram (BDD) based logic optimization engine, and a satisfiability (SAT) based logic optimization engine; and
optimize the logic network by using the logic optimization engine.
18. The system of claim 17 , wherein the set of characteristics includes a depth of an and-inverter-graph (AIG) decomposition of the logic network.
19. The system of claim 17 , wherein the set of characteristics includes a ratio between a count of internal nodes of the logic network and the count of primary inputs of the logic network.
20. The system of claim 17 , wherein the set of characteristics includes a monotonicity characteristic that indicates whether or not the logic network shows monotonicity.