000224342 001__ 224342
000224342 005__ 20190317000615.0
000224342 0247_ $$2doi$$a10.1109/TCAD.2017.2664059
000224342 022__ $$a0028-0070
000224342 02470 $$2ISI$$a000413332700007
000224342 037__ $$aARTICLE
000224342 245__ $$aExact Synthesis of Majority-Inverter Graphs and Its Applications
000224342 260__ $$bIeee-Inst Electrical Electronics Engineers Inc$$c2017$$aPiscataway
000224342 269__ $$a2017
000224342 300__ $$a14
000224342 336__ $$aJournal Articles
000224342 520__ $$aWe propose effective algorithms for exact synthesis of Boolean logic networks using satisfiability modulo theories (SMT) solvers. Since exact synthesis is a difficult problem, it can only be applied efficiently to very small functions, having up to 6 variables. Key in our approach is to use majority-inverter graphs as underlying logic representation as they are simple (homogeneous logic representation) and expressive (contain And/Or-inverter graphs) at the same time. This has a positive impact on the problem formulation: it simplifies the encoding as SMT constraints and also allows for various techniques to break symmetries in the search space due to the regular data structure. Our algorithm optimizes with respect to the MIG’s size or depth and uses different ways to encode the problem and several methods to improve solving time, with symmetry breaking techniques being the most effective ones. We discuss several applications of exact synthesis and motivate them by experiments on a set of large arithmetic benchmarks. Using the proposed techniques, we are able to improve both area and delay after LUT-based technology mapping beyond the current results achieved by state-of-the-art logic synthesis algorithms.
000224342 6531_ $$alogic gates
000224342 6531_ $$aencoding
000224342 6531_ $$ainverters
000224342 6531_ $$aoptimization
000224342 6531_ $$aBoolean functions
000224342 6531_ $$abenchmark testing
000224342 6531_ $$aheuristic algorithms
000224342 700__ $$0249604$$g263922$$aSoeken, Mathias
000224342 700__ $$aAmaru, Luca
000224342 700__ $$aGaillardon, Pierre-Emmanuel
000224342 700__ $$0240269$$g167918$$aDe Micheli, Giovanni
000224342 773__ $$j36$$tIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems$$k11$$q1842-1855
000224342 8564_ $$uhttps://infoscience.epfl.ch/record/224342/files/07842552.pdf$$zn/a$$s1224919$$yn/a
000224342 909C0 $$xU11140$$0252283$$pLSI1
000224342 909CO $$particle$$ooai:infoscience.tind.io:224342$$qGLOBAL_SET$$pSTI$$pIC
000224342 917Z8 $$x112915
000224342 917Z8 $$x112915
000224342 917Z8 $$x112915
000224342 937__ $$aEPFL-ARTICLE-224342
000224342 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000224342 980__ $$aARTICLE