Publications related to Structural Rewriting in XOR-Majority Graphs

Scalable Logic Rewriting Using Don’t Cares

Giovanni De Micheli, Alessandro Tempia Calvino

Logic rewriting is a powerful optimization technique that replaces small sections of a Boolean network with better implementations. Typically, exact synthesis is used to compute optimum replacement on-the-fly, with possible support for Boolean don't cares. ...

2024

Orthologic with Axioms

Viktor Kuncak, Simon Guilloud

We study the proof theory and algorithms for orthologic, a logical system based on ortholattices, which have shown practical relevance in simplification and normalization of verification conditions. Ortholattices weaken Boolean algebras while having polyno ...

Association for Computing Machinery2024

LISA – A Modern Proof System

Viktor Kuncak, Simon Guilloud, Sankalp Gambhir

We present LISA, a proof system and proof assistant for constructing proofs in schematic first-order logic and axiomatic set theory. The logical kernel of the system is a proof checker for first-order logic with equality and schematic predicate and fun ...

Dagstuhl, Germany, Schloss Dagstuhl - Leibniz-Zentrum fur Informatik2023

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Viktor Kuncak, Simon Guilloud

We present a quasilinear time algorithm to decide the word problem on a natural algebraic structures we call orthocomplemented bisemilattices, a subtheory of boolean algebra. We use as a base a variation of Hopcroft, Ullman and Aho algorithm for tree isomo ...

Springer2022

Further Results on Efficient Implementations of Block Cipher Linear Layers

Subhadeep Banik

At the FSE conference of ToSC 2018, Kranz et al. presented their results on shortest linear programs for the linear layers of several well known block ciphers in literature. Shortest linear programs are essentially the minimum number of 2-input xor gates r ...

2021

Preserving Self-Duality During Logic Synthesis for Emerging Reconfigurable Nanotechnologies

Giovanni De Micheli, Heinz Riener, Shubham Rai, Akash Kumar

Emerging reconfigurable nanotechnologies allow the implementation of self-dual functions with a fewer number of transistors as compared to traditional CMOS technologies. To achieve better area results for Reconfigurable Field-Effect Transistors (RFET)-base ...

IEEE2021

Three-Input Gates for Logic Synthesis

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

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 ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

Data Structures and Algorithms for Logic Synthesis in Advanced Technologies

Eleonora Testa

Logic synthesis is a key component of digital design and modern EDA tools; it is thus an essential instrument for the design of leading-edge chips and to push the limits of their performance. In the last decades, the electronic circuits community has evolv ...

EPFL2020

Advanced Functional Decomposition Using Majority and Its Applications

Giovanni De Micheli, Mathias Soeken, Zhufei Chu

Typical operators for the decomposition of Boolean functions in state-of-the-art algorithms are AND, exclusive-OR (XOR), and the 2-to-1 multiplexer (MUX). We propose a logic decomposition algorithm that uses the majority-of-three (MAJ) operation. Such a de ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Programmable Logic Gates Based On Tunable Multistable Mechanisms

Simon Nessim Henein, Ilan Vardi, Mohamed Gamal Abdelrahman Ahmed Zanaty, Hubert Pierre-Marie Benoît Schneegans

Binary logic operations are the building blocks of computing machines. In this paper, we present a new programmable binary logic gate based on programmable multistable mechanisms (PMM), which are multistable structures whose stability behavior depends on m ...

AMER SOC MECHANICAL ENGINEERS2020

More Results on Shortest Linear Programs

Subhadeep Banik

At the FSE conference of ToSC 2018, Kranz et al. presented their results on shortest linear programs for the linear layers of several well known block ciphers in literature. Shortest linear programs are essentially the minimum number of 2-input xor gates r ...

2019

Exact Synthesis of Boolean Functions in Majority-of-five Forms

Giovanni De Micheli, Winston Jason Haaswijk, Mathias Soeken, Zhufei Chu

Recent studies show that majority-based logic synthesis is beneficial for both traditional and nanotechnology digital designs. However, most of the existing synthesis algorithms for majority logic generate majority-of-three (M-3) networks. The optimization ...

IEEE2019

Size Optimization of MIGs with an Application to QCA and STMG Technologies

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

Majority-inverter graphs (MIGs) are a logic representation with remarkable algebraic and Boolean properties that enable efficient logic optimizations beyond the capabilities of traditional logic representations. Further, since many nano-emerging technologi ...

ASSOC COMPUTING MACHINERY2018

Nonsilicon, Non-von Neumann Computing—Part I

Giovanni De Micheli

Majority-inverter graphs (MIGs) are a logic representation with remarkable algebraic and Boolean properties that enable efficient logic optimizations beyond the capabilities of traditional logic representations. Further, since many nano-emerging technologi ...

IEE2018

Functional Decomposition Using Majority

Giovanni De Micheli, Mathias Soeken, Zhufei Chu

Typical operators for the decomposition of Boolean functions in state-of-the-art algorithms are AND, exclusive-OR (XOR), and a 2-to-1 multiplexer (MUX). We propose a logic decomposition algorithm that uses the majority-of-three (MAJ) operation. Such decomp ...

IEEE2018

Mapping Monotone Boolean Functions into Majority

Giovanni De Micheli, Luca Gaetano Amarù, Winston Jason Haaswijk, Eleonora Testa, Mathias Soeken

We consider the problem of decomposing monotone Boolean functions into majority-of-three operations, with a particular focus on decomposing the majority-n function. When targeting monotone Boolean functions, Shannon's expansion can be expressed by a single ...

2018

Exact Synthesis of Majority-Inverter Graphs and Its Applications

Giovanni De Micheli, Luca Gaetano Amarù, Pierre-Emmanuel Julien Marc Gaillardon, Mathias Soeken

We 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 varia ...

Ieee-Inst Electrical Electronics Engineers Inc2017

A Novel Basis for Logic Rewriting

Giovanni De Micheli, Luca Gaetano Amarù, Pierre-Emmanuel Julien Marc Gaillardon, Winston Jason Haaswijk, Mathias Soeken

Given a set of logic primitives and a Boolean function, exact synthesis finds the optimum representation (e.g., depth or size) of the function in terms of the primitives. Due to its high computational complexity, the use of exact synthesis is limite ...

Ieee2017

Improving Circuit Mapping Performance Through MIG-based Synthesis for Carry Chains

Paolo Ienne, Giovanni De Micheli, Ana Petkovska, Grace Zgheib, Luca Gaetano Amarù, Xifan Tang, Pierre-Emmanuel Julien Marc Gaillardon, Mathias Soeken, Zhufei Chu

Hard-wired carry chains in FPGAs are designed to improve efficiency of important arithmetic primitives. Although they are proven to be effective for arithmetic-rich functions, there are very few studies on the optimization opportunities of carry chains for ...

ACM2017

Busy Man’s Synthesis: Combinational Delay Optimization With SAT

Giovanni De Micheli, Mathias Soeken

Boolean SAT solving can be used to find a minimum- size logic network for a given small Boolean function. This paper extends the SAT formulation to find a minimum-size network under delay constraints. Delay constraints are given in terms of input arrival t ...

Ieee2017