Automated layout generation using gate matrix approach

ABSTRACT

This paper presents a software system ALSUGMA for automated gate matrix layout generation. Its structured Net-List and Realization Matrix models which are different from previous interval graph approach are introduced. Algorithms to minimize and realize the gate matrix layout are also presented with examples. Empirical results showed good performance in terms of both speed and layout quality. Folding technique for such layout style is also introduced.

REFERENCES

• 1: A. D. Lopez and H. F. S. Law, "A dense gate matrix layout method for MOS VLSI," IEEE Trans. Electron Devices, pp. 1671-1675, Aug. 1980.
• 2: A. Weinberger, "Large scale integration of MOS complex logic : A Layout Method," IEEE J. Solid State Circuits, vol. SC-2, pp. 182-190, Dec. 1967.
• 3: S. M. Kang, R. H. Krambeck~ H. F. S. Law and A. D. Lopez, "Gate matrix layout of random control logic in a 32-bit CMOS CPU chip adaptable to evolving logic design," IEEE Trans. on CAD, vol. CAD-2, pp. 18-29, Jan. 1983.
• 4: H. F. S. Law, "Gate matrix : a practical, stylized approach to symbolic layout," VLSI design, pp.49-59, Sep. 1983
• 5: O. Wing, "Automated gate matrix layout," in Proc. 1982 IEEE Int. Symp. Circuits and Systems, Rome, Italy, pp. 681-685, 1982.
• 6: T. Ohtsuki, H. Mori, E. S. Kuh, T. Kashiwabara and T. Fujisawa, "One dimensional logic gate assignment and interval graphs, "IEEE Trans. Circuits Syst., vol. CAS-26, pp. 675-684, Sep. 1979.
• 7: T. Kashiwabara and T. Fujisawa, "An NP- complete problem on interval graph," Proc. 1979 ISCAS, pp. 82-83, 1979.
• 8: O. Wing, "Interval graph based gate matrix layout," in Proc. 1983 IEEE Int. Conf. CAD, Santa Clara, CA, pp. 84-85, Sep. 1983.
• 9: J. T. Li, "Algorithms for gate matrix layout," in Proc. 1983 IEEE Int. Symp. Circuits Syst., Newport Beach, CA, pp. 1013- 1016, 1983.
• 10: O, Wing, S. Huang and R. Wang, "Gate Matrix Layout," IEEE Trans. on CAD, vol. CAD-4, pp. 220-231, July 1985.
• 11: M. L. Yu and W. Kubitz, "A VLSI cell synthesizer with structural constraint considerations," Proc. IEEE Int. Conf. on CAD, pp.58-60, 1985.
• 12: D. K. Hwang, W. K. Fuchs, and S. M. Kang, "An efficient approach to gate matrix layout," Proc.IEEE Int. Conf. on CAD, pp.312-315, 1986.
• 13: H. W. Leong, "A new algorithm for gate matrix layout," Proc. IEEE Int. Conf. on CAD, pp.316-319, 1986.
• 14: S. Huang and O. Wing, "Improved gate matrix layout," Proc. IEEE Int. Conf. on CAD, pp.320-323, 1986.
• 15: K. Nakatani, T. Fujii, T. Kikuno, and N. Yoshida, "A heuristic algorithm for gate matrix layout," Proc. IEEE Int. Conf. on CAD, pp.324-327, 1986.
• 16: N. Deo, M. S. Krishnamoorthy, and M. A. Langston, "Exact and approximate solutions for the gate matrix layout problem," IEEE Trans. on CAD, Vol. CAD-6, pp.79-84, Jan. 1987.
• 17: Y. C. Chang, "Design and Implementation of an Automatic Layout System - Using Gate Matrix Approach," Master thesis at National Chiao Tung University, Insistute of Computer Engineering, R.O.C., 1985.
• 18: Y. C. Chang, S. C. Chang, and L. H. Hsu, "Automatic gate matrix layout algorithms," Proc. Int. Computer Symp., Tainan, Taiwan, R.O.C. pp.1549-1557, Dec. 1986.
• 19: M. C. Golumbic, Algorithmic Graph Theory and Perfect Graph, Academic Press, New York, 1980.
• 20: Akihiro Hashimoto , James Stevens, Wire routing by optimizing channel assignment within large apertures, Proceedings of the 8th workshop on Design automation, p.155-169, June 28-30, 1971, Atlantic City, New Jersey, United States [doi>10.1145/800158.805069]
• 21: S. C. Chang, "Gate matrix folding," Master thesis at National Chiao Tung University, Insistute of Computer Engineering, R.O.C., 1987.
• 22: J. R. Egan and C. L. Liu, "Bipartite folding and partition of a PLA," IEEE Trans. Computer Aided Design, Vol. CAD-3, no. 3, pp.191-199, July 1984.
• 23: Y. S. Kuo and C. Chen, "A heuristic algorithm for PLA block folding," Information Science and Engineering, Academia Sinica, R.O.C., Vol. 2, no. i, pp. 43-57, Jan. 1986.
• 24: M. Morris Mano, Digital Logic and Computer Design, Prentice Hall PTR, Upper Saddle River, NJ, 1979
• 25: Y. Z. Liao and C. K. Wong, "An algorithm to compact a VLSI symbolic layout with mixed constraints," IEEE Trans. on CAD, Vol. CAD-2, pp.62-69, Apr. 1983.
• 26: Neil Weste, Virtual grid symbolic layout, Proceedings of the 18th conference on Design automation, p.225-233, June 29-July 01, 1981, Nashville, Tennessee, United States
• 27: N. P. Chen, "Routing System For Building Block Layout," Ph.D. thesis at U. C. Berkley, 1983.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance