A new min-cut placement algorithm for timing assurance layout design meeting net length constraint

ABSTRACT

This paper presents a new min-cut placement algorithm for timing assurance layout design. When critical nets are given net length constraints, the proposed algorithm can place cells so that the constraints may be met. This algorithm is built into the layout system for gate arrays called GALOP [1] and has been successfully applied to clock skew control of an ECL 12K-gate gate array.

REFERENCES

• 1: M.Terai, "A Method of Improving the Terminal Assignment in the Channel Routing for Gate Arrays," IEEE Trans. Computer-Aided Des., vol. CAD-4, 1985, pp. 329-336.
• 2: A. E. Dunlop , V. D. Agrawal , D. N. Deutsch , M. F. Jukl , P. Kozak , M. Wiesel, Chip layout optimization using critical path weighting, Proceedings of the 21st conference on Design automation, p.133-136, June 25-27, 1984, Albuquerque, New Mexico, United States
• 3: Michael Burstein , Mary N. Youssef, Timing influenced layout design, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.124-130, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317845]
• 4: Yasushi Ogawa , Tatsuki Ishii , Yoichi Shiraishi , Hidekazu Terai , Tokinori Kozawa , Kyoji Yuyama , Kyoji Chiba, Efficient placement algorithms optimizing delay for high-speed ECL masterslice LSIs, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.404-410, July 1986, Las Vegas, Nevada, United States
• 5: S.Teig, R.L.Smith and J.Seaton,"I'iming-Driven Layout of Cell-Based ICs," VLSI System Design, May I986, pp. 63-73.
• 6: P.S.Hauge, R.Nair and E.J.Yoffa, "Circuit Placement for Predictable Performance," Proc. IEEE ICCAD, 1987, pp.88-91.
• 7: M. A. B. Jackson , E. S. Kuh, Performance-driven placement of cell based IC's, Proceedings of the 26th ACM/IEEE conference on Design automation, p.370-375, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74444]
• 8: M.A.Breuer, "Min-Cut Placement," J. Design Automation & Fault-Tolerant Computing, vol.1, no.4, 1977, pp.343-362.
• 9: Hiroshi Shiraishi , Fumiyasu Hirose, Efficient placement and routing techniques for master slice LSI, Proceedings of the 17th conference on Design automation, p.458-464, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804570]
• 10: B.W.Kemighan and S.Lin, "An Efficient Procedure for Partitioning Graphs," Bell Syst. Tech. J, Feb. 1970, pp. 291-307
• 11: T.Nishimura, et.at., "A Bipolar 18K-Gate Variable Size Cell Masterslice," IEEE J. Solid-State Circuits, vol. SC-21, 1986, pp. 727-732.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.0 General
      B.7.2 Design Aids
          Subjects: Placement and routing; Layout

General Terms:
Design