Timing-driven N-way decomposition

ABSTRACT

Logic decomposition has been extensively used to optimize the worst-case delay and the area in the technology independent phase. Bi-decomposition is one of the state-of-art techniques to reduce the depth of the netlist due to the affordable computational cost. We present a novel n-way decomposition technique that improves bi-decomposition. The problem of decomposition is formulated as a Boolean relation which captures a larger set of possible solutions compared to bi-decomposition. The solution obtained from the Boolean relation improves the delay with near-zero cost in area. As it is shown on the experimental results, a considerable improvement is achieved on large netlists and even larger depending on which technology mapper is used.

REFERENCES

• 1: D. Bochmann , F. Dresig , B. Steinbach, A new decomposition method for multilevel circuit design, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
• 2: S. Yamashita, H. Sawada, and A. Nagoya, "New methods to find optimal non-disjoint bi-decompositions," in Proc. ACM/IEEE Design Automation Conference, 1998, pp. 59--68.
• 3: Congguang Yang , Maciej Ciesielski , Vigyan Singhal, BDS: a BDD-based logic optimization system, Proceedings of the 37th Annual Design Automation Conference, p.92-97, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337323]
• 4: Alan Mishchenko , Bernd Steinbach , Marek Perkowski, An algorithm for bi-decomposition of logic functions, Proceedings of the 38th annual Design Automation Conference, p.103-108, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378353]
• 5: B. Steinback and A. Wereszczynski, "Synthesis of multi-level circuits using exor-gates," in Proc. of Reed-Muller'95, 1995, pp. 161--168.
• 6: Y.-Y. Lian and Y.-L. Lin, "Layout-based logic decomposition for timing optimization," in Proc. of Asia and South Pacific Design Automation Conference, 1999, pp. 229--232.
• 7: J. Cortadella, "Timing-driven logic bi-decomposition," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 22, no. 6, pp. 675--685, June 2003.
• 8: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 9: D. Baneres, J. Cortadella, and M. Kishinevsky, "A recursive paradigm to solve
• 10: David Baneres , Jordi Cortadella , Mike Kishinevsky, A Recursive Paradigm to Solve Boolean Relations, IEEE Transactions on Computers, v.58 n.4, p.512-527, April 2009 [doi>10.1109/TC.2008.165]
• 11: K. J. Singh, A. Wang, R. Brayton, and A. Sangiovanni-Vincentelli, "Timing optimization of combinational logic," in Proc. Int. Conf. Computer-Aided Design (ICCAD), Nov. 1988, pp. 282--285.
• 12: Richard L. Rudell , Alberto Sangiovanni-Vincentelli, Logic synthesis for vlsi design, University of California, Berkeley, 1989
• 13: Hervé J. Touati , Cho W. Moon , Robert K. Brayton , Albert Wang, Performance-oriented technology mapping, Proceedings of the sixth MIT conference on Advanced research in VLSI, p.79-97, March 1990, Boston, Massachusetts, United States
• 14: S. Chatterjee , A. Mishchenko , R. Brayton , X. Wang , T. Kam, Reducing structural bias in technology mapping, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.519-526, November 06-10, 2005, San Jose, CA

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design

Keywords:
decomposition, logic design, timing optimization