Layout compaction with attractive and repulsive constraints

ABSTRACT

A one-dimensional compaction algorithm with attractive and repulsive constraints is proposed. Depending on these constraints, the proposed algorithm shrinks[expands] the spaces among the specified layout elements without causing any design rule violations, as if some force were affecting them. It implies that the resultant layout has less cross talk and delay. The proposed network simplex algorithm experimentally proves to be efficient in both time and space.

REFERENCES

• 1: David G. Boyer, Symbolic layout compaction review, Proceedings of the 25th ACM/IEEE conference on Design automation, p.383-389, June 12-15, 1988, Atlantic City, New Jersey, United States
• 2: Y.-z. Liao and (3. K. Wong, An algorithm to compact a VLSI symbolic layout with mixed constraints, IEEE Trans. Computer-Aided Desig.n, vol. CAD-2, no.2, pp.62-69, April 1983.
• 3: W. L. Schiele, Improved compaction by minimized length of wires, Proceedings of the 20th conference on Design automation, p.121-127, June 27-29, 1983, Miami Beach, Florida, United States
• 4: T. Yoshimura, A graph theoretical compaction al. gorithm, in Proe. ISCAS 85, pp.1455-1458, June 1985.
• 5: David Marple , Michiel Smulders , Henk Hegen, An efficient compactor for 45° layout, Proceedings of the 25th ACM/IEEE conference on Design automation, p.396-402, June 12-15, 1988, Atlantic City, New Jersey, United States
• 6: J. Burns and A.R. Newton, 5'PARCS:A new constraint-based IC symbolic spacer, Proc. of Custom Integrated Circuit Conference, pp.534- 539, 1986.
• 7: Saul I. Gass, Linear programming: methods and applications (5th ed.), McGraw-Hill, Inc., New York, NY, 1985
• 8: IMSL MATH/LIBRARY USER'S MANUAL vol.3, IBM.

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.2 Design Aids
          Subjects: Layout

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Experimentation