Spectral Techniques for Technology Mapping

Abstract

Technology mapping is the crucial step in logic synthesis where technology dependent optimizations take place. The matching phase of a technology mapping algorithm is generally considered the most computationally intensive task, because it is called on repeatedly. In this work, we investigate applications of spectral techniques in doing matching. In particular, we present an algorithm that will detect NPN-equivalent Boolean functions. We show that while generating the spectra for Boolean functions may be expensive, this algorithm offers significant pruning of the search space and is simple to implement. The algorithm is implemented as part of the Specter technology mapper, and results are compared to other Boolean matching techniques.