Abstract
In this paper, we address the problem of P-equivalence Boolean matching. We outline a formal framework that unifies some of the spectral- and 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, over a large set of randomly generated Boolean functions, our approach is up to five times faster than the main competitor on 20-variable input and scales better, allowing to match even larger components. Finally, as a representative set of Boolean functions that arise in practice, we considered multiplexers with three, four, and five selectors and functions extracted from the ISCAS85 benchmarks suite with a number of input variables up to 20. The reported performance results show that our approach allows us to halve the canonizing computation time.
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
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.