IEEE/ACM International Conference on Computer-Aided Design · 1992 · 63 citations · 10 references
EngineeringComputer EngineeringComputer ScienceAlgorithmsComputer ArchitectureDesign AutomationBoolean AlgebraCircuit ComplexityCombinational Logic DescriptionDigital Logic DesignLogic SynthesisLookup TablesBoolean Function RepresentationBoolean Logic OptimizationBoolean MatchingCombinational Logic SynthesisMatchingMatching AlgorithmsPolynomial Time ComplexityTechnology Mapping For Combinational Logic
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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
10
Graph-Based Algorithms for Boolean Function Manipulation
Bryant · IEEE Transactions on Computers · 1986 · 8.9K citations · Full text
Efficient implementation of a BDD package
Karl S. Brace, Richard Rudell, Randal E. Bryant · 1990 · 1.1K citations · Full text
Logic synthesis for programmable gate arrays
Rajeev Murgai, Yoshihito Nishizaki, Narendra Shenoy et al. · 1990 · 194 citations