A new method towards achieving global optimality in technology mapping

ABSTRACT

This paper presents a new method for covering a Boolean network by library cells. In this method, matches are classified according to their properties. Some matches are selected unconditionally into a cover and the remaining nodes are divided into independent portions. Then, a match compatibility graph (MCG) is constructed for each portion and an optimum cover is found for it using the MCG. Thus, our method finds an efficient and closer to optimum cover for the complete network.

REFERENCES

• 1: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 2: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• 3: E. Detjens,. G. Grannot, R. Rundell, A. San~iovanni, and A. Wang, "Technology Mapping in MIS," Proc. ICCAD, pp. 116-119, 1987.
• 4: R. Bergamaschi, "SKOL: A System for Logic Synthesis and Technology Mapping," IEEE Trans. Computer-Aided Design, vol. CAD-10, pp. 1342-1355, Nov. 1991.
• 5: K. ChamthatT and M. Pedtam, "Computing the Area versus Delay Trade-Off Curves in Technology Mapping, Trads. Computer-Aided Design, vol. CAD-14, pp. 1480- 1489, De~. 1995.
• 6: David Gregory , Karen Bartlett , Aart de Geus , Gary Hachtel, SOCRATES: a system for automatically synthesizing and optimizing combinational logic, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.79-85, July 1986, Las Vegas, Nevada, United States
• 7: M. Kahrsb "Matching a Parts Library in a Silicon Compiler, Proc. ICCAD, pp. 169-171, I987.
• 8: F. Brglez and H. Fujiwara, "A Neutral Netlist of 10 Combinational Benchmark Circuits and a Target Translator in Fortran," Proc. ISCAS'85, 1985.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Experimentation

Keywords:
Combinational Logic Synthesis, Technology Mapping, Optimality.