A 2-dimensional placement algorithm for the layout of electrical circuits.

ABSTRACT

PLAC is a multi-algorithm, 2-dimensional placement program which accommodates many of the “real world” constraints which occur in the layout of electrical circuits. PLAC was implemented as part of LTX [1], a general integrated circuit layout system, but is capable of handling circuit layout tasks from other technologies (e.g., PC boards, ceramic substrates). PLAC interlaces constructive initial placement with iterative pairwise exchange, using an approximation of total routing length as the primary figure-of-merit. The layout designer can influence the placement by providing a “seed” preplacement of key cells. PLAC results are given for a DIP board layout and two polycell integrated circuit layouts. Comparisons are made to other semi-automatic and manual placement procedures. Running time on an HP21MX minicomputer ranged from 4 minutes on a 34-cell problem to 1 hour on a 511-cell problem.

REFERENCES

• 1: G. Persky , D. N. Deutsch , D. G. Schweikert, LTX - a system for the directed automatic design of LSI circuits, Proceedings of the 13th conference on Design automation, p.399-407, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804840]
• 2: G. Persky, PRO - an automatic string placement program for polycell layout, Proceedings of the 13th conference on Design automation, p.417-424, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804842]
• 3: David N. Deutsch, A “Dogleg” channel router, Proceedings of the 13th conference on Design automation, p.425-433, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804843]
• 4: D. G. Schweikert , B. W. Kernighan, A proper model for the partitioning of electrical circuits, Proceedings of the 9th workshop on Design automation, p.57-62, June 26-28, 1972 [doi>10.1145/800153.804930]
• 5: M.Hanan, "On Steiner's problem with rectilinear distance", SIAM J. Appl. Math, vol. 14(1966), 255-265.
• 6: F.K.Hwang, "On Steiner minimal trees with rectilinear distance", SIAM J. Appl. Math, vol. 30(1976), 104-114.
• 7: G.W.Smith,Jr., "Net-span minimization: an N-dimensional placement optimization criteria", internal BTL memorandum, 1 Nov 1972.
• 8: Roland L. Mattison, A high quality, low cost router for MOS/LSI, Proceedings of the 9th workshop on Design automation, p.94-103, June 26-28, 1972 [doi>10.1145/800153.804934]
• 9: R.L.Mattison, private communication.
• 10: Donald M. Schuler , Ernst G. Ulrich, Clustering and linear placement, Proceedings of the 9th workshop on Design automation, p.50-56, June 26-28, 1972 [doi>10.1145/800153.804929]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

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

General Terms:
Algorithms, Design, Performance