Automatic layout algorithms for function blocks of CMOS gate arrays

ABSTRACT

Automatic layout algorithms, placement and routing, for function blocks of CMOS gate arrays are presented. The placement algorithm assigns transistors to basic cells so as to minimize the number of cells used and to minimize the number of interconnections crossing cut-lines. The former objective is achieved by finding a maximum matching and the latter is achieved by iterative interchanges of transistor pairs. A new routing technique based on channel routing methods is introduced to handle the internal cell area. It intends to route with the primary use of the first layer and with the least use of tracks. A program based on the algorithms has been developed and applied to many block designs for up to 200 transistors. The results show that the presented algorithms could realize as good a layout as manual.

REFERENCES

• 1: S. Yabe, et al., "MASTER2:A Hierarchical Layout System for Gate Arrays," Proc. ICCAD, pp46-48, (1983)
• 2: H. Miyashita, et al., "Cell Pattern Generation for CMOS Masterslice LSI," Trans. IECE, VoI.J66-C No.12, ppi140-i147 (1983) (in Japanese)
• 3: Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science (Prentice Hall Series in Automatic Computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1974
• 4: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 5: H. Yoshizawa , H. Kawanishi , K. Kani, A heuristic procedure for ordering MOS arrays, Proceedings of the 12th conference on Design automation, p.384-393, January 1975
• 6: S. Even, et al., An O(N2"5) Algorithm for Maximum Matching in General Graphs," 16th Annual Symp. on Foundation of Computer Science, ppl00-112 (1975)

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

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

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