A Unified Approach to Canonical Form-based Boolean Matching

Abstract

In this paper, we face the problem of P-equivalence Boolean matching. We outline a formal framework that unifies some of the canonical form-based approaches to the problem. As a first major contribution, we show how these approaches are particular cases of a single generic algorithm, parametric with respect to a given linear transformation of the input function. As a second major contribution, we identify a linear transformation that can be used to significantly speed up Boolean matching with respect to the state of the art. Experimental results show that, on average, our approach is five times faster than the main competitor on 20-variables input functions, and scales better, allowing to match even larger components.

Publication
DAC ‘07 Proceedings of the 44th annual Design Automation Conference
Giovanni Agosta
Giovanni Agosta
Associate Professor

Giovanni Agosta, Associate Professor at Politecnico di Milano, holds a Laurea in Computer Engineering (2000) and a PhD in Information Technology (2004). His research focuses on compiler-computer architecture interaction, emphasizing performance, energy-efficiency, and security. He has authored 100+ papers, won multiple awards, and participated in 17 EU-funded projects.

Gerardo Pelosi
Gerardo Pelosi
Associate Professor

Gerardo Pelosi received the Laurea degree in Telecommunications Engineering in 2003 and the Ph.D. degree in Computer Engineering and Information Technology in 2007 from Politecnico di Milano. His research fields cover (1) the area of information security and privacy including access control models, models for encrypted data management in relational databases, and secure data outsourcing; (2) the area of applied cryptography including side-channel cryptanalysis, system-level attacks, and efficient hardware and software design of cryptographic algorithms; other research interests are in designing security support into computer architectures and the logic synthesis of combinatorial circuits.