The edge-based design rule model revisited

ABSTRACT

A model for integrated circuit design rules based on rectangle edge constraints has been proposed by Jeppson, Christensson, and Hedenstierna. This model appears to be the most rigorous proposed to date for the description of such edge-based design rules. However, in certain rare circumstances their model is unable to express the correct design rule when the constrained edges are not adjacent in the layout. We introduce a new notation, called an edge path, which allows us to extend their model to allow for constraints between edges separated by an arbitrary number of intervening edges. Using this notation we enumerate all edge paths that are required to correctly model the original design rule macros of the JCH model, and prove that these macros are sufficient to model the most common rules. We also show how this notation alows us to directly specify many kinds of conditional design rules that required ad hoc specification under the JCH model.

REFERENCES

• 1: Michael H. Arnold , John K. Ousterhout, Lyra: A new approach to geometric layout rule checking, Proceedings of the 19th conference on Design automation, p.530-536, January 1982
• 2: CHENG, C.-K., DENG, X., LIAO, Y.-Z., AND YAO, S.Z. 1992. Symbolic layout compaction under conditional design rules. IEEE Trans. Comput. Aided Des. 11, 4 (April), 475-486.
• 3: DRACULA. 1994. Dracula Reference Manual. Cadence Design Systems, Inc., San Jose, CA.
• 4: JEPPSON, K., CHRISTENSSON, S., AND HEDENSTIERNA, N. 1993. Formal definitions of edgebased geometric design rules. IEEE Trans. Comput. Aided Des. 12, 1 (Jan.), 59-69.
• 5: LEE, J. 1988. A new framework of design rules for compaction of VLSI layouts. IEEE Trans. Comput. Aided Des. 7, 11 (Nov.), 1195-1204.
• 6: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 7: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 8: MODARRES, H. AND LOMAX, R. 1987. A formal approach to design-rule checking. IEEE Trans. Comput. Aided Des. 6, 4 (July), 561-572.
• 9: John K. Ousterhout , Gordon T. Hamachi , Robert N. Mayo , Walter S. Scott , George S. Taylor, Magic: A VLSI layout system, Proceedings of the 21st conference on Design automation, p.152-159, June 25-27, 1984, Albuquerque, New Mexico, United States
• 10: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 11: RAZDAN, R. AND STROJWAS, A. 1986. A statistical design rule developer. IEEE Trans. Comput. Aided Des. 5, 4 (Oct.), 508-520.
• 12: WOLF, S. 1990. Silicon Processing, Vol. 2. Lattice Press, Sunset Beach, CA.
• 13: WOLF, W. AND DUNLOP, n. 1988. Symbolic layout and compaction. In Physical Design Automation of VLSI Systems. Benjamin/Cummings, Reading, MA, 211-281.

INDEX TERMS

Primary Classification:
  J. Computer Applications

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

General Terms:
Theory, Verification

Keywords:
design rule checking, design rules, layout verification