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.

REFERENCES

• 1: Afshin Abdollahi , Massoud Pedram, A new canonical form for fast boolean matching in logic synthesis and verification, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065681]
• 2: Ken G. Beauchamp. Applications of Walsh and Related Functions. Academic Press, 1984.
• 3: Luca Benini , Giovanni De Micheli, A survey of Boolean matching techniques for library binding, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.3, p.193-226, July 1997 [doi>10.1145/264995.264996]
• 4: J. R. Burch , D. E. Long, Efficient Boolean function matching, 1992 IEEE/ACM international conference proceedings on Computer-aided design, p.408-411, December 1992, Santa Clara, California, United States
• 5: Donald Chai , Andreas Kuehlmann, Building a better Boolean matcher and symmetry detector, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 6: Jovanka Ciric and Carl Sechen. Efficient canonical form for Boolean matching of complex functions in large libraries. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 22(5):535--544, May 2003.
• 7: Debatosh Debnath , Tsutomu Sasao, Efficient computation of canonical form for Boolean matching in large libraries, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan
• 8: C. R. Edwards , S. L. Hurst, A Digital Synthesis Procedure Under Function Symmetries and Mapping Methods, IEEE Transactions on Computers, v.27 n.11, p.985-997, November 1978 [doi>10.1109/TC.1978.1674988]
• 9: Serge Lang. Linear Algebra. Addison Wesley, 1966.
• 10: Janett Mohnke , Paul Molitor , Sharad Malik, Limits of using signatures for permutation independent Boolean comparison, Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), p.74-es, August 29-September 01, 1995, Makuhari, Massa, Chiba, Japan [doi>10.1145/224818.224955]
• 11: Fabio Somenzi. CUDD: CU Decision Diagram Package. http://vlsi.colorado.edu/fabio/CUDD/.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

General Terms:
Design

Keywords:
Boolean matching, logic synthesis