TGSyn: Transformer Guided Topology-based Exact Synthesis for Majority-Inverter Graphs

Exact synthesis is a method to find an optimal circuit that meets the specification. SAT-based exact synthesis is commonly used for its ability to allow for a more versatile approach to addressing synthesis requirements. However, the runtime of SAT-based exact synthesis is very long and unpredictable to check all possible structures. Recently, topologybased exact synthesis methods have been studied to reduce the runtime of exact synthesis, where all structures are classified into sub-classes of topologies and each sub-class is checked using a simpler Conjunctive Normal Form separately. There is a freedom on the order of topologies to be checked, and we found that the Transformer is effective to decide the order. This paper proposes a Transformer-guided topology-based exact synthesis method (TGSyn) to achieve better time efficiency. A Transformer model is used to predict the success probability of synthesis for each topology in topology-based exact synthesis, and the order is decided based on the predicted probability to accelerate the synthesis process. The proposed Transformer-based model archives 98.56% of top-15 categorical accuracy. To evaluate the TGSyn, we used subgraphs in MIG with 3 to 5 inputs in EPFL and ISCAS'85 benchmarks using cut enumeration. The TGSyn reduces the runtime of the exact synthesis of 19,148 circuits by 64.02% compared with a method without Transformer guiding.