Cell Generator-Based Technology Mapping by Constructive Tree-Matching and Dynamic Covering

Technology mapping is the final step of logic synthesis which consists of mapping an optimized technologyindependent logic network representation into a circuit realization in a given technology. An important componentof the technology mapping problem is the identification of feasible library cells for the realization of the logicoperators in the logic tree. There are two main classes of such matching algorithms. Library-based matchingalgorithms [1–4] require that all available physical components be represented explicitly in a pattern library.Sections of the logic network are then matched against this pattern list for the identification of suitablecomponents. In contrast, cell generator-based matching techniques [6–8] accept feasibility constraints on thecomplexity and quantity of physical components according to limits imposed by the target technology or thecapabilities of the cell generator. Hence, individual patterns are not stored in a library and are instead generatedas needed. In this paper, we present a new cell generator-based constructive matching algorithm. Because thealgorithm builds matched patterns incrementally, very large cell families can be accommodated using time andspace resources that are proportional to the size of the largest feasible cell pattern and not the size of the libraryof patterns as would be the case for library-based approaches. Also, whereas existing cell generator-basedmatching techniques combine the tasks of matching (identification) and covering (selection), constructive matchingprovides more flexibility by not restricting the covering phase. Empirical results demonstrate the increased qualityof the technology-mapped circuits when larger cells are available