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.

A Unified Approach to Canonical Form-based Boolean Matching

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

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.
DAC '07 Proceedings of the 44th annual Design Automation Conference
9781595936271
INF
File in questo prodotto:
File Dimensione Formato  
p841-agosta.pdf

Accesso riservato

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 149.94 kB
Formato Adobe PDF
149.94 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/240745
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 7
social impact