Efficient Boolean matching in technology mapping with very large cell libraries

A new method for quickly retrieving Boolean functions from an arbitrarily large library is introduced. The method relies on signature calculation for variables of Boolean functions. Signatures induce an ordering of the variables which is used to construct a BDD (binary decision diagram). The potential of the method is demonstrated by an application in technology mapping for Actel FPGAs (field programmable gate arrays). The proposed approach can handle any kind of gate in the library. Experimental results show that libraries 3 to 4 orders of magnitude larger than those previously used can be dealt with efficiently.