Gate matrix layout synthesis with two-dimensional folding

ABSTRACT

We have developed a gate matrix layout synthesis tool which utilizes folding technique on both rows and columns. The conventional interval graph model and the recently proposed dynamic net-list representation can not fully depict circuit schematics such as inter-net connections. The incomplete representations may mislead the search process for an optimal solution during the layout partitioning and the gate ordering phases. We propose a new graph-based model called hierarchical dynamic net-list to improve the schematic representation. Based on the new model, the folded layout area in the partitioning phase can be more accurately estimated. The new gate ordering algorithm proposed by us also takes the advantages of the hierarchical dynamic net-list model to handle the gate placement in the folded layouts. The experimental results show 12% to 15% improvement in layout area for small circuits and 30% improvement for a large circuit.

REFERENCES

• Lopez80: A.Lopez, H.Law, "A dense gate matrix layout method for MOS VLSI", IEEE Trans. Electron Devices, pp 1671-167,5, Aug 1980.
• Wing85: O.Wing, S.Huang, R.Wang, "Gate Matrix Layout", IEEE Trans. CAD, voi CAD-4, no.3, pp 220-231, July 1985.
• Hwang86: D.Hwang, W.Fuchs, S.Kang, "An efficient approach to gate matrix layout", Proc. IEEE Int. Conf. on CAD, pp 312-315, 1986.
• Leong86: H.Leong, "A new algorithm for gate matrix layout", Proc. IEEE Int. Conf. on CAD, pp 316-319, 1986.
• Hwang87: D.Hwang, W.Fuchs, S.Kang, "An efficient approach to gate matrix layout", IEEE Trans. on CAD, vol CAD-6, no.5, pp.802-809, Sep 1987.
• Wong87: D. F. Wong , C. L. Liu, Array optimization for VLSI synthesis, Proceedings of the 24th ACM/IEEE conference on Design automation, p.537-543, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37968]
• Deva87: S.Srinivas and R.Newton, "Topological Optimization of Multiple-Level Array Logic", IEEE Trans. CAD, vol CAD-6, no.6, pp 915-941, Nov. 1987.
• Chang87: Y.-C. Chang , S.-C. Chang , L.-H. Hsu, Automated layout generation using gate matrix approach, Proceedings of the 24th ACM/IEEE conference on Design automation, p.552-558, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37970]
• Kirk83: S.Kirkpatrick, C.D.Gelatt Jr. and M.P.Vecchi, "Optimization by Simulated Annealing", Science, voi. 220, pp.671-680, 1983.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays
      B.7.2 Design Aids
          Subjects: Layout

General Terms:
Algorithms, Design, Experimentation, Performance