Mathias Soeken | EPFL Graph Search

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Three-Input Gates for Logic Synthesis

Giovanni De Micheli, Dewmini Sudara Marakkalage, Heinz Riener, Mathias Soeken, Eleonora Testa

Most logic synthesis algorithms work on graph representations of logic functions with nodes associated with arbitrary logic expressions or simple logic functions and iteratively optimize such graphs. While recent multilevel logic synthesis efforts focused primarily on graphs with 2-input nodes such as AND and OR gates, the recently proposed paradigm of Majority-Inverter Graphs (MIGs) instead uses the 3-input Majority gate as the node function. As this technique proved to be a success, it is natural to ask: are there other 3-input gates better suited for logic synthesis? Motivated by this question, we investigate the relative advantages of 3-input gates as constituents of logic networks. We consider representative gates from each of the ten nondegenerate 3-input NPN classes and study how powerful they are at representing Boolean functions. Using SAT-based exact synthesis, we evaluate each 3-input gate using the minimum number of such gates (together with inverters) needed to synthesize all 4-input Boolean functions and a subset of frequent 5-input and 6-input Boolean functions. We show that the logic gate Dot(x,y, z) := x circle plus (z boolean OR xy) outperforms the rest in terms of expressive power. We further confirm this observation by showing that Dot-Inverter Graph representations are more than 14% smaller as compared to MIG representations of EPFL benchmarks.

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

A Logic Synthesis Toolbox for Reducing the Multiplicative Complexity in Logic Networks

Luca Gaetano Amarù, Giovanni De Micheli, Heinz Riener, Mathias Soeken, Eleonora Testa

Logic synthesis is a fundamental step in the realization of modern integrated circuits. It has traditionally been employed for the optimization of CMOS-based designs, as well as for emerging technologies and quantum computing. Recently, it found application in minimizing the number of AND gates in cryptography benchmarks represented as xor-and graphs (XAGs). The number of AND gates in an XAG, which is called the logic network's multiplicative complexity, plays a critical role in various cryptography and security protocols such as fully homomorphic encryption (FHE) and secure multi-party computation (MPC). Further, the number of AND gates is also important to assess the degree of vulnerability of a Boolean function, and influences the cost of techniques to protect against side-channel attacks. However, so far a complete logic synthesis flow for reducing the multiplicative complexity in logic networks did not exist or relied heavily on manual manipulations. In this paper, we present a logic synthesis toolbox for cryptography and security applications. The proposed tool consists of powerful transformations, namely resubstitution, refactoring, and rewriting, specifically designed to minimize the multiplicative complexity of an XAG. Our flow is fully automatic and achieves significant results over both EPFL benchmarks and cryptography circuits. We improve the best-known results for cryptography up to 59%, resulting in a normalized geometric mean of 0.82.

2020

A Spectral Algorithm for 3-valued Function Equivalence Classification

Mathias Soeken

Spectral techniques for Boolean and multiple-valued functions have been well studied and found to be useful in logic design and testing for conventional circuits. Spectral techniques also have potential application for reversible and quantum circuits. This paper addresses the classification of 3-valued functions into spectral translation equivalence classes. A transform algorithm is presented that determines the spectral translations to map a given function to the representative function for the equivalence class containing the given function. Using this algorithm we show, by exhaustive enumeration, that the 2-variable 3-valued functions partition into 11 equivalence classes. The number of 3-valued functions with 3 or more variables is very large, prohibiting exhaustive enumeration. We show that a search of 3-valued function 1-neighbourhoods yields 167,266 equivalence classes for 3 variables. The transform algorithm can be used for a higher number of variables to determine if two functions fall within the same equivalence class and, if they do, to find a sequence of spectral translations to map one to the other.

OLD CITY PUBLISHING INC2020