Efficient Boolean function matching
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Efficient algorithms for performing the matching step in technology mapping are proposed. The main result is an algorithm for matching under input negations that takes time polynomial in the size of the BDDs representing the functions to be matched. This algorithm is the basis for efficient methods for matching under permutations, bridging and constant inputs. A simple mapper based on the algorithms was implemented and tested on a suite of combinational circuits. Using the Actel type 1 mother cell, the mapper required an average of 8.5% fewer cells than mispga. When integrated into a more sophisticated technology mapper, the matching algorithms could provide even better performance.Keywords
This publication has 5 references indexed in Scilit:
- Logic synthesis for programmable gate arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Efficient implementation of a BDD packagePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Technology mapping using Boolean matching and don't care setsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Technology mapping for electrically programmable gate arraysPublished by Association for Computing Machinery (ACM) ,1991
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986