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.

A Transform-Parametric Approach to Boolean Matching

AGOSTA, GIOVANNI;BRUSCHI, FRANCESCO;PELOSI, GERARDO;SCIUTO, DONATELLA
2009

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.
File in questo prodotto:
File Dimensione Formato  
boolean_matching.pdf

Accesso riservato

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 295.1 kB
Formato Adobe PDF
295.1 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/544104
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 11
social impact